分形网络的理论、算法及应用研究

发布时间：2019-11-14 07:37

【摘要】：复杂网络是复杂系统的抽象和重要的研究工具。对复杂网络的拓扑结构的研究是最基础也是最重要的方面之一。自从Song等人2005年在"Nature"上发表文章,通过引入重整化群分析方法揭示了复杂网络中许多实际网络的分形性和自相似性,复杂网络的分形特征研究也成为复杂网络研究的一个重要的方向。复杂网络中的分形研究主要集中在以下几个方面：分形起源研究,分形的定义,分形的算法,分形网络的性质等。本文主要研究复杂网络中分形结构的起源,算法和应用,主要内容及创新有以下几个方面：(1)提出了一种新的分形网络增长模型,该模型生成的网络为当前分形结构涌现的原因的反例。研究者广泛认为,复杂网络中的分形的涌现是由于Hub节点之间的排斥性。这个假设通过Song等人提出的动态增长的分形网络模型得到。我们发现该模型假设所有的跨盒子的边连接到Hub的概率e都是相同的。因此,我们使用可变的概率e修改了该模型,使得Hub之间的连接概率较大,非Hub的连接概率较小。通过新的模型,我们得到了具有Hub吸引特性的分形网络。同时,我们还发现现实中的演员合作网络也具有同样的性质。因此,我们提出结构均衡的概念来解释分形特性的涌现。此外,我们还对随机网络的分形产生的条件进行了数学推导,发现结论为要求节点之间的距离的分布呈Frechet分布。(2)提出了两种能得到更精确解的分形的盒子覆盖算法。复杂网络的分形结构的分析通常使用盒子覆盖法。在盒子覆盖法中,如何使用最小的盒子数量来役盖整个网络是一个NP难的问题。研究者们提出了许多的算法来提高算法的精确性。首先,我们引入了差分演化算法对盒子覆盖问题进行优化。在不同结构上网络上进行对比,发现我们算法的解大部分情况下都比当前最优的算法更精确。其次,为了减小算法的时间复杂度和减小搜索空间,我们提出了基于离散粒子群优化的盒子覆盖算法,并将该算法扩展到加权网络中。实验结果表明,我们的算法的解相对当前的算法具有稳定的改进。(3)提出了一种以分形模块度和最小化盒子数量为目标的多目标盒子覆盖算法。根据标度理论,研究者们通过重整化群方法对网络在不同尺度上的统计特性进行分析。通常采用盒子覆盖法来进行重整化分析,在这个分析的过程中,研究者发现分形模块度与网络的信息传输有密切关系。如何使盒子覆盖能得到准确的分形模块度对网络结构的研究非常重要,但是,当前的分形算法都没有考虑到对分形模块度进行优化。而且,我们发现分形模块度目标的一部分和最小化盒子的目标负相关,为了解决这种困境,我们提出了多目标粒子群优化的盒子覆盖算法。我们采用分解的方式来接近Pareto前沿。实验结果表明,我们的算法在各个目标上得到的结果都比当前算法优。并且,我们得到的盒子覆盖与实际网络的层次机构更接近。(4)对社会编程GitHub网络进行了实证研究。首先,针对GitHub平台中存在许多大型项目的开发者之间未必有实际的合作关系这样的现象,引入了边的权重来移除弱连接的边。通过重整化群分析,发现GitHub网络在移除弱连接的边之后网络结构从小世界变化为分形网络。此外,对网络的Pearson相关系数和邻居相关度的分析后发现网络具有很强的同配性,验证了之前对分形涌现的研究结论。其次,通过超网络建模的方式分析GitHub网络的演化特征,并根据分析结果提出了新的超网络增长模型。该模型考虑了知识的多样性,并且综合了基于超度和基于知识量的优先连接策略。实验结果表明,该模型能更好的模拟实际网络。
【图文】：

方程,分形特征,倍周期

图２．１：OT）Ｌｏ．ｇｉｓｉｉｃ方程的倍周期，（６）邋Ｌｏ如ｓ执；方程巧混化区的分形特征。该困Ｘ轴为ｒ的取逡逑值，ｙ轴为种群数量，图中的点代表系统的稳定值。图片引自文献脚：／。逡逑分形和混浊是两个紧密巧系不可分割的研究领域混淹是指非线性系统的逡逑一种表面上无规律而实际上隐含着一定的规律的现象。比如，大家所熟知的＂蝴蝶效逡逑

自相似,线段,维度,立方体

图２．２：传统几何结构的自相似化：线段，正方形，立方体在初始时刻〔图左列），与经过一次增逡逑长居〔图中列）。逡逑如图２．２所示，对于线段，有ｇ二３和ａ邋＝邋３，因此线段的自相似维度＿０邋＝邋１；对逡逑于正方形，有ｇ邋＝邋２和ａ邋＝邋４，因此正方形的自相似维度方＝２，对于立方体，有逡逑９邋＝邋２和ａ邋＝邋８，因此立方体的自相似维度Ｄ邋＝邋３。标度因子可ＬNB取任意整数，得到的逡逑结果是一样的。可＾＾看到线段，正方形，立方体的自相似维度与传统的维度一致，下逡逑面我们计算几个分形图形的自相似维度。逡逑如阐２．３所不，３故口记５］＾垫片的边长标度因子９邋＝邋２，，子模块的数扇为（１邋＝邋３，逡逑因此，Ｓｉｅｒｐｉｎｓｋｉ垫片的自相似维度＿０邋＝邋ｌｏｇ３／ｌｏｇ２邋１．５８５０。另如图２．４所示，逡逑Ｓｉｅｒｐｉｎｓｋｉ地毯的边长标度因子ｇ邋＝邋３，子模块的数巧为ａ邋＝邋８，因此，Ｓｋｒｐｉｎｓｋｉ垫片逡逑的自相似维度邋0邋二邋ｌｏｇ８／ｌｏｇｓ邋１．８９２８。逡逑－１０－逡逑
【学位授予单位】：武汉大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：O157.5

【相似文献】