Efficient Attribute-Constrained Co-Located Community Search

Jiehuan Luo, Xin Cao, Xike Xie, Qiang Qu, Zhiqiang Xu, Christian S. Jensen

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

1 Citation (Scopus)


Networked data, notably social network data, often comes with a rich set of annotations, or attributes, such as documents (e.g., tweets) and locations (e.g., check-ins). Community search in such attributed networks has been studied intensively due to its many applications in friends recommendation, event organization, advertising, etc. We study the problem of attribute-constrained co-located community (ACOC) search, which returns a community that satisfies three properties: i) structural cohesiveness: the members in the community are densely connected; ii) spatial co-location: the members are close to each other; and iii) attribute constraint: a set of attributes are covered by the attributes associated with the members. The ACOC problem is shown to be NP-hard. We develop four efficient approximation algorithms with guaranteed error bounds in addition to an exact solution that works on relatively small graphs. Extensive experiments conducted with both real and synthetic data offer insight into the efficiency and effectiveness of the proposed methods, showing that they outperform three adapted state-of-the-art algorithms by an order of magnitude. We also find that the approximation algorithms are much faster than the exact solution and yet offer high accuracy.

Original languageEnglish
Title of host publication2020 IEEE 36th International Conference on Data Engineering
Number of pages12
Publication date2020
Article number9101525
ISBN (Print)978-1-7281-2904-4
ISBN (Electronic)9781728129037
Publication statusPublished - 2020
Event36th IEEE International Conference on Data Engineering - Dallas, United States
Duration: 20 Apr 202024 Apr 2020


Conference36th IEEE International Conference on Data Engineering
CountryUnited States
Internet address
SeriesProceedings of the International Conference on Data Engineering

Fingerprint Dive into the research topics of 'Efficient Attribute-Constrained Co-Located Community Search'. Together they form a unique fingerprint.

Cite this