张国防　徐建民

关键词： 社交网络； 信息传播； 积极交互作用； 节点影响力

ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１００８－０８２１．２０２３．０５．００９

〔中图分类号〕Ｇ２０６ 〔文献标识码〕Ａ 〔文章编号〕１００８－０８２１ （２０２３） ０５－００９０－１４

２０２２年政府工作报告中关于加强和创新互联网内容建设， 深化网络生态治理的相关内容， 充分表明弘扬正能量、处置违法、抑制虚假和恶意等不良信息的必要性和迫切性。开放、易用、时效性强的社交网络在为用户提供信息、共享便利的同时， 也滋生并传播了大量虚假信息， 在政治、经济、心理学等方面给个人甚至整个社会带来深远的负面影响，且不益于网络信息内容的生态治理［１］ 。因此， 如何识别社交网络中的高影响力节点， 从而抑制虚假信息的传播， 已成为网络信息生态治理中需要解决的一个重要问题。且随着社交网络在人们获取信息、共享便利过程中发挥的优势越来越大， 研究社交网络信息传播机制， 挖掘网络中的高影响力节点， 对管控网络信息传播、深化网络信息生态治理有重要意义。

在度量网络用户节点影响力并进行排序时， 研究者们通常将现实的社交网络抽象为无向图或有向图， 网络用户对应图中的节点， 而用户间的各种关系借助图中相应节点间的连边加以表示， 进而基于网络的拓扑结构， 对用户节点的影响力进行分析研究。而在现实社交网络中的节点通常为具有社会属性的人， 所以在影响或激活节点的过程中， 其多个入邻居之间通常情况下不是相互独立的。一种模式是入邻居之间相互促进， 积极合作， 共同影响目标节点， 称之为积极交互作用； 另一种模式则相反，入邻居间矛盾重重， 相互制约， 在影响目标节点时呈现出消极交互作用。本文将节点之间进行积极或消极合作所表现出来的影响效应视为节点间的交互作用。如节点Ｃ 有Ａ 和Ｂ 两个入邻居节点， 对Ｃ的影响权重（或者理解为关系强度）分别为０.５ 和０.３， 如图１（ａ）所示。从网络拓扑结构来看， 节点Ａ 和Ｂ 之间存在着某种耦合关系。另外， 从用户群体心理角度出发， 同时考虑到在实际的社交网络中Ａ 和Ｂ 之间可能存有连边的情况， Ａ 和Ｂ 两者可能具有交互关系， 或者是相互促进的积极合作关系，或者是相互制约的消极合作关系。也就是说Ａ 和Ｂ被激活或被影响后， Ｃ节点被激活应该是Ａ 单向影响、Ｂ 单向影响、Ａ与Ｂ交互合作影响３种模式综合作用的结果。图１（ｃ）表示Ａ 和Ｂ 之间具有积极交互作用， 图１（ｄ）表示Ａ 和Ｂ 之间具有消极交互作用， 而图１（ｂ）表示Ａ 和Ｂ 之间是相互独立的。

在进行多属性决策时通常会考虑属性间的交互作用， 因为各属性之间通常存在关联， 而这种关联对决策的影响不可以忽略， 且交互模式也是制定最终决策需要考虑的重要因素之一［２－３］ 。近年来， 从多属性决策视角进行网络节点影响力排序的相关研究相继展开［４－５］ ， 因此， 正如在解决多属性决策问题时不可以忽略属性间的交互作用对决策的影响，在进行社交网络节点影响力的排序时也不能不考虑节点入邻居间的交互作用对该节点影响力以及活跃性的影响。

综上， 网络节点间的交互性以及交互作用模式（积极或消极）在有向加权社交网络中起着重要作用， 因此， 要想扩大信息在网络中的传播范围， 或对网络节点影响力进行排序， 需要考虑到相应节点间的交互作用。本文在深入分析节点间交互模式对社交网络信息传播具有重要影响的基础上， 面向有向加权网络充分挖掘积极交互作用并加以利用， 提出一种新的网络节点影响力排序方法， 从扩大信息传播范圍的角度验证了方法的有效性。

１相关研究

目前对网络节点影响力进行排序的相关研究主要基于局部属性、社团关系、全局属性和随机游走４ 个视角来展开。

１.１基于局部属性的节点影响力排序

基于局部属性的网络节点影响力排序研究以度中心性（Ｄｅｇｒｅｅ Ｃｅｎｔｒａｌｉｔｙ） 分析最为常见［６］ ， 该方法以节点的邻居数量为主要考量指标， 反映相应节点的直接影响程度， 但其局限性在于未考虑用户在网络中的位置［７］ 。Ｃｈｅｎ Ｄ Ｂ 等［８］ 综合节点及其邻居的度信息， 通过局部中心性（Ｌｏｃａｌ Ｃｅｎｔｒａｌｉｔｙ）指标度量节点的局部影响力， 之后考虑到节点邻居间的拓扑结构的重要性， 提出了融合度和聚类系数的节点影响力排序方法， 发现即使在两节点的度相同情况下， 相应节点的影响力关于聚类系数递减［９］ 。包括后续围绕度中心性和聚类系数等网络结构特征进行的影响力分析研究着眼于网络的局部属性以及用户节点的内部属性， 然而节点的传播能力易受其所在社区的规模及社区内节点间紧密度的影响［１０］ 。因此， 从社区关系角度出发， 展开网络用户节点影响力度量及排序的研究引起了相关学者的注意。

１.２基于社团关系的节点影响力排序

此类研究主要依据弱连接经典理论， 聚焦于网络用户及其邻居所在社区的拓扑结构特征， 探讨用户节点的信息传播能力。如Ｚｈａｏ Ｚ Ｙ 等［１１］ 采用社区发现方法将社交网络进行适当划分， 结合已有影响力排序指标， 考虑节点所连接的社区数量， 提出量化节点影响力的Ｖ_ｃ指标。此外， 基于结构洞理论， Ｓｕ Ｘ Ｐ 等［１２］ 深入分析了网络用户节点所在社区的中心性以及“桥接” 不同社区的连通性， 提出了Ｎ－Ｂｕｒｔ 网络用户节点影响力排序模型； Ｈａｎ Ｚ Ｍ等［１３］ 利用结构洞节点在连接不同社区、加速信息扩散方面的优势， 融合多种度量指标， 提出基于ＬｉｓｔＮｅｔ 的节点影响力排序方法， 取得了较好的效果。基于社区关系的节点影响力排序方法着重考虑了网络用户节点的邻居以及社区性， 能够充分揭示个体和群体间的影响程度， 但排序结果易受社区发现算法影响， 因此， 若社交网络的社区结构不明显， 则排序结果不理想。

１.３基于全局属性的节点影响力排序

相对于局部属性或社区关系视角下的节点影响力排序方法， 基于全局属性的排序方法着重考虑用户节点在网络中的全局信息， 能够充分揭示节点的拓扑特征， 但因时间复杂度较高而只适用于规模不大的社交网络。其中较为常用的除了传统的介数中心性、紧密度中心性、特征向量中心性和Ｋａｔｚ 中心性外， 基于Ｋ－ｓｈｅｌｌ 分解的节点影响力排序方法近年来受到关注［１４］ 。如Ｌｉｕ Ｙ 等［１５］ 利用Ｋ－核分解挖掘并深入分析真实社交网络中的核心结构， 剖析网络中“伪核心” 的存在原因， 度量局部小团体的信息量， 提出基于网络连接熵的节点影响力排序方法。另外， Ｌü Ｌ 等［１６］ 考虑到Ｈ 指数作为学者或期刊影响力的重要评价指标， 也是从节点的全局属性角度量化其影响力， 将其引入社交网络用于节点影响力排序， 在证明了Ｈ 指数与Ｋ 核数之间关联性基础上， 指出了Ｈ 指数在社交网络节点影响力排序方面的优势。

１.４基于随机游走的节点影响力排序

上述３ 类节点影响力排序方法是一种确定性排序方法， 而基于随机游走的排序方法则是以概率统计为理论基础， 围绕网络拓扑结构展开节点影响力排序的不确定性方法， 其中典型方法包括ＰａｇｅＲ?ａｎｋ、ＨＩＴＳ、ＬｅａｄｅｒＲａｎｋ 以及基于此３ 类算法的改进方法［１４］ 。如阚长江等［１７］ 深入分析网络中互惠边对信息传播速度和规模的影响， 结合ＰａｇｅＲａｎｋ 和ＬｅａｄｅｒＲａｎｋ 的优缺点， 提出了基于节点互惠边的随机游走算法， 对微博网络中节点的影响力进行排序，在关键节点识别方面优于ＰａｇｅＲａｎｋ 和ＬｅａｄｅｒＲａｎｋ算法； 顾洁等［１８］ 考虑到社交网络中普遍存在正负两面的链接性， 将ＰａｇｅＲａｎｋ 算法推广到符号社交网络， 从正负两个角度对节点影响力进行排序， 结果符合符号网络中正负关系的特性； 董伟等［１９］ 结合ＳＶＭ 算法， 基于用户交互和评论情感信息， 对Ｐａｇ?ｅＲａｎｋ 算法进行改进， 提出用于在线健康社区用户影响力的排序方法； Ｚｈａｎｇ Ｐ 等［２０］ 通过引入调剂用户节点间链接边权重和相应节点度的参变量， 将ＰａｇｅＲａｎｋ 算法推广到有向加权社交网络环境中， 提出了一种高效的迭代算法以适应大规模网络； Ｌｉ Ｑ等［２１］ 考虑到ＬｅａｄｅｒＲａｎｋ 算法收敛速度快、有较强的抗攻击性、对噪声数据的低敏感性和最具影响力节点精准识别能力， 基于网络节点的入度对背景节点的出度进行加权， 进而改进ＬｅａｄｅｒＲａｎｋ 算法， 提出优于ＬｅａｄｅｒＲａｎｋ 算法的节点影响力排序方法。

上述方法主要基于网络的拓扑结构对节点影响力进行排序， 未考虑节点之间的交互作用对其邻居活跃性的影响， 这里节点间交互作用可以简单认为是在激活其邻居节点、传递影响力、扩大信息传播范围过程中， 节点之间进行积极或消极合作所表现出来的影响效应。本文在现有研究的基础上， 基于网络节点间交互模式对社交网络信息传播规模的影响， 提出一种充分利用用户节点间积极交互作用的网络信息传播模型， 探讨积极交互模式在网络信息传播中的作用； 考虑节点间积极交互可以影响其邻居节点的活跃性， 提出一种最大化节点间积极交互作用的随机游走算法， 用于识别社交网络中的高影响力节点。

２考虑积极交互作用的网络信息传播机制研究

图３从新增被激活总数角度可视化不同信息传播模型下信息的传播规模， 而图４ 则从单位时间新增被激活节点数视角揭示不同信息传播模型下信息的传播速度， 继而可以看出信息传播的周期性。从两图可以看出， 在所构建的不同网络中， 基于积极交互作用最大化的信息传播模型表现出较大的信息传播规模， 究其原因主要是充分挖掘了网络用户节点入邻居之间的积极交互作用， 增大了节点的激活函数值。这与理论证明的结果相吻合， 即基于积极交互作用最大化的信息传播模型下成功激活网络节点的概率大于或等于线性阈值信息传播模型和独立级联信息传播模型下成功激活节点的概率， 且在线性阈值信息传播模型和独立级联信息传播模型下最终被激活的节点个数为基于积极交互作用最大化的信息传播模型下最终被激活的节点个数的下界。这样的结果也表明， 节点间的积极交互在社交网络信息传播中发挥着重要的作用， 在信息传播中充分挖掘并利用节点间的积极交互作用， 将有利于信息的更广传播。即使信息本身的吸引力较弱， 如果能很好地发挥节点间的积极交互作用， 也可以扩大信息在网络中的传播规模。因而， 在利用免疫信息对网络虚假信息进行传播抑制时， 若希望免疫信息得到广泛的传播， 除了信息本身的價值外， 在组织免疫信息时也需使免疫信息尽量引起节点间的积极交互， 充分考虑节点间的积极交互作用。而在实际的社交网络中， 由于共同兴趣或其他的同质性特征，影响同一节点多个节点（即使是虚拟用户节点）之间也存在交互现象， 因此， 相比独立级联和线性阈值信息传播模型， 基于最大化积极交互作用的信息传播模型更能真实地反映网络信息传播机制。

４.３新排序算法有效性分析

为了说明新的节点影响力排序算法在识别高影响力节点方面的有效性， 本文针对有向加权网络，将ＩｎｔｅｒａｃｔｉｖｉｔｙＲａｎｋ 算法与加权入度中心性算法［２０］ 、加权ＰａｇｅＲａｎｋ 算法和加权ＬｅａｄｅｒＲａｎｋ 算法进行比较。显然， 若节点在某种算法下的排序值越大， 则其影响力越大， 排序越靠前。因此， 节点排序值与其实际的影响力传播规模正相关性越强， 算法的有效性越好。考虑到边缘节点可能会影响算法排序的有效性， 实验的研究对象限定为加权入度值排序靠前的ｎ 个节点。本文就网络１ ～ ４， 通过Ｋｅｎｄａｌｌｓｔａｕ 方法计算了ＩｎｔｅｒａｃｔｉｖｉｔｙＲａｎｋ 算法与加权入度中心性算法、加权ＰａｇｅＲａｎｋ 算法和加权ＬｅａｄｅｒＲａｎｋ算法排序结果的相关性， 分别简记为ＩＲ－ＷＫ、ＩＲＷＰＲ和ＩＲ－ＷＬＲ， 如表４所示。

表４ 中数据显示， ＩｎｔｅｒａｃｔｉｖｉｔｙＲａｎｋ 算法的排序结果均与加权ＰａｇｅＲａｎｋ 算法和加权ＬｅａｄｅｒＲａｎｋ 算法的排序结果具有较强的相关性， 且与加权Ｌｅａｄ?ｅｒＲａｎｋ 算法的排序结果表现出最高的相关性， 超过０ ９５； 相比而言， 与加权入度中心性算法排序结果的相关性较弱， 只达到中等程度。基于此可以得出， 如果加权ＰａｇｅＲａｎｋ 算法和加权ＬｅａｄｅｒＲａｎｋ算法有效， 那么ＩｎｔｅｒａｃｔｉｖｉｔｙＲａｎｋ 算法也是有效的。在识别高影响力节点方面， 已有相关研究表明（加权ＰａｇｅＲａｎｋ 算法和加权ＬｅａｄｅｒＲａｎｋ 算法文献）加权ＰａｇｅＲａｎｋ 算法和加权ＬｅａｄｅｒＲａｎｋ 算法具有较高的效率。

为了进一步比较ＩｎｔｅｒａｃｔｉｖｉｔｙＲａｎｋ 算法、加权ＰａｇｅＲａｎｋ 算法和加权ＬｅａｄｅｒＲａｎｋ 算法的优劣， 运行这３ 个算法， 分别选取３ 个算法中排序值最大的前ｎ（本文ｎ ＝６０）个节点进行比较， 去除同时存在的节点， 将剩余的节点作为种子节点， 基于交互作用最大化的信息传播模型， 获得各种子节点的传播规模， 并依据其平均值来衡量各算法优劣。显然，由排序算法挖掘到的种子节点的平均传播规模越大， 该种子节点的实际影响力就越大。针对ＬＭＮ、ＴＭＮ、ＣＭＮ 和ＦＭＮ ４ 种网络， 由ＩｎｔｅｒａｃｔｉｖｉｔｙＲａｎｋ算法、加权ＬｅａｄｅｒＲａｎｋ 算法和加权ＰａｇｅＲａｎｋ 算法分别获得１０ 个节点， 且均不存在对方排序靠前的６０ 个节点中， 在进行两两比较时， 分别以这１０ 个节点为信息传播的种子节点， 使用本文提出的基于交互作用最大化的信息传播模型重复模拟信息传播过程２０ 次， 获得离散时间点ｔ（ｔ ＝ ０，１，２，…，ｎ）时每次各种子节点的传播规模， 取平均值作为评价算法优劣的标准。在ｎ ＝６０ 的情况下， 各算法的比较结果如图５ 所示（图中横坐标种子个数为不存在于對方排序靠前的６０ 个节点中的节点数）。

从图５ 可以看出， 在４ 种信息传播网络中， 与加权ＰａｇｅＲａｎｋ 算法和加权ＬｅａｄｅｒＲａｎｋ 算法相比，由ＩｎｔｅｒａｃｔｉｖｉｔｙＲａｎｋ 算法所获取的高影响力节点均表现出较大的传播规模， 实现较好的信息传播结果。这也说明， 针对加权ＰａｇｅＲａｎｋ 算法和加权ＬｅａｄｅｒＲａｎｋ 算法难以识别但实际具有较高影响力的节点， ＩｎｔｅｒａｃｔｉｖｉｔｙＲａｎｋ 算法更易赋予较大的排序值， 进而将其作为候选节点被识别出来。

在算法时间复杂度方面， 由于ＩｎｔｅｒａｃｔｉｖｉｔｙＲａｎｋ算法在修改节点随机转移概率时， 需要求解一个优化问题， 其求解复杂度与相应节点的入邻居数量正相关， 因此， 与加权ＰａｇｅＲａｎｋ 算法和加权Ｌｅａｄｅｒ?Ｒａｎｋ 算法相比， ＩｎｔｅｒａｃｔｉｖｉｔｙＲａｎｋ 算法的时间复杂度稍高， 而高出的幅度由求解网络节点所对应优化问题的变量个数决定。因此， 本文所提的Ｉｎｔｅｒａｃ?ｔｉｖｉｔｙＲａｎｋ 节点影响力排序方法更适合网络链接稀疏， 或者链接复杂而不过分追求运行时间的情况。

５结论

本文从网络节点间交互作用的角度对社交网络信息传播机制和节点影响力排序问题进行深入研究， 分析了网络节点间的交互模式， 挖掘并充分利用节点间的积极交互作用， 提出了一种新的信息传播模型（基于积极交互作用最大化的信息传播模型）。在不考虑节点间的交互作用时， 即节点间相互独立的情况下， 新的信息传播模型可退化为线性阈值信息传播模型。考虑到在社交网络中用户节点间的交互作用形成的群体影响力对其邻居节点活跃性的影响， 提出了一种新的识别高影响力节点的随机游走方法（ＩｎｔｅｒａｃｔｉｖｉｔｙＲａｎｋ 节点影响力排序算法）。首先， 基于网络节点的交互作用， 分析了网络信息传播模式， 通过新的信息传播模型探讨了积极交互作用在网络信息传播过程中的作用。结果表明， 节点间的积极交互作用对其邻居的群体影响效应以及信息传播规模均有较大影响， 提高用户节点间的积极交互在信息传播中的作用可以使信息传播范围更广。根据以上的分析结果， 在通过发布免疫信息抑制网络虚假信息时， 即使免疫信息本身的吸引力较低， 但是提高用户节点之间的积极交互能力同样可以使信息的传播范围更广。ＩｎｔｅｒａｃｔｉｖｉｔｙＲａｎｋ算法正是以上述结论为切入点， 在充分考虑用户节点间的积极交互作用并加以利用的基础上所提出的。研究结果表明， ＩｎｔｅｒａｃｔｉｖｉｔｙＲａｎｋ 算法与原有的加权ＰａｇｅＲａｎｋ 算法和加权ＬｅａｄｅｒＲａｎｋ 算法在排序上具有较高的相似性， 但是ＩｎｔｅｒａｃｔｉｖｉｔｙＲａｎｋ 算法所识别到的高影响力节点可以促进网络信息的传播规模。