Butterfly-core community search over labeled graphs

Zheng Dong, Xin Huang*, Guorui Yuan, Hengshu Zhu*, Hui Xiong

*Corresponding author for this work

Research output: Contribution to journalConference articlepeer-review

19 Citations (Scopus)


Community search aims at finding densely connected subgraphs for query vertices in a graph. While this task has been studied widely in the literature, most of the existing works only focus on finding homogeneous communities rather than heterogeneous communities with different labels. In this paper, we motivate a new problem of cross-group community search, namely Butterfly-Core Community (BCC), over a labeled graph, where each vertex has a label indicating its properties and an edge between two vertices indicates their cross relationship. Specifically, for two query vertices with different labels, we aim to find a densely connected cross community that contains two query vertices and consists of butterfly networks, where each wing of the butterflies is induced by a k-core search based on one query vertex and two wings are connected by these butterflies. We first develop a heuristic algorithm achieving 2-approximation to the optimal solution. Furthermore, we design fast techniques of query distance computations, leader pair identifications, and index-based BCC local explorations. Extensive experiments on seven real datasets and four useful case studies validate the effectiveness and efficiency of our BCC and its multi-labeled extension models.

Original languageEnglish
Pages (from-to)2006-2018
Number of pages13
JournalProceedings of the VLDB Endowment
Issue number11
Publication statusPublished - Jul 2021
Event47th International Conference on Very Large Data Bases, VLDB 2021 - Virtual, Online
Duration: 16 Aug 202120 Aug 2021

Scopus Subject Areas

  • Computer Science (miscellaneous)
  • Computer Science(all)


Dive into the research topics of 'Butterfly-core community search over labeled graphs'. Together they form a unique fingerprint.

Cite this