基于信息维数的复杂网络自相似性的研究

《基于信息维数的复杂网络自相似性的研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基于信息维数的复杂网络自相似性的研究报告人:陶少华导师:刘玉华教授2006年6月引言BA模型的扩展复杂网络的自相似性研究仿真分析结论参考文献1.引言1960年数学家Erdos和Renyi提出了随机图理论，研究复杂网络中随机的拓扑模型，自此ER模型一直是研究复杂网络的基本模型。但是，但是近年的研究发现：现实网络中得到的许多实验数据结果与随机图模型并不符合，因此需要新的网络模型合理描述实际网络。1998年Watts和Strgatz提出了小世界（WS）模型[2]，刻画了真实的网络所兼有的大聚簇和短平均路径距离的特性。然而现实世界中的网络还被统计到极少数接

2、点拥有大量的连接，而众多的接点仅具有少量连接的特性，这些也无法用随机图模型加以合理解释。999年Barabasi和Albert提出了无尺度模型（BA）[3]。BA模型指出了决定互联网、万维网等网络具有无尺度模型的两个基本原理：增长性和择优连接。虽然小世界网络与无尺度网络刻画了网络的基本特性，但它们是基于对现实网络进行简化的前提下得到的结果。因此我们有必要对复杂网络建模进行深入研究，使它更加符合现实世界。本文提出了网络的自相似性，网络通过节点与节点相连汇聚形成，节点与节点之间是通过某种共性而连接在一起的。如人际关系之间的“物以类聚，人以群分”。。2.

3、BA模型的扩展BA模型在研究在引起了很多人的注意。除了对模型本身进行定性或定量研究外，很多人建议应扩展或修正该模型，使其行为更接近实际网络。BA模型认为顶点的年龄和度数之间有相关性，而Adamic和Huberman发现实际的WWW网中没有这一性质。因为他们认为，顶点的度是其内在价值的函数，有些Web站点对相对较多的人有用，因而就有更高的连接率。Bianconi和Barabasi通过模仿这一过程提出了BA模型的一个扩展模型。在他们的扩展模型中，每个新出现的顶点i都赋予一个“适应度”fi,它代表该顶点的吸引力和由些而产生新连接的倾向。适应度是从某一分布

4、中选取的。新边连接到顶点i的概率不是与顶点的度数ki成比例，而是与kifi成比例。模型算法如下：（1）开始总共有N个节点，每一个节点i分配一个度fi，fi是一个真实的数值为了测量它的重要性或级别。度值是一个从给定的概率p(x)中随机获得的数字。对每一对节点，i,j相连接的概率是f(xi,xj),f(xi,xj)依赖于在xi,xj上两个顶点的重要性。“度的重要性”或适应度在复杂网络领域中已经成功的介绍过了，但在BA模型中是作为一种附加的成份。当然，在这里通过消除择优规则而强调适应度的重要性。正如所定义的，模型是静态的，但通过在每一时间步里加入新的节点

5、可以把它看作动态的，通过上述规则把它们连接到已存在的节点上。对BA模型的另一推广就是顶点拷贝模型。Kleinberg等人认为有些模型是通过拷贝顶点来生长的。他们对Web网的生长感兴趣，其模型介绍如下。该网络通过随机地增加顶点、随机地增加边或从其他顶点拷贝边来进行生长。特别地，我们先选择一个已经存在的顶点及M条边，然后确定这M条边的目标顶点，通过随机地选择其他顶点或拷贝这M条边的目标顶点，即可完成一个网络图的生长。如果所选顶点出席小于M，则其M条边将是拷贝的，且一个顶点接一个顶点地拷贝它的边，直到M条边都拷贝完为止。显然，拷贝机制将会产生幂律度分布。

6、随机选取某个顶点，它的一条边连向入度为K的其他某个特定顶点的概率是与K与比例的。因而，一个顶点的度数的增加与其当前度数成比例。但这会出现一种特殊情况，即当前度数为0的顶点将永远不会获取新的边。3.自相似性复杂网络3.1问题的提出虽然BA扩展模型描述现实世界中网络最基本的特性，但它们仍然存在一定的局限性。在现实世界中一些网络常常并不具有幂律特征，如指数中止、小变量饱和等。为了在微观层面更深入研究复杂网络的拓扑结构和演化规律，研究人员作了大量新的尝试和努力，对网络的演化与建模已经有了长足的进展，演化因素包括各种类型的择优连接、局域世界、竞争等。尽管众多

7、的网络演化模型已经被用来分析和研究可能潜藏的演化规律，但这些研究仍然忽视了一些重要因素。例如计算机网络节点之间的连接。如果是按照择优连接概率：则新的节点会全部连接到同一个节点上，但现实网络并非如此，而是形成不同的集散节点。这个例子说明了网络节点之间的连接有可能是基于一些相似的性质，节点与节点之间有某种共性才相连。因此建立并研究基于相似性的网络演化模型有利于我们更好地认识现实世界中的复杂网络。3.2自相似性网络容量维数1975年美国数学系教授曼德布罗特首次提出了“分形”概念，其原意是“不规则的、非整数的、支离破碎的”物体，我们把具有某种自相似性的图形

8、或集合称为分形。大自然中存在的不规则的物体，可能存在不同尺度上的相似性，称为自相似性。自相似性就是局部与整体相似，局部中又