Geographical Coarse Graining of Complex Networks

We perform a renormalization-grouplike numerical analysis of geographically embedded complex networks on a two-dimensional square lattice. At each step of the coarse-graining procedure, the four vertices on each $2\times 2$ square box are merged to a single vertex, resulting in a coarse-grained system of smaller size. Repetition of the process leads to the observation that the coarse-graining procedure does not alter the qualitative characteristics of the original scale-free network, which opens the possibility of subtracting a smaller network from the original network without destroying the important structural properties. The implication of the result is also suggested in the context of the recent study of the human brain functional network.

Figure 1

Coarse-graining procedure. Four vertices in each $2\times 2$ box are merged to a single vertex. After merging, two edges (thin solid lines) connecting vertices in different boxes become one edge (thick solid line) with the weight $w=2$. This procedure is repeated for all $2\times 2$ square boxes resulting in the coarse-grained network which is 4 times smaller than the original network. We then remove edges of smaller weights in order to fix the average degree.

Figure 2

Degree distribution $p(k)$ versus the degree $k$ for geographically embedded scale-free networks. The original $64\times 64$ networks in (a) with the degree exponents $\gamma =2.5$, 3.0, 4.0, and 5.0 are coarse-grained $n$ times; (b) $n=1$, (c) $n=2$, and (d) $n=3$. Clearly shown is that the degree exponent does not change upon the iteration of coarse graining. Full lines in (a)-(c) are for the power-law distributions with the exponents 2.5 and 5.0, while in (d) only the line for the exponent 2.5 is shown for comparison. $\gamma$ values in (b)-(d) only indicate the degree exponents for the corresponding initial networks.

Figure 3

Degree distribution $p(k)$ versus the degree $k$ for the networks with the degree exponent $\gamma =3$. The original network sizes are (a) $32\times 32$, (b) $64\times 64$, (c) $96\times 96$, and (d) $128\times 128$. The resulting coarse-grained network at the $n$th iteration displays the same degree exponent.

Figure 4

The clustering coefficient $C(k)$ versus $k$ for the $128\times 128$ network with $\gamma =3$ at the $n$th iteration step of coarse graining for (a) $n=0$ , (b) $n=1$, (c) $n=2$, and (d) $n=3$. The qualitative feature remains the same upon coarse-graining procedure.

Figure 5

(a)-(c) Density plot of the degrees $k_v$ and $k_w$ where $v$ and $w$ are two vertices connected by each edge. A brighter region indicates that there are more edges in that region. The initial network shows disassortative behavior (higher $k_v$ prefers lower $k_w$, and vice versa), which remains qualitatively the same as the coarse-graining procedure proceeds $n$ times: (a) $n=0$ (initial network), (b) $n=1$, and (c) $n=2$. (d) Assortativity coefficient $r$ versus the number $n$ of iterations of coarse graining. After the coarse graining, the network remains to be disassortative.

Figure 6

Geographically embedded WS network at the rewiring probability $P=0.1$. (a) Degree distribution $p(k)$ at the iteration steps $n=0$, 1, 2, and 3. (b) Clustering coefficient $C(n)$ versus $n$.