姚月娇 刘 向 余博文

(华中师范大学信息管理学院，湖北 武汉 430079)

面对现实生活中存在的舆论传播[1]、疫情防控[2]、交通调度[3]等重要问题，可以将其抽象为复杂网络进行分析，找到高影响力的因素是解决问题的关键环节。学者们基于不同的情境和理论提出了多种衡量节点影响力的算法，其中基于特征向量的方法同时考虑了相邻节点的数量和质量，例如特征向量中心性算法、PageRank算法、LeaderRank算法、Hits算法等。

PageRank算法由Sergey和Lawrence提出，是目前最经典的排序算法之一。为了增强PageRank算法的适用性，姜帆[4]采用PageRank算法与引文分析方法考察了经济管理学领域的44项国际学术奖项的中心性影响力与文献影响力；张欣等[5]结合专利的被引次数和年龄得到了PatentRank算法；霍朝光等[6]利用PagaRank算法进行国际深度学习领域研究热点文献排序，强调全部关键词共词网络的重要性；戴炳荣等[7]将公证人评价机制与PageRank算法相融合，提出跨链公证人机制评价模型。也有一些学者从原理层面对PageRank算法进行了改进：LeaderRank算法[8]将跳转概率转化为背景节点，更加灵活地解决了悬挂节点的问题；臧思思等[9]在考虑时间异质性后得到了T-PR算法并用于评价作者的学术影响力；张宪立等[10]根据反向PageRank思想和度中心性来评估节点影响力，形成启发式算法MPRD；臧志栋等[11]融入时间异质性因子，构建了基于PageRank算法的被引时间影响因子，并以图书情报领域的44种期刊为例进行实证研究。

尽管改进PageRank算法的研究已经不胜枚举，但是考虑弱连接的研究不多。在度量强弱连接的研究中，Arthur A等[12]提出了IOS量表、Dibble J L等[13]提出了单维关系紧密度尺度(URCS)，均通过人的主观意识来判断连接强度；岳增慧等[14]将节点之间的连边权重作为连接强度，但是没有给出区分强弱的依据；Krämer N C等[15]采用定性与定量相结合的方法，通过交互参数、感知到的社会支持等指标来综合衡量连接强度，并提出连接强度应该是一个连续变量，而非二分变量。Liu Z等[16]提出，相似性是节点相互作用的依据，可以度量关系紧密程度。在此基础上，Zhang Y等[17]利用关系强度挖掘高影响力节点，认为关系越紧密则影响力越大。但根据Mark S G提出的弱连接理论[18]，不仅是联系紧密的节点，联系疏远的节点也会对彼此产生一定的作用。基于此，本研究在PageRank的基础上，根据节点相似性和弱连接理论重新构建了节点间相互影响的关系，得到了模型TransRank。通过在推特网络、引文网络、比特币网络和发明者网络中进行SI传染实验，检验新模型的优化效果。

1 节点影响力模型

1.1 PageRank算法

PageRank算法认为万维网中一个页面的重要性取决于指向它的其他页面的数量和质量，被很多高质量页面指向的页面也会有很高的质量。算法初始，赋予网络中每个节点相同的PR值，并且和为1；在每次迭代时，节点需要把当前的PR值平分给指向的节点，新PR值是其收到的PR值之和；当所有节点的PR值不再变化时停止迭代。

对于网络中出度为0的节点(称为悬挂节点)，它的PR值会随着每次迭代不断增长。为解决这个问题，引入一个随机跳转概率c，即在迭代过程中每个节点的PR值都将以(1-c)的概率均分给网络中所有节点，以c的概率均分给它指向的节点。节点i在t时刻的PR值为：

(1)

PageRank算法中的节点会将自己的值平均分配给其指向的节点，但是不同节点对同一节点的影响力是有差异的，同一节点对不同节点的影响程度也有高低之分，所以平均分值的传值方法不能真实反映节点之间的影响关系，由此计算出的节点PR值也不能准确表示节点在网络中的影响力。

1.2 弱连接的影响

Hansen M T[19]将组织中密切、频繁的直接联系称为强连接，疏远、不频繁的直接联系称为弱连接。1973年，Mark S G提出了弱连接理论[18]，强调弱连接可以帮助人们在社会网络中获得重复率低、价值性高的信息，进而扩大信息交流的范围。Abbasi A等[20]发现，弱连接可以促使节点与不同类群中的节点建立更为广泛的关联；牌艳欣等[21]根据引文之间的弱关系构建网络，在此基础上识别出的跨学科相关知识组合在指导跨学科合作上具有一定的意义。

弱连接理论可以应用到复杂网络中计算节点之间的影响力。将两个节点之间的联系程度定义为连接强度，用Rij表示；将两个节点对彼此的影响力定义为影响强度，用Eij表示。研究认为，若节点j与节点i相连，那么随着它们的连接强度逐渐增强，虽然相互作用的频次和强度有所提高，但它们之间的异质性会随之降低，所以它们对彼此的影响强度会逐渐减弱；之后随着两个节点之间的连接强度继续加强，相互作用的频次和强度大幅提升，对彼此的影响强度会不断增强。

1.3 TransRank算法

TransRank算法是本研究提出的用于衡量节点影响力的新模型，在PageRank算法的基础上改善了传值规则，可以抽象为网络中各节点互相传值的过程，于是取“传递”的英文“Transmit”来命名新算法。在TransRank算法初始，赋予网络中每个节点均等的初始TR值，且和为1。然后，根据Liu Z等[16]的研究，计算每两个节点的共同邻居在它们所有邻居中的比例，即节点相似性，以此判断节点之间的关系是否紧密[22]，本研究将该比例值对应为连接强度Rij，公式如下：

(2)

其中，m为节点i的邻居数量，n为节点j的邻居数量，k为节点i和j的共同邻居数量。

之后，根据弱连接理论，影响强度Eij会随着连接强度Rij变化而变化，过程类似于倒置的抛物线[23]，可以用以下函数来拟合：

(3)

其中0

最后，为了防止悬挂节点不断接收其他节点的值，每个节点以c的概率根据影响强度的比例将TR值分配给它指向的节点，以(1-c)的概率均分给网络中所有节点。当所有节点的TR值都不再变动时迭代停止，最终节点的TR值越大，说明节点在网络中影响力越大。节点i在t时刻的TR值为：

(4)

其中，OUTj为节点j的后向节点集，INi为节点i的前向节点集。

1.4 TransRank算法收敛性

1)设T是一个n×n的矩阵，其中：

(5)

2)设R是一个包含着n个元素的向量，对应着每个节点的TR值，其中：

‖R‖=1

(6)

3)算法迭代过程如下：

(7)

其中，e的长度为n、元素都是1的列向量。

4)算法迭代终止条件为：

(8)

5)令：

(9)

无论网络连通性如何，T′都是一个正矩阵。根据Perron-Frobenius定理，可以得到：

a.矩阵T′的最大特征值为正实数特征值λ，其绝对值是所有特征值中最大的。

b.与正实数特征值λ对应的特征向量的元素均为正。

c.矩阵T是行随机矩阵，所以矩阵R*也是行随机矩阵，故存在λ=1，对应的向量为e，即对于任意非零和非负的单位初始向量，都可以收敛到R*(此时R*=e)。

2 实 验

2.1 数 据

本研究的实验对象是4个真实网络数据[24]。其一，Twitter是一个在线社交平台，用户可以发表推文，也可以对其他用户的推文进行评论或者转发。本研究截取部分推特用户之间的转发关系，构成了推特网络，其中推文被转发的数量是用户影响力的一种表现。其二，ArXiv是由康奈尔大学运营维护的一个非盈利的数据库，学术研究人员可以将自己最新的研究成果发布到该平台上，其中论文之间的引用可以看作是研究影响力的扩散。本研究使用1993年1月至2003年4月发表在ArXiv的有关高能物理理论的文章，并通过引用关系构建了引文网络。其三，Bitcoin-OTC是人们进行比特币场外交易的线上市场，其中的用户都是匿名的，为了维护交易秩序，用户需要在每次交易完成后为彼此评分，被多次评分的用户活动广泛，会在市场中产生一定程度的影响。本研究选择了一些匿名用户及其评论关系，构成了比特币网络。其四，美国专利数据库收录了1790年至今的美国专利全文，本研究提取了化学领域1978—2002年的专利数据，根据专利发明者之间的引用关系构建了发明者网络。

各个网络的特征如表1所示，它们的数据规模和平均度、最大度和平均聚类系数等网络特征均有较大的差异，具有一定的代表性。

表1 实验网络数据特征

2.2 实验过程

本研究根据式(4)与(1)计算出了每个实验网络中各节点的TR值和PR值，值越大表明节点的影响力越大。在每个实验网络中，分别按照TR值和PR值由大到小排列所有节点，排名较前的节点被视为对应算法识别出的高影响力节点。

为了检验TransRank算法识别出的高影响力节点是否具有更高的影响水平，本研究选择SI模型，每个节点只会保持易染态或者从易染态转变为感染态。将识别出的高影响力节点作为初始感染节点，根据一定的感染率开始传染进程，感染节点会逐渐增多并达到稳定，感染的速度和范围可以体现出算法的优劣。具体实验过程如下：

实验初始，设定SI的模型两个参数，感染率p和初始感染范围α。感染率p可以代表不同的影响情境，比如不同的疾病传染力大小；初始感染范围α可以表示影响力的不同等级，α的值越小，说明节点的排名越靠前，在网络中的影响力就越大。

其次，确定初始感染节点集。先提取出两种算法排序结果中前α的节点集P和T，再剔除重复节点，得到初始感染节点集P′和T′。

再次，比较传染进程。设定两个算法的跳转概率c为0.85，SI模型的感染率p=0.2、初始感染范围α=2%，结果如图1所示。

最后，观察SI模型参数变化对算法优化效果的影响。定义优化值β来更加直观地反映两个算法感染效果的差距，计算公式如下：

(10)

其中，TI(k)和PI(k)分别表示由初始感染节点集T′和P′在传染到第k代时的感染比例。

检验TransRank算法在不同影响情境中的优化效果时，初始感染范围α控制为2%(比特币网络中控制为3.5%)，感染率p分别取0.1、0.2、0.3、0.4，结果如图2所示；检验TransRank算法在挖掘各级影响力节点的优化效果时，感染率p控制为0.2，初始感染范围α以0.5%为单位从0.5%递增到6%，结果如图3所示。图2、图3中的横坐标为传染代数(iters)，纵坐标为优化值β，不同颜色的线条表示不同的参数取值。

2.3 实验结果

在图1中，TransRank算法对应的曲线始终高于PageRank算法对应的曲线，但在子图B、C、D中，两个算法对应的曲线会达到相同的稳定值。以上说明，TransRank算法在3个真实网络中对应的传染进程均明显快于PageRank算法，在推特网络中的感染范围也大于PageRank算法。

图1 两种算法的传播效果

在图2中，前3个子图里曲线的形态均为先升高再降低最后保持平稳，最后1个子图中的曲线一直升高最后保持平稳，取值均不小于0。这说明在不同的网络中，基于不同的感染率，TransRank算法的传染速度都优于PageRank算法，最终感染范围也不会劣于PageRank算法。

图2 不同感染率下两种算法的传播效果

在图3中，每一列图像代表1个网络的全部实验数据，其中绝大多数的曲线分布在0值以上。说明在不同的网络中，基于不同的初始感染比例，TransRank算法的传染速度很大概率优于PageRank算法，最终感染范围很少会劣于PageRank算法。

综上所述，TransRank算法具有明显的优化效果，但是会受到SI模型参数变化的影响。

3 讨 论

3.1 高影响力节点

根据TransRank算法和PageRank算法计算出实验网络中每个节点的TR值和PR值后，按照大小顺序进行排列。由于网络中节点数量巨大，为便于比较，不妨选择排名前2%的节点作为高影响力节点。推特网络中，共有467个高影响力节点，剔除相同节点后，两种算法各剩余31个节点，如表2所示；引文网络中，共有555个高影响力节点，剔除相同节点后，两种算法各剩余9个节点，如表3所示；比特币网络中，共有117个高影响力节点，剔除相同节点后，两种算法各剩余1个节点，如表4所示；发明者网络中，共有162个高影响力节点，剔除相同节点后，两种算法各剩余1个节点，如表5所示。

表2 推特网络中的高影响力节点

表3 TransRank算法在引文网络中识别的高影响力节点

表3(续)

表4 TransRank算法在比特币网络中识别的高影响力节点

表5 TransRank算法在发明者网络中识别的高影响力节点

在推特网络和发明者网络中，TransRank算法识别的高影响力节点集在入度和聚类系数方面平均值较低，在出度方面平均值较高，说明这些节点更擅长面向多类节点传播自身影响力。TransRank算法在引文网络中识别的高影响力节点集有更高的入度平均值和出度平均值，其聚类系数平均值略低于PageRank算法识别的高影响力节点集，表明这些节点不仅会受很多节点影响，还会将自身影响辐射到周围许多节点。在比特币网络中，TransRank算法识别的高影响力节点在聚类系数、入度和出度方面均有更高取值，从而有更多样的影响对象。综上，TransRank算法识别的高影响力节点有更为广泛的影响覆盖面。研究还选择了5%和10%的比例进行分析，结果和结论没有改变。

具体来看，以发明者网络为例，TransRank算法识别的高影响力节点为发明者、澳大利亚科学家巴里·马歇尔，与罗宾·沃伦一同发现了幽门螺杆菌以及这种细菌在胃炎和胃溃疡等疾病中的作用，被授予2005年诺贝尔生理学或医学奖。1978—2002年，巴里·马歇尔在化学领域共申请成功了7项专利，均有关于肠胃内的微生物和分泌物。由于他没有较高的被引量和施引量，所以被PageRank算法识别为边缘节点。但是根据TransRank算法，巴里·马歇尔被标记为高影响力节点，体现出了他在该领域的重要地位。

3.2 不同影响情境

图2代表着在4个网络中不同感染率下TransRank算法的优化效果，每个图像中的4个曲线表示不同的感染率，取值越大则表示TransRank算法越有利于影响力传播。图2A和2D中曲线的取值始终大于0，说明对于不同的影响情境，TransRank算法在推特网络中识别出的高影响力节点既有较快的影响速度，又有较大的影响范围。在图2B和2C中，曲线在前期均高于0，在后期平稳时取值为0，说明在引文网络和比特币网络中，TransRank算法识别出的高影响力节点拥有更快的影响速度。

在所有实验网络中，TransRank算法识别的高影响力节点均有更快的影响速度，可以迅速发挥自身影响力；同时，这些节点的影响范围不会低于PageRank算法识别出的节点，可以将影响力扩散到与PageRank算法相同甚至更广泛的区域。综上，不论环境是否有利于影响力传播，TransRank算法的优化效果都很明显。

3.3 不同影响等级

图3比较了TransRank算法在4个网络中不同初始感染比例下的优化效果，每个网络都包含12条曲线，每条曲线对应一个初始感染比例α，比例越小则选出的节点影响力越大。

在推特网络中，当α等于0.5%和2.5%时，曲线会上升并在最高点保持平稳；当α等于1%、2%、3.5%和6%时，曲线会有少许的上下波动，以上6种初始感染比例对应的优化值都始终大于0，说明TransRank算法在速度和范围上均优于PageRank算法。当α等于3%时，曲线先上升后下降，最后在0值保持平稳，说明两算法的最终感染范围相同但TransRank算法的感染进程更快；当α取其他值时，曲线会下降并在最低点保持平稳，并且大部分处于0值以下，说明TransRank算法在速度和范围上均比PageRank算法差。由上可知，在多数初始感染比例下，TransRank算法在推特网络中识别的节点会有更好的影响效果。

在引文网络中，当α等于1.5%、2%、2.5%、4.5%和5.5%时，曲线会先上升后下降，最后在0值处保持平稳，说明TransRank算法的传染速度更快，但两种算法的感染范围一致；α等于3%、3.5%、4%、5%和6%时，曲线大致是先下降后上升最后在0值处保持平稳，说明PageRank算法的传染速度更快，而两种算法的感染范围相同；当α取其他值时，曲线会下降并在最低点保持平稳，说明TransRank算法在速度和范围上都较差。对于大多数的初始感染比例，两个算法在引文网络识别的节点的影响范围一致，其中半数情况下TransRank算法识别的节点有更快的影响速度。

在比特币网络中，当α为0.5%、1%、2%、2.5%、3%和4.5%时，两个算法识别出的节点完全一致，所以没有对应的曲线；当α为1.5%、3.5%、4%、5%和6%时，曲线会先上升后下降，最后在0值处保持平稳，说明TransRank算法的传染速度更快，两种算法的感染范围相同；当α为5.5%时，曲线先下降后上升，最后在0值处保持平稳，说明PageRank算法的传染速度更快，两种算法的感染范围相同。由此可知，在比特币网络中，在半数情况下，两个算法识别节点的影响效果一致；在部分情况下，TransRank算法识别的节点会在影响速度上表现更好。

在发明者网络中，当α为0.5%、2%、2.5%、3%、4%和5.5%时，两个算法识别出的节点完全一致，所以没有对应的曲线；当α为1%时，曲线先上升，然后在最高点保持平稳，说明TransRank算法的传染速度更快、感染范围更广；当α为1.5%、3.5%时，曲线一直贴合于0值，说明两个算法效果相当；当α为5%时，曲线先下降后，稍微回升，最后在0值处保持平稳，说明TransRank算法的传染速度更快，两种算法的感染范围相同；当α为4.5%和6%时，曲线会先在0值下起伏，最后在0值处保持平稳，说明PageRank算法的传染速度更快，两种算法的感染范围相同。由此可知，在发明者网络中，在多数情况下，两个算法识别节点的影响效果一致；在部分情况下，TransRank算法识别的节点会在影响速度上表现更好。

表6汇总了在4个网络中不同初始感染比例下TransRank算法的优化效果，从中可以清晰看到，当选择排名前2%或者2.5%的节点时，TransRank算法的优势会稳定地体现出来；在选择其他α值时，TransRank算法也只会在部分实验网络中表现较差，大多数情况下都会在影响速度上优于PageRank算法。

表6 不同网络中在不同初始感染比例下的优化效果

相对于其他网络，引文网络的优化效果较差，可能是因为引文网络的平均度更大，节点之间的联系更加密集和频繁，弱连接的比例较低。推特网络的优化效果最好，原因可能是该网络聚类系数较低，节点较为分散，主要是通过弱连接进行联系。

3.4 弱连接的作用

实验显示TransRank算法的影响效果普遍较好，那么这是不是弱连接发挥的作用呢？为验证此想法，将节点集T′和指向它的节点集toT′都提取出来，计算弱连接连边对识别重要节点的贡献率γ(连接强度为0的连边集传给节点i的值占节点i接收总值的比例)，结果如表7所示。

表7 不同网络中弱连接对两种算法贡献率的比较

在4个实验网络中，节点集T'和toT′之间的弱连接均占有很高的比例，是节点接收值的主要途径。同时，相较于PageRank算法，TransRank算法会赋予节点集中绝大部分节点更大的值，并且经由弱连接接收到的值更大、贡献率更高。以上说明，弱连接确实在识别重要节点时发挥了很大的作用，帮助改善了算法的准确性和有效性。

4 结 语

本研究根据弱连接理论提出了新的节点影响力模型TransRank算法。新算法识别出的高影响力节点会将影响力扩展到更广的范围中，通过在推特网络、引文网络、比特币网络、发明者网络4个真实网络中进行SI传播实验，发现新算法可以有效地改善影响速度，即在同样的时间里基于相同影响力的节点群开展感染进程，TransRank算法影响到的节点数量更多。同时，新算法也有可能扩大影响范围，即从相同影响力的节点群开展感染进程，TransRank算法影响到的节点数量更多。在此基础上，不论所处的情境是否有利于影响力的传播，TransRank算法的优化效果都不会改变；对于不同影响等级的节点集，TransRank算法大概率会优于PageRank算法，其中当初始感染比例为2%和2.5%时，优化效果会更加明显和稳定。

目前，本研究还存在以下不足：首先，只是在无权有向网络中进行了算法检验并得到了较好的结果，还需要在加权网络和无向网络中开展实验，验证TransRank算法的普适性；其次，只考虑了在静态网络中挖掘高影响力节点，忽视了节点影响力的动态变化。在未来的工作中，将继续考察TransRank算法在不同类型网络中的表现，并探索节点影响力的演化轨迹，继续完善模型以识别出动态更新的高影响力节点集。