Optimal Community Detection in Weighted Directed Networks using Voronoi Diagrams

Community detection is a constantly occurring problem in complex networks, which are widely used to model an endless number of systems in biology, neuroscience, social sciences, information technology, etc. The widespread technique is to use a simple unweighted and undirected model to represent these systems, for which there are several good known algorithms to perform an optimal clustering. However, more and more complex and realistic systems use weighted and directed network models. The authors of this study developed a novel algorithm for community detection on weighted and directed networks based on Voronoi diagrams. This new method is also capable of performing partitioning on very dense networks, where communities are not defined by the structure of the network, but rather by the weights of links. In this approach a metric was used to define distance between nodes, which translates the weights to length. Moreover, the selection of the Voronoi cell generator points and the assignment of all other nodes to the Voronoi regions includes the directions of links. An extensive testing of the method was performed on randomly generated benchmark networks and also on real-life inter-areal cortical network of the macaque monkey obtained by retrograde-tracing experiments and many more.