Querying K-truss community in large and dynamic graphs
- Publication Type:
- Conference Proceeding
- Proceedings of the ACM SIGMOD International Conference on Management of Data, 2014, pp. 1311 - 1322
- Issue Date:
Files in This Item:
|[2014 SIGMOD] Querying K-Truss Community in Large and Dynamic Graphs.pdf||Published version||328.27 kB|
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
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 κ-truss concept, which brings nice structural and computational properties. We design a compact and elegant index structure which supports the efficient search of κ-truss communities with a linear cost with respect to the community size. In addition, we investigate the κ 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. © 2014 ACM.
Please use this identifier to cite or link to this item: