Fractal dimension on networks

Fractal dimension on networks

=Self-similarity of complex networks=

Many real networks have two fundamental properties, scale-free property and small-world property. If the degree distribution of the network follows a power-law, the network is scale-free; if any two arbitrary nodes in a network can be connected in a very small number of steps, the network is said to be small-world.

The small-world properties can be mathematically expressed by the slow increase of the average diameter of the network, with the total number of nodes N,

leftlangle l ight anglesimln{N}

where l is the shortest distance between two nodes.

Equivalently, we obtain:

Nsim e^{/l_0}
where l_0 is a characteristic length.

For a self-similar structure, a power-law relation is expected rather than the exponential relation above. From this fact, it would seem that the small-world networks are not self-similar under a length-scale transformation.

However, analysis of a variety of real complex networks shows they are self-similar on all length scales, a conclusion derived from measuring a power-law relation between the number of boxes needed to cover the network and the size of the box, so called fractal scalingC. Song, S. Havlin, and H. A. Makse, Nature (London)433, 392 (2005).] .

The methods for calculation of the dimension

Generally we calculate the fractal dimension using either the Box Counting Method or the Cluster Growing Method.

The Box Counting Method

Let N_B be the number of boxes of linear size l_B, needed to cover the given network. The fractal dimension d_B is then given by
N_Bsim l_B^{-d_B}

This means that the average number of vertices leftlangle M_Bleft(l_B ight) ight angle within a box of size d_B
leftlangle M_Bleft(l_B ight) ight angle sim l_B^{d_B}

By measuring the distribution of N for different box sizes or by measuring the distribution of leftlangle M_Bleft(l_B ight) ight angle for different box sizes, the fractal dimension d_B can be obtained by a power law fit of the distribution.

The Cluster Growing Method

One seed node is chosen randomly. If the minimum distance l is given, a cluster of nodes separated by at most l from the seed node can be formed. The procedure is repeated by choosing many seeds until the clusters cover the whole network. Then the dimension d_f can be calculated by

leftlangle M_C ight angle sim l^{d_f}

where leftlangle M_C ight angle is the average mass of the clusters, defined as the average number of nodes in a cluster.

These methods are difficult to apply to networks since networks are generally not embedded in another space. In order to measure the fractal dimension of networks we add the concept of renormalization.

Fractal scaling in scale-free networks

Box-counting and Renormalization

To investigate self-similarity in networks, we use the box-counting method and renormalization. Fig.(3a) shows this procedure using a network composed of 8 nodes.

For each size "l""B", boxes are chosen randomly (as in the cluster growing method) until the network is covered, A box consists of nodes separated by a distance "l" < "l""B". Then each box is replaced by a node(renormalization). The renormalized nodes are connected if there is at least one link between the unrenormalized boxes. This procedure is repeated until the network collapses to one node. Each of these boxes has an effective mass (the number of nodes in it) which can be used as shown above to measure the fractal dimension of the network. In Fig.(3b), renormalization is applied to a WWW network through three steps for "l""B" = 3.

Fig.(5) shows the invariance of the degree distribution "P"("k") under the renormalization performed as a function of the box size on the world wide web. The networks are also invariant under multiple renormalizations applied for a fixed box size "l""B". This invariance suggests that the networks are self-similar on multiple length scales.

Fig.(4) Skeleton of a NetworkK.-I. Goh, G. Salvi, B. Kahng and D. Kim, Phys. Rev.Lett. 96, 018701 (2006).] .

keleton and Fractal Scaling

The fractal properties of the network can be seen in its underlying tree structure. In this view, the network consists of the skeleton and the shortcuts. The skeleton is a special type of spanning tree, formed by edges the having the highest betweenness centralities, and the remaining edges in the network are shortcuts.If the original network is scale-free, then its skeleton also follows a power-law degree distribution, where the degree can be different from the degree of the original network. For the fractal networks following fractal scaling, each skeleton shows fractal scaling similar to that of the original network. The number of boxes to cover the skeleton is almost the same as the number needed to cover the network.

Real-world fractal networks

Since fractal networks and their skeletons follow the relation
leftlangle M_Bleft(l_B ight) ight anglesim l_B^{d_B},
we can investigate whether a network is fractal and what is the fractal dimension of the network. For example, the WWW, metabolic network, protein interaction network(PIN) of "H". "sapiens", and PIN of "S". "cerevisiae"are considered as fractal networks. Furthermore, the fractal dimensions measured are d_B = 4.1,mbox{ } 3.4,mbox{ } 2.0, mbox{ and } 1.8 for the networks respectively. On the other hand, the Internet, actor network, and artificial models (for instance, the BA model) do not show the fractal properties.

Other definitions for network dimensions

The best definition of dimension for a complex network or graph depends on the application. For example, metric dimension is defined in terms of the resolving set for a graph. Definitions based on the scaling property of the "mass" as defined above with distancecite journal|author=Shanker, O.|year=2007|title=Defining Dimension of a Complex Network |journal=Modern Physics Letters B|volume= 21(6)|pages=321–326|doi=10.1142/S0217984907012773] ,or based on the complex network zeta functioncite journal|author=Shanker, O.|year=2007|title=Graph Zeta Function and Dimension of Complex Network|journal=Modern Physics Letters B|volume= 21(11)|pages=639–644|doi=10.1142/S0217984907013146] have also been studied.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Fractal analysis — is the modelling of data by fractals.It consists of methods to assign a fractal dimension and other fractal characteristics to a signal, dataset or object which may be sound, images, molecules, networks or other data.Fractal analysis is now… …   Wikipedia

  • Dimension — 0d redirects here. For 0D, see 0d (disambiguation). For other uses, see Dimension (disambiguation). From left to right, the square, the cube, and the tesseract. The square is bounded by 1 dimensional lines, the cube by 2 dimensional areas, and… …   Wikipedia

  • Fractal — A fractal is generally a rough or fragmented geometric shape that can be split into parts, each of which is (at least approximately) a reduced size copy of the whole, [cite book last = Mandelbrot first = B.B. title = The Fractal Geometry of… …   Wikipedia

  • List of mathematics articles (F) — NOTOC F F₄ F algebra F coalgebra F distribution F divergence Fσ set F space F test F theory F. and M. Riesz theorem F1 Score Faà di Bruno s formula Face (geometry) Face configuration Face diagonal Facet (mathematics) Facetting… …   Wikipedia

  • Complex network zeta function — Different definitions have been given for the dimension of a complex network or graph. For example, metric dimension is defined in terms of the resolving set for a graph. Dimension has also been defined based on the box covering method applied to …   Wikipedia

  • Ising model — The Ising model, named after the physicist Ernst Ising, is a mathematical model in statistical mechanics. It has since been used to model diverse phenomena in which bits of information, interacting in pairs, produce collectiveeffects.Definition… …   Wikipedia

  • Shortcut model — An important question in statistical mechanics is the dependence of model behaviour on the dimension of the system. The shortcut modelcite journal|author=Shanker, O.|year=2007|title=Graph Zeta Function and Dimension of Complex… …   Wikipedia

  • Wu Xing — For other uses, see Wu Xing (disambiguation). Wu Xing Chinese 五行 Transcriptions Mandarin …   Wikipedia

  • Emergence — For other uses see Emergence (disambiguation), Emergent, and Emergency. : See also the closely related articles: Spontaneous order and self organization. In philosophy, systems theory and the sciences, emergence is the way complex systems and… …   Wikipedia

  • Simplex — For other uses, see Simplex (disambiguation). A regular 3 simplex or tetrahedron In geometry, a simplex (plural simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimension. Specifically, an n… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”