Fast Algorithms for Intimate-Core Group Search in Weighted Graphs

Longxu Sun*, Xin HUANG, Rong Hua Li, Jianliang XU

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference contributionpeer-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 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.

Original languageEnglish
Title of host publicationWeb Information Systems Engineering – WISE 2019 - 20th International Conference, Proceedings
EditorsReynold Cheng, Nikos Mamoulis, Yizhou Sun, Xin Huang
PublisherSpringer
Pages728-744
Number of pages17
ISBN (Print)9783030342227
DOIs
Publication statusPublished - 2019
Event20th International Conference on Web Information Systems Engineering, WISE 2019 - Hongkong, Hong Kong
Duration: 26 Nov 201930 Nov 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11881 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference20th International Conference on Web Information Systems Engineering, WISE 2019
Country/TerritoryHong Kong
CityHongkong
Period26/11/1930/11/19

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Community search
  • Graph mining
  • K-core
  • Weighted graphs

Fingerprint

Dive into the research topics of 'Fast Algorithms for Intimate-Core Group Search in Weighted Graphs'. Together they form a unique fingerprint.

Cite this