Index-based intimate-core community search in large weighted graphs

Longxu Sun, Xin Huang*, Ronghua Li, Byron Koon Kau Choi, Jianliang Xu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish
Pages (from-to)4313-4327
Number of pages15
JournalIEEE Transactions on Knowledge and Data Engineering
Volume34
Issue number9
Early online date26 Nov 2020
DOIs
Publication statusPublished - 1 Sep 2022

Scopus Subject Areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

User-Defined Keywords

  • Graph mining
  • community search
  • k-core
  • weighted graphs

Fingerprint

Dive into the research topics of 'Index-based intimate-core community search in large weighted graphs'. Together they form a unique fingerprint.

Cite this