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

${\displaystyle N_{B}\sim l_{B}^{-d_{B}}}$

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

${\displaystyle \left\langle M_{B}\left(l_{B}\right)\right\rangle \sim l_{B}^{d_{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

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

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.

Box-counting and renormalization

To investigate self-similarity in networks, we use the box-counting method and renormalization. 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.^[4]

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]