Community Search (CS) aims to identify densely interconnected subgraphs
corresponding to query vertices within a graph. However, existing heterogeneous
graph-based community search methods need help identifying cross-group
communities and suffer from efficiency issues, making them unsuitable for large
graphs. This paper presents a fast community search model based on the
Butterfly-Core Community (BCC) structure for heterogeneous graphs. The Random
Walk with Restart (RWR) algorithm and butterfly degree comprehensively evaluate
the importance of vertices within communities, allowing leader vertices to be
rapidly updated to maintain cross-group cohesion. Moreover, we devised a more
efficient method for updating vertex distances, which minimizes vertex visits
and enhances operational efficiency. Extensive experiments on several
real-world temporal graphs demonstrate the effectiveness and efficiency of this
solution.

该论文提出了一种基于蝴蝶核心社区结构的快速搜索方法，用于在异构图中识别与查询顶点对应的密集相互连接的子图。通过随机游走与重新开始算法和蝴蝶度綜合评估社区内顶点的重要性，并采用更有效的顶点距离更新方法，避免不必要的顶点访问，提高操作效率。通过多个真实世界临时图的广泛实验验证了该解决方案的有效性和效率。

大规模标记图的快速蝴蝶核社区搜索

Fast Butterfly-Core Community Search For Large Labeled Graphs

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 的。为了有效地解决这个问题，本文开发了一种启发式算法和一组高效的算法来识别和维护蝴蝶芯，通过八个真实网络和四个新颖案例的广泛实验验证了算法的有效性和效率。