基于复杂网络的节点影响力评价模型研究

来源:用户上传      作者: 徐健

　　摘要：评价复杂网络节点影响力主要依靠节点的度、邻近度、介数和K-shell等中心性指标值，但此类方法的挖掘精度和适应性均不理想。提出了一种新的复杂网络节点影响力评价模型——KSC中心性度量模型。该模型不仅考虑节点的内部属性，还考虑节点的外部属性。通过SIR模型进行了仿真传播实验，实验结果表明，该算法适用于各种复杂网络并且能够很好地发现影响力更大的传播节点。
　　关键词：复杂网络；评价模型；中心性；邻近度；介数
　　中图分类号：TP302
　　文献标识码：A 文章编号：1672-7800（2014）003-0042-04
　　基金项目：山东省教育科学规划项目（ZK1101322D089）
　　作者简介：徐健（1980-），男，山东青年政治学院信息工程学院讲师，研究方向为复杂网络。
　　0 引言
　　近年来，复杂网络已成为多个学科的研究热点。许多复杂网络具有社区结构，社区可以被看作一个网络的子图，同一社区中节点间联系紧密而不同社区间的节点联系松散。研究表明，社会网络和生物网络都具有明显的社区结构。网络的结构与其功能有密切关系，在线社区结构可以揭示复杂网络中的隐藏规则并帮助预测和控制行为，如Web社区发现、蛋白质网络分析和功能预测等。对复杂网络中节点重要性的评价一直受到研究人员的广泛关注，发现网络中的关键节点是网络研究的重要内容。
　　在社会网络分析中，“中心性”一般用来测度最有影响力的节点。Pastor-Satorras R和其他一些人用中心性（度中心性）来测度最有影响力的节点，与非均匀幂律网络一致，度越大的枢纽节点影响越大，这是目标免疫和熟人免疫策略的基本依据。Brin S、 Page L等人提出了PageRank算法用以衡量网页的重要性，该算法认为网页节点的重要性取决于其前向链路的数量和质量。Opsahl T用紧密度（邻近中心性）来描述一个节点到其它节点的难度。kitsak M等通过K-shell分解来确定最有影响力的单源节点。
　　从一个角度来讨论节点的重要性，比如：以节点度作为重要性评价依据的方法，强调节点边的数量，在一定程度上显示出节点在网络中的重要程度，但具有相同度的节点未必具有相同的重要性；介数用于描述节点或边对于网络信息或信息流的控制能力，介数中心性一般根据最短路径和大多数实际网络来定义。但网络信息并不沿着最短路径流动而是随机流动。因此，在一些网络中，介数中心性不用于衡量节点的重要性。邻近中心性考虑节点间的独立性，这种独立性是指与其它节点联系时需要最少的中介节点的可能性，但邻近中心性在很大程度上依赖于网络拓扑结构，它可以准确发现集中型网络的中心节点，但不适合正则图、ER随机网络等。此外，本研究发现，度量与中心性程度是有关联的，度中心性较高的网络节点通常具有较高的邻近中心性。其它诸如特征向量中心性则充分考虑与目的节点的重要性，通过相邻节点的重要性来确定中心节点的位置。子图中心性反映了节点在局部网络中的作用，网络流和随机游走都采用了模拟现实的思想。
　　本文认为，节点的影响不仅取决于内部属性，也与外部特性密切相关。内部属性有诸如度、邻近度、介数以及其它定心指标，外部属性诸如社区规模、社区内关系的亲密程度等等。社区是由有共同爱好的人、或同一个地方的人、或从事相同工作的人、或有亲缘关系的人组成的群体。社区内的节点是密切联系的，不同社区的节点则关系松散。
　　在社会网络中，找到最有影响力的节点可以帮助我们有效地控制疾病的传播、谣言的散布和计算机病毒的传播，也可以传播新产品、新思路以推进社会发展[2]。
　　1 复杂网络中心性
　　1.1 度中心性
　　dlm表示从源节点l到节点m的最短距离。
　　本文提出了KSC指标模型（K-shell and community centrality）。这一模型不仅考虑节点的内部属性，而且考虑节点的外部特性，如节点归属社团的特征。用SIR模型（Susceptible-Infected-Recovered）模拟传输，实验表明该方法可以较好地确定最有影响力的节点。本文针对这一有挑战性的研究提出了新的思路和方法，
　　主要在以下领域进行了拓展和创新。（1）以前挖掘复杂网络中的潜在传播点主要依赖于节点的度、邻近度、介数和K-shell等中心性指标，但此类方法存在挖掘精度不高、适应性不强等缺点，因此本文提出KSC中心性度量模型。该模型不仅依据节点的内部属性来分析节点影响力，而且还考虑节点外部特性。内部属性包括度、邻近度、介数和K-shell等中心性指标，外部特性包括社区规模、社区内关系的紧密程度等等。该模型对于挖掘复杂网络中有影响力传播节点具有显著意义。（2）为了进一步验证所提出模型的正确性和有效性，本文使用SIR模型进行仿真实验，分析和比较了KSC、度、邻近度、介数、K-Shell等中心性指标。在实验模拟的传播过程中，每次只在网络中选择一个节点作为初始传播节点，设置一个较短的传播时间（t=10），对每个节点进行1000次实验然后取均值，最终的感染节点和恢复节点总数定义为影响力F（t）。仿真结果表明：使用KSC模型挖掘复杂网络潜在节点精度更高、范围更大。
　　2 模型和算法
　　K-shell给出了网络节点的粗粒度重要性。网络边缘节点的K-shell值为1，然后就像剥洋葱一样一层层地进入到网络的核心。首先移除网络中所有度小于K的节点及与之关联的边，如果仍然存在值小于K的节点，就继续移除这些节点，直至网络中其余节点的值不小于u，依次令u=1，2，3，…n，即可得到网络的K-shell分解，具体过程可参考图1。kitsak等人的实验研究表明，对于一个感染率较低的单一传播源，具有较大的度或介数的节点未必是最有影响力的节点，由K-Shell分解得到的网络核心节点（具有较大K值）才具有最大的影响力。研究表明，K-Shell分解是一种更好的方法，它可以更好地确定有影响力的节点以及预测病毒的传播[3]。当感染疫情在网络中具有较大K值的节点上爆发时，该病毒总是通过多种途径感染网络核心的部分。无论该节点的度是大还是小，这个结论都是正确的。反过来，这些途径的存在也就意味着如果一个源节点随机爆发病毒，具有较大K值的节点比其它节点更易被感染（预测传染）。 　　2.1 SIR模型
　　节点的传播不仅仅关系到度、邻近度、介数、K值等内在特性，也关系到外部环境特征，比如节点所在的外部环境：社团大小、社团联系的紧密程度等等。本文提出了新的思路和方法：节点的影响力取决于内部和外部的原因，即KSC定性指标模型。这个模型符合“内因和外因共同对事物起作用”这一哲理。
　　现实社会网络中的传染病模型已经广泛应用于疾病传播研究和信息及谣言传播研究。为了验证所提出的模型，使用SIR模拟传输，并与模型实验结果进行比较。
　　模型有3种状态：易感染状态、感染状态和免疫状态。当一个个体处于感染状态时，它会感染处于易感染状态且感染可能性为β的相邻个体，处于感染状态的节点恢复为免疫状态的概率为γ。如果β值较大且节点传播能力较强，节点将迅速感染整个网络，使区分单个个体重要性变得困难；较小的β值可以更好地在限定时间内显示感染范围。我们在本文中设置一个较小的β值：0.04。
　　2.2 算法
　　3 实验与分析
　　3.1 实验数据
　　考虑到不同的社会网络代表了不同网络拓扑结构的特点，我们选择4个真实的社会网络数据集来进行分析和比较。表2给出了每个网络的性能：①MSN博客空间关系网络；②尼特软件公司纽曼梅杰关系网络，它选择了一个拥有379名作者的最大连接子图网络；③路由器网络，数据是由Rocketfuel工程收集的路径层次网络；④电子邮件网络，这个网络是大学成员Weier Jili of Luowei La发出的消息关系网络。此模型也能够应用于其它类型的复杂网络。
　　3.2 实验结果
　　应用SIR模型，对提出的KSC指标、邻近度、介数和K –shell值等进行分析和比较。在仿真实验的传播过程中，每次只选择一个网络节点作为传播源，设置较短的传播时间（t = 10），对每个节点进行1 000次重复实验并取平均值，最终感染节点和恢复节点的总数被定义为影响力F （t）。在KSC模型中，内部影响因素α和外部影响因素β（α+β=1）的影响力在结果中出现不同的值。在哲学范畴，事物的运动和变化都取决于其固有的内在矛盾，但与其外部条件相关，内部和外部因素对事物的发展起到不同的作用。
　　这与“内部影响因素和外部影响因素均影响传播”这一假设相符。当0≤α≤0.30，1≤β≤0.85， 或1≤α≤0.821， 0≤β≤0.250时，可以看到影响力曲线的波动十分明显，排名靠后节点的影响力反而更大，也就是说，如果仅仅简单地考虑内部节点或外部节点，就会发现最有影响力的节点准确性和适应性都较差。如表3所示，实验结果显示了4种不同拓扑结构网络中的内部影响因素和外部影响因素，可以在不同的网络结构中看到内外影响因素角色的不同，由表3得出实验中的α和 β起明显作用，这从另一方面证明了KSC模型的合理性和普适性。表3代表了定心指标及其在不同网络中实际影响程度之间的关系。
　　对于博客网络，度、K-shell值、指标数量和影响指数F（t）之间的关系不是很明显。例如，一些介数较大的节点F （t）值甚至低于具有较小介数的节点，但KSC指标能够更好地区分最有影响力的节点。在电子邮件网络，所有的指标表现得都不错，与网络拓扑结构相关，邻近度和KSC更加理想。在尼特软件网络，介数的结果是最差的，邻近度、K- shell值和F （t）值之间的关系不明显，KSC优于度。在路由网络，K-shell值 和KSC的结果比较相近，而从其它指标中获得一个具有更大传播力的节点很困难。简言之，在不同网络中，传统中心性指标各有利弊，但KSC的总体效果却较好，它可以有效区分最有影响力的节点且通用性较强。
　　Kitsak等人在《自然物理》中提出，单源传播情况下最有影响力的节点不是度最大或介数最大的节点，而是K-shell值最大的节点。实验结果显示，KSC方法明显地优于现有的4种典型方法[4]。因此，考虑节点的外部特征对于识别最有影响力的节点具有显著意义，并且具有很强的通用性，这表明我们提出的模型是合理的和普适的。
　　从图2的结果分析可以看出，4种经典方法在不同网络中各有利弊，总体上灵活性不强，特别是影响力前10的波动十分明显。具有较小指标值节点的传播力大于具有较大指标值的节点，特别是在博客网络中，现有4种指标方法的结果都不是很准确，但KSC指标在几乎所有网络中均正确地呈现出单调递减曲线。
　　横轴代表根据不同指标得到的排序，纵轴代表影响力函数F （t），曲线代表不同的方法。
　　算法在寻找恶意节点方面也独具优势。K halil等人提出的DICAS算法需要一个“监控节点”对恶意节点发送的消息进行监控，一旦节点的拓扑结构不满足这一要求，恶意节点的检测率将大大降低，本文提出的算法几乎摆脱了网络拓扑结构的限制，并且一直保持着较好的恶意节点检测率。Cao Z等人使用消息发送反馈机制来保证网络的可靠性，但对恶意节点的判断过于简单，基站附近的节点和一些“热点”节点经常被报告为恶意节点。在未考虑节点失效的实验环境下，给出的算法则在保持对恶意节点较高检测率的同时避免误报。
　　4 结语
　　复杂网络节点影响力研究对于预防病毒扩散和谣言传播，以及传播新的思想和产品具有显著意义。基于传统中心性指标的方法缺乏普适性和准确性，本文有针对性地提出了KSC评价模型并进行了仿真实验。实验结果表明，节点的影响不仅取决于其内部属性，也取决于外部特征，表明本文提出的KSC模型是合理的、普适的。
　　参考文献：
　　[1] 刘建国，任卓明，郭强，等.复杂网络中节点重要性排序的研究进展[J].物理学报，2013（17）.
　　[2] 付立东，高琳，马小科. 基于社团检测的复杂网络中心性方法[J].中国科学，2012（5）.
　　[3] 张金柱. 利用 K - shell 分析合著网络中的作者传播影响力[J].现代图书情报技术，2012（5）.
　　[4] 王晰巍，靖继鹏，范晓春. 知识供应链组织模式构建机理[J].清华大学学报：自然科学版，2006（46）.
转载注明来源:https://www.xzbu.com/8/view-4924440.htm