Abstract: The (α, β)-core is a fundamental model for mining dense subgraphs in bipartite graphs. However, existing index-based (α, β)-community search algorithms suffer from low query efficiency or high index space consumption and cannot achieve both temporal and spatial efficiency on large-scale bipartite graphs. To address this issue, a (α, β)-community search algorithm based on a Multi-layer Hierarchical Graph (MHG) index was proposed. First, an (α, β)-community decomposition algorithm was developed, and two key concepts, community labels and (α, β)-clusters, were introduced to characterize vertex membership and finer-grained cohesive units within communities. Second, a connected cluster graph of (α, β)-clusters was designed to represent inter-community relationships more compactly. Subsequently, the MHG index was constructed through pruning optimization and mapped spatial partitioning techniques. This index enables community search to be accelerated while controlling space overhead. Experimental results on eight real-world bipartite graph datasets showed that MHG reduced index space by 10 to 33 percent compared with the most space-efficient existing index, while improving community search efficiency by one to three orders of magnitude.

Key words: bipartite graph, community search, (α,, β), -core, (α,, β), -cluster, Multi-Level Index

摘要： (α, β)-核是二部图稠密子图挖掘的一个基本模型，但目前基于(α, β)-核的社区搜索索引均存在查询效率低或索引空间大的缺点，面向大规模二部图社区搜索时不能兼具时间效率和空间效率。为此，本文提出一种基于多层索引MHG（Multi-layer Hierarchical Graph）的(α, β)-社区搜索算法。首先，提出(α, β)-社区分解算法，并引入2个重要概念：社区标签和(α, β)-簇，用于刻画顶点归属关系和社区中更细粒度的内聚单元。其次，设计(α, β)-簇的连通簇图，以更紧凑地表示社区之间的关系。随后，通过剪枝优化技术和映射空间划分技术构建索引MHG。该索引能够在控制空间开销的同时提高社区搜索效率。在8个真实二部图数据集上的实验结果表明：MHG的空间开销较现有最低索引提高了%10~%33，但社区搜索效率提高了1~3个数量级。

关键词: 二部图, 社区搜索, (α,, β)-核, (α,, β)-簇, 多层索引