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

标题: 复杂网络的盒计数法 [打印本页]

作者: snachina    时间: 2019-7-13 15:23
标题: 复杂网络的盒计数法
*在复杂网络研究中分形性和自相似性并不总是互相包含,一般而言,分形网络总是自相似的,但是自相似网络并不总是分形的。
*NB与lB之间满足幂律关系的网络就是分形的,该式既可用来判断网络是否分形,还可以求分形维数。
*用不同尺寸的盒子覆盖网络,以及在连续的重整化过程中网络都具有标度不变性,则称网络是自相似的。
还有一点没有明确支撑,但是我认为应该是这样的,即“标度不变性未必是幂律分布,度分布如果是指数分布且保持一致,也应该是自相似的”。实际上复杂网络中讨论的大多是“统计自相似”,而不是科赫曲线、康托尘埃那样的“几何自相似”。也就是说这样的自相似网络中,部分和部分、整体和部分只是统计规律上表现出相同、相似的形态,从中取部分网络未必和其它部分或者网络整体看起来一致。
盒覆盖法

盒覆盖法本是用于传统分形几何的算法,可以求出在欧几里得空间中图形的分形维数,Song等人将其推广到了复杂网络中。二者的区别在于复杂网络没有传统几何意义上的度量,节点的相对位置是任意的而不是固定的,节点之间的距离是用所经过的边的最少数量衡量的,而不是厘米、英寸等长度单位,这一点类似于路由算法中以“跳”数作为优化策略。

首先介绍Song等人的盒覆盖法。

图中每列表示用不同尺寸的盒子覆盖网络。规则是用最少的盒子数覆盖整个网络,盒子中节点之间的最大距离不能超过lB,即lB=2时节点之间的距离都是1lB=4时节点之间的距离最大为3。每行表示用不变的盒子尺寸连续覆盖网络,即网络的连续重整化。将每个盒子整合为一个节点,盒子之间若原本有节点连接的话则在整合后的节点之间建立一条边。重复该过程直到网络最终化为一个节点。该方法的关键在于找到覆盖网络的最少的盒子数NB,而这个“最少”是有相当难度的。Song等人用的是穷举法,这样的话需要相当长的计算时间,对于我等草民靠P8400跑程序算数据的人来说简直是梦魇。

2007年,文献[6]的作者设计了另外一种盒覆盖法[11-13],该方法规则为:首先将所有节点置为“未标记”,每次随机选择一个节点作为种子,然后从该节点出发,以lB为路径长度对网络进行搜索(深度优先或者广度优先),找到的未标记节点就放入一个盒子中,重复该过程直到所有节点都放进盒子里。

如图alB=1,随机选择节点1,则从点1一步可达的节点放入红圈盒子中;第二步随机选择节点2,在从点2一步可达的4个节点中只有节点3还不属于旧的盒子,所以新的粉色盒子中只包含节点3;第三步随机选择节点3,同理,点2和点4以被标记,所以新的绿色盒子只包含点3左侧的三个节点;最后一步,随机选择点4,把最后的一个节点划入新的蓝色盒子中。需要注意的是,盒子中的节点不一定要相互连接,如绿色盒子。

b表示图a的最小支撑树,是为了证明文献[6]的结论,显然二者的划分不同但是盒子数相同。

据文献[13]RS方法随机选择盒子的中心节点,因此盒子之间可以重叠。这种情况下,预先分配的盒子中的节点不会包含在新盒子中,因此每个盒子中的节点不一定是彼此连接的,而是可以通过其它盒子中的节点相互连接。当然了,这样的情况要算做一个盒子。这样的计数规则在分形网络中是必要的,如果不允许这种“不连接的”盒子,则观察不到无标度的分形行为。实证结果显示,RS法可以获得与传统盒计数法相同的分形维数。

在这三篇文献中,作者反复强调该方法找到的盒子数不是最少的盒子数,但[11]中又说“In this study, for simplicity, we choose the smallest number of boxes among all the trials.”只是为找到这样的最少数需要大约O(10)次Monte Carlo试验。如此来看到底要不要找这个最少数呢?如果不需要的话,算法会简单很多,一次运算后就可以得到所要的盒子数。只是暂时不知道每次找到的盒子数波动会不会很大。

6.        PhysRevLett_96_018701_2006--Skeleton and fractal scaling in complex networks.
11.        CHAOS-17-2007-026116--box-covering algorithm for fractal scaling in scale-free networks.
12.        PhysRevE_75_016110_2007--Fractality in complex networks Critical and supercritical skeletons.
13.        NJP-9-2007-177--Fractality and self-similarity in scale-free networks.






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