科学网 › 标签 › 盒计数法

标签: 盒计数法

相关帖子	版块	作者	回复/查看	最后发表

没有相关内容

相关日志

复杂网络的盒计数法: 热度 1 supermac 2010-12-13 21:09; 上一篇笔记后就开始忙毕业论文，之后又把做好的结论整理了一篇英文小论文，对网络分形的研究中断了，万分感谢周老师和章老师回复邮件答疑解惑！现在把后来的一些笔记整理一下。首先给出判断复杂网络分形与自相似的标准：结论 *在复杂网络研究中分形性和自相似性并不总是互相包含，一般而言，分形网络总是自相似的，但是自相似网络并不总是分形的。 * NB与lB之间满足幂律关系的网络就是分形的，该式既可用来判断网络是否分形，还可以求分形维数。 *用不同尺寸的盒子覆盖网络，以及在连续的重整化过程中网络都具有标度不变性，则称网络是自相似的。还有一点没有明确支撑，但是我认为应该是这样的，即标度不变性未必是幂律分布，度分布如果是指数分布且保持一致，也应该是自相似的。实际上复杂网络中讨论的大多是统计自相似，而不是科赫曲线、康托尘埃那样的几何自相似。也就是说这样的自相似网络中，部分和部分、整体和部分只是统计规律上表现出相同、相似的形态，从中取部分网络未必和其它部分或者网络整体看起来一致。盒覆盖法盒覆盖法本是用于传统分形几何的算法，可以求出在欧几里得空间中图形的分形维数， Song 等人将其推广到了复杂网络中。二者的区别在于复杂网络没有传统几何意义上的度量，节点的相对位置是任意的而不是固定的，节点之间的距离是用所经过的边的最少数量衡量的，而不是厘米、英寸等长度单位，这一点类似于路由算法中以跳数作为优化策略。首先介绍 Song 等人的盒覆盖法。图中每列表示用不同尺寸的盒子覆盖网络。规则是用最少的盒子数覆盖整个网络，盒子中节点之间的最大距离不能超过 lB ，即 lB=2 时节点之间的距离都是 1 ， lB=4 时节点之间的距离最大为 3 。每行表示用不变的盒子尺寸连续覆盖网络，即网络的连续重整化。将每个盒子整合为一个节点，盒子之间若原本有节点连接的话则在整合后的节点之间建立一条边。重复该过程直到网络最终化为一个节点。该方法的关键在于找到覆盖网络的最少的盒子数 NB ，而这个最少是有相当难度的。 Song 等人用的是穷举法，这样的话需要相当长的计算时间，对于我等草民靠 P8400 跑程序算数据的人来说简直是梦魇。 2007 年，文献的作者设计了另外一种盒覆盖法，该方法规则为：首先将所有节点置为未标记，每次随机选择一个节点作为种子，然后从该节点出发，以 lB 为路径长度对网络进行搜索（深度优先或者广度优先），找到的未标记节点就放入一个盒子中，重复该过程直到所有节点都放进盒子里。如图 a ， lB=1 ，随机选择节点 1 ，则从点 1 一步可达的节点放入红圈盒子中；第二步随机选择节点 2 ，在从点 2 一步可达的 4 个节点中只有节点 3 还不属于旧的盒子，所以新的粉色盒子中只包含节点 3 ；第三步随机选择节点 3 ，同理，点 2 和点 4 以被标记，所以新的绿色盒子只包含点 3 左侧的三个节点；最后一步，随机选择点 4 ，把最后的一个节点划入新的蓝色盒子中。需要注意的是，盒子中的节点不一定要相互连接，如绿色盒子。图 b 表示图 a 的最小支撑树，是为了证明文献的结论，显然二者的划分不同但是盒子数相同。据文献， RS 方法随机选择盒子的中心节点，因此盒子之间可以重叠。这种情况下，预先分配的盒子中的节点不会包含在新盒子中，因此每个盒子中的节点不一定是彼此连接的，而是可以通过其它盒子中的节点相互连接。当然了，这样的情况要算做一个盒子。这样的计数规则在分形网络中是必要的，如果不允许这种不连接的盒子，则观察不到无标度的分形行为。实证结果显示， RS 法可以获得与传统盒计数法相同的分形维数。在这三篇文献中，作者反复强调该方法找到的盒子数不是最少的盒子数，但中又说 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.; 个人分类: 科研资料|11124 次阅读|4 个评论

更多...

帐号		自动登录	找回密码
密码			注册

关闭 安全验证

标签: 盒计数法

相关帖子

相关日志

关闭安全验证