New Journal of Physics · 2014 · 30 citations · 40 references
ComputingGeoinformaticsComputational GeometryGraph VisualizationNetwork VisualizationCommunity DetectionCommunity StructureGraph AlgorithmsGraph TheoryNetwork AnalysisVoronoi DiagramsComplex Network AnalysisComplex Network TheoryComplex NetworksDistance MetricsNetwork Community DetectionVoronoi Cells
Accurate and efficient community detection in networks is a key challenge for complex network theory and its applications. The problem is analogous to cluster analysis in data mining, a field rich in metric space-based methods. Common to these methods is a geometric, distance-based definition of clusters or communities. Here we propose a new geometric approach to graph community detection based on graph Voronoi diagrams. Our method serves as proof of principle that the definition of appropriate distance metrics on graphs can bring a rich set of metric space-based clustering methods to network science. We employ a simple edge metric that reflects the intra- or inter-community character of edges, and a graph density-based rule to identify seed nodes of Voronoi cells. Our algorithm outperforms most network community detection methods applicable to large networks on benchmark as well as real-world networks. In addition to offering a computationally efficient alternative for community detection, our method opens new avenues for adapting a wide range of data mining algorithms to complex networks from the class of centroid- and density-based clustering methods.
40
Collective dynamics of ‘small-world’ networks
Duncan J. Watts, Steven H. Strogatz · Nature · 1998 · 43.2K citations
Data mining: concepts and techniques
Jiawei Han, Micheline Kamber · Choice Reviews Online · 2012 · 28.9K citations
A density-based algorithm for discovering clusters in large spatial Databases with Noise
Martin Ester, Hans‐Peter Kriegel, Jörg Sander et al. · 1996 · 19.1K citations
Least squares quantization in PCM
Sheelagh Lloyd · IEEE Transactions on Information Theory · 1982 · 15.6K citations · Full text