Abstract | ||
---|---|---|
Community detection which discovers densely connected structures in a network has been studied a lot. In this paper, we study online community search which is practically useful but less studied in the literature. Given a query vertex in a graph, the problem is to find meaningful communities that the vertex belongs to in an online manner. We propose a novel community model based on the k-truss concept, which brings nice structural and computational properties. We design a compact and elegant index structure which supports the efficient search of k-truss communities with a linear cost with respect to the community size. In addition, we investigate the k-truss community search problem in a dynamic graph setting with frequent insertions and deletions of graph vertices and edges. Extensive experiments on large real-world networks demonstrate the effectiveness and efficiency of our community model and search algorithms. |
Year | DOI | Venue |
---|---|---|
2014 | 10.1145/2588555.2610495 | SIGMOD Conference |
Keywords | Field | DocType |
dynamic graph,community search,k-truss,graph algorithms,data mining | Data mining,Search algorithm,Online community,Vertex (geometry),Computer science,Level structure,Theoretical computer science,Null graph,Bidirectional search,Database,Feedback vertex set,Voltage graph | Conference |
Citations | PageRank | References |
93 | 2.01 | 19 |
Authors | ||
5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Xin Huang | 1 | 379 | 29.42 |
Hong Cheng | 2 | 3694 | 148.72 |
Lu Qin | 3 | 1430 | 95.44 |
Wentao Tian | 4 | 146 | 4.23 |
Jeffrey Xu Yu | 5 | 7018 | 464.96 |