VAC: Vertex-Centric Attributed Community Search
Authors:
- 1 April 2020
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 937-948
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.Keywords
This publication has 38 references indexed in Scilit:
- Efficient and effective community searchData Mining and Knowledge Discovery, 2015
- Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity2015
- Clustering attributed graphs: Models, measures and methodsNetwork Science, 2015
- Robust local community detectionProceedings of the VLDB Endowment, 2015
- Querying k-truss community in large and dynamic graphs2014
- Local search of communities in large graphs2014
- Description-Driven Community DetectionACM Transactions on Intelligent Systems and Technology, 2014
- Seed-Centric Approaches for Community Detection in Complex Networks2014
- Denser than the densest subgraph2013
- Online search of overlapping communities2013