New Journal of Physics (Jan 2014)

Community detection by graph Voronoi diagrams

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

DOI
https://doi.org/10.1088/1367-2630/16/6/063007
Journal volume & issue
Vol. 16, no. 6
p. 063007

Abstract

Read online

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.

Keywords