Community detection by graph Voronoi diagrams

Dávid Deritei, Zsolt I. Lázár, I. Papp, Ferenc Járai-Szabó, Róbert Sumi, Levente Varga, Erzsébet Ravasz Regan, Mária Ercsey-Ravasz

New Journal of Physics · 2014 · 30 citations · 40 references

DOIFull text

Open access

Concepts

Abstract

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.

References

40