Centre National de la Recherche Scientifique, CLLE, ISCPIF, Toulouse, France.
PLoS One. 2023 Aug 24;18(8):e0290090. doi: 10.1371/journal.pone.0290090. eCollection 2023.
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.
给定一个图 G=(V,E) 和两个顶点 i,j∈V,我们引入了 Confluence(G,i,j), 这是一种基于短随机游走的顶点介观接近度度量, 它将来自图 G 同一过连通区域的顶点聚集在一起, 并将来自两个不同过连通区域的顶点分开。Confluence 成为定义给定聚类 Γ 的新聚类质量函数 QConf(G,Γ)和定义用于优化聚类质量函数 QConf 的新启发式 Starling 以找到图 G 的分区聚类的有用工具。我们将 Starling 的准确性与三种最先进的图聚类方法的准确性进行了比较: Spectral-Clustering、Louvain 和 Infomap。这些比较一方面是在人工图 (a) 随机图和 (b) 经典图聚类基准上进行的, 另一方面是在 (c) 从真实数据中收集的地形图上进行的。我们表明, 在 (a)、(b) 和 (c) 中, Starling 总是能够获得与其他三种方法等效或更好的准确性。我们还表明, 在基准 (b) 中, Starling 能够获得与仅从基准中知道预期过连通区域而忽略具体构建的边的 Oracle 等效的准确性, 甚至有时更好。
