资源描述：
《复杂网络中重要性节点发掘综述_赫南》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、计算机科学2007Vol134№1123复杂网络中重要性节点发掘综述1231赫南李德毅淦文燕朱熙12(北京航空航天大学计算机系北京100083)(电子系统工程研究所北京100039)3(清华大学计算机系北京100084)1摘要发掘网络中重要性节点(边)一直是图论领域的一个基本问题。随着近年来复杂网络研究热潮的兴起,特别是很多实际网络所抽象出来的复杂网络,表现出了与以往图理论不同的特性,如小世界特性、无尺度特性等。如何在复杂网络环境下,发掘重要性节点已经成为复杂网络研究的一个基本问题。本文简要介绍了复杂网络的基本概念,详细总结、分析了在复杂网络环境下几个领域中发掘重要性节点
2、的方法,最后提出了这一领域内几个有待深入研究的问题和可能的应用方向。关键词复杂网络,节点重要性,图,相对重要性MiningVitalNodesinComplexNetworks1231HENanLIDe2YiGANWen2YanZHUXi(DepartmentofComputerScience,BeijingUniversityofAeronauticsandAstronautics,Beijing100083)1(InstituteofElectronicSystemEngineering,Beijing100039)2(DepartmentofComputerScie
3、nce&Technology,TsinghuaUniversity,Beijing100084)3AbstractMiningvitalnodes/edgeshasalwaysbeenabasicprobleminGraphTheory.AsthestudyofComplexNet2workshasbecomemoreandmorehot,especiallythattherearelotsofreal2worldnetworksthatcanbemodeledasCom2plexNetworks,whichalsohavemanyimportantpropertiesd
4、ifferentfromthoseinthetraditionalGraphTheory,e.g.small2worldproperty,scale2freeproperty,etc.HowtominevitalnodesinComplexNetworkshasbecomeanew2bornproblem.ThispaperreviewssomebasicconceptsofComplexNetworks,summariesandanalysessomeclassicmeas2uresofminingvitalnodesinsomefields,andpredictsso
5、mefurther2studiedquestionsandpossibleapplications.KeywordsComplexnetworks,Vitalnodes,Graph,Relativeimportance连一条边,反之则不连边,有边相连的两个节点在网络中被看1引言:无处不在的复杂网络作是相邻的。数学在研究网络的时候,只关心节点之间有没自然界中存在的大量复杂系统都可以通过形形色色的网有边相连,至于节点在什么位置、边是什么形状等都是不需要络加以描述,网络是由许多节点与连接节点之间的边组成的。关心的。通常把不依赖于节点的具体位置和边的具体形态所[1]其中,节点代表
6、真实系统中不同的个体,而边则代表这些个体表现出来的网络结构叫做网络拓扑。之间的联系。通常,当两个节点之间具有某种特定的关系则图1复杂网络实例3)国家自然科学基金(60496323,60375016),现代设计大型应用软件的共性基础973计划(2004CB719401)。赫南硕士,研究方向:不确定性人工智能、复杂网络、网络化数据挖掘。1节点的重要性根据所抽象的不同网络具有不同的含义,例如核心性、声望、吞吐量等。这里用重要性表达一种通用的定性概念。·1·复杂网络(ComplexNetworks)并没有精确严格的定义,化结构特征,可以直观地显示哪些节点是相连接的。同样,对它可以
7、看作是大量真实复杂系统的拓扑抽象。它既不是规则网络的属性进行定量的刻画也是非常重要的,尤其是当网络网络,也不是随机网络,而是具有与两者皆不相同的统计特征的规模和复杂度非常大的时候,使用图形的表示来分析问题的网络。复杂网络在现实世界中无处不在,如社会领域的社就非常困难了。在各种复杂网络中,用定量分析的方法寻找[2][3]会关系网络、科学家合作者网络;信息领域的WWW网超大规模网络中哪个节点(边)最重要,或者某个节点相对于[4][5][6]络、论文引用网络;技术领域的自治层Internet、软件类其他一个或多个节点的重要程度,是复
