Abstract
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 language | English |
---|---|
Title of host publication | Proceedings - 2020 IEEE 36th International Conference on Data Engineering, ICDE 2020 |
Publisher | IEEE Computer Society |
Pages | 937-948 |
Number of pages | 12 |
ISBN (Electronic) | 9781728129037 |
DOIs | |
Publication status | Published - Apr 2020 |
Event | 36th IEEE International Conference on Data Engineering, ICDE 2020 - Dallas, United States Duration: 20 Apr 2020 → 24 Apr 2020 https://ieeexplore.ieee.org/xpl/conhome/9093725/proceeding (Link to conference proceedings) |
Publication series
Name | Proceedings - International Conference on Data Engineering |
---|---|
Volume | 2020-April |
ISSN (Print) | 1084-4627 |
Conference
Conference | 36th IEEE International Conference on Data Engineering, ICDE 2020 |
---|---|
Country/Territory | United States |
City | Dallas |
Period | 20/04/20 → 24/04/20 |
Internet address |
|