社会网络分析论坛 social network analysis forum

标题: 复杂网络的分形与自相似 [打印本页]

作者: snachina 时间: 2019-7-13 15:23
标题: 复杂网络的分形与自相似
用模块生成的等级网络具有一个明显的特征就是自相似性，是分形的一个基本特征。讨论复杂网络中的自相似问题有如下几篇重要文献：
显然，Song、Havlin和Makse的两篇文章享有最高的引用率。
在文献[3]中，作者先提出了一个疑问，即现实世界中的很多网络具有小世界特征，意味着网络的平均路径长度随网络规模对数增长，L(N)~logN，等价表达式为

，自相似则要求二者之间是幂律关系。但是，跟多具有小世界特征的网络，如WWW、社会网、PIN、细胞网等在某种长度标度下具有自相似性。那么该如何协调这个矛盾呢？作者将20世纪30年代就已经开始在整形空间中使用的盒计数法推广到了复杂网络中，定义盒子尺寸lB为盒子中任意两点之间的距离都小于lB，然后节点不重叠地覆盖整个网络，并保证所用盒子数NB最少。如果有

，则网络是自相似的，dB为分形维数，也称为自相似指数。然后作者对网络进行了重整化，证明在整个粗粒化过程中，网络都具有无标度性和自相似性，即度分布在重整化下的标度不变性。作者还介绍了一种簇增长法并与盒覆盖法进行了对比，研究了多个标度指数之间的关系，这里暂不讨论。这篇文章的最大价值应该在于找到了判断复杂网络是否自相似的途径，就是用盒覆盖法对网络进行重整化，若这个过程中度分布的标度不变，则网络是自相似的。
随后，他们三人又写了另一篇文章[4]来讨论复杂网络上分形结构的起源。开头提到分形的概念“the structures of which look the same on all length scales”显然是一种各个标度上的相似。文章通篇以具有拓扑分形的WWW、PIN、新陈代谢网和不具有拓扑分形的Internet为例来介绍展开讨论。作者认为分形网络一般具有小世界特征和无标度特征以及等级结构，随机连接和优先连接都不能解释分形现象。作者发现无标度网络模型不具有分形特征。分形结构源自一种相关的自相似模块方式增长，而不是优先连接模型的不相关式的增长。自相似的分形网络的出现是由于所有长度标度上hub节点的强烈相互排斥引起的。换句话说，hub节点倾向于连接具有较少连接的节点而不是其它的hub节点，这种效应可看作有效的hub排斥。在这样的模式下，尽管还有穷人，但富人更富。换句话说，hub节点通过优先连接那些连接较少的节点来增长，以生成鲁棒性更强的分形拓扑。相比之下，较弱的反相关或不相关增长则导致非分形的拓扑结构，如Internet，这样的结构是自相似也有小世界特征，但非分形，hub节点相互连接使得网络容易遭受蓄意攻击。这种自相似的组织方式也可以产生等级结构。
这两篇文章中，作者并不严格区分分形和自相似的概念，基本是等同的，只是表达的侧重点不同。自相似偏重于描述标度不变性，整体与部分，部分与部分相似；而分形则侧重于描述整体的拓扑结构和鲁棒性。
不久后，Gallos又与Song和Makse合作写了一篇关于网络分形和自相似的小综述。文中澄清或阐明了这么几个问题：1.fractality指的就是不同标度上的自相似。2.分形与小世界的矛盾点在于“网络中甚至不存在不同的长度标度，因此这两个特征在同一个网络中无法共存”。这句是原文翻译，我没大看懂，大概是因为这句话原本就是讲不通的，分形和小世界可以和平共处。3.判断网络分形的方法就是盒覆盖法，然后看是否满足

。分形网络具有有限的维数，而非分形网络的维数趋于无穷大。4. 尽管传统的分形理论并不严格区分分形和自相似，但是在复杂网络的研究领域中这两个性质是截然不同的。分形网络指那些维数取有限值的情况，而自相似网络指在重整化过程中具有标度不变性的网络。5.所有的分形网络都属于无标度网络类。6.分形结构对网络的影响在于鲁棒性、网络流和模块化。
文献[6]研究的也是无标度网络中分形的起源，用的工具是最小支撑树。文章引言部分先对几个重要概念下了定义，小世界和无标度无须赘述，作者将NB和lB之间的幂律关系

定义为分形标度(fractal scaling)，而自相似性指度分布的标度不变性(scale invariance)。作者证明了网络的分形拓扑源自于低层的支撑树结构。作者验证网络是自相似的方法是用盒覆盖法对网络进行粗粒化，如果用不同尺寸的盒子覆盖网络，以及在连续的重整化过程中网络都具有标度不变性，则称网络是自相似的。
类似的，文献[7]将幂律关系

定义为分形行为(fractal behavior)，那么于是产生疑问是否可以理解为，判断是否分形的标准是

而判断自相似的标准是标度不变性？是否需要同时满足标度不变性在“用不同尺寸的盒子覆盖网络”和“连续的重整化过程”中都成立才能称为自相似？若满足关系

的网络就是分形的，如果又发现标度不变性不存在，则网络就不具有自相似性了？分形但不自相似——这岂不与分形的概念相左？文献[7]还提到在等级网络中，除了小世界和无标度特征，存在聚类系数和节点度之间的幂律关系

，是否意味着等级网络必然是小世界和无标度的？

网络拓扑性质之间的相互关系
1.    无标度与小世界：二者是复杂网络的两个重要特征，没有必然联系，小世界网络的度分布可以服从幂律，也可以服从指数分布，如WS小世界模型。
2.    无标度与等级结构：无标度网络中必然有少量节点拥有大量连边，即hub节点，其它节点只需要连在hub节点上就可以连入网络，因此不需要太大的度，也不需要相互连接。因此hub节点的聚类系数必然小，也就是度与聚类系数的反比关系，这样就有可能出现等级结构要求的幂律关系。当然了hub节点之间的连接方式对网络结构也有重要影响，如前文所述的hub吸引与hub排斥。
3.    小世界与分形：完全的hub吸引（hub节点只和其它hub节点连接）使网络任意两点间存在捷径的可能性大大增大，最短路径长度缩短，即小世界，但此时是没有分形结构的；而完全的hub排斥会产生分形结构但与此同时会破坏小世界效应。但实际上网络的形成机制不可能这么单一，必然是两种方式的结合，因此网络既可以是小世界的，同时又是分形的。
4.    无标度与分形：目前的无标度网络模型如BA模型等都不能产生分形结构，但是实际中存在分形无标度网络，二者并不矛盾。
5.    分形与自相似：很多现实网络无论是否分形都具有长度标度不变性，即自相似网络未必都有分形结构。
6.    分形与等级结构：分形/自相似网络经常是具有等级结构的，描述了系统的模块性。

欢迎光临社会网络分析论坛 social network analysis forum (http://snachina.com/)