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 κ-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.
Original language | English |
---|---|
Title of host publication | SIGMOD '14: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data |
Publisher | Association for Computing Machinery (ACM) |
Pages | 1311-1322 |
Number of pages | 12 |
ISBN (Print) | 9781450323765 |
DOIs | |
Publication status | Published - 18 Jun 2014 |
Event | ACM SIGMOD International Conference on Management of Data, SIGMOD 2014 - Snowbird, United States Duration: 22 Jun 2014 → 27 Jun 2014 https://dl.acm.org/doi/proceedings/10.1145/2588555 |
Publication series
Name | Proceedings of the ACM SIGMOD International Conference on Management of Data |
---|---|
ISSN (Print) | 0730-8078 |
Conference
Conference | ACM SIGMOD International Conference on Management of Data, SIGMOD 2014 |
---|---|
Country/Territory | United States |
City | Snowbird |
Period | 22/06/14 → 27/06/14 |
Internet address |
Scopus Subject Areas
- Software
- Information Systems
User-Defined Keywords
- Community search
- Dynamic graph
- κ-truss