基于图论的网络鲁棒性增强算法  

Enhancing algorithm for network robustness based on graph theory

作　　者：祝延波[1,2] 傅建明[2] 王丽娜[2] 

机构地区：[1]青海民族大学物理与电子信息工程学院,青海西宁810007 [2]武汉大学计算机学院,湖北武汉430079

出　　处：《兰州理工大学学报》2010年第5期83-87,共5页Journal of Lanzhou University of Technology

基　　金：国家自然科学基金重大研究计划(90718006);青海省科技厅软科学项目(2008-Z-615)

摘　　要：针对网络节点抗漏洞攻击能力弱、网络鲁棒性差的情况,提出一种基于图论的鲁棒性增强算法.首先介绍基于图论和多样性的网络鲁棒性策略,提出节点相关度的概念、分类描述及量化指标;其次分析多样性对各种漏洞攻击的作用.对采用该算法生成的一种30个节点、4种着色方案的图进行详细分析,对由本算法生成的六种图的统计特征进行归纳.实例表明,依照该算法构建的网络是一种较均匀的网络,这种网络能有效增强节点的抗漏洞攻击能力,阻断各种可能的漏洞攻击在节点之间的渗透和传播,减少相继故障,避免雪崩效应,具有较强的鲁棒性.Aimed at the cases of poor ability against vulnerable attack upon network node and poor network robustness,an enhancing algorithm for network robustness was proposed based on graph theory.The strategy for network robustness based on graph theory and diversity was introduced first,and then,the concept,categorizing description and quantitative index of node correlativity were proposed.The effect of diversity on various vulnerable node attacks was analyzed,also.The graphs derived from this algorithm with 30 nodes and 4 coloring were analyzed in detail.The statistical characters of 6 graphs generated according to this algorithm were induced,also.An actual example showed that the networks constructed according to this algorithm were more balanced network which could enhance the node ability of anti-vulnerable attacks,interdict infiltration and propagation of various possible vulnerable attacks between nodes,cut down the possibility of network cascading failure,avoid the avalanche effects so that the network would be made to have stronger robustness.

关 键 词：图论 网络鲁棒性 节点 多样性 漏洞 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]