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 Proceedingspeer-review


    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
    Number of pages12
    ISBN (Electronic)9781538674741
    Publication statusPublished - 1 Apr 2019
    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
    ISSN (Print)1084-4627


    Conference35th IEEE International Conference on Data Engineering, ICDE 2019


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

    Cite this