英语原文共 9 页

文献翻译

文献名称：Identifying influential nodes in complex networks: A node information dimension approach

文献作者：Tian Bian, and Yong Deng

文献译名：在复杂网络中识别有影响力的网络节点：一种节点信息规模方法

摘要：在复杂网络领域，如何识别有影响力的节点是分析网络结构时的一个至关重要的问题。现有的识别有影响力节点的方法基于本地尺度，复杂网络中的全局结构信息没有被纳入考虑。本文通过在不同拓扑距离中综合本地尺度提出了一种节点信息尺度，并使用了一种网络来验证所提出方法了实用性和效果。

如何识别复杂网络中有影响的节点是复杂网络中最重要的研究方向之一。已经提出了许多方法来识别复杂网络中的有影响的节点。最近，通过获得每个节点的不同尺度的局部尺寸（LD），已经提出了一种方法。 基于该方法，提出了通过比较每个节点在最远距离处的局部尺寸（LD）来识别网络中的有影响节点的测量。但是，它只考虑节点的本地信息。在本文中，提出节点信息维度（NID）以通过合成每个分段局部维度来识别有影响的节点。结果表明，有影响的节点的识别具有理论和实际意义。

1. 引言

近年来，评估复杂网络中节点重要性因其重要的理论意义和广泛的应用引起了人们的广泛关注，如控制疾病传播[1-3]，开创新的营销手段[4-6]，和研究舆论和谣言动态[7-10]。作为识别复杂网络中节点影响的必要工具，许多中心性措施已被普遍使用，例如度中心性（Degree Centrality, DC）[11]，中介中心性（Betweenness Centrality, BC）[11]，亲密度中心性（Closeness Centrality, CC）[11]，特征向量中心性（Eigenbector Centrality, EC） [12]，网页排名（PageRank, PR）[13]，领导力排名（LeaderRank, LR）[14]，和许多其他方法 [15 -20]。DC方法简洁但不考虑网络的全局特性。尽管中介中心性和亲密度中心性是全局度量标准，但由于其计算复杂性，它们难以应用于大规模网络。

分形是物理学的基本属性，它可以表征复杂的图形和动态系统的复杂过程。复杂网络中的维度首先由Csanyi [21]描述，然后由许多研究人员开发[22-25]。Song等发现各种真实的复杂网络都表现出自相似性 [26] ，并提出了一种盒子覆盖算法来评估复杂网络的分形维数。然而，当通过盒子覆盖算法计算分形维数时，不能表达节点的均匀分布，因为不同框中的节点的数量是不同的。因此，一个称为信息维度的维度 [28] 被提出以揭示复杂网络的自相似性。从那时起，许多研究人员一直在广泛地研究复杂网络的分形和自相似性[29-33]，然而，对复杂网络的局部分形特性并没有给予太多的关注。最近，Silva和Costa [34] 提出了一种方法，包括为每个节点获得不同尺度的局部维数。它可以很好地描述网络的局部分散。基于该方法，Pu等人[35] 提出了一种测量方法，通过比较每个节点在最远距离的局部尺寸（LD）来识别网络中有影响的节点。但是，它只考虑节点的本地信息。在本文中，提出了节点信息维度，通过合成每个分段局部维度来识别有影响的节点。该方法首先计算每个节点在不同距离尺度下的局部尺寸，然后将这些局部尺寸转换为概率，以计算每个节点的不同拓扑距离尺度的信息熵。最后，节点信息维度可以通过每个节点的不同尺度的信息熵和距离的线性回归来计算。本文提出的方法不仅考虑了节点与其他节点之间的距离，还考虑了网络中周围节点的分布。如果节点在网络中的分布是令人满意的，则正在测量的节点的其他节点越近，节点的信息维度就越大，然后节点将更加重要。

所提出的方法融合了网络的局部和全局特性，当节点在网络中的重要性不完全由节点的层次或鲁棒性决定时，可以更好地识别有影响的节点，例如社交网络，基础设施网络和共同作者网络，因为在这些网络中具有影响力的节点不仅需要具有高度，而且还需要在网络结构的中心具有高鲁棒性并且在通信中起关键作用。但由于其计算复杂性，所提出的方法不适合应用于大规模网络，例如维基百科网络[36]（节点是维基百科中的页面，边缘对应于超链接），其具有数千万个节点。虽然所提出的方法具有与BC和CC相同的复杂计算，但是其在不同距离处的节点分布信息的合成使得它成为分析不大规模网络的更好方法。例如，与CC相比，所提出的方法不仅考虑从节点到其他节点的距离，还考虑局部维度，使得结果与周围节点的分布密切相关。因此，所提出的方法比CC更优越。

本文的其余部分安排如下：第二章首先简要概述了现有的中心性措施，并介绍了地方层面。 在第三章，示例网络提出并示出了用于识别有影响节点的节点信息维度。然后，说明了所提出方法的应用。第四章采用Netscience的案例研究来评估所提方法的性能。最后，在第五章中提出了一些结论。

1. 初步措施
2. 中心措施

考虑一个图：G=（V,E），它拥有n=|V|节点和m=|E|链接。各种节点中心性的测量方法如下所示。

1. 度中心性

网络i的度中心性，表示为CD（i），定义为

(1)

其中i是焦点节点，j代表所有其他节点，N是总节点数，xij代表节点i和节点j之间的链接，xij的值在节点i和节点j相连且没有其他链接的情况下定义为1.

1. 中介中心性

网络i的中介中心性，表示为BD（i），定义为

(2)

Gjk表示节点j和k之间最短路径的数量，表示节点j和k之间通过节点i的最短路径的数量。

1. 亲密度中心性

网络i的亲密度中心性，表示为CC（i），定义为

(3)

其中表示节点i和节点j之间的距离

1. 特征向量中心性

令A为一个n*n的相似矩阵。节点i的特征向量中心性xi定义为第i个属于A的最大特征值的归一化的特征向量的入度。lambda;是A的最大特征值，n是顶点的数量

(4)

同时比例因子 因此xi与连接到它的所有节点的相似性得分之和成比例。

1. 网页排名

网页排名算法是特征向量中心性的著名变体，用于对Google搜索引擎和其他商业场景中的网站进行排名。与特征向量中心性类似，网页排名假设网页的重要性由链接到它的页面的数量和质量决定。最初，每个节点获得一个单位网页排名值。然后，每个节点沿其外向链路均匀地将网页排名值分配给其邻居。数学上，步长为t的节点vi的网页排名值是

(5)

其中n是网络中的总节点数，是节点vi的出度。如果所有节点的网页排名值达到稳定状态，则上述迭代将停止。

图一 获得网络维度的过程。从节点开始，随着距离r=0到r=3的扩展，我们可以得到四个不同的。因此，在双对数尺度上，尺寸可以通过曲线的斜率获得，而r=0则不包括在内。（来自参考文献34）

1. 领导力排名

领导力排名由吕等人提出。它是网页排名算法的变体。总的来说，他们介绍了一种和其他所有节点都连接的“地节点”，然后，随机游走过程用于找到有影响的节点，并且该过程继续直到达到稳定状态。该过程可以由随机矩阵P描述，同时具有一个节点i的随机游走者下次去j的概率 ，其中aij=1意味着节点i指向j，指出度。所以节点i在t时刻的得分可以被定义为

(6)

所有节点i的初始分数都是1，地节点是0。当所有i的得分收敛到一个可以表示为的特定稳定状态时，tc是收敛时间。因此，节点的最终得分可以被定义为

(7)

这里是地节点在稳定状态的得分。因此，我们可以通过Si值得下降排列每个节点。

1. 局部维度

复杂网络的一个特征是节点的程度遵循幂律分布，这意味着在拓扑距离r（包括r）内，每个节点i关于拓扑距离r的节点的数量遵循幂律如下

（8）

其中距离d表示网络的维度。然而，由于局部性的概念，可以通过考虑尺寸d来进一步发展公式8，尺寸d可以针对每个节点i和拓扑距离r而变化。 因此，公式8中的尺寸d被重新定义为局部尺寸 。每个局部尺寸系数可以通过如下所示双对数尺度下（如图1所示）的 曲线的斜率获得

(9-10)

对于复杂网络的离散性质，上述公式可表示如下

(11-13)

其中 表示距中心节点i的拓扑距离恰好等于拓扑

图二 获得节点a的局部维数的过程

距离r的节点数。简而言之，节点i的局部维度 随着不同的起始节点i和拓扑距离r而不同。例如，为了获得图2中箭头所指向的节点a的局部维度，距离r = 3以内的节点数应计算为 ，r = 3时的节点数应计为。 根据公式13，节点a的局部尺寸约为1。

1. 信息熵

在信息科学领域，当我们想要分析任何信息的不确定性时，我们需要对信息进行定量分析。香农提出了信息熵来表示信息的不确定程度。而且，熵越大，信息越不确定。 这里，信息捕获网络中的全局结构，并且熵越大，节点的影响越大。该公式可表示如下

(14)

其中N是从网络中最远节点到我们正在计算的节点的距离， 是节点的距离i的局部维度与节点在每个距离处的局部维度之和的比率，b是对数的基数。在本文中，我们让b = e。

1. 节点信息维度

在本节中，通过合成每个分段局部维度来提出节点信息维度（NID）。换句话说，局部维度可以针对每个节点i和拓扑距离r而变化，但是节点信息维度是针对每个节点i在不同拓扑距离r处的局部维度的聚合，它仅针对每个节点i而变化。因此，它比Pu等人提出的识别复杂网络中有影响的节点的局部维数方法更全面。获得节点信息维度的推导过程如下。

1. 提出的方法

第一步：计算对于每个节点i的最大最短路径长度Ri。

第二步：计算每个节点i的不同拓扑距离标度r的信息熵 。

首先，我们应该得到我们需要按照每个拓扑距离尺度r计算的步骤如下

(15)

其次，根据公式13计算不同步骤的局部尺寸如下

(16)

第三步：节点信息维度可以由下式给出

(17)

1. 示例说明

基于上面提出的方法，给出了一个简单的例子来解释NID在这部分中的表现。从图2中，我们可以得到节点a的最大最短路径，Ra=4。

对于r等于1，步长Sa（1）显然等于4。

之后，我们可以计算本地唯独dj（1）。

(18)

之后，概率Pj（1）根据公式17计算

(19)

信息熵Ia（1）可以通过公式18获得

(20)

以这种方式，关于不同拓扑距离标度r的信息熵可以用下列方式获得

(21)

最后节点a的节点信息维度可用公式19计算，其过程如图3所示

(22)

图三 获取节点a的节点信息维度的过程

1. 案例研究

在本节中，我们使用对网络科学感兴趣的科学家（即在线科学网络）之间的共同作者网络来证明，当网络中有影响的节点不完全由其确定时，本文所提出的方法比其他中心方法做得更好，具有良好的稳健性。在线科学网络是由379名科学家组成的共同作者网络，他们的研究主要集中在各种各样的网络的属性上。

在这种情况下，我们将提出的方法与纽曼工作中获得的结果进行比较。在纽曼的工作中，他提出了一种名为社区中心性的方法，用于对科学家之间共同作者网络中的节点进行排名。这项措施的结果表明，它有能力在本地社区找到中心。实际上，在网络科学网络中具有最高社区中心地位的作者都是在这一领域工作的团体领导者或高级研究人员。同时，DC，CC，BC，EC，PageRank（PR）和LeadRank（LR）也与Newman的结果进行比较。表1中显示了用于不同测量的前10个有影响的节点的列表。在前10个列表中，所提出的方法，DC，CC，BC，EC，PR和LR具有相同的7,8,3,4 ，3,6和8个节点分别具有社区中心性。只有所提出的方法，DC和LR具有良好的性能来识别网络科学网络中的有影响的节点。同时，从表一中可以看出，局部措施和全局措施的结果差异很大；因此非常需要局部和全局综合方法。lt;

资料编号：[5408]