Community detection in directed weighted networks using Voronoi partitioning

Area of Science:

• Network analysis
• Graph theory
• Computational topology

Background:

• Community detection is crucial in network analysis but challenging for directed and weighted networks.
• Existing algorithms struggle with high graph density and diverse link information.
• Link weights and graph density pose significant challenges for current community detection methods.

Purpose of the Study:

• To present a novel algorithm for community detection in directed and weighted networks.
• To generalize Voronoi partitioning for complex network structures.
• To offer a method that directly uses edge weights representing lengths.

Main Methods:

• A generalized Voronoi partitioning algorithm applied to directed weighted networks.
• Direct integration of edge weights, including those representing lengths.
• Comparative performance analysis against established algorithms on benchmark and real-world networks.

Main Results:

• The algorithm effectively detects communities in dense graphs where weights are primary.
• Hierarchical network structures, exemplified by brain connectivity, are successfully identified.
• Comparable or superior time efficiency to state-of-the-art algorithms was demonstrated.

Conclusions:

• The proposed Voronoi partitioning algorithm offers an efficient solution for community detection in directed and weighted networks.
• This method handles complex network data, including length-based weights and hierarchical structures.
• The algorithm shows promise for applications in neuroscience, transportation, and social network analysis.