2019/08/30 by Longxu Sun, Sun, Longxu, Xin Huang +5
Computer Science · #Databases (cs.DB) #FOS: Computer and information sciences #Social and Information Networks (cs.SI) #cs.DB #cs.SI
paper · pdf · doi:10.48550/arxiv.1908.11788
15 pages, 10 figures
arxiv created 2019/08/30 · arxiv updated 2019/09/02
Community search that finds query-dependent communities has been studied on various kinds of graphs. As one instance of community search, intimate-core group search over a weighted graph is to find a connected k-core containing all query nodes with the smallest group weight. However, existing state-of-the-art methods start from the maximal k-core to refine an answer, which is practically inefficient for large networks. In this paper, we develop an efficient framework, called local exploration k-core search (LEKS), to find intimate-core groups in graphs. We propose a small-weighted spanning tree to connect query nodes, and then expand the tree level by level to a connected k-core, which is finally refined as an intimate-core group. We also design a protection mechanism for critical nodes to avoid the collapsed k-core. Extensive experiments on real-life networks validate the effectiveness and efficiency of our methods.