复杂网络的盒计数法

snachina

*在复杂网络研究中分形性和自相似性并不总是互相包含，一般而言，分形网络总是自相似的，但是自相似网络并不总是分形的。
*NB与lB之间满足幂律关系的网络就是分形的，该式既可用来判断网络是否分形，还可以求分形维数。
*用不同尺寸的盒子覆盖网络，以及在连续的重整化过程中网络都具有标度不变性，则称网络是自相似的。

还有一点没有明确支撑，但是我认为应该是这样的，即“标度不变性未必是幂律分布，度分布如果是指数分布且保持一致，也应该是自相似的”。实际上复杂网络中讨论的大多是“统计自相似”，而不是科赫曲线、康托尘埃那样的“几何自相似”。也就是说这样的自相似网络中，部分和部分、整体和部分只是统计规律上表现出相同、相似的形态，从中取部分网络未必和其它部分或者网络整体看起来一致。

盒覆盖法

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

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

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

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

如图a，lB=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.