摘 要

随着现代人对社交网络依赖性的增强，研究社交网络中各节点影响力的工作变得更加重要。社交网络中的关键节点在提高信息传播效率、合理控制广告投放、制定市场营销策略等方面都能体现重要作用。鉴于现存各种指标方法在识别复杂网络中节点影响力时仍存在一定局限性，本文提出一种基于k-shell算法的改进识别方法。

k-shell算法通过衡量节点在网络中的位置来评价其重要性，具有较好的识别效果。但此算法存在排序结果单调性较差的弊端，并且与较多传统中心性算法一样，只从网络的核心区域识别关键节点，忽视了处于外围的重要传播者。为此，考虑将节点的多阶邻居度与加权k-shell指数结合起来构建改进方法。且为了达到合理分辨不同阶数邻居对节点影响力加持权重不同的目的，引入节点的影响力邻域集及测地线来控制节点度的影响，这同时也是优化算法时间复杂度的需要。

为了准确评价改进方法的效果，将改进方法与经典指标方法一同应用于实际社交网络中实验，使用SIR传播模型作为传播机制进行验证。结果表明，所提出的改进方法及其扩展形式能够在社交网络中更准确识别出有影响力的节点。同时，也有效解决了传统k-shell算法单调性差的问题，显著提高了排序结果的分辨率。适合应用于大型社交网络关键节点的识别工作之中。

关键词：节点中心性；k-shell算法；社交网络

Abstract

With the increasing dependence of modern people on social networks, it becomes more important to study the influence of nodes in social networks. The key nodes in the social network can play an important role in improving the efficiency of information dissemination, reasonably controlling advertisement delivery and formulating marketing strategies. In view of the limitations of various existing index methods in identifying node influence in complex networks, this paper proposes an improved identification method based on k-shell algorithm.

K-shell algorithm evaluates the importance of nodes by measuring their positions in the network, and has good recognition effect. However, this algorithm has the disadvantage of poor monotonicity of ranking results. Like many traditional centrality algorithms, it only identifies key nodes from the core region of the network, ignoring important spreaders in the periphery. For this reason, it is considered to combine the multi-order neighbor degree of nodes with the weighted k-shell index to construct an improved method. Moreover, in order to reasonably distinguish the different influence weights of neighbors with different orders on nodes, the influence neighborhood set of nodes and contact distance are introduced to control the influence of node degree, which is also the need to optimize the time complexity of the algorithm.

In order to accurately evaluate the effect of the improved method, the improved method and the classical index method are applied to experiments in actual social networks, and SIR epidemic simulator is used as a propagation mechanism for verification. The results show that the proposed improved method and its expanded form can more accurately identify influential nodes in social networks. At the same time, the problem of poor monotonicity of traditional k-shell algorithm is effectively solved, and the resolution of sorting results is significantly improved. It is suitable for identification of key nodes in large social networks.

Key Words：Node centrality；K-shell algorithm；Social network

目 录

摘要 I

Abstract II

第1章 绪论 1

1.1 研究背景 1

1.2 国内外研究现状 1

1.2.1 传统中心性指标方法 2

1.2.2 k-shell方法及其拓展 2

1.3 研究目的与意义 3

1.4 研究思路与内容 4

1.4.1 研究的基本内容 4

1.4.2 研究思路 4

1.4.3 章节安排 5

第2章 相关理论与研究方法 7

2.1 复杂网络基本概念 7

2.1.1 网络的图与矩阵表示 7

2.1.2 网络基本拓扑性质 7

2.2 经典中心性度量方法 8

2.2.1 度中心性 8

2.2.2 介数中心性 9

2.2.3 接近中心性 9

2.2.4 k-shell分解算法 9

第3章 社交网络节点中心性问题的研究 12

3.1 社交网络的构建 12

3.2 中心性算法在社交网络中的应用 14

3.2.1 节点影响力排名及可视化 14

3.2.2 指标方法时间复杂度分析 17

第4章 基于k-shell算法的改进节点中心性算法 19

4.1 提出改进k-shell算法 19

4.1.1 改进k-shell方法 19

4.1.2 参数讨论 19

4.1.3 扩展的改进k-shell方法 20

4.1.4 提出算法的算例 20

第5章 方案的分析与验证 22

5.1 改进k-shell算法的仿真 22

5.1.1 SIR传播模型 22

5.1.2 算法的仿真 23

5.2 指标方案准确性的验证 25

5.2.1 肯德尔相关系数 25

5.2.2 指标方法之间的相关性 25

5.2.3 指标方法与SIR仿真结果的相关性 27

5.3 指标方法单调性的验证 28

5.3.1 CCDF函数验证 28

5.3.2 单调性指标验证 29

5.4 总结 30

第6章 结论 31

6.1 论文的研究成果 31

6.2 论文的不足与展望 31

参考文献 32

附录A 社交网络的邻接矩阵 34

附录B 算法与方案实现的代码 35

致谢 53

第1章 绪论

现如今，越来越多的人们更频繁地使用社交网络，对于社交网络中极具影响力节点的识别也变得更有价值。一旦我们能够准确找到并很好地利用社交网络中的关键节点，那么信息的传播就会变得更方便而高效，这一点可以在病毒营销、舆论导向等方面得到体现。本文所提出的一种基于k-shell算法的衡量网络节点中心性方法致力于进一步有效识别社交网络中的关键节点。

1.1 研究背景

在现代社会中，越来越多的系统可以自然抽象为复杂网络，如电力网络、交通网络、引文网络等，还有近年来迅猛发展的社交网络。在众多新媒体以及以QQ、微信为首的社交网络越来越风靡的大背景下，在日益发展壮大的信息技术支持下，网络科学正快速发展。因此，研究者们开始着手于在实际社交网络中进行信息传播仿真相关工作的研究。于是，研究者们在一些自媒体信息传播过程中发现社会网络中的一些关键节点往往扮演着重要的角色。如2016年美国大选时社交网络研究实验室发现选举日前数月在推特上1.71亿条推文中有近三成伪造或偏激信息，其中那些极具影响力的用户，对选民们的行动产生了关键影响^[1]。2014年发生了一时火爆的“冰桶挑战”与震惊世界的“马航悬案”，其在社交网络上传播速度之快、范围之广，再次彰显了关键节点强大的社会影响力^[2]。更典型的是随着网络的发展，在线社交网络为市场营销发展提供了很大支持。许多企业基于在线社交网络的影响进行病毒营销，时常会以较小的成本获得巨大收益，而其中的关键正是在于寻找到社交网络中具有高影响力的节点^[3]。

上述事实说明了网络中极具影响力的关键节点将很大程度影响着网络的结构和功能，应用复杂网络理论及方法确定网络中的关键节点将有利于我们更有效对复杂系统的特征进行识别和分析，并进行更好地预测和控制。而如果它们不能正常工作，将会对整个网络的结构和稳定性产生较大负面影响。并且这样的影响会快速扩散至整个网络，最终甚至有可能造成网络功能的瘫痪^[4]-[5]。此现象在社交网络中尤其明显，在社交网络中，如果能准确识别并利用其中所谓的关键节点，那么重要消息的传播会变得高效，同样也可以通过移除这些节点来抑制谣言的扩散。