第24卷第10期(总第154期)2006年10月系统工程SystemsEngineeringVol.24,No.10Oct.,2006:100124098(2006)1020011204Ξ具有任意度分布的复杂网络拓扑结构建模方法邓宏钟,朱大智,吴俊,谭跃进(国防科学技术大学信息系统与管理学院管理系,湖南长沙410073)摘要:给出复杂网络节点连接度分布与节点度秩函数之间的数学关系,在此基础上提出一种具有任意度分布的复杂网络拓扑结构建模方法。以无标度网络和指数网络为例,验证该方法的有效性。关键词:复杂网络;度分布;度秩函数;无标度网络;指数网络:N945文献标识码:A前面所说的这些复杂网络拓扑模型及构造方法,要么是针对某类特殊的复杂网络进行的拓扑结构建模,要么就是从特殊的节点连接度序列开始的复杂网络拓扑结构的构造,因此,这些网络的拓扑模型及构造方法具有较大的局限性。目前学术界主要是以网络节点的度分布为基础来区分不同拓扑结构的复杂网络。则是否可以直接从节点连接度分布出发,构造出具有任意度分布、任意参数的复杂网络拓扑结构呢?这正是本文所要解决的问题。为了构造具有任意度分布、任意参数的复杂网络的拓扑结构,在第二节我们先引出度秩函数并给出节点连接度分布与度秩函数之间的关系,第三节以第二节给出的函数关系为基础,我们提出了一个具有任意度分布复杂网络拓扑结构的建模方法,并以无标度网络和指数网络为例进行仿真分析,验证本文方法的有效性。2节点连接度分布与度秩函数之间的关系复杂网络可以用图G=(V,E)来表示,其中图G是一1引言目前,复杂网络的研究正渗透到从物理学到生物学等众多不同的学科,逐渐成为多个学科共同关注的前沿热点1-4。而复杂网络拓扑结构建模是复杂网络研究的一个重要内容,我们期望构造出能够代表真实网络的拓扑结构,从而将对现实世界中复杂网络的研究“搬到”这些模型上来。对复杂网络拓扑结构建模的关键在于我们对复杂网络一般属性有多少了解,我们对复杂网络一般属性了解越多、越精确,我们在实验中构造的网络就越接近真实网络,对现实生活中复杂网络的研究就越有价值。1959年,Erdoβs和Rényi提出了一种随机网络模型(ER模型)5来描述现实生活中的复杂网络。1998年,Watts和Strogatz提出了具有小世界效应的小世界网络模型(WS模型)6。1999年,Barabási等在对万维网拓扑结构进行研究时,提出了节点连接度分布服从幂率分布(p(k)»kΚ)的无标度网络(scale2freenetwork)模型(BA模型)7。不管是随机网络模型(ER模型),小世界网络模型(WS模型),还是无标度网络模型(BA模型),它们都是针对某类特殊的网络进行的建模,并不能代表一般的复杂网个无向简单连通图,有N个节点,M条边,V={v1,v2,,vN}代表节点集合,E={e1,e2,,eM}ΑV×V代表边的集络建模。在文献8中,Dorogovtsev等人给出了一种有“肥合。令di表示节点vi的连接度,显然1≤di≤N-1。同时称大尾巴”的连接度分布的随机演化网络的构造方法。在文献9中,Palmer和Steffan给出了两种节点连接度分布为幂率分布的构造方法,即PLOD(Power2LowOut2Degree)算法和RTG(RecursiveTopologyGenerator)算法。文献10提出了一个给定度序列的随机图构造方法,文献11D={d1,d2,,dN}为图G的度序列,不失一般性,假设总有d1≥d2≥≥dN.由于不同的节点可能具有相同的连接度,如图1所示,将图G中的节点按照连接度降序排列成N-1段,其中第s段中节点的连接度均为N-s,令ls表示第s段中节点的数目,即网络中连接度为N-s的节点的数目。Ξ收稿日期:2006209206基金项目:国家自然科学基金资助项目(70501032)作者简介:邓宏钟(19742),男,国防科学技术大学信息系统与管理学院副教授,研究方向:复杂系统理论,人工智能和遗传算法。图1将节点按照连接度从大到小排序令p(k)表示图G的连接度分布,即节点恰好与其它kT3di=f(ri)=N-(8)个节点相连接的概率,令节点vi处于第si段,令ri表示节点vi的排序号,称di=f(ri)为图G的度秩函数,也就是将网络中的节点按照连接度的大小排序之后,节点的连接度di与节点排序号ri之间的关系函数。为了得到具有任意连接度分布,任意参数的复杂网络拓扑图,先给出节点度分布p(k)与度秩函数f(r)之间的关系。定理1具有度序列D={d1,d2,,dN}的图G的节其中,T3满足T3∫1(9)pk=N-sds=()ri证毕。由定理1可以得到任...