VAC: Vertex-centric attributed community search

Qing Liu, Yifan Zhu, Minjun Zhao, Xin Huang, Jianliang Xu, Yunjun Gao*

*Corresponding author for this work

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

58 Citations (Scopus)


Attributed community search aims to find the community with strong structure and attribute cohesiveness from attributed graphs. However, existing works suffer from two major limitations: (i) it is not easy to set the conditions on query attributes; (ii) the queries support only a single type of attributes. To make up for these deficiencies, in this paper, we study a novel attributed community search called vertex-centric attributed community (VAC) search. Given an attributed graph and a query vertex set, the VAC search returns the community which is densely connected (ensured by the k-truss model) and has the best attribute score. We show that the problem is NP-hard. To answer the VAC search, we develop both exact and approximate algorithms. Specifically, we develop two exact algorithms. One searches the community in a depth-first manner and the other is in a best-first manner. We also propose a set of heuristic strategies to prune the unqualified search space by exploiting the structure and attribute properties. In addition, to further improve the search efficiency, we propose a 2-approximation algorithm. Comprehensive experimental studies on various realworld attributed graphs demonstrate the effectiveness of the proposed model and the efficiency of the developed algorithms.

Original languageEnglish
Title of host publicationProceedings - 2020 IEEE 36th International Conference on Data Engineering, ICDE 2020
PublisherIEEE Computer Society
Number of pages12
ISBN (Electronic)9781728129037
Publication statusPublished - Apr 2020
Event36th IEEE International Conference on Data Engineering, ICDE 2020 - Dallas, United States
Duration: 20 Apr 202024 Apr 2020 (Link to conference proceedings)

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627


Conference36th IEEE International Conference on Data Engineering, ICDE 2020
Country/TerritoryUnited States
Internet address

Scopus Subject Areas

  • Software
  • Signal Processing
  • Information Systems


Dive into the research topics of 'VAC: Vertex-centric attributed community search'. Together they form a unique fingerprint.

Cite this