Synergetic Community Search over Large Multilayer Graphs

Download PDF

Abstract

Community search is a fundamental problem in graph analysis and has attracted much attention for its ability to discover personalized communities. In this paper, we focus on community search over multilayer graphs. We design a novel cohesive subgraph model called synergetic core for multilayer graphs, which requires both local and global cohesiveness. Specifically, the synergetic core man- dates that the vertices within the subgraph are not only densely connected on some individual layers but also form more cohesive connections on the projected graph that considers all layers. The local and global cohesiveness collectively ensure the superiority of the synergetic core. Based on this new model, we formulate the problem of synergetic community search. To efficiently retrieve the community, we propose two algorithms. The first is a progressive search algorithm, which enumerates potential layer combinations to compute the synergetic core. The second is a trie-based search algorithm, leveraging our novel index called dominant layers-based trie (DLT). DLT compactly stores synergetic cores within the trie structure. By traversing the DLT, we can efficiently identify the syn- ergetic core. We conduct extensive experiments on ten real-world datasets. Experimental results demonstrate that (1) the synergetic core can find communities with the best quality among the state- of-the-art models, and (2) our proposed algorithms are up to five orders of magnitude faster than the basic method.