Detecting alternative graph clusterings.

Area of Science:

• Complex networks analysis
• Graph theory
• Data mining

Background:

• Graph clustering, or community detection, is crucial for understanding complex networks.
• Modularity is a common metric for evaluating clustering quality, but often yields many similar, near-optimal partitions.
• A single optimal partition may not fully represent the network's topological organization.

Purpose of the Study:

• To address the limitation of single optimal partitions in complex networks.
• To propose a novel method for identifying an ensemble of diverse and near-optimal clusterings.
• To enhance the understanding of complex network topology through diverse partitions.

Main Methods:

• Developed a graph perturbation scheme to generate diverse clusterings.
• Analyzed the analytical properties of the modularity function under perturbation to ensure diversity.
• Demonstrated the algorithm-independent nature of the proposed methodology.

Main Results:

• The graph perturbation scheme successfully identifies an ensemble of near-optimal and diverse clusterings.
• The method systematically reveals very different partitions across various datasets.
• Analytical properties of modularity under perturbation guarantee the diversity of identified partitions.

Conclusions:

• The proposed graph perturbation method provides a more complete understanding of complex network topology.
• Identifying diverse partitions offers deeper insights than relying on a single optimal clustering.
• This approach is versatile and can be integrated with existing modularity maximization algorithms.