Contextual community search over large social networks

Lu Chen, Chengfei Liu, Kewen Liao, Jianxin Li, Rui Zhou

Research output: Chapter in Book/Report/Conference proceedingConference Paper published in Proceedings

Abstract

Community search on attributed networks has recently attracted great deal of research interest. However, most of existing works require query users to specify some community structure parameters. This may not be always practical as sometimes a user does not have the knowledge and experience to decide the suitable parameters. In this paper, we propose a novel parameter-free contextual community model for attributed community search. The proposed model only requires a query context, i.e., a set of keywords describing the desired matching community context, while the community returned is both structure and attribute cohesive w.r.t. the provided query context. We theoretically show that both our exact and approximate contextual community search algorithms can be executed in worst case polynomial time. The exact algorithm is based on an elegant parametric maximum flow technique and the approximation algorithm that significantly improves the search efficiency is analyzed to have an approximation factor of 1/3. In the experiment, we use six real networks with ground-truth communities to evaluate the effectiveness of our contextual community model. Experimental results demonstrate that the proposed model can find near ground-truth communities. We also test both our exact and approximate algorithms using eight large real networks to demonstrate the high efficiency of the proposed algorithms.

Original languageEnglish
Title of host publicationProceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019
PublisherIEEE Computer Society
Pages88-99
Number of pages12
ISBN (Electronic)9781538674741
DOIs
Publication statusPublished - 1 Apr 2019
Externally publishedYes
Event35th IEEE International Conference on Data Engineering, ICDE 2019 - Macau, China
Duration: 8 Apr 201911 Apr 2019

Publication series

NameProceedings - International Conference on Data Engineering
Volume2019-April
ISSN (Print)1084-4627

Conference

Conference35th IEEE International Conference on Data Engineering, ICDE 2019
CountryChina
CityMacau
Period8/04/1911/04/19

Fingerprint Dive into the research topics of 'Contextual community search over large social networks'. Together they form a unique fingerprint.

  • Cite this

    Chen, L., Liu, C., Liao, K., Li, J., & Zhou, R. (2019). Contextual community search over large social networks. In Proceedings - 2019 IEEE 35th International Conference on Data Engineering, ICDE 2019 (pp. 88-99). [8731482] (Proceedings - International Conference on Data Engineering; Vol. 2019-April). IEEE Computer Society. https://doi.org/10.1109/ICDE.2019.00017