资源描述:
《复杂网络研究进展_模型与应用》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、小型微型计算机系统2011年2月第2期JournalofChineseComputerSystemsVol132No.22011复杂网络研究进展:模型与应用112詹卫华,关佶红,章忠志1(同济大学计算机科学与技术系,上海201804)2(复旦大学计算机学院,上海200433)E-mai:l08zhanwh@tongj.iedu.cn摘要:作为研究各种复杂系统的一种通用工具,复杂网络已经在许多学科中产生了深刻地影响,引起了各领域学者的广泛关注.本文全面地介绍复杂网络的各种主要统计特性和最具有代表性的
2、网络模型,并且对计算机科学中关注的语言网络,Internet和P2P这些现实网络,从复杂网络的角度进行分析,展示了复杂网络理论和方法在这些领域中的应用和得到的重要结果.关键词:小世界网络;无标度网络;度分布;聚类系数中图分类号:TP311文献标识码:A文章编号:1000-1220(2011)02-0193-10AdvanceintheResearchofComplexNetwork:ModelandApplication112ZHANWe-ihua,GUANJ-ihong,ZHANGZhong-z
3、hi1(DepartmentofComputerScienceandEngineering,TongjiUniversity,Shanhai201804,China)2(SchoolofComputerScience,FudanUniversity,Shanhai200433,China)Abstract:Asancommontoolforstudyingvariouscomplexsystems,complexnetworkhasmadedeeplyeffectonmanydiscipline,
4、andhasattractedwideattentions.Variousimportantstatisticalpropertiesofcomplexnetworkanddominantnetworkmodelsaread-dressed.Moreover,weanalysesomerea-llifenetworkssuchaslanguagenetworks,WWWandInternetthatareofinterestincompu-terscience,andshowtheapplicat
5、ionoftheoryandmethodsofcomplexnetworktothesefields.Keywords:smal-lworldnetwork;scale-freenetwork;degreedistribution;clusteringcoefficient[4]1引言Science上发表的无标度网络(Scale-freeNetworks)直接推动了人们对从简单规则网络转向了复杂网络的研究,并进而自然界和人类社会中存在各种各样的复杂系统.这些系掀起了复杂网络研究的空前的浪潮.复杂网
6、络已经成为系统统由许多相互联系的单元构成,网络是描述复杂系统最自然科学,复杂性科学和统计物理学研究的中心和焦点.它作为一的工具)))节点表示系统组成单元,边表示单元间的联系.在种研究模式或者手段,已经渗透到生物学、医学、计算机科学、我们周围环绕着形形色色的网络:节点表示web页面,边来社会学和管理学等众多领域,并成为研究热点.表示页面间的链接,这就形成了www网络;节点表示作者,边表示两人在同一篇科学文献中合作,就形成了合著者网络;2复杂网络的结构特性节点表示底物,边表示底物间发生的生化反应,就形
7、成了代谢简单地说,复杂网络就是比规则网络具有更复杂拓扑特网络.性的网络.具体地,这些特性包括:平均距离、度分布、簇系数、网络在数学上用图来表示,因此网络的研究源于对图的度-度相关性、社区结构和层次性等.研究.1736年,著名的瑞士数学家欧拉为了解决KÊnigsberg2.1度、度分布和度相关性(DegreeCorrelation)七桥问题,发表了第一篇图论文章.图(Graph)这个词第一次无向网络的节点的度(Degree)是指与节点连接的边数;出现在Nature期刊上.进入20世纪30年代,出现了
8、一大批精而有向网络的节点的度分为入度(In-degree)和出度(Ou-tde-彩的关于图的新理论和结果.gree).网络中所有节点度的列表称为度序列(DegreeSe-除了在数学上图论方面的发展,网络在社会科学中也受quence),度序列的平均值称为网络的平均度,记为.给到了广泛的研究.社会网络分析在十九世纪20年代早期就开定了网络的度序列就确定了该网络的度分布(DegreeDistr-i始发展,当时研究者把目光投向了社会实体间的关系,如组织bution).度分布是指从图中