Community detection in complex networks via node similarity, graph representation learning, and hierarchical clustering

查看原文 / View Original 编辑 / Edit

Computer Science > Social and Information Networks arXiv:2303.12212 (cs) [Submitted on 21 Mar 2023 (v1), last revised 3 Nov 2026 (this version, v3)] Title: Community detection in complex networks via node similarity, graph representation learning, and hierarchical clustering Authors: Łukasz Brzozowski, Grzegorz Siudem, Marek Gagolewski.

计算机科学 > 社交与信息网络 arXiv:2303.12212 (cs) [提交于 2023 年 3 月 21 日 (v1)，最后修订于 2026 年 11 月 3 日 (本版本，v3)] 标题：通过节点相似性、图表示学习和层次聚类进行复杂网络中的社区检测作者：Łukasz Brzozowski, Grzegorz Siudem, Marek Gagolewski。

Abstract: Community detection is a significant challenge in analysing real graphs, including social, citation, biological, and many other networks. This article proposes three new, general, hierarchical frameworks to deal with this task. The introduced approach supports various linkage-based clustering algorithms, vertex proximity matrices, and graph representation learning models.

摘要：社区检测是分析真实图（包括社交、引文、生物学以及许多其他网络）时的一项重大挑战。本文提出了三种新的通用层次化框架来处理这一任务。所引入的方法支持多种基于链接的聚类算法、顶点邻近矩阵和图表示学习模型。

We compare 364 module combinations on Stochastic Block Model graphs and real-life datasets. We observe that our best pipelines (Wasserman-Faust and the mutual information-based PPMI proximity, as well as the deep learning-based DNGR representations) perform competitively with the state-of-the-art Leiden and Louvain algorithms.

我们在随机块模型图和真实数据集上比较了 364 种模块组合。我们观察到，我们最好的流水线（Wasserman-Faust 和基于互信息的 PPMI 邻近度，以及基于深度学习的 DNGR 表示）在性能上与最先进的 Leiden 和 Louvain 算法具有竞争力。

At the same time, unlike the latter, they remain hierarchical. Thus, they output a series of nested partitions of all possible cardinalities which are compatible with each other. This feature is crucial when the number of correct partitions is unknown in advance, and we show that it is obtained at near-zero practical cost in terms of partition quality.

同时，与后者不同的是，它们保持了层次性。因此，它们输出一系列相互兼容的、所有可能基数的嵌套分区。当预先不知道正确分区的数量时，这一特性至关重要，并且我们证明，在分区质量方面，它是以几乎为零的实际成本获得的。

On graphs composed of many small communities, our pipelines are more accurate than the reference solutions. Nevertheless, the downside of our approach is its time complexity, which confines the framework to networks of some 10000 vertices on personal machines.

在由许多小社区组成的图上，我们的流水线比参考解决方案更准确。然而，我们方法的缺点在于其时间复杂度，这使得该框架在个人计算机上仅限于处理约 10000 个顶点的网络。