弱连接视角下的高影响力节点识别

来源:用户上传      作者:姚月娇　刘向　余博文

　　摘要：[目的/意义]PageRank是被普遍接受并广泛使用的排序算法，通过在节点之间传递PR值识别网络中的重要节点。针对PageRank算法对节点间连接强度和影响强度的忽视问题，提出TransRank算法以更有效地挖掘高影响力节点。[方法/过程]TransRank算法利用节点相似性度量连接强度，再基于弱连接理论拟合连接强度和影响强度的关系，并将影响强度作为传值依据。[结果/结论]通过在3个现实网络中进行SI传染实验，检验TransRank算法的优化效果，结果显示TransRank算法挖掘出的高影响力节点在影响速度上始终优于PageRank算法，在影响范围上有很大可能优于PageRank算法。
　　关键词：弱连接;节点相似性;连接强度;影响强度;节点影响力
　　DOI：10.3969/j.issn.1008-0821.2022.09.006
　　〔中图分类号〕G250.252〔文献标识码〕A〔文章编号〕1008-0821（2022）09-0058-10
　　High-influence Node Recognition from the Perspective of Weak TiesYao YuejiaoLiu Xiang Yu Bowen
　　（School of Information Management，Central China Normal University，Wuhan 430079，China）
　　Abstract：[Purpose/Significance]PageRank is a generally accepted and widely used ranking algorithm，which identifies important nodes in the network by passing PR values between nodes.Aiming at the problem of the PageRank algorithm's neglect of the connection strength and influence strength between nodes，the TransRank algorithm is proposed to mine high-impact nodes more effectively.[Method/Process]The TransRank algorithm used node similarity to measure the connection strength，and then matched the relationship between the connection strength and the influence strength based on the weak tie theory，and used the influence strength as the basis for value transmission.[Result/Conclusion]Through SI infection experiments in three real networks，the optimization effect of the TransRank algorithm is tested.The results show that the high-impact nodes mined by the TransRank algorithm are always better than the PageRank algorithm in terms of impact speed，and are likely to be better than the PageRank algorithm in terms of impact range.
　　Key words：weak ties;node similarity;connection strength;influence strength;node influence
　　面ο质瞪活中存在的舆论传播[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]将节点之间的连边权重作为连接强度，但是没有给出区分强弱的依据;Krmer N C等[15]采用定性与定量相结合的方法，通过交互参数、感知到的社会支持等指标来综合衡量连接强度，并提出连接强度应该是一个连续变量，而非二分变量。Liu Z等[16]提出，相似性是节点相互作用的依据，可以度量关系紧密程度。在此基础上，Zhang Y等[17]利用关系强度挖掘高影响力节点，认为关系越紧密则影响力越大。但根据Mark S G提出的弱连接理论[18]，不仅是联系紧密的节点，联系疏远的节点也会对彼此产生一定的作用。基于此，本研究在PageRank的基础上，根据节点相似性和弱连接理论重新构建了节点间相互影响的关系，得到了模型TransRank。通过在推特网络、引文网络、比特币网络和发明者网络中进行SI传染实验，检验新模型的优化效果。

nlc202209161500

ij表示;将两个节点对彼此的影响力定义为影响强度，用Eij表示。研究认为，若节点j与节点i相连，那么随着它们的连接强度逐渐增强，虽然相互作用的频次和强度有所提高，但它们之间的异质性会随之降低，所以它们对彼此的影响强度会逐渐减弱;之后随着两个节点之间的连接强度继续加强，相互作用的频次和强度大幅提升，对彼此的影响强度会不断增强。
　　1.3TransRank算法
　　1.4TransRank算法收敛性
　　2实验
　　2.1数据
　　2.2实验过程
　　2.3实验结果
　　3讨论
　　3.1高影响力节点
　　根据TransRank算法和PageRank算法计算出实验网络中每个节点的TR值和PR值后，按照大小顺序进行排列。由于网络中节点数量巨大，为便于比较，不妨选择排名前2%的节点作为高影响力节点。推特网络中，共有467个高影响力节点，剔除相同节点后，两种算法各剩余31个节点，如表2所示;引文网络中，共有555个高影响力节点，剔除相同节点后，两种算法各剩余9个节点，如表3所示;比特币网络中，共有117个高影响力节点，剔除相同节点后，两种算法各剩余1个节点，如表4所示;发明者网络中，共有162个高影响力节点，剔除相同节点后，两种算法各剩余1个节点，如表5所示。
　　在推特网络和发明者网络中，TransRank算法识别的高影响力节点集在入度和聚类系数方面平均值较低，在出度方面平均值较高，说明这些节点更擅长面向多类节点传播自身影响力。TransRank算法在引文网络中识别的高影响力节点集有更高的入度平均值和出度平均值，其聚类系数平均值略低于PageRank算法识别的高影响力节点集，表明这些节点不仅会受很多节点影响，还会将自身影响辐射到周围许多节点。在比特币网络中，TransRank算法识别的高影响力节点在聚类系数、入度和出度方面均有更高取值，从而有更多样的影响对象。综上，TransRank算法识别的高影响力节点有更为广泛的影响覆盖面。研究还选择了5%和10%的比例进行分析，结果和结论没有改变。
　　具体来看，以发明者网络为例，TransRank算法识别的高影响力节点为发明者、澳大利亚科学家巴里・马歇尔，与罗宾・沃伦一同发现了幽门螺杆菌以及这种细菌在胃炎和胃溃疡等疾病中的作用，被授予2005年诺贝尔生理学或医学奖。1978―2002年，巴里・马歇尔在化学领域共申请成功了7项专利，均有关于肠胃内的微生物和分泌物。由于他没有较高的被引量和施引量，所以被PageRank算法识图2不同感染率下两种算法的传播效果
　　别为边缘节点。但是根据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条曲线，每条曲线对应一个初始感染比例α，比例越小则选出的节点影响力越大。

nlc202209161500

转载注明来源:https://www.xzbu.com/4/view-15439821.htm