TY - GEN
T1 - VAC
T2 - 36th IEEE International Conference on Data Engineering, ICDE 2020
AU - Liu, Qing
AU - Zhu, Yifan
AU - Zhao, Minjun
AU - HUANG, Xin
AU - XU, Jianliang
AU - Gao, Yunjun
N1 - Funding Information:
Acknowledgments. This work is supported by Research Grants Council of Hong Kong under GRF Projects 12201018, 12200917, CRF Project C6030-18GF, the NSFC under Grant No. 61702435 & 61972338, the National Key R&D Program of China under Grant No. 2018YFB1004003, the NSFC-Zhejiang Joint Fund under Grant No. U1609217, and the ZJU-Hikvision Joint Project. Qing Liu and Yifan Zhu have contributed equally to this work. Yunjun Gao is the corresponding author.
PY - 2020/4
Y1 - 2020/4
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85085863364&partnerID=8YFLogxK
U2 - 10.1109/ICDE48307.2020.00086
DO - 10.1109/ICDE48307.2020.00086
M3 - Conference contribution
AN - SCOPUS:85085863364
T3 - Proceedings - International Conference on Data Engineering
SP - 937
EP - 948
BT - Proceedings - 2020 IEEE 36th International Conference on Data Engineering, ICDE 2020
PB - IEEE Computer Society
Y2 - 20 April 2020 through 24 April 2020
ER -