超越网络社区：权力层级揭示了更多真相

《Engineering Applications of Artificial Intelligence》：Beyond network community: Authority hierarchy reveals more

社区检测方法通过构建有向权威层级图，识别多节点领导核心并反向遍历划分社区，有效揭示复杂网络内部层级结构，在六个真实网络上表现优于基准方法，成功应用于图像聚类和国际贸易网络分析。

　　

王子宁|张子瑜|唐俊|吴贤|潘庆涛|吕兆林|王浩森|王星|范耀军

中国国防科技大学系统工程学院大数据与决策实验室，长沙，410073

摘要

大多数复杂网络（如果不是全部的话）本质上都具有社区结构和层次结构。这些社区内部节点之间的层次结构为网络分析和优化提供了更精细的视角，相较于中观层面的社区结构更为有效。为此，我们提出了一种基于权威层次结构（LCDAH）的局部社区划分新方法。该方法通过构建权威层次图——一种明确模拟节点间权威关系的有向结构——来推进网络数据挖掘。在该图中，可以高效地识别出处于顶层的紧密连接的核心节点，这些节点成为社区形成的共同领导者；随后通过从这些核心节点向下遍历图来为每个节点分配所属社区。该方法不仅能够高精度地检测社区边界，在六个真实世界网络上的表现优于现有基准方法，还能揭示网络的内部层次结构，提供超出简单划分的深度洞察。我们通过两个数据挖掘应用展示了其实用性：一是通过网络转换进行图像聚类，二是分析国际贸易网络，验证了其在建模复杂系统方面的有效性。

引言

网络是由节点及其相互关系组成的集合，是建模和描述自然与社会复杂系统的强大工具。在这些网络中，社区被定义为内部连接紧密、外部连接稀疏的模块或簇（Fortunato和Newman，2022；Moscato和Sperlì，2021）。检测社区有助于揭示网络的局部中观结构和潜在模式，从而为脑网络（Han等人，2023）、社交媒体网络（Ma等人，2024）、城市交通网络（Cesario等人，2017）以及城市共址网络（Liu等人，2022）等系统的实际应用和管理提供宝贵见解。

现有的社区检测方法大致可分为全局方法和局部方法。全局方法（如模块度优化（Vincent D Blondel等人，2008；Clauset等人，2004；Newman，2004；Newman和Girvan，2004）和统计推断（Holland等人，1983；Lyzinski等人，2017；Mu等人，2022；Peixoto，2013）会划分整个网络，但往往引入人为的分割，存在分辨率限制（Fortunato和Barthélemy，2007；Fortunato和Newman，2022；Peixoto，2014；Reichardt和Bornholdt，2006），或者无法捕捉到内在的层次结构（Borgatti和Everett，2000；Gallagher等人，2021；Shi等人，2024；Smith和Sarabi，2022）。最近的研究表明，真实世界的网络通常表现出局部主导性、层次结构和社区中心（Clauset等人，2008；Shi等人，2024）。局部信息可以揭示社区如何通过节点的自发聚类行为自然形成，从而提供更自然的社区组织视角。与全局方法不同，局部社区检测避免了在考虑整个网络时可能出现的数据伪影和人为划分。例如，它克服了模块度优化和随机块模型（Fortunato和Barthélemy，2007；Fortunato和Newman，2022；Peixoto，2014；Reichardt和Bornholdt，2006）固有的分辨率限制，并减少了在连通性均匀的网络中的误识别（Shi等人，2024）。此外，局部方法减轻了计算负担，且无需完整的网络信息，而这在实践中往往难以获得（Wang等人，2017）。

作为网络分析工具，社区提供了对复杂系统的粗粒度视图。然而，许多检测方法忽略了内部社区结构（如核心-边缘组织和层次结构（Borgatti和Everett，2000；Gallagher等人，2021；Smith和Sarabi，2022），这些结构所提供的洞察与宏观分析同样重要（Shi等人，2024）。研究表明，网络中普遍存在非对称互动（Vincent D. Blondel等人，2008；R. Li等人，2021；Serrano等人，2009；Stanoev等人，2011），社区通常表现出区分核心节点和边缘节点的隐含层次结构。这些内部结构捕捉了网络的关键特征，有助于社区划分和对组织的更深入理解（Vincent D. Blondel等人，2008）。

为了解决这些局限性，我们提出了一种基于权威层次结构（LCDAH）的局部社区检测方法。LCDAH首先通过建模节点间的影响传播来构建有向的权威层次图，自然捕捉非对称关系，然后识别出共同领导的核心节点群组，并通过反向遍历来为节点分配社区。LCDAH具有几个关键优势：

(1)

揭示内部层次结构。LCDAH不仅揭示了社区成员身份，还通过可解释的中间图揭示了内部权威结构，包括核心-边缘模式和多节点领导结构，比扁平划分方法提供了更深入的洞察。

(2)

显式的共同领导模型。将社区核心视为潜在的多节点集合，LCDAH自然地容纳了共同领导现象，避免了单核心模型的过度简化，并防止了同级影响者之间的人为层次结构。

(3)

高鲁棒性和通用性。广泛的实验表明，LCDAH在多样化的合成和真实世界网络上的表现优于现有最先进方法，即使在密集小团体或连通性均匀的网络等具有挑战性的情况下也能准确恢复真实社区。

本文的结构如下：第2节回顾了当前的社区检测研究；第3节介绍了LCDAH的过程；第4节通过一系列人工和真实世界数据集验证了LCDAH的性能；最后第5节总结了该方法并提出了未来工作的方向。

相关研究

社区检测方法通常依赖于整个网络的全局信息，例如与全局零模型进行比较（Fortunato和Newman，2022；Newman，2004；Newman和Girvan，2004；Shi等人，2024）。然而，这种全局方法将检测粒度限制在中观层面，缺乏深入探索内部结构模式的能力（Chen等人，2016）。实际上，在进一步划分社区时，它们的内部组织往往揭示出

模型与方法

在网络中，边作为信息传递的桥梁，但它们本质上只通过连接节点对来传递局部信息。然而，传统的社区检测方法通常被视为需要整体网络视图的全局任务。这种方法可能效率低下，因为社区是主要由局部互动驱动形成的中观结构，可能与远端节点关系不大（Fortunato和Newman，2022）。

实验设置

我们在一系列人工和真实数据集上验证了LCDAH的性能。我们设置${\gamma }_{con\mathrm{et}ct}={\gamma }_{n\mathrm{ei}gh\mathrm{ob}}=0.5。本文中的所有实验都在配备第13代Intel(R)\; Core(TM)\; i9-13900HX处理器（2.20\; GHz，32\; GB\; RAM）的计算机上进行。$

层次结构和共同领导的精确建模

作为一种网络分析方法，准确揭示社区层次结构可以为理解复杂系统提供宝贵信息。为了研究LCDAH理解社区层次结构的能力，我们

讨论与未来工作

在本文中，我们提出了一种基于权威层次结构检测（LCDAH）的局部社区划分新方法。通过聚合节点的成对互动数据，LCDAH创建了一个权威层次图，利用局部互动信息来识别和分割网络中的社区。LCDAH提供了对社区核心及其真实内部层次的全面视图，使得更有效地捕捉到其中的细微异质性模式。

CRediT作者贡献声明

王子宁：撰写——审稿与编辑，撰写——初稿，可视化，软件开发，方法论，概念化。张子瑜：撰写——审稿与编辑。唐俊：撰写——审稿与编辑，监督，项目管理，资金获取。吴贤：撰写——审稿与编辑，正式分析，数据整理。潘庆涛：可视化，调查。吕兆林：可视化，调查。王浩森：验证，软件开发。王星：撰写——审稿与

利益冲突声明

作者声明他们没有已知的可能会影响本文报告工作的财务利益或个人关系。

致谢

本工作得到了国家自然科学基金（项目编号：62073330和72101265）、国家基础研究基金（项目编号：2021XXJJ081）以及国防科技大学创新科学基金项目（项目编号：23-ZZCX-JDZ-32）的支持。