Abstract
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 language | English |
---|---|
Title of host publication | 2020 IEEE 36th International Conference on Data Engineering |
Number of pages | 12 |
Publisher | IEEE |
Publication date | 2020 |
Pages | 1201-1212 |
Article number | 9101525 |
ISBN (Print) | 978-1-7281-2904-4 |
ISBN (Electronic) | 9781728129037 |
DOIs | |
Publication status | Published - 2020 |
Event | 36th IEEE International Conference on Data Engineering - Dallas, United States Duration: 20 Apr 2020 → 24 Apr 2020 https://www.utdallas.edu/icde/ |
Conference
Conference | 36th IEEE International Conference on Data Engineering |
---|---|
Country/Territory | United States |
City | Dallas |
Period | 20/04/2020 → 24/04/2020 |
Internet address |
Series | Proceedings of the International Conference on Data Engineering |
---|---|
ISSN | 1063-6382 |