Spectral density-based clustering algorithms for complex networks.

Area of Science:

• Graph theory
• Network science
• Data mining

Background:

• Traditional graph clustering focuses on vertex grouping.
• Grouping networks by connectivity is crucial for applications like identifying brain network patterns in disorders.
• Real-world networks exhibit natural fluctuations that complicate clustering.

Purpose of the Study:

• To develop and evaluate novel graph clustering methods for grouping networks based on connectivity structure.
• To address the challenge of natural fluctuations in real-world network data.
• To apply these methods to functional brain networks and chemical compound datasets.

Main Methods:

• Introduced k-means for clustering graphs of the same size.
• Developed gCEM, a model-based approach for clustering graphs of different sizes.
• Utilized spectral density as a key feature for distinguishing graph connectivity structures.

Main Results:

• Both k-means and gCEM demonstrated effective performance on toy models and real-world data.
• The methods successfully clustered graphs with differing connectivity structures, even with similar numbers of edges, vertices, and centrality.
• Performance was validated on functional brain networks of monkeys and chemical compound datasets.

Conclusions:

• K-means is recommended for graph clustering when graphs have an equal number of vertices.
• The gCEM method is recommended for graph clustering when graphs have varying numbers of vertices.
• These spectral density-based clustering approaches offer a robust way to analyze network connectivity.