Efficient Attribute-Constrained Co-Located Community Search

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

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

1 Citationer (Scopus)

Abstrakt

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.

OriginalsprogEngelsk
Titel2020 IEEE 36th International Conference on Data Engineering
Antal sider12
ForlagIEEE
Publikationsdato2020
Sider1201-1212
Artikelnummer9101525
ISBN (Trykt)978-1-7281-2904-4
ISBN (Elektronisk)9781728129037
DOI
StatusUdgivet - 2020
Begivenhed36th IEEE International Conference on Data Engineering - Dallas, USA
Varighed: 20 apr. 202024 apr. 2020
https://www.utdallas.edu/icde/

Konference

Konference36th IEEE International Conference on Data Engineering
LandUSA
ByDallas
Periode20/04/202024/04/2020
Internetadresse
NavnProceedings of the International Conference on Data Engineering
ISSN1063-6382

Fingeraftryk Dyk ned i forskningsemnerne om 'Efficient Attribute-Constrained Co-Located Community Search'. Sammen danner de et unikt fingeraftryk.

Citationsformater