# Butterfly-Core Community Search over Labeled Graphs

arXiv: https://arxiv.org/abs/2105.08628 · HTML: https://mlsanity.com/paper/2105.08628/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 May 2021.

## Built on by (most cited first, 4 of 4)

- [A Comprehensive Survey of Artificial Intelligence Techniques for Talent Analytics](https://mlsanity.com/paper/2307.03195/) (2023)
- [CS-MLGCN : Multiplex Graph Convolutional Networks for Community Search in Multiplex Networks](https://mlsanity.com/paper/2210.08811/) (2022)
- [CS-TGN: Community Search via Temporal Graph Neural Networks](https://mlsanity.com/paper/2303.08964/) (2023)
- [Fast Butterfly-Core Community Search For Large Labeled Graphs](https://mlsanity.com/paper/2401.10642/) (2024)

## Abstract (arXiv)

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. Indeed, the BCC structure admits the structure cohesiveness and minimum diameter, and thus can effectively capture the heterogeneous and concise collaborative team. Moreover, we theoretically prove this problem is NP-hard and analyze its non-approximability. To efficiently tackle the problem, we develop a heuristic algorithm, which first finds a BCC containing the query vertices, then iteratively removes the farthest vertices to the query vertices from the graph. The algorithm can achieve a 2-approximation to the optimal solution. To further improve the efficiency, we design a butterfly-core index and develop a suite of efficient algorithms for butterfly-core identification and maintenance as vertices are eliminated. Extensive experiments on eight real-world networks and four novel case studies validate the effectiveness and efficiency of our algorithms.