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.

本文提出了一种新的问题，即基于具有不同标签的查询顶点的异构交叉社区查询，即蝴蝶芯社区 (butterfly-core community)，并证明该问题是 NP-hard 的。为了有效地解决这个问题，本文开发了一种启发式算法和一组高效的算法来识别和维护蝴蝶芯，通过八个真实网络和四个新颖案例的广泛实验验证了算法的有效性和效率。