Paper Info
Title
Effective and efficient attributed community search.
Abstract
Given a graph and a vertex , the query returns a subgraph of that contains vertices related to . Communities, which are prevalent in such as social networks and knowledge bases, can be used in emerging applications such as product advertisement and setting up of social events. In this paper, we investigate the (or ACQ), which returns an (AC) for an . The AC is a subgraph of , which satisfies both (i.e., its vertices are tightly connected) and (i.e., its vertices share common keywords). The AC enables a better understanding of how and why a community is formed (e.g., members of an AC have a common interest in music, because they all have the same keyword “music”). An AC can be “personalized”; for example, an ACQ user may specify that an AC returned should be related to some specific keywords like “research” and “sports”. To enable efficient AC search, we develop the CL-tree index structure and three algorithms based on it. We further propose efficient algorithms for maintaining the index on dynamic graphs. Moreover, we study two problems that are related to the ACQ problem. We evaluate our solutions on six large graphs. Our results show that ACQ is more effective and efficient than existing community retrieval approaches. Moreover, an AC contains more precise and personalized information than that of existing community search and detection methods.
Year
DOI
Venue
2017
https://doi.org/10.1007/s00778-017-0482-5
VLDB J.
Keywords
Field
DocType
Community search,Attributed graphs,Graph queries
Graph,Data mining,Community search,Social network,Vertex (geometry),Computer science,Group cohesiveness,Database
Journal
Volume
Issue
ISSN
26
6
1066-8888
Citations 
PageRank 
References 
11
0.47
34
Authors
5
Name
Order
Citations
PageRank
Yixiang Fang122723.06
Reynold Cheng23069154.13
Yankai Chen3142.18
Siqiang Luo424014.59
Jiafeng Hu516210.87