论文总字数：17727字

目 录

1绪论 3

1.1研究背景和意义 3

1.2复杂网络概况 4

1.2.1复杂系统 4

1.2.2复杂网络 4

1.3节点重要性的度量方法 5

2 k-shell算法 6

2.1 k-shell算法介绍 6

2.2 k-shell算法实现 7

2.2.1算法流程 7

2.2.2数据结构 7

2.2.3算法实现 8

3 MD-shell算法 9

3.1 k-shell算法的不足 10

3.2 MD-shell算法 10

3.2.1算法流程 11

3.2.2算法实现 11

4 测试与分析 12

4.1 网络概况 12

4.2 算法结果分析 13

4.3 SIR 模型 15

4.3.1 算法描述 15

4.3.2算法实现 17

4.3.3结果分析 18

4.4 相关系数测试 21

4.4.1 Kendall tau相关系数 21

4.4.2相关系数分析 22

5总结 24

参考文献 25

致谢 27

基于K-shell的网络节点信息传播能力的识别算法的研究

杨阳

ABSTRACT：In this paper, we first introduce the background and significance of the research on the algorithm of information dissemination capability of network nodes and summarizes the research status of complex systems and complex networks in the light of the present research situation. A measure of the importance of nodes. And then details the contents of k-shell algorithm and implementation. Based on this work, the k-shell algorithm is analyzed, and the algorithm is improved according to the existing problems. The implementation of the improved process and algorithm is described in detail, and the algorithm is run on the real network to analyze the result of the algorithm. Finally, the Kendall tau correlation coefficient is used to verify the results of the SIR model, and it is proved that it has higher discrimination degree.

Key words: k-shell， Node importance， SIR model， complex network

1绪论

1.1研究背景和意义

我们可以用网络来描述自然界的各种复杂系统，将个体抽象为节点，将它们之间的关系抽象为边，这样就可以用网络的方法研究这些系统^[1]。我们周围存在着各种网络，比如用Email联系起来的通讯网络、人与人之间的人际网络、使生活更加便捷的电力网络。这个社会变的越来越网络化，这些网络的特征越来越明显，那就是复杂。复杂的结构、多样的连接和多样的节点是这个特征的主要体现。这样的网络被称为复杂网络。社交网络、电力网络、交通网络、互联网等这些网络都属于复杂网络^[2]。各领域的研究人员，如物理学、数学、系统科学、计算机科学、社会科学等，都开始使用网络的方法研究复杂系统，引发了大家对复杂网络的研究与关注。

如今信息技术发展迅猛，无处不在的网络，例如电力网络、社交网络，正在逐步改变着社会。人们开始对复杂网络的行为和特性进行研究，首先收集网络中的数据，通过数据分析网络的特征，在此基础上建立起网络模型，最后用模型研究网络行为，从而改善网络性能。

进过大量研究，研究人员发现在网络中不同节点的重要性是不同的，一部分重要性较高的节点成为了网络的核心。节点的重要性在不同的网络中也有着不同的含义，比如代表声望，地位，社会影响力等等。不同重要性的节点对于网络的结构和性能有着不同的影响，由此引出了一些有待进一步思考和研究的问题。例如：预防传染病流行，预防网络攻击阻止网络病毒的传播，抑制流言的传播等等。

度量网络中节点的重要性，识别出重要的节点具有很高的实用价值。特别是针对性的分析具体网络的性质，制定正确的策略。比如：在电力网络中，对重要的单元进行保护，能够有效的防止由级联引发的大范围事故；在计算机网络中，根据节点的重要程度，针对性的对节点、服务器进行备份和保护，可以减小网络的故障率；在传染病、病毒网络中，有效的识别出高危人群，针对性的进行治疗，隔离病源，能够有效的防止病毒的传播扩撒；在谣言传播网络中，了解不同传播者在传播过程中的作用，针对性的采取措施，发掘出始作俑者，控制谣言的主要传播者，消除谣言带来的危害；在犯罪网络中，识别出团伙头目，集中警力进行抓捕，达到瓦解团伙的目的。

社交网络中的“中心节点”在营销传播中有着重要的意义。有一部分善于交往的人是社会网络中极其重要的部分，他们将不同种族、不同背景的人联系在一起，可以让信息更快的传播到网络中去。有别于大众消费品的覆盖传播，在分众的市场传播中为了更好的渗透到客户中去做传播覆盖，我们需要摸清楚人群中的中心节点群。大部分人拥有着一个独立的朋友圈，每个人都以独特的方式将多个群体的人联系到一起。例如，一个人有小学同学、高中同学、大学同学、同事群体，这个人就是世上唯一将这几个群体联系到一起的人。信息的传递通常是从一个群体到另一个群体，信息只有通过这个人才能从一个群体到另一个群体。将特定的圈子当作网络，节点在信息传播路径上能够发挥作用的大小取决于其在网络中所处的位置。当节点处在网络的末端或者狭隘的边角时，那么它只能成为信息的接受者，不能引爆全网。着眼于社交网络中的中心节点，研究群体之间信息传递的方式，能够让信息更好更快的扩散。

1.2复杂网络概况

1.2.1复杂系统

随着科技的发展复杂系统应运而生，作为一门新兴学科其发展过程是一个从量变达到质变的过程。简单系统与复杂系统的差别就相当于牛顿三大定律相对于量子力学。相对于简单系统，复杂系统具有规模庞大、结构复杂、关系交错等特点，而且具有智能性、自组织性、自适应性。作为一门多学科交叉的系统，传统的研究方法已经不再适用与复杂系统，尤其是传统的数学推理的方法。不过随着计算机科学的发展、计算机计算性能的提高，人们开始采用计算机模拟的方法对复杂系统进行研究。简单系统、随机系统和复杂系统是复杂系统发展的几个主要阶段。

简单系统：特点是元素数目少，元素间的关系简单。具有可控性、可预见性，可以通过经典的图论方法进行研究。

随机系统：元素数量增多，而且它们之间的关系变的多样化。研究随机系统的一般方法为随机图论。

复杂系统：比随机系统更复杂。元素众多、信息量极大、元素间的相互关系非常复杂。具有智能性、自组织性、自适应性、不稳定性、非线性、不确定性和不可预测性等特性。单一的、传统的方法已经不再适用与复杂系统的研究了。

复杂系统涉及的学科众多，如生物学、物理学、社会学、经济学、计算机学等等。随着科技的发展，研究的深入，人们将渐渐揭开复杂系统的神秘面纱，在复杂系统的理论指导下人们的生活将变得更加便利。

1.2.2复杂网络

传统的研究方法已经不能用于研究复杂系统，急需一种有效的研究方法，复杂网络在此时应运而生。我们可以使用网络来描述复杂系统，用网络的方法研究复杂系统，复杂网络成为了一个新的研究方向。研究者通过收集网络数据，分析网络特性建立起网络模型，通过分析网络模型来了解复杂网络。

节点众多、结构复杂、个体行为复杂是复杂网络的特点，对于如此复杂的网络我们应当采取什么方法了解网络结构、衡量网络复杂度呢？应当如何度量个体对网络整体的影响呢？

为了了解网络性能、网络结构和内部联系等，级联性、传播性和同步性等方法被学者们提出。在复杂网络研究领域中，网络节点重要性度量有着重要意义和深远影响。复杂网络节点重要度在很多不同的领域都具有重要意义，比如互联网、社交网、交通网、电力网等领域。节点重要度对于防控网络攻击、控制谣言传播、控制交通拥堵、控制传染病的扩散等都有着重要影响倘若我们可以快速、有效地找到某个重要节点或某些重要节点群，及对网络整体结构有重大影响的节点，及时对这些节点采取相应措施，就可以避免或减少损失。

1.3节点重要性的度量方法

通过分析网络中节点的重要性人们可以更好的理解网络的特征，而如何定量的描述网络中节点的重要性成为复杂网络研究的基本问题之一。通过近年来的研究，已有很多的研究结果，研究学者们根据不同网络和需求采用不同的度量方法来刻画节点的重要程度。具体方法有以下几种：

1. 基于节点度中心性的节点重要性度量方法。

这种评价方法是所有方法中最简单、最直观的方法。顾名思义，基于节点度中心性的度量方法跟节点的度有关系，利用网络中节点的度来度量节点在网络中的重要程度。节点度越大说明节点的重要性越高；节点的度越小说明节点重要性越小。

基于节点度中心性的度量方法，有一定的理论意义和实际应用价值，但是该方法也有着一定的局限性，该评价方法只着眼于局部的节点和节点的度，所以其考虑的因素不够全面。当然也有学者认为节点的重要性不仅仅由自己的自身的度决定，还受到邻居节点的影响。

2. 基于路径的节点重要性度量方法。

路径是度量节点重要性的重要指标，这个路径既可以是节点之间的距离也可以是节点之间节点的个数。在交通网络中，节点之间的联通效率受节点间距离的影响，距离越短效率越快，距离越长效率越慢。在通讯网络中，节点间信息传递的效率和准确性会受到节点间节点数目的影响，节点数目越多中专时间越长效率慢，节点数目越少中专时间越短效率高。

基于路径的节点重要性度量方法有着较高的时间复杂度，不适用于大型网络。路径的评价指标又可以详细的分为离心中心性指标、接近中心性评价指标、介数中心性评价指标、社团中心性评价指标等。

剩余内容已隐藏，请支付后下载全文，论文总字数：17727字