Misplaced Pages

Part of a series on
Network science
Theory
Graph Complex network Contagion Small-world Scale-free Community structure Percolation Evolution Controllability Graph drawing Social capital Link analysis Optimization Reciprocity Closure Homophily Transitivity Preferential attachment Balance theory Network effect Social influence
Network types
Informational (computing) Telecommunication Transport Social Scientific collaboration Biological Artificial neural Interdependent Semantic Spatial Dependency Flow on-Chip
Graphs
Features Clique Component Cut Cycle Data structure Edge Loop Neighborhood Path Vertex Adjacency list / matrix Incidence list / matrix Types Bipartite Complete Directed Hyper Labeled Multi Random Weighted
Metrics Algorithms
Centrality Degree Motif Clustering Degree distribution Assortativity Distance Modularity Efficiency
Models
Topology Random graph Erdős–Rényi Barabási–Albert Bianconi–Barabási Fitness model Watts–Strogatz Exponential random (ERGM) Random geometric (RGG) Hyperbolic (HGN) Hierarchical Stochastic block Blockmodeling Maximum entropy Soft configuration LFR Benchmark Dynamics Boolean network agent based Epidemic/SIR
Lists Categories
Topics Software Network scientists Category:Network theory Category:Graph theory
v t e

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 ${\displaystyle N}$,

where ${\displaystyle l}$ is the shortest distance between two nodes.

Equivalently:

where ${\displaystyle 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. 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.

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.

The box counting method

Let ${\displaystyle N_{B}}$ be the number of boxes of linear size ${\displaystyle l_{B}}$, needed to cover the given network. The fractal dimension ${\displaystyle d_{B}}$ is then given by

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

By measuring the distribution of ${\displaystyle N}$ for different box sizes or by measuring the distribution of ${\displaystyle \left\langle M_{B}\left(l_{B}\right)\right\rangle }$ for different box sizes, the fractal dimension ${\displaystyle 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 ${\displaystyle l}$ is given, a cluster of nodes separated by at most ${\displaystyle 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 ${\displaystyle d_{f}}$ can be calculated by

where ${\displaystyle \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 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.

Real-world fractal networks

Since fractal networks and their skeletons follow the relation

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 ${\displaystyle 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.

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

References

1. Moret, M. A.; Zebende, G. F. (2007-01-19). "Amino acid hydrophobicity and accessible surface area". Physical Review E. 75 (1). American Physical Society (APS): 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. 415. Elsevier BV: 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)
4. ^ 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
5. ^ 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.
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.
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.

• Network theory