Truss-based Community Search over Large Directed Graphs

Qing Liu, Minjun Zhao, Xin Huang, Jianliang Xu, Yunjun Gao

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

52 Citations (Scopus)


Community search enables personalized community discovery and has wide applications in large real-world graphs. While community search has been extensively studied for undirected graphs, the problem for directed graphs has received attention only recently. However, existing studies suffer from several drawbacks, e.g., the vertices with varied in-degrees and out-degrees cannot be included in a community at the same time. To address the limitations, in this paper, we systematically study the problem of community search over large directed graphs. We start by presenting a novel community model, called D-truss, based on two distinct types of directed triangles, i.e., flow triangle and cycle triangle. The D-truss model brings nice structural and computational properties and has many advantages in comparison with the existing models. With this new model, we then formulate the D-truss community search problem, which is proved to be NP-hard. In view of its hardness, we propose two efficient 2-approximation algorithms, named Global and Local, that run in polynomial time yet with quality guarantee. To further improve the efficiency of the algorithms, we devise an indexing method based on D-truss decomposition. Consequently, the D-truss community search can be solved upon the D-truss index without time-consuming accesses to the original graph. Experimental studies on real-world graphs with ground-truth communities validate the quality of the solutions we obtain and the efficiency of the proposed algorithms.

Original languageEnglish
Title of host publicationSIGMOD 2020 - Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data
PublisherAssociation for Computing Machinery (ACM)
Number of pages15
ISBN (Electronic)9781450367356
Publication statusPublished - 14 Jun 2020
EventACM SIGMOD International Conference on Management of Data, SIGMOD 2020 - Portland, United States
Duration: 14 Jun 202019 Jun 2020

Publication series

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


ConferenceACM SIGMOD International Conference on Management of Data, SIGMOD 2020
Country/TerritoryUnited States
Internet address

Scopus Subject Areas

  • Software
  • Information Systems

User-Defined Keywords

  • community search
  • d-truss
  • directed graph


Dive into the research topics of 'Truss-based Community Search over Large Directed Graphs'. Together they form a unique fingerprint.

Cite this