When Structure Meets Keywords: Cohesive Attributed Community Search

Yuanyuan Zhu*, Jian He, Junhao Ye, Lu Qin, Xin Huang, Jeffrey Xu Yu

*Corresponding author for this work

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

13 Citations (Scopus)


As an online, query-dependent variant of the well-known community detection problem, community search has been studied for years to find communities containing the query vertices. Along with the generation of graphs with rich attribute information, attributed community search has attracted increasing interest recently, aiming to select communities where vertices are cohesively connected and share homogeneous attributes. However, existing community models may include cut-edges/vertices and thus cannot well guarantee the strong connectivity required by a cohesive community. In this paper, we propose a new cohesive attributed community (CAC) model that can ensure both structure cohesiveness and attribute cohesiveness of communities. Specifically, for a query with vertex vq and keyword set S, we aim to find the cohesively connected communities containing vq with the most shared keywords in S. It is nontrivial as we need to explore all possible subsets of S to verify the existence of structure cohesive communities until we find the communities with the most common keywords. To tackle this problem, we make efforts in two aspects. The first is to reduce the candidate keyword subsets. We achieve this by exploring the anti-monotonicity and neighborhood-constraint properties of our CAC model so that we can filter out the unpromising keyword subsets. The second is to speed up the verification process for each candidate keyword subset. We propose two indexes TIndex and MTIndex to reduce the size of the candidate subgraph before the verification. Moreover, we derive two new properties based on these indexes to reduce the candidate keyword subsets further. We conducted extensive experimental studies on four real-world graphs and validated the effectiveness and efficiency of our approaches.

Original languageEnglish
Title of host publicationCIKM 2020 - Proceedings of the 29th ACM International Conference on Information and Knowledge Management
PublisherAssociation for Computing Machinery (ACM)
Number of pages10
ISBN (Electronic)9781450368599
Publication statusPublished - 19 Oct 2020
Event29th ACM International Conference on Information and Knowledge Management, CIKM 2020 - Virtual, Online, Ireland
Duration: 19 Oct 202023 Oct 2020

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings


Conference29th ACM International Conference on Information and Knowledge Management, CIKM 2020
CityVirtual, Online

Scopus Subject Areas

  • Business, Management and Accounting(all)
  • Decision Sciences(all)

User-Defined Keywords

  • attributed graphs
  • community search
  • truss model


Dive into the research topics of 'When Structure Meets Keywords: Cohesive Attributed Community Search'. Together they form a unique fingerprint.

Cite this