Locally optimal heuristic for modularity maximization of networks

Area of Science:

• Network Science
• Computer Science
• Data Analysis

Background:

• Community detection is crucial for understanding network structures.
• Current methods often use hierarchical or partitioning heuristics.
• Hierarchical networks present unique challenges for community detection.

Purpose of the Study:

• To propose a novel divisive heuristic for community detection in hierarchical networks.
• To ensure each bipartition within the heuristic is provably optimal.
• To compare the proposed heuristic against existing methods.

Main Methods:

• Developed a locally optimal divisive heuristic for hierarchical networks.
• Compared the heuristic with Newman's spectral-based divisive method.
• Evaluated performance against Clauset, Newman, and Moore's agglomerative heuristic.

Main Results:

• The proposed divisive heuristic yielded superior results compared to Newman's method.
• The heuristic outperformed the Clauset et al. agglomerative method.
• Effective on networks up to 4941 vertices and 6594 edges.

Conclusions:

• The novel divisive heuristic offers improved community detection in hierarchical networks.
• Provably optimal bipartitions contribute to enhanced accuracy.
• This method provides a more effective alternative for analyzing complex network structures.