探索网络影响力的新视角：DomiRank中心性与网络结构的脆弱性

发布时间：2024-12-20 13:25

原创刘志航集智俱乐部

导语

从社交媒体到全球交通网络，这些相互连接的复杂系统在方便我们的同时，也暴露出潜在的脆弱性。这种脆弱性可能源于网络结构本身，也可能因为某些关键节点的影响而显著增强。那么，如何评估和理解这种脆弱性呢？最新发表于 Nature Communications 的一项研究提出了一种全新的网络中心性度量方法——DomiRank。DomiRank 引入节点竞争机制，通过综合考量网络的局部（节点级）和中尺度（结构级）信息的权衡，评估节点的重要性。这些节点不仅在其直接的邻域内发挥作用，还可能通过与其他间接的节点产生的联合支配影响，对整个网络的稳定性和功能性产生深远影响。这种新的度量方法为我们理解和应对复杂网络中的脆弱性问题提供了新的视角。

研究领域：复杂网络，中心性度量，网络结构，节点支配力，网络脆弱性

刘志航 | 作者

论文题目：DomiRank Centrality reveals structural fragility of complex networks via node dominance
论文来源：Nature Communications
论文链接：https://www.nature.com/articles/s41467-023-44257-0

复杂系统由众多互动组件构成，其动力学和涌现特性是系统的基本属性。然而，并非系统中的所有组成部分都对其结构和动力学同等重要。在某些系统中，少数元素可能对保持复杂系统的结构完整性或功能至关重要。我们能否准确高效地识别这些复杂系统中的关键元素，对于从提供互联网搜索中最合适的网站，到定义疫苗接种方案以减少疾病传播，再到确保交通网络和关键基础设施的完整性和功能，都具有核心意义。

1. DomiRank中心性概念与计算

网络中心性（Network centrality）度量提供了评估节点在网络中相对重要性的一般框架。这些节点中心性的定义多种多样，从仅考虑节点的连接数（度中心性），到聚合节点邻域的重要性（如特征向量、Katz 和 PageRank 中心性），再到考虑节点在网络中的相对位置（如接近度和介数中心性）或节点在动态过程中的作用（如电流、纠缠和随机游走中心性）。

这项最新的工作介绍了一种名为 DomiRank 的中心性度量方法。DomiRank 直观地量化了节点在各自邻域中的支配程度（degree of dominance）。高DomiRank得分的节点往往是那些被大量不重要节点（例如，通常度数较低的节点）所包围并支配的节点。与其他中心性如特征向量或 PageRank 不同，DomiRank中的节点得分更加分散，这归因于DomiRank定义中隐含的竞争机制。

这个公式是用来计算网络中每个节点的 DomiRank 中心性的数学表达式。简单来说，让我们把一个复杂的网络比作一个大型的社交圈。在这个社交圈中，每个人（节点）都有他们的朋友（连接）。有些人有很多朋友，而有些人则相对较少。

代表的是一个向量，它包含了网络中每个节点的DomiRank值，记录了社交圈中每个人的受欢迎程度或影响力。A是网络的邻接矩阵，表示节点之间的连接关系，是一个记录谁与谁是朋友的社交网络图。IN×N是一个单位矩阵，它的大小与网络中节点的数量相同，可以想象成一个基准线，确保我们在评估每个人的受欢迎程度时不会偏离太远。θ是一个常数，用于调整 DomiRank 值的规模。

其中，σ是一个可调节的参数，它控制着局部（节点级别）和网络结构的平衡。竞争机制是通过参数σ来体现的。这个参数就像是一个“放大镜”，它帮助我们调整我们看待这个社交圈的方式。当它值较大时，我们更关注一个人在整个社交圈中的位置；当它值较小时，我们则更关注一个人的直接朋友数量。因此，当σ较大时，它强调了节点在整个网络结构中的相对位置和作用，从而体现出节点之间的竞争关系。而当σ较小时，节点的 DomiRank 值更多地依赖于它们的局部连接（比如它们有多少邻居）。

图1 σ 在计算 DomiRank 值中的作用。

作者通过在具有明显中尺度结构的方格网络中探索不同σ值下的 DomiRank 分数来展示这一点（图1）。当σ接近其下界时（即接近 0），DomiRank 主要基于节点的度数（即局部信息），导致除了边缘节点外，大部分节点的 DomiRank 值几乎相同。随着σ的增加，DomiRank 值开始偏离单纯基于度数的评分，每个节点的 DomiRank 开始受到其直接邻居的影响。这意味着与边缘节点直接相连的节点可以部分支配这些边缘节点，从而提高自己的 DomiRank 分数。此时，一个节点的 DomiRank 分数不再仅由其直接邻居决定，还受到更远距离的影响。当σ达到最大值时，每个节点的 DomiRank 分数部分受到整个网络通过竞争机制的影响。在这种极端竞争环境下，形成了支配和被支配节点的最终交替模式，这一模式由网络的有限边界和全局对称性决定。

2. DomiRank与网络脆弱性

DomiRank特别适用于分析和理解网络的结构脆弱性，无论是在结构上还是在动力学上。这是基于DomiRank权衡了网络的两个关键因素，即节点的度数（邻居数量）和邻居的邻域特征（周边）。

具有高度数并连接到拥有少量连接的邻居（稀疏周边）的节点，是获得高 DomiRank 分数的主要候选节点。这种节点在网络脆弱性中也扮演着核心角色，因为它们的失效可能导致其邻域的瓦解。在高度竞争的环境中（高σ值），还存在一种基于节点在全局网络结构中位置的支配。这种支配主要来自于联合支配，即一组节点共享重叠的邻域但彼此之间没有直接连接。在这种情况下，每个节点都有助于在共享的邻域内压制支配。因此，这种机制还有助于识别网络中的脆弱部分。如果移除这些具有支配地位的节点，将导致它们共享的邻域瓦解，从而突出这种结构的脆弱性。

作者探究了基于DomiRank中心性的有针对性攻击在不同网络拓扑（包括合成和现实世界网络）中的效果，分析了这种攻击对瓦解网络结构和功能的能力，并将其与基于其他中心性的攻击进行了对比。在进行序列节点移除（攻击）时，使用最大连通组件（LCC）的相对大小作为网络鲁棒性的主要指标。通过比较不同攻击下的最大联通组件曲线，以及曲线下的面积作为鲁棒性的综合指标，来比较不同网络在不同攻击下的鲁棒性（图2）。DomiRank中心性在识别和瓦解网络脆弱点方面的高效性，特别是在高度竞争的环境下，DomiRank的攻击尤其有效，因为这时网络结构的影响超过了局部节点属性的影响。

图2 在攻击 2D-网格、Erdős-Rényi 和 Barabási-Albert 网络中将 DomiRank与其他中心性指标进行比较。

为了更全面地评估DomiRank的性能，研究者分析了不同大小的多种真实网络拓扑。包括航空运输网络（RyanAir连接）、神经网络（秀丽隐杆线虫）、空间网络（美国西部电网）、引文网络（高能物理学arXiv）、社交网络（LiveJournal用户及其连接）和大规模空间运输网络（美国完整道路网络）。结果显示，与合成网络的分析一致，基于DomiRank的攻击比其他中心性攻击更有效地瓦解了这些网络（图3）。

图3 针对合成网络和现实世界网络的基于中心性的攻击。

3. DomiRank与集体影响力算法的区别

作者发现，基于介数中心性的迭代攻击在破坏最大连通组件方面最为高效，因为它专注于找到网络中的瓶颈节点，从而简单地分割网络。在这种思想的基础上，近期关于网络中心性比较前沿的方法是集体影响力（Collective Influence, CI）算法，这种旨在识别和最小化影响网络传播的关键节点集合。CI算法攻击致力于找到根据其潜在传播影响的重要节点。与DomiRank一样，CI算法不仅考虑局部信息，还整合了节点周围结构的信息。

但是这两种算法的计算机制有本质的区别。DomiRank是基于节点支配力的概念，它考虑了节点与其邻居的相互作用以及它们对邻域的支配情况。DomiRank通过解动力学方程来确定每个节点的中心性，其中包括了节点间的竞争关系和节点对邻居的支配。而CI算法是通过最小化非回溯矩阵的最大特征值来识别网络中的关键影响者。这个算法更侧重于全局网络结构，尤其是在大规模网络中。CI算法评估了节点及其周围邻域的集体影响力，特别强调了低度节点周围的高度节点的重要性。

与CI算法相比，DomiRank在移除较少节点时更有效，但随着更多节点的移除，CI算法的竞争性增强。DomiRank通过移除局部支配节点集合来阻止传播过程，从而有效阻止信息在其邻域的传播。相比之下，CI算法的目标是通过移除潜在的超级传播者来削弱连锁传播效应。DomiRank的策略旨在通过分割传播域来阻止传播过程，几乎隔离网络中的邻域。DomiRank揭示的节点集合能有效建立防火墙，减缓谣言传播，这一概念可推广至其他动力学过程，如信息传输或疫情传播等，这些机制也暗示DomiRank可用于制定高效的疫苗策略。

总之，DomiRank是一种新的中心性度量，它通过单一可调参数集成了网络拓扑的不同方面，控制着局部（节点级别）和中尺度（结构级别）信息的权衡。DomiRank中定义的竞争机制提供了一种在网络功能性和完整性中识别高度重要节点的替代视角，通过考虑节点在各自邻域中的相关性，以及非直接连接节点在重叠邻域上的紧密合作（即联合支配）。DomiRank通过揭示网络脆弱性的基本方面，可以促进进一步研究，以开发更有效的缓解策略，改善我们对复杂系统结构和韧性的整体理解。

集智百科词条“网络中心性”中介绍了一系列网络中心性度量方法：

度中心性 Degree centrality

紧密中心性 Closeness centrality

调和中心性 Harmonic centrality

中介中心性 Betweenness centrality

特征向量中心性 Eigenvector centrality

使用邻接矩阵发现特征向量中心性 Eigenvector centrality

卡兹中心性 Katz centrality

网页排名中心性 PageRank centrality

渗滤中心性 Percolation centrality（PC）

跨团中心性 Cross-clique centrality

弗里曼中心度 Freeman centralization