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

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