I/O efficient k-truss community search in massive graphs

Yuli Jiang, Xin HUANG*, Hong Cheng

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

8 Citations (Scopus)


Community detection that discovers all densely connected communities in a network has been studied a lot. In this paper, we study online communitysearch for query-dependent communities, which is a different but practically useful task. 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 community model based on the k-truss concept, which brings nice structural and computational properties. We design a compact and elegant index structure which supports the efficient search of k-truss communities with a linear cost with respect to the community size. We also investigate the k-truss community search problem in a dynamic graph setting with frequent insertions and deletions of graph vertices and edges. In addition, to support k-truss community search over massive graphs which cannot entirely fit in main memory, we propose I/O-efficient algorithms for query processing under the semi-external model. Extensive experiments on massive real-world networks demonstrate the effectiveness of our k-truss community model, the efficiency, and the scalability of our in-memory and semi-external community search algorithms.

Original languageEnglish
Pages (from-to)713-738
Number of pages26
JournalVLDB Journal
Issue number5
Early online date22 Apr 2021
Publication statusPublished - Sept 2021

Scopus Subject Areas

  • Information Systems
  • Hardware and Architecture

User-Defined Keywords

  • community search
  • dynamic graphs
  • k-truss
  • semi-external algorithms


Dive into the research topics of 'I/O efficient k-truss community search in massive graphs'. Together they form a unique fingerprint.

Cite this