Starling: Introducing a mesoscopic scale with Confluence for Graph Clustering.

Area of Science:

• Graph theory
• Network analysis
• Data mining

Background:

• Graph clustering is essential for understanding complex networks.
• Existing methods like Spectral-Clustering, Louvain, and Infomap have limitations in certain graph structures.
• There is a need for improved graph clustering algorithms that accurately identify overconnected regions.

Purpose of the Study:

• To introduce Confluence, a novel mesoscopic closeness measure for graph vertices.
• To develop a new graph clustering heuristic, Starling, optimized using the Confluence measure.
• To evaluate the performance of Starling against state-of-the-art graph clustering methods.

Main Methods:

• Introduced Confluence(G, i, j), a vertex closeness measure based on short random walks.
• Developed the Starling heuristic for partitional graph clustering, optimizing a new quality function QConf(G, Γ).
• Compared Starling's accuracy against Spectral-Clustering, Louvain, and Infomap on artificial and real-world graphs.

Main Results:

• Starling consistently achieved equivalent or better clustering accuracy than Spectral-Clustering, Louvain, and Infomap on random graphs, a benchmark dataset, and real-world terrain graphs.
• On the benchmark dataset, Starling's accuracy was comparable or superior to an Oracle that knew the expected overconnected regions.
• Confluence effectively groups vertices within overconnected regions and separates vertices from distinct regions.

Conclusions:

• The Confluence measure and Starling heuristic offer a powerful new approach to graph clustering.
• Starling demonstrates robust and often superior performance across diverse graph types.
• This method provides a valuable tool for analyzing complex network structures and identifying community patterns.