复杂网络免疫策略及重要节点排序研究(硕士)(论文32000字)
Research on Immunization Strategy and Ranking Nodes in complex networks
摘要
传染病、计算机病毒以及谣言的传播严重危害了人类的生命财产安全，如何对社会网络中传染病的蔓延和计算机网络中病毒和谣言的传播进行控制具有极大的研究价值。复杂网络可以对传染病、计算机病毒和谣言的传播进行量化描述并分析，因此被广泛应用于研究人类社会中的各种复杂体系。找到高效的抑制传染病、计算机病毒以及谣言传播的方法其实可以转化为如何挖掘复杂网络中的重要节点以及找到在病毒传播过程中的一些有效的免疫策略。因此，本文在免疫策略方面提出了加权网络中考虑边权和度的熟人免疫策略，在挖掘复杂网络的重要节点方面提出了无权网络中改进的K-shell算法和基于权重的K-shell改进算法。具体的研究工作内容及成果如下：
(1).在加权网络中，一个节点被感染的概率不仅与邻居节点的联系的紧密程度有关，还和其邻居节点的个数有关。根据加权网络的特点，基于熟人免疫的思想，提出了同时考虑边权和度的熟人免疫策略(AI-CWD)，并分别在人工BBV网络和真实网络上进行仿真实验。同时还进一步研究了边权和度在乘积中的占比对该免疫策略的免疫效果的影响。研究结果表明，在相同的免疫节点密度下，使用AI-CWD免疫策略进行免疫后网络中感染节点的密度比最大权值免疫、改进的熟人免疫和基于ClusterRank算法免疫要低，即AI-CWD免疫效果要优于另外三种免疫策略。并且在相同的免疫节点密度下，通过对边权和度的占比与感染节点密度关系的研究，可以得出：存在一个最优的 值，使得最终的感染节点密度最低。
(2).为了解决K-shell算法导致的大量节点具有相同Ks值的问题，提出了全能节点的概念，即在众多不同的排名指标中得分都较高的节点。考虑到较高的聚类系数不利于节点影响力的传播，综合考虑聚类系数、度数以及Ks值，提出无权网络中改进的K-shell算法(KCD)。使用KCD算法、K-shell分解算法以及KCK算法分别在航空网络、科学家合作网络以及Email网络中进行实验仿真。研究结果表明，在节点重要性排序方面，KCD算法要优于K-shell分解算法和KCK方法。
(3).网络中节点 的本身特性和在拓扑结构中的位置特性，即度数和Ks值会对节点 的重要性造成一定的影响。除此之外，节点 本身的局部特性，即节点 的邻居节点对节点 的影响力的贡献，也会对节点 本身的重要性造成一定程度的影响。为了有效度量像社交网络这类的含权网络中节点的影响力，更加准确地进行节点重要性排序，所以本章提出了基于权重的K-shell改进算法(KWK)。使用KWK算法、K-shell算法和KCK算法分别在航空网络和科学家合作网络中进行实验仿真。研究结果表明，在节点重要性排序领域，KWK算法要比K-shell分解算法和KCK算法更好，较为适合应用于含权网络。
关键词:复杂网络，熟人免疫，BBV网络，SI传播模型，K-shell分解算法，节点重要性排序，最有影响力节点
Abstract
Infectious diseases, computer viruses and the spread of rumors cause the loss of human life and property seriously. It is worth researching the ways of controlling the spread of diseases in social networks and the spread of viruses and rumors in computer networks. Complex networksare used to quantify and analyze the spread of diseases, computer viruses and rumors, so complex networks is also widely used to research various complex systems in human society. The problem that how to find effective ways to contain diseases, computer viruses and rumors is actually equal to the problem that how to mine important nodes in complex networks and find some effective immunization strategies in the process of virus transmission. So an improved Acquaintance Immunization strategy by considering the weights and degrees(AI-CWD), an improved K-shell algorithm by considering clustering coefficient and degrees(KCD) and an improved K-shell algorithm by considering weights and degrees(KWK) are proposed. Specific research work and results are as follows:
(1).In weighted networks, the probability of a node being infected is not only related to the closeness of the neighbors, but also to the number of its neighbors. According to the characteristics of weighted networks and the idea of acquaintance immunization, AI-CWD strategy is proposed. And then, simulations are conducted on artificial and real networks respectively. Besides, the effect of the proportion of the weight in the product is further studied. The simulation results show that under the circumstance that the densities of immune nodes are the same, the density of infected nodes in the network immunized by the AI-CWD strategy is lower than that of the network immunized by Max-Weight strategy, the Improved Acquaintance Immunization strategy and the strategy based on ClusterRank algorithm. Namely, the immunization effect of proposed strategy in this paper is better than the other three immunization strategies. A parameter that characters the proportion of weights in the product between degree and weight is also introduced in this paper. Simulation results show that by controlling the parameter in the product, there exits an optimal proportion of weights that can make the density of infected nodes lowest.
(2).In order to solve the problem that a large number of nodes have the same Ks value caused by the K-shell algorithm, a concept of an all-purpose node is proposed, that is, a node which has a higher score in many different ranking indicators. Considering that the higher clustering coefficient is not conducive to the spread of node influence, the improved K-shell algorithm is proposed in unweighted networks based on the clustering coefficient, degree and Ks value. Simulations are conducted on artificial networks and real networks with KCD algorithm, K-shell decomposition algorithm and KCK algorithm respectively. The simulation results show KCD algorithm outperforms K-shell decomposition algorithm and KCK algorithm in the field of nodes’ importance rank.
(3).The influence of a node in a network is not only related to its own attributes and location attributes but also to the local attributes of the node, that is the contribution of its neighboring nodes to the node’s influence. In order to measure the importance of nodes more accurately, an improved K-shell algorithm by considering weights and degrees is proposed. Simulations are conducted on artificial networks and real networks with KWK algorithm, K-shell decomposition algorithm and KCK algorithm respectively. The simulation results show KWK algorithm outperforms K-shell decomposition algorithm and KCK algorithm in the field of nodes’ importance rank, and is more suitable for the weighted networks..
Key words:complex networks,acquaintance immunization strategy, BBV networks, SI model, K-shell decomposition, ranking nodes, the most influential node
目录
第一章绪论 1
1.1研究背景 1
1.2研究现状 2
1.2.1重要节点排序 2
1.2.2复杂网络中的免疫策略 4
1.3本文主要研究内容和结构 6
第二章相关背景知识介绍 8
2.1复杂网络经典模型 8
2.1.1 ER随机网络模型 8
2.1.2 WS小世界网络模型 8
2.1.3 BA无标度网络模型 9
2.1.4其他网络模型 9
2.2重要节点排序 10
2.2.1基于节点度中心性的排序方法 10
2.2.2基于路径的排序方法 11
2.2.3基于特征向量的排序方法 12
2.2.4基于随机游走的排序方法 13
2.2.5基于节点位置的排序方法 14
2.3复杂网络中的免疫策略 17
2.3.1随机免疫 17
2.3.2目标免疫 18
2.3.3熟人免疫 19
2.3.4加权网络中相关的免疫策略 19
2.4本章小结 20
第三章加权网络中考虑边权和度的熟人免疫策略 21
3.1引言 21
3.2考虑边权和度的熟人免疫策略(AI-CWD) 22
3.3实验仿真与结果分析 24
3.3.1在BBV网络上的仿真结果分析 27
3.3.2在真实网络上的仿真结果分析 29
3.3.3边权值和度的占比对免疫效果的影响 30
3.4本章小结 31
第四章无权网络中改进的K-shell分解算法 33
4.1引言 33
4.2无权网络中改进的K-shell分解算法(KCD) 33
4.3在真实网络上的仿真结果分析 34
4.4本章小结 37
第五章基于权重的K-shell改进算法 38
5.1引言 38
5.2基于权重的K-shell改进算法(KWK) 38
5.3在真实网络上的仿真结果分析 39
5.4本章小结 41
第六章总结与展望 42
6.1全文工作总结 42
6.2研究展望 43
参考文献 44 |
