文章速递：从聚集的局部信息对网络中有影响的节点进行排序

文章标题：

Ranking influential nodes in networks from aggregate local information

期刊来源：

Phys. Rev. Research

地址：

https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.5.033123

补充文件：https://journals.aps.org/prresearch/supplemental/10.1103/PhysRevResearch.5.033123/Supplemental_PRR.pdf

摘要：许多复杂系统都呈现出一种自然的层次结构，其中的元素可以根据"影响力"的概念进行排序。虽然计算节点的影响力通常需要完整而准确地了解组成元素之间的交互作用，但本文作者利用低秩近似方法证明，在各种情况下，节点邻域的局部和总体信息足以可靠地估计节点的影响力，而无需推断或重建整个交互作用图。只要底层网络不是过于稀疏，本文提出的框架就能成功地高精度逼近WWW PageRank、生态系统的营养级、复杂经济体中工业部门的上游性以及社交网络的中心性度量等各种系统中不同的影响力化身。

了解复杂系统的内部组织和集体功能是许多科学领域的核心问题，其应用范围广泛，从流行病学中的中心检测、生物应用中的蛋白质-蛋白质相互作用网络的了解到金融网络中的系统风险研究。其中一个最相关的问题是，如何根据一些有意义的局部或全局指标对复杂网络中的节点等成分进行有效排序。最简单的局部观测指标是节点 $i$ 的度数 $k_i$ ，这是一种有用的方法，尽管很简单，但可以仅根据节点直接联系人的数量和强度来评估节点的"重要性"。全局衡量标准，如不同类型的中心度，在信息从节点向网络外部区域传播的速度角度，对节点进行更全面的衡量。但缺点是，它们通常更难精确计算，而且对网络组织的微小细节非常敏感。此外，现在有不少证据表明，许多中心度测量方法尽管以全局性为前提，但通常与局部度相关。

在典型的全局衡量标准中，对节点进行分类和排序的一个重要方法是基于一个总括概念，我们将其称为"影响力"，它可以在整个网络中自洽地定义。我们的想法是，一个节点 $i$ 的影响力 $\mathcal{I}_i$ 应该比受 $i$ "影响 "的节点（即其邻域 $\partial i$ 中的节点 $j$ ）的影响力 $\mathcal{I}_i$ 平均略大。在公式中

$\mathcal{I}_i = 1+\left\langle\mathcal{I}_{j \in \partial i}\right\rangle$ 例如，在理论生态学中，构成复杂生态系统的物种可以在食物链层次结构中被赋予一个自然的 "影响"（营养）等级，这可以通过上式精确计算出来：顶级捕食者在食物链中处于较高的位置，因为它们要么吃掉顶级捕食者本身，要么吃掉大量中级或低级物种。不过，上式中定义的影响力概念还有更广泛的表现形式：谷歌使用的 PageRank 算法将被其他非常相关的地址链接或被非常多的其他网页链接的网页归类为非常相关的网页。在经济学中，不同国家的工业部门可以根据其在生产链中的位置和重要性进行排序，使用所谓的上游度量指标来衡量产品与最终消费的距离。节点 $i$ 的卡茨中心度 $\mathcal{K}_i$ 是经过 $i$ 的路径的加权和，它本身可以用上式的形式表示，也可以用步行者从源节点到目标节点的平均首次通过时间来表示。这些例子证明，"影响 "框架原则上是一种从全局角度解决网络排序问题的相当普遍和直观的方法。

部分结果：

图 1. 节点的近似Katz 中心度与精确Katz 中心度之间关系的示例。在一个由 $N=9$ 个节点组成的小型、无向、密集网络中，基于Katz 中心度的影响力节点排序[公式 (12)；红色实线]与我们的近似公式[公式 (9)，只有行约束；绿色虚线]之间的比较（网络连边为灰色实线）。每个节点的颜色反映了Katz中心度排名（归一化为 1），而节点大小与其度成正比。矩阵 $A=\alpha \tilde{A}=\left(\eta / k_{\max }\right) \tilde{A}(\eta=0.46)$ 与网络的邻接矩阵 $\tilde{A}$ 成比例，以最大度数 $k_{\max }$ 归一化。完全中心性度量和近似中心性度量都归一化为最大值 1，并在同一刻度上进行比较（右侧）。我们可以看到，秩-1 公式很好地近似了每个节点的Katz 中心度的精确值，并正确地反映了每个节点的 "度中心度"（在草图中用节点大小表示）。

图 2. ER随机和无标度（SF）网络的Katz中心度。我们绘制了 $\sigma$ 指标（定义见 (17)）与 ER 稀疏性参数 $p$ 的函数关系图，以及大小为N=1000的 SF 网络 $(\gamma=2.2)$ 的等价 $\langle k\rangle /(N-1)$ 的函数关系图，其中 $\langle k\rangle$ 是平均度数。曲线对应的是 $M=3600$ 实例的平均值。这些实例的分布与曲线的粗细相当，而圆点则标出了曲线的计算值。在插图中，我们提供了在 $p=0.5$ 时数值中心度测量与近似中心度测量的散点图。

图 4. 在实际数据中检验影响的近似公式。在单约束（绿点）和双约束（红点）[公式(9)]模型中，经验影响力[使用公式(2)通过数据交互矩阵计算得出]与我们的近似公式的不同化身的散点图。左上图为世界银行数据集，我们计算了复杂经济体中工业部门的上游性；中上图为 9914 个节点的斯坦福数据集，我们计算了网页的 PageRank；右上图为圣马克生态系统中物种的营养级。下排从左到右依次计算了 Facebook 用户数据集、arXiv Gr-Qc 协作网络和 OpenFlights 数据集的Katz中心度。

· 往期精彩内容 ·

⁜ Nature Reviews Physics：四篇关于网络科学的研究亮点报道

⁜ 用于评估图脆弱性和鲁棒性的Python工具箱

⁜ 文章速递：为什么社交网络中存在六度分离？

⁜ 文章速递：在相互依赖的话题中建立爆炸性意见去极化的模型

⁜ Physics Reports：复杂网络近五年综述15篇

END

点个赞+在看你最好看

内容中包含的图片若涉及版权问题，请及时与我们联系删除

文章速递：从聚集的局部信息对网络中有影响的节点进行排序

Phys. Rev. Research

评论列表

评论