Querying K-truss community in large and dynamic graphs

Xin Huang, Hong Cheng, Lu Qin, Wentao Tian, Jeffrey Xu Yu

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

387 Citations (Scopus)

Abstract

Community detection which discovers densely connected structures in a network has been studied a lot. In this paper, we study online community search which is practically useful but less studied in the literature. Given a query vertex in a graph, the problem is to find meaningful communities that the vertex belongs to in an online manner. We propose a novel community model based on the κ-truss concept, which brings nice structural and computational properties. We design a compact and elegant index structure which supports the efficient search of κ-truss communities with a linear cost with respect to the community size. In addition, we investigate the κ truss community search problem in a dynamic graph setting with frequent insertions and deletions of graph vertices and edges. Extensive experiments on large real-world networks demonstrate the effectiveness and efficiency of our community model and search algorithms.

Original languageEnglish
Title of host publicationSIGMOD '14: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data
PublisherAssociation for Computing Machinery (ACM)
Pages1311-1322
Number of pages12
ISBN (Print)9781450323765
DOIs
Publication statusPublished - 18 Jun 2014
EventACM SIGMOD International Conference on Management of Data, SIGMOD 2014 - Snowbird, United States
Duration: 22 Jun 201427 Jun 2014
https://dl.acm.org/doi/proceedings/10.1145/2588555

Publication series

NameProceedings of the ACM SIGMOD International Conference on Management of Data
ISSN (Print)0730-8078

Conference

ConferenceACM SIGMOD International Conference on Management of Data, SIGMOD 2014
Country/TerritoryUnited States
CitySnowbird
Period22/06/1427/06/14
Internet address

Scopus Subject Areas

  • Software
  • Information Systems

User-Defined Keywords

  • Community search
  • Dynamic graph
  • κ-truss

Fingerprint

Dive into the research topics of 'Querying K-truss community in large and dynamic graphs'. Together they form a unique fingerprint.

Cite this