用户名: 密码: 验证码:
复杂网络的病毒传播模型及其免疫策略研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
目前,复杂网络的研究已日渐成熟,并且已渗透到各个学科领域,其研究不仅局限于数学领域,也正渗透到生命学科和工程学科等众多不同的领域,同时在计算机网络控制、社会网络分析和生物网络等领域也取得了一系列成就。随着对复杂网络的研究,复杂网络中的传播机制也演变成为其中的一个重要分支。传播现象在自然界和人类社会生活中广泛存在,如病毒传播,谣言传播等。而随着人们之间的交流不断密切,不管是网络中的病毒爆发还是社会生活当中的疾病传播,都会给人类的生活及经济带来巨大的影响。这些问题促使研究者们对复杂网络上的传播规律进行研究。复杂网络病毒传播的研究包括病毒传播模型的研究和网络免疫策略的研究。
     随着流行病在社会网络中的大规模爆发,计算机病毒也在肆意吞噬着因特网等网络。由于邮件是网络服务中最频繁的应用服务之一,因此依附于邮件的病毒传播也开始出现,并造成了一系列损失。传统的病毒传播主要依靠个体接触,主要模型有Susceptible-Infected(SI)模型、Susceptible-Infected-Susceptible(SIS)模型和Susceptible-Infected-Removed(SIR)模型等。然而,邮件病毒的传播不仅受传统的个体接触的影响,同时也受很多其他因素影响。例如用户的背景知识,抵抗病毒的自我保护能力和用户间的信任度等。因此,传统的流行病传播模型己不再适合用来描述这类网络病毒的传播。同时,针对网络的拓扑结构,前人又提出了随机免疫策略、熟人免疫策略、目标免疫策略以及各种改进的免疫策略。因此,一个可靠模型的建立和相关免疫策略的提出被认为是一个具有挑战性的问题。本文通过分析邮件病毒传播的方式和特点,提出一种改进的传播模型即具有自我保护能力和信任度的交互式邮件病毒传播模型,同时针对交互式邮件病毒传播模型提出一种基于节点重要性的动态免疫算法。
     本文的主要工作包括:
     1)复杂网络病毒传播模型研究
     目前已有的病毒传播模型都只是基于个体接触的。通过分析邮件病毒传播的方式和特点,我们发现用户自身对病毒的抵抗能力和用户间的信任度等因素也严重影响了病毒的传播。为此,本文基于用户对病毒的自我保护能力和信任度提出一种新的交互式传播模型。我们的仿真实验结果表明提出的模型能精确的描述病毒传播的过程,且网络中被感染个体数量也相当低。与此同时,在新模型中研究不同影响因子对病毒传播的影响,可为网络的免疫提供新方法。
     2)网络免疫策略相关研究
     目前大多数免疫策略都是只利用网络中节点的局部度信息或介数对网络进行免疫,这种方法不适用于大规模网络且忽略了其周围节点的最近邻和次近邻对病毒传播的影响。因此我们既考虑直接邻居节点也考虑间接邻居节点对病毒传播的影响,而提出一种利用节点局部中心值来计算节点重要性的免疫策略,并分析和比较目标免疫策略和本文所提的基于节点重要性的动态免疫策略的优缺点。实验结果证明动态免疫策略有效的降低了病毒爆发的速度,具有更优的免疫效率。
Currently, the research on complex network has become mature; and it has permeated various disciplines. The theory research is not only limited to Mathematics but also life discipline and engineering discipline and so on. Simultaneously it has attained a series of achievements in computer network control, society network analysis and biological network. With the study of complex network, the transmission mechanism has become one of the important branches. Propagation exists widely in nature and human life, such as virus propagation, rumor propagation. While with the closer communication among people, virus outbreak in the network and disease propagation in social network will cause enormous impact on human life and economic. All these problems prompt researchers to study propagation law. The research on complex network includes virus propagation model and network immunization strategies.
     With the large-scale outbreak of epidemic in social network, computer virus are devouring the Internet and other networks. Because email is one of the most frequent application in network, so virus propagation attaching to email has appeared and caused a series of losses. Traditional virus propagation relies mainly on individual contact, including Susceptible-Infected (SI) model, Susceptible-Infected-Susceptible (SIS) model, and Susceptible-Infected-Removed (SIR) model and so on. However, email virus propagation is effected not only by individual contact but also other factors. For example, background knowledge of users, the ability of self-protection and trust level among users. Therefore, traditional epidemic propagation model is no longer suitable for describing such kind of virus propagation. At the same time, according to the topology of the network, some researchers have proposed random immunization, acquaintance immunization, target immunization and some improved immunization strategies. So the establishment of a reliable model and related immunization strategies are considered as a challenging problem. This dissertation proposed an improved propagation by analyzing the spreading way and characteristics of email virus propagation. Also, we propose a dynamic immunization algorithm based on importance of the nodes for interactive email virus propagation model.
     The main work is summarized as follows:
     1) Research on virus propagation model in complex network
     Currently, the existed virus propagation model is just based on individual contact. By analyzing the spreading way and characteristics of email virus propagation, we discover background knowledge of users, the ability of self-protection and trust level among users also effect virus propagation. Therefore, this dissertation presents a novel interactive email virus propagation model based on users' ability of self-protection and trust level. Our simulation experimental results show that the proposed model can accurately describe the process of spreading of virus, and the number of infected individuals in the network is also quite low. At the same time, we research the effect of different factors on virus propagation in the novel model, which provides a novel method for network immunization.
     2) Research on network immunization strategy
     Most of immunization strategies only make use of local degree information or betweenness of nodes. This method is not suitable for large-scale network and ignores of the influence of the nearest neighbors and the next neighbors on virus propagation. Therefore, considering the effect of the nearest neighbors and the next nearest neighbors, we present an immunization strategy by local central value to compute the importance of nodes. Also we analyze and compare advantages and disadvantages between target immunization and the novel immunization strategy based on the importance of nodes proposed in this thesis. The experimental results prove dynamic immunization can reduce effectively the speed of outbreak, and has better immunization efficiency.
引文
[1]Eedos P, Renyi A. On the evolution of random graphs[J]. Publ. Math. Inst. Hung. Acad. Sci,1960,5:17-61.
    [2}Watts D-J. The new science of networks[J]. Annual Review of Sociology,2004,30: 243-27.
    [3]马于涛,何克清,李兵,刘倩.网络化软件的复杂网络特性实证[J].软件学报,2011,22(3):381-407.
    [4]M. Faloutsos, P. Faloutsos, C. Faloutsos. On power-law relationships of the internet topology[C]. ACM SIGCOMM Computer Communication Review,1999,29(4):251-162.
    [5]R. Albert, H. Jeong, A.-L. Barabasi. Internet:Diameter of the world-wide web[J]. Nature, 1999,401(6749):130-131.
    [6]M. E. J. Newman. The structure of scientific collaboration networks[J]. Proceedings of the National Academy of Sciences,2001,98(2):404-409.
    [7]S.Wasserman, K. Faust. Social Network Analysis[J]. Cambridge:Cambridge University Press,1994.
    [8]J. Scott. Social Network Analysis[M]. SAGE Publications Limited,2012.
    [9]南晋华,齐欢.图顶点覆盖问题决策神经网络模型[J].计算机学报,2009,32(8):1683-1686.
    [10]Bullmore E, Sporns O. Complex brain networks:graph theoretical analysis of the structural and functional systems[J]. The Neuroscience,2009,10(3):186-198.
    [11]汪秉宏,周涛,周昌松.人类行为、复杂网络及信息挖掘的统计物理分析[J].上海理工大学学报,2012,34(2):103-117.
    [12]林兵,郭文忠,陈国龙,等.无标度网络中基于最短路径免疫策略的病毒传播研究[J].计算机科学,2012,39(B06):136-138.
    [13]王凌.计算机病毒的感染原理及防范技术研究[J].中国管理信息化,2013(1):79-80.
    [14]彭梅,李传东,何兴.基于直接免疫的SEIR计算机病毒传播模型[J].重庆师范大学学报(自然科学版),2013.
    [15]D. J. Watts, S. H. Strogatz. Collection dynamics of small-world networks[J]. Nature, 1998,393(6684):440-442.
    [16]A.-L. Barabasi, R. Albert. Emergence of scaling in random networks[J]. Science,1999, 286(5439):509-512.
    [17]M. E. J. Newman. Models of the small world[J]. Journal of Statistical Physics,2000, 101(3-4):819-841.
    [18]Milgram S. The small world problem[J]. Psychology Today,1967,2(1):60-67.
    [19]S.H. Strogatz. Exploring complex networks[J]. Nature,2001,410(6825):268-276.
    [20]项林英,陈增强,刘忠信等.复杂动态网络的建模、分析与控制研究综述[J].自然科学进展.2006,16(12):1543-1551.
    [21]Li X, Chen G. A local world evolving network model [J]. Phys A,2003,328(1):274-286.
    [22]Pastor-Satorras, R, Vespignani, A. Epidemic Spreading in Scale-Free Networks[J]. Physical Review Letters 2001,86(14):3200-3203.
    [23]Eguiluz V M, Klemm, K.. Epidemic Threshold in Structured Scale-Free Networks[J]. Physical Review Letters,2002,89(10):108701.
    [24]Moore C, Newman, M E J. Epidemics and Percolation in Small-world Network [J]. Physical Review E,2000,61(5):5678-5682.
    [25]May S R. Enhanced:Simple Rules with Complex Dynamics[J]. Science,2000, 287(5453):601-602.
    [26]SONG Yu-rong, JIANG Guo-ping. Epidemic spreading on scale-free networks with diversity of node anti-attack abilities[J]. The Journal of China Universities of Posts and Telecommunications,2010,17(1):73-76.
    [27]Yanping Zhang, Tingting Sun, Shu Zhao. A Novel Model to Restrain Email Virus Propagation[C].2012 IEEE International Conference on Granular Computing. Hangzhou, China,2012,645-650.
    [28]Williamson M M, Leveille J. An epidemiological model of virus spread and cleanup[C]. Proceedings of Virus Bulletin, Toronto, Canada,2003.
    [29]Zou C C, Towsley D, Gong W. Modeling and Simulation Study of the Propagation and Defense of Internet Email Worm [J]. Dependable and Secure Computing, IEEE Transactions on,2007,4(2):105-118.
    [30]高超,刘际明,钟宁等.邮件网络中基于介数的免疫策略研究[J],计算机工程,2010,36(6):840-844.
    [31]王亚奇,蒋国平.复杂网络中考虑不完全免疫的病毒传播研究[J].物理学报,2010,59(10):6734-6743.
    [32]Anderson R M, May R M, Anderson B. Infectious Diseases of Humans:Dynamics and Control[M]. Oxford:Oxford university press.1992(28):328-460.
    [33]Romualdo Pastor-Satorras, Alessandro Vespignani. Immunization of Complex networks [J]. Physical Review E,2002,65(3):036104.
    [34]Cohen R, Havlin S, Ben-Avraham D. Efficient Immunization Strategies for Computer Networks and Populations[J]. Physical review letters,2003,91(24):247901.
    [35]J.G6mez-Gardenes, P. Echenique, Y. Moreno and A.Vazquez. Distance-d covering problem in scale-free networks with degree correlations[J]. Phys.Rev.E,2005, 71(3):035102.
    [36]Hu Ke and Tang Yi. Immunization for scale-free networks by random walker[J]. Chinese Physics,2006,15(12):2782-2787.
    [37]Chen Y, Paul G, Havlin S, et al. Finding a better immunization strategy[J]. Physical review letters,2008,101(5):058701.
    [38]Yoshida T, Yamada Y. Community structure based node scores for network immunization[M]. PRICAI 2012:Trends in Artificial Intelligence. Springer Berlin Heidelberg,2012:899-902.
    [39]方宝平.复杂网络的病毒传播及免疫策略[D].安徽:安徽大学计算机科学与技术学院,2010.
    [40]M. E. J. Newma. The structure and function of complex networks[J]. SIAM Review, 2003,45(2):167-256.
    [41]M. E. J. Newman. Threshold effects for two pathogens spreading on a network[J]. Physical Review Letters,2005,95(10):108701.
    [42]T. Gross, C. J. D. D'Lima, B. Blasius. Epidemic dynamics on an adaptive network [J]. Physical Review Letters,2006,96(20):208701
    [43]Bailey N T J. The mathematical theory of infectious diseases and its applications[M]. Charles Griffin & Company Ltd,5a Crendon Street, High Wycombe, Bucks HP136LE., 1975.
    [44]Y. Moreno, J. B. Gomez, A. F. Pacheco. Epidemic incidence in correlated complex networks[J]. Physical Review E,2003,68(3):035101.
    [45]M. E. J. Newman, S. Forrest, J. Balthrop. Email networks and the spread of computer viruses[J]. Physical Review E,2002,66(3):035101.
    [46]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京:清华大学出版社,2006.
    [47]L. Lloyd, R. M. May. How viruses spread among computers and people [J]. Science,2001, 292(5520):1316-1317.
    [48]Bu T, Towsley D. On Distinguishing Between Internet Power Law Topology Generators[C], In:D. Lee and A. Orda,eds. Proceedings of the Twenty First Annual Joint Conference of the IEEE Computer and Communications Societies(INFOCOM'02), New York:IEEE,2002:638-647.
    [49}http://deim.urv.cat/-aarenas/data/welcome.htm
    [5O]M. Girvan and M. E. J. Newman. Community structure in social and biological networks[J]. Proc. Natl., Acad. Sci., USA,2002,99(12):7821-7826.
    [51]http://www-personal.umich.edu/-mejn/netdata/
    [52JMarcel Salathe, James H. Jones. Dynamics and control of diseases in networks with community structure[J]. PloS Computational Biology,2010,6(4):e1000736.
    [53}Duanbin Chen, Linyuan Lv. Identifying influential nodes in complex networks[J]. Physica A,2012,391:1777-1787.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700