Starling: Introducing a mesoscopic scale with Confluence for Graph Clustering
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 regio...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2023-01-01
|
| Series: | PLoS ONE |
| Online Access: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10449208/?tool=EBI |
| _version_ | 1797736598656253952 |
|---|---|
| author | Bruno Gaume |
| author_facet | Bruno Gaume |
| author_sort | Bruno Gaume |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T13:16:14Z |
| format | Article |
| id | doaj.art-213da4a0029e4f57a92ed80f57a92bad |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-03-12T13:16:14Z |
| publishDate | 2023-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-213da4a0029e4f57a92ed80f57a92bad2023-08-27T05:31:58ZengPublic Library of Science (PLoS)PLoS ONE1932-62032023-01-01188Starling: Introducing a mesoscopic scale with Confluence for Graph ClusteringBruno GaumeGiven 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.https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10449208/?tool=EBI |
| spellingShingle | Bruno Gaume Starling: Introducing a mesoscopic scale with Confluence for Graph Clustering PLoS ONE |
| title | Starling: Introducing a mesoscopic scale with Confluence for Graph Clustering |
| title_full | Starling: Introducing a mesoscopic scale with Confluence for Graph Clustering |
| title_fullStr | Starling: Introducing a mesoscopic scale with Confluence for Graph Clustering |
| title_full_unstemmed | Starling: Introducing a mesoscopic scale with Confluence for Graph Clustering |
| title_short | Starling: Introducing a mesoscopic scale with Confluence for Graph Clustering |
| title_sort | starling introducing a mesoscopic scale with confluence for graph clustering |
| url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10449208/?tool=EBI |
| work_keys_str_mv | AT brunogaume starlingintroducingamesoscopicscalewithconfluenceforgraphclustering |