2014 · 490 citations · 21 references
ComputingComputer ScienceComputational GeometryData StructuresDistributed SystemsCommunity DetectionCommunity StructureGraph AlgorithmsGraph AnalyticsGraph MiningGraph TheoryDynamic Graph AlgorithmsGraph IndexingGraph QueryingGraph SearchIndex SetsIndex StructuresInsertionsOnline Search
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.
21
Finding and evaluating community structure in networks
Michelle G. Newman, Michelle Girvan · Physical Review E · 2004 · 14.1K citations · Full text
Uncovering the overlapping community structure of complex networks in nature and society
Gergely Palla, Imre Derényi, Illés J. Farkas et al. · Nature · 2005 · 5.4K citations · Full text
Algorithm 457: finding all cliques of an undirected graph
Coen Bron, Joep Kerbosch · Communications of the ACM · 1973 · 2.5K citations · Full text
Link communities reveal multiscale complexity in networks
Yong‐Yeol Ahn, James P. Bagrow, Sune Lehmann · Nature · 2010 · 2K citations · Full text