基于节点相似性、图表示学习与层次聚类的复杂网络社区检测框架研究

《Information Sciences》：Community detection in complex networks via node similarity, graph representation learning, and hierarchical clustering

　　

社区检测是分析真实图（包括社交、引文、生物及许多其他网络）中的一项重大挑战。本文提出了三个新的、通用的层次化框架来处理该任务。所引入的方法支持多种基于链接的聚类算法、顶点邻近矩阵以及图表示学习模型。研究人员在随机块模型（Stochastic Block Model, SBM）图与真实数据集上比较了364种模块组合。研究发现，最优流程（Wasserman–Faust度量、基于互信息的正点互信息（PPMI）邻近度，以及基于深度学习的DNGR表示）与最先进的Leiden和Louvain算法表现相当。与此同时，与后者不同，这些流程保持层次性。因此，它们输出一系列所有可能基数（cardinalities）的嵌套分区，且这些分区彼此兼容。当正确分区的数量事先未知时，这一特性至关重要，并且研究表明，在分区质量方面，该特性几乎以零实际成本获得。在由许多小社区组成的图上，所提流程比参考解决方案更准确。然而，该方法的一个缺点是其时间复杂度，这将其应用范围限制在个人机器上约104个顶点的网络中。

一、研究背景与问题

复杂网络普遍存在于社会、引文、生物等多个领域，社区检测是分析这些网络结构的关键任务。尽管已有大量算法被提出，但社区的定义本身具有广泛性和模糊性——社区既可以指紧密连接的顶点群体，也可以指在网络结构中扮演相似角色的顶点集合。传统聚类算法与社区检测在数据空间上存在差异，前者主要针对欧氏空间等度量空间，后者则直接作用于图结构。随着图机器学习（尤其是图表示学习）的兴起，跨领域方法的融合成为可能，但如何系统地将层次聚类算法应用于社区检测，并对其中的关键组件——节点相似性度量与图表示学习方法——进行大规模比较，仍是研究空白。

二、研究内容与结论

针对上述问题，本研究开发了一个模块化框架，将层次聚类算法应用于社区检测任务。该框架支持三类节点建模途径：基于节点相似性度量的距离矩阵、顶点相似性矩阵的特征分解（谱方法），以及通过图表示学习算法自动发现的欧氏空间表示。研究对24种顶点相似性建模技术（涵盖Wasserman–Faust度量、Jaccard系数、?-步游走概率、Katz指数、Rooted PageRank、Adamic–Adar相关指数、Blondel–Gajardo度量、正点互信息（PPMI）等经典度量，以及DeepWalk、DNGR、Graph Factorisation、GraRep、HARP、HOPE、Laplacian Eigenmaps、Node2Vec等表示学习算法）与7种聚类设置进行组合，共评估364种配置，在2880个随机块模型（SBM）图和6个真实网络上进行系统比较。

研究得出以下主要结论：第一，最优流程（Wasserman–Faust度量、基于互信息的PPMI邻近度、DNGR表示）在分区质量上与Leiden和Louvain算法相当，但保持层次性，能够输出任意基数（cardinalities）的嵌套分区，且各分区彼此兼容；第二，当正确分区数未知时，通过内部准则切割树状图（dendrogram）可恢复已知真实社区数条件下至少97%的准确率，即层次性的获取几乎不牺牲分区质量；第三，在由许多小社区组成的图上，所提框架比参考解决方案更准确，且该优势与模块度最大化算法合并小社区的缺陷直接相关；第四，框架的时间复杂度约为n^2.8至n^2.9，而Leiden仅为n^0.9，这限制了方法在个人机器上处理约10⁴个顶点的网络；第五，将拉普拉斯矩阵替换为任意顶点相似性矩阵并不能产生有效的谱方法，对两种度量而言这种替换被证明是不利的。

三、关键技术方法

研究采用的核心技术方法包括：1）多种节点相似性度量，如Wasserman–Faust度量、Jaccard邻域重叠系数、?-步游走概率、Katz指数、Rooted PageRank、Adamic–Adar相关指数、Blondel–Gajardo度量、正点互信息（PPMI）；2）谱方法，即对上述相似性矩阵进行特征分解；3）图表示学习算法，包括DeepWalk、DNGR、Graph Factorisation、GraRep、HARP、HOPE、Laplacian Eigenmaps、Node2Vec；4）七种层次聚类设置（不同链接函数）；5）用于选择社区数量的内部准则。实验数据包括2880个随机块模型（SBM）合成图以及6个真实世界网络数据集。

四、研究结果

4.1 组件筛选与流程选择（Section 5）：在合成数据集上对364种配置进行系统筛选，确定了九种最优流程，其中Wasserman–Faust度量、基于互信息的PPMI邻近度以及DNGR表示表现最为突出。

4.2 无已知社区数的检测（Section 6.2）：通过内部准则切割树状图，可恢复已知真实社区数条件下至少97%的准确率，表明层次性特征以极低的实际成本获得。

4.3 真实网络验证（Section 6.3）：在六个真实世界网络上，最优流程与Leiden和Louvain算法表现相当，且在包含许多小社区的网络中更为准确，该优势与模块度最大化算法合并小社区的缺陷直接相关。

4.4 时间复杂度特征（Section 6.4）：运行时间随n^2.8至n^2.9增长，而Leiden仅为n^0.9，将框架的实际应用限制在约10⁴个顶点的网络规模。

4.5 谱方法的负结果（Section 6.5）：将拉普拉斯矩阵替换为任意顶点相似性矩阵不能产生有效的谱方法，对两种度量而言该替换被证明是不利的。

五、讨论与结论

讨论部分指出，层次化方法的核心优势在于其输出的嵌套分区结构本身即是对网络组织的描述，而非获得单一分区的副产品。当网络真正具有层次结构（如部门内的子部门、领域内的子主题）时，无需预先决定观察层级即可获得该结构。此外，层次方法允许选择任意数量的社区，这是Leiden和Louvain等算法所缺乏的特性——后者虽然也产生少量嵌套分区，但仅在算法自行确定的解析度上，通常不存在恰好具有K个社区的层级。

研究结论表明，通过节点相似性、图表示学习与层次聚类的结合，可以在保持与最先进算法相当的分区质量的同时，获得层次性这一重要特性。该框架在由许多小社区组成的网络上优于模块度最大化方法，但时间复杂度限制了其在大规模网络上的应用。未来的研究方向可能包括开发更高效的近似算法，以扩展框架的适用规模。