Starling: Introducing a mesoscopic scale with Confluence for Graph Clustering

Abstract

Given a Graph G = (V, E) and two vertices i, j ∈ V, we introduce Confluence(G, i, j), a vertex mesoscopic closeness measure based on short Random walks, which brings together vertices from a same overconnected region of the Graph G, and separates vertices coming from two distinct overconnected regions. Confluence becomes a useful tool for defining a new Clustering quality function QConf(G, Γ) for a given Clustering Γ and for defining a new heuristic Starling to find a partitional Clustering of a Graph G intended to optimize the Clustering quality function QConf. We compare the accuracies of Starling, to the accuracies of three state of the art Graphs Clustering methods: Spectral-Clustering, Louvain, and Infomap. These comparisons are done, on the one hand with artificial Graphs (a) Random Graphs and (b) a classical Graphs Clustering Benchmark, and on the other hand with (c) Terrain-Graphs gathered from real data. We show that with (a), (b) and (c), Starling is always able to obtain equivalent or better accuracies than the three others methods. We show also that with the Benchmark (b), Starling is able to obtain equivalent accuracies and even sometimes better than an Oracle that would only know the expected overconnected regions from the Benchmark, ignoring the concretely constructed edges.

Fig 1. Optimal Clusterings for QPedge and Q_Conf on Gtoy1.

If two vertices have same color, then they are in a same Module, with 〈P, R, F〉 where $\mathbf{P}=Precision\left(\mathcal{P}airs\right(\mathrm{\Gamma }),E)$, $\mathbf{R}=Recall\left(\mathcal{P}airs\right(\mathrm{\Gamma }),E)$, $\mathbf{F}=Fscore\left(\mathcal{P}airs\right(\mathrm{\Gamma }),E)$.

Fig 2. Homogeneity and Completeness: {x, y} ∈ E iff x and y have same color.

Fig 3. Binary classifiers of nodes pairs by nodes blocks.

Fig 4. Performance with Benchmark_ER.

Each point (x, y) is the average over 100 Graphs with p = x.

Fig 5. Performance with Benchmark_LFR (k = 15).

Each point (x, y) is the average over 100 Graphs with μ = x. Fig 5(a)–5(c) are zooms on the Fscores when the overconnected regions are less clear (i.e. when we can no longer trust $Oracl{e}_{LFR}\left(G_{LFR}\right)={\mathrm{\Gamma }}_{G_{LFR}}$).

Fig 6. Performance with Benchmark_LFR (k = 25).

Each point (x, y) is the average over 100 Graphs with μ = x. Fig 6(a)–6(c) are zooms on the Fscores when the overconnected regions are less clear (i.e. when we can no longer trust $Oracl{e}_{LFR}\left(G_{LFR}\right)={\mathrm{\Gamma }}_{G_{LFR}}$).

Fig 7. Performance of SGC(GEmail=(VGEmail,EGEmail), κ), κ varying.

According to the intrinsic truth $E_{G_{Email}}$ in Fig 7(a), and in Fig 7(b) according to the extrinsic truth $\mathcal{P}airs({\mathrm{\Gamma }}_{Dep})={\cup }_{\gamma \in {\mathrm{\Gamma }}_{Dep}}{\mathcal{P}}_2^{\gamma }$.

Fig 8. Performance of SGC(G = (V,E), κ) according to the intrinsic truth E, κ varying.

Fig 9. Performance with Benchmark_ER.

Each point (x, y) is the average over 100 Graphs with p = x.

Fig 10. Performance with Benchmark_LFR (k = 15).

Each point (x, y) is the average over 100 Graphs with μ = x. Fig 10(a)–10(c) are zooms on the Fscores when the overconnected regions are less clear (i.e. when we can no longer trust $Oracl{e}_{LFR}\left(G_{LFR}\right)={\mathrm{\Gamma }}_{G_{LFR}}$).

Fig 11. Performance with Benchmark_LFR (k = 25).

Each point (x, y) is the average over 100 Graphs with μ = x. Fig 11(a)–11(c) are zooms on the Fscores when the overconnected regions are less clear (i.e. when we can no longer trust $Oracl{e}_{LFR}\left(G_{LFR}\right)={\mathrm{\Gamma }}_{G_{LFR}}$).

Fig 12. Optimal Clusterings for QConf0.0 with t = 3 and with t = 6: Shapes describe an optimal Clustering for QConf0.0 with t = 3, colors describe an optimal Clustering for QConf0.0 with t = 6.