Fractal dimension on networks

Last updated January 29, 2024

Fractal analysis is useful in the study of complex networks, present in both natural and artificial systems such as computer systems, brain and social networks, allowing further development of the field in network science.

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$ ,

\left\langle l\right\rangle \sim \ln {N}

where $l$ is the shortest distance between two nodes.

Equivalently:

N\sim e^{\left\langle l\right\rangle /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.

Self-similarity has been discovered in the solvent-accessible surface areas of proteins.^[1]^[2] Because proteins form globular folded chains, this discovery has important implications for protein evolution and protein dynamics, as it can be used to establish characteristic dynamic length scales for protein functionality.^[3]

Methods for calculation of the dimension

The fractal dimension can be calculated using methods such as the box counting method or the cluster growing method.

Box counting method. Boxcounting.jpg — Box counting method.

Cluster growing method. Clustergrow.jpg — 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_{B}\sim l_{B}^{-d_{B}}

This means that the average number of vertices $\left\langle M_{B}\left(l_{B}\right)\right\rangle$ within a box of size $l_{B}$

\left\langle M_{B}\left(l_{B}\right)\right\rangle \sim l_{B}^{d_{B}}

By measuring the distribution of $N$ for different box sizes or by measuring the distribution of $\left\langle M_{B}\left(l_{B}\right)\right\rangle$ 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

\left\langle M_{C}\right\rangle \sim l^{d_{f}}

where $\left\langle M_{C}\right\rangle$ 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, the box-counting method with renormalization can be used. 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 all separated by a distance of l < l_B, that is every pair of nodes in the box must be separated by a minimal path of at most l_B links. 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.

The plot 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.

Skeleton of a network. Skeleton of a network.jpg — Skeleton of a network.

Skeleton 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 the edges 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.^[4]

Real-world fractal networks

Fractal scaling analysis of WWW network. Red-the original network, Blue-the skeleton, and Orange-a random spanning tree. Fractal scaling analysis of WWW network.jpg — Fractal scaling analysis of WWW network. Red-the original network, Blue-the skeleton, and Orange-a random spanning tree.

Since fractal networks and their skeletons follow the relation

\left\langle M_{B}\left(l_{B}\right)\right\rangle \sim l_{B}^{d_{B}}

,

A network can be classified as fractal or not and the fractal dimension can be found. For example, the WWW, the human brain, metabolic network, protein interaction network (PIN) of H. sapiens, and PIN of S. cerevisiaeare considered as fractal networks. Furthermore, the fractal dimensions measured are $d_{B}=4.1,{\mbox{ }}3.7,{\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.^[5]^[6]

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 distance,^[7] or based on the complex network zeta function ^[8] have also been studied.

Related Research Articles

<span class="mw-page-title-main">Inner product space</span> Generalization of the dot product; used to define Hilbert spaces

In mathematics, an inner product space is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, often denoted with angle brackets such as in $. Inner products allow formal definitions of intuitive geometric notions, such as lengths, angles, and orthogonality of vectors. Inner product spaces generalize Euclidean vector spaces, in which the inner product is the dot product or scalar product of Cartesian coordinates. Inner product spaces of infinite dimension are widely used in functional analysis. Inner product spaces over the field of complex numbers are sometimes referred to as unitary spaces . The first usage of the concept of a vector space with an inner product is due to Giuseppe Peano, in 1898.$

The uncertainty principle, also known as Heisenberg's indeterminacy principle, is a fundamental concept in quantum mechanics. It states that there is a limit to the precision with which certain pairs of physical properties, such as position and momentum, can be simultaneously known. In other words, the more accurately one property is measured, the less accurately the other property can be known.

In linear algebra, a symmetric matrix is a square matrix that is equal to its transpose. Formally,

The ground state of a quantum-mechanical system is its stationary state of lowest energy; the energy of the ground state is known as the zero-point energy of the system. An excited state is any state with energy greater than the ground state. In quantum field theory, the ground state is usually called the vacuum state or the vacuum.

The Ising model, named after the physicists Ernst Ising and Wilhelm Lenz, is a mathematical model of ferromagnetism in statistical mechanics. The model consists of discrete variables that represent magnetic dipole moments of atomic "spins" that can be in one of two states. The spins are arranged in a graph, usually a lattice, allowing each spin to interact with its neighbors. Neighboring spins that agree have a lower energy than those that disagree; the system tends to the lowest energy but heat disturbs this tendency, thus creating the possibility of different structural phases. The model allows the identification of phase transitions as a simplified model of reality. The two-dimensional square-lattice Ising model is one of the simplest statistical models to show a phase transition.

A conformal field theory (CFT) is a quantum field theory that is invariant under conformal transformations. In two dimensions, there is an infinite-dimensional algebra of local conformal transformations, and conformal field theories can sometimes be exactly solved or classified.

In mathematical analysis, Parseval's identity, named after Marc-Antoine Parseval, is a fundamental result on the summability of the Fourier series of a function. The identity asserts the equality of the energy of a periodic signal and the energy of its frequency domain representation. Geometrically, it is a generalized Pythagorean theorem for inner-product spaces.

The density matrix renormalization group (DMRG) is a numerical variational technique devised to obtain the low-energy physics of quantum many-body systems with high accuracy. As a variational method, DMRG is an efficient algorithm that attempts to find the lowest-energy matrix product state wavefunction of a Hamiltonian. It was invented in 1992 by Steven R. White and it is nowadays the most efficient method for 1-dimensional systems.

In mathematics, specifically in operator theory, each linear operator $on an inner product space defines a Hermitian adjoint operator on that space according to the rule$

The classical XY model is a lattice model of statistical mechanics. In general, the XY model can be seen as a specialization of Stanley's n-vector model for $n = 2$ .

In linear algebra, the Gram matrix of a set of vectors $in an inner product space is the Hermitian matrix of inner products, whose entries are given by the inner product . If the vectors are the columns of matrix then the Gram matrix is in the general case that the vector coordinates are complex numbers, which simplifies to for the case that the vector coordinates are real numbers.$

In the study of graphs and networks, the degree of a node in a network is the number of connections it has to other nodes and the degree distribution is the probability distribution of these degrees over the whole network.

In quantum field theory and statistical mechanics, the Hohenberg–Mermin–Wagner theorem or Mermin–Wagner theorem states that continuous symmetries cannot be spontaneously broken at finite temperature in systems with sufficiently short-range interactions in dimensions $d \leq 2$ . Intuitively, this means that long-range fluctuations can be created with little energy cost, and since they increase the entropy, they are favored.

The fundamental plane is a set of bivariate correlations connecting some of the properties of normal elliptical galaxies. Some correlations have been empirically shown.

In computer science, in the area of formal language theory, frequent use is made of a variety of string functions; however, the notation used is different from that used for computer programming, and some commonly used functions in the theoretical realm are rarely used when programming. This article defines some of these basic terms.

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 graphs. Here we describe the definition based on the complex network zeta function. This generalises the definition based on the scaling property of the volume with distance. The best definition depends on the application.

In the context of the physical and mathematical theory of percolation, a percolation transition is characterized by a set of universal critical exponents, which describe the fractal properties of the percolating medium at large scales and sufficiently close to the transition. The exponents are universal in the sense that they only depend on the type of percolation model and on the space dimension. They are expected to not depend on microscopic details such as the lattice structure, or whether site or bond percolation is considered. This article deals with the critical exponents of random percolation.

Robustness, the ability to withstand failures and perturbations, is a critical attribute of many complex systems including complex networks.

Evolution of a random network is a dynamical process, usually leading to emergence of giant component accompanied with striking consequences on the network topology. To quantify this process, there is a need of inspection on how the size of the largest connected cluster within the network, $, varies with the average degree . Networks change their topology as they evolve, undergoing phase transitions. Phase transitions are generally known from physics, where it occurs as matter changes state according to its thermal energy level, or when ferromagnetic properties emerge in some materials as they are cooling down. Such phase transitions take place in matter because it is a network of particles, and as such, rules of network phase transition directly apply to it. Phase transitions in networks happen as links are added to a network, meaning that having N nodes, in each time increment, a link is placed between a randomly chosen pair of them. The transformation from a set of disconnected nodes to a fully connected network is called the evolution of a network.$

In network science, the configuration model is a method for generating random networks from a given degree sequence. It is widely used as a reference model for real-life social networks, because it allows the modeler to incorporate arbitrary degree distributions.

References

↑ Moret, M. A.; Zebende, G. F. (2007-01-19). "Amino acid hydrophobicity and accessible surface area". Physical Review E. American Physical Society (APS). 75 (1): 011920. Bibcode:2007PhRvE..75a1920M. doi:10.1103/physreve.75.011920. ISSN 1539-3755. PMID 17358197.
↑ Phillips, J.C. (2014). "Fractals and self-organized criticality in proteins". Physica A: Statistical Mechanics and Its Applications. Elsevier BV. 415: 440–448. Bibcode:2014PhyA..415..440P. doi:10.1016/j.physa.2014.08.034. ISSN 0378-4371.
↑ 3. Phillips, J. C. Quantitative molecular scaling theory of protein amino acid sequences, structure, and functionality. arXiv 1606.1004116 (2016)
1 2 K.-I. Goh, G. Salvi, B. Kahng and D. Kim, Skeleton and Fractal Scaling in Complex Networks, Phys. Rev. Lett. 96, 018701 (2006), http://iopscience.iop.org/article/10.1088/1367-2630/9/6/177/pdf
1 2 J.S. Kim et al.,Fractality in complex networks: critical and supercritical skeletons, 2006, arXiv : cond-mat/0605324
↑ F. Klimm; Danielle S. Bassett; Jean M. Carlson; Peter J. Mucha (2014). "Resolving structural variability in network models and the brain". PLOS Computational Biology. 10 (3): e1003491. arXiv: 1306.2893 . Bibcode:2014PLSCB..10E3491K. doi: 10.1371/journal.pcbi.1003491 . PMC 3967917 . PMID 24675546.
↑ Shanker, O. (2007). "Defining Dimension of a Complex Network". Modern Physics Letters B . 21 (6): 321–326. Bibcode:2007MPLB...21..321S. doi:10.1142/S0217984907012773.
↑ Shanker, O. (2007). "Graph Zeta Function and Dimension of Complex Network". Modern Physics Letters B . 21 (11): 639–644. Bibcode:2007MPLB...21..639S. doi:10.1142/S0217984907013146.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Moret, M. A.; Zebende, G. F. (2007-01-19). "Amino acid hydrophobicity and accessible surface area". Physical Review E. American Physical Society (APS). 75 (1): 011920. Bibcode:2007PhRvE..75a1920M. doi:10.1103/physreve.75.011920. ISSN 1539-3755. PMID 17358197.

[2] Phillips, J.C. (2014). "Fractals and self-organized criticality in proteins". Physica A: Statistical Mechanics and Its Applications. Elsevier BV. 415: 440–448. Bibcode:2014PhyA..415..440P. doi:10.1016/j.physa.2014.08.034. ISSN 0378-4371.

[3] 3. Phillips, J. C. Quantitative molecular scaling theory of protein amino acid sequences, structure, and functionality. arXiv 1606.1004116 (2016)

[goh-4] 1 2 K.-I. Goh, G. Salvi, B. Kahng and D. Kim, Skeleton and Fractal Scaling in Complex Networks, Phys. Rev. Lett. 96, 018701 (2006), http://iopscience.iop.org/article/10.1088/1367-2630/9/6/177/pdf

[kim-5] 1 2 J.S. Kim et al.,Fractality in complex networks: critical and supercritical skeletons, 2006, arXiv : cond-mat/0605324

[6] F. Klimm; Danielle S. Bassett; Jean M. Carlson; Peter J. Mucha (2014). "Resolving structural variability in network models and the brain". PLOS Computational Biology. 10 (3): e1003491. arXiv: 1306.2893 . Bibcode:2014PLSCB..10E3491K. doi: 10.1371/journal.pcbi.1003491 . PMC 3967917 . PMID 24675546.

[Shankera-7] Shanker, O. (2007). "Defining Dimension of a Complex Network". Modern Physics Letters B . 21 (6): 321–326. Bibcode:2007MPLB...21..321S. doi:10.1142/S0217984907012773.

[Shankerb-8] Shanker, O. (2007). "Graph Zeta Function and Dimension of Complex Network". Modern Physics Letters B . 21 (11): 639–644. Bibcode:2007MPLB...21..639S. doi:10.1142/S0217984907013146.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]