TY - JOUR
T1 - Index-based intimate-core community search in large weighted graphs
AU - Sun, Longxu
AU - Huang, Xin
AU - Li, Ronghua
AU - Choi, Byron Koon Kau
AU - Xu, Jianliang
N1 - Funding information:
This paper was supported by NSFC 61702435, 62072034, 61772346, HK RGC Grants Nos. 22200320, 12201518, 12200817, 12232716, HK RGC CRF C6030-18G, and Guangdong Basic and Applied Basic Research Foundation (Project No. 2019B1515130001).
Publisher Copyright:
© 1989-2012 IEEE.
PY - 2022/9/1
Y1 - 2022/9/1
N2 - Community search that finds query-dependent communities has been studied on various kinds of graphs. As one instance of community search, intimate-core group (community) 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. In addition, to support the intimate group search over large weighted graphs, we develop a weighted-core index (WC-index) and two new WC-index-based algorithms for expansion and refinement phases in LEKS. Specifically, we propose a WC-index-based expansion to efficiently find a candidate graph of intimate-core group, leveraging on a two-level expansion of k-breadth and 1-depth. We propose two graph removal strategies: coarse-grained refinement is designed for large graphs to delete a batch of nodes in a few iterations; fine-grained refinement is designed for small graphs to remove nodes carefully and achieve high-quality answers. Extensive experiments on real-life networks with ground-truth communities validate the effectiveness and efficiency of our proposed methods.
AB - Community search that finds query-dependent communities has been studied on various kinds of graphs. As one instance of community search, intimate-core group (community) 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. In addition, to support the intimate group search over large weighted graphs, we develop a weighted-core index (WC-index) and two new WC-index-based algorithms for expansion and refinement phases in LEKS. Specifically, we propose a WC-index-based expansion to efficiently find a candidate graph of intimate-core group, leveraging on a two-level expansion of k-breadth and 1-depth. We propose two graph removal strategies: coarse-grained refinement is designed for large graphs to delete a batch of nodes in a few iterations; fine-grained refinement is designed for small graphs to remove nodes carefully and achieve high-quality answers. Extensive experiments on real-life networks with ground-truth communities validate the effectiveness and efficiency of our proposed methods.
KW - Graph mining
KW - community search
KW - k-core
KW - weighted graphs
UR - http://www.scopus.com/inward/record.url?scp=85136329312&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2020.3040762
DO - 10.1109/TKDE.2020.3040762
M3 - Journal article
SN - 1041-4347
VL - 34
SP - 4313
EP - 4327
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 9
ER -