Fractality in complex networks: Critical and supercritical skeletons
Fractality in complex networks: Critical and supercritical skeletons
复制标题
DOI：
10.1103/physreve.75.016110
复制
发表时间：
2007-01-01
影响因子：
2.4
通讯作者：
Kim, D.
中科院分区：
文献类型：
--
作者：
Kim, J. S.;Goh, K. -I.;Kim, D.
分形缩放-一个幂律行为的盒子的数量需要平铺一个给定的网络相对于横向尺寸的盒子-进行了研究。我们引入了一个盒子覆盖算法，它是由Song [Nature（伦敦）433，392（2005）]引入的原始算法的修改版本;该算法使得易于实现。分形网络被视为包括骨架和快捷方式。骨架嵌入在原始网络的下面，是一种基于边介数中心性的特殊类型的生成树;它为网络的分形性提供了一个支架。当骨架被视为一个分支树，它表现出一个平台的平均分支数作为一个函数的距离根。另一方面，对于非分形网络，平均分支数衰减到零而不形成平台。基于这些观察，我们通过结合随机分支树和局部捷径来构建分形网络模型。支架分支树可以是临界的或超临界的，这取决于给定网络的小世界性。对于由临界（超临界）分支树构造的网络，在簇生长方法中，给定盒子内的平均顶点数根据幂律（指数）形式随着盒子的横向大小而增长。临界骨架和超临界骨架分别在蛋白质相互作用网络和万维网中被观察到。箱形质量的分布，即，每个盒子内的顶点数遵循类似于M-eta的幂律P-m（M）。指数eta取决于盒子横向尺寸中心点（B）。对于较小的中心点（B），eta等于给定无标度网络的度指数gamma，而当中心点（B）增加时，eta接近指数tau=gamma/（gamma-1），这是随机分支树的簇大小分布的指数。最后，我们研究了给定盒α的周长H α，即，连接到给定盒α的不同盒的边的数量，作为盒质量M-B、M-alpha的函数。得到了具有盒质量M-B的盒上的平均周长可能缩放为类似于M-B的< H（M-B）>，而与盒大小中心点（B）无关。
Fractal scaling-a power-law behavior of the number of boxes needed to tile a given network with respect to the lateral size of the box-is studied. We introduce a box-covering algorithm that is a modified version of the original algorithm introduced by Song [Nature (London) 433, 392 (2005)]; this algorithm enables easy implementation. Fractal networks are viewed as comprising a skeleton and shortcuts. The skeleton, embedded underneath the original network, is a special type of spanning tree based on the edge betweenness centrality; it provides a scaffold for the fractality of the network. When the skeleton is regarded as a branching tree, it exhibits a plateau in the mean branching number as a function of the distance from a root. For nonfractal networks, on the other hand, the mean branching number decays to zero without forming a plateau. Based on these observations, we construct a fractal network model by combining a random branching tree and local shortcuts. The scaffold branching tree can be either critical or supercritical, depending on the small worldness of a given network. For the network constructed from the critical (supercritical) branching tree, the average number of vertices within a given box grows with the lateral size of the box according to a power-law (an exponential) form in the cluster-growing method. The critical and supercritical skeletons are observed in protein interaction networks and the World Wide Web, respectively. The distribution of box masses, i.e., the number of vertices within each box, follows a power law P-m(M)similar to M-eta. The exponent eta depends on the box lateral size center dot(B). For small values of center dot(B), eta is equal to the degree exponent gamma of a given scale-free network, whereas eta approaches the exponent tau=gamma/(gamma-1) as center dot(B) increases, which is the exponent of the cluster-size distribution of the random branching tree. Finally, we study the perimeter H-alpha of a given box alpha, i.e., the number of edges connected to different boxes from a given box alpha as a function of the box mass M-B,M-alpha. It is obtained that the average perimeter over the boxes with box mass M-B is likely to scale as < H(M-B)>similar to M-B, irrespective of the box size center dot(B).