Geographical networks: geographical effects on network properties

Abstract

Complex networks describe a wide range of systems in nature and society. Since most real systems exist in certain physical space and the distance between the nodes has influence on the connections, it is helpful to study geographical complex networks and to investigate how the geographical constrains on the connections affect the network properties. In this paper, we briefly review our recent progress on geographical complex networks with respect of statistics, modelling, robustness, and synchronizability. It has been shown that the geographical constrains tend to make the network less robust and less synchronizable. Synchronization on random networks and clustered networks is also studied.

Graphical abstract

Keywords

complex networks / network properties / geographical networks / synchronization / clustered networks

Complex networks provide powerful tools to investigate complex systems in nature and society [1−3]. The properties of complex systems are affected by the geographical distribution of the components. For example, routers of the Internet [4] and transport networks [5, 6] lay on the two-dimensional surface of the globe; world-wide airport network is confined by the geography [7−9]; neuronal networks in brains [10] occupy three-dimensional space. Thus it is helpful to study the geographical complex networks [11−19].

To be specific, for the Chinese railway system, viewing the stations as “nodes” and rails as “links”, the railway system is actually a complex geographical network. Our recent statistics on 3431 stations and 2147 trains nationwide [20] reveals that for this network, the clustering coefficient is almost zero, indicating sparse connections between the stations, therefore it is a tree network. This is the most economic way to construct a transportation network. On the other hand, viewing the stations as “nodes” and say if there is a link between two stations if at least one train stops at both stations, the railway system can be viewed as a geographical traffic network. Statistics reveals that this traffic network has large clustering coefficients (\langle C\rangle =0.83) and small average network distance (\langle d\rangle =3.27), that is, starting from any station, one only need to transfer at most twice to reach another station (could be a very small station) through the railway system. The degree distribution is scale-free. Consequently, the railway traffic network is a small world network with scale-free property.

To investigate the effect of geographical constrains on network properties, we first proposed a geographical network model with a tunable parameter to control the geographical effects [21], then studied the percolation problem [22, 23], cascading breakdown [24], and synchronization [25] on this network model to find out how the geographical constrains affect these network properties. Synchronization on random networks [26] and on clustered networks [27] is also discussed.

In this paper, we mainly focus on scale-free (SF) networks, i.e., the degrees of nodes satisfy a power law distribution: P(k) ~ k^−λ, for their ubiquity in real systems [1−3]. The network is generated as follows [21]. It begins with an L\times L lattice, with periodical boundary conditions, and for each node assigned a degree k drawn from the prescribed SF degree distribution P (k)∼k−λ, k⩾m. Then a node i is picked out randomly; according to a Gaussian weight function f_i(r)=D{\text{e}}^{-{(r/A\sqrt{k_i})}^2}, it selects other nodes and establishes connections until its degree quota k_i is filled or until it has tried many enough times. Duplicate connections are avoided. The process is carried out for all the nodes in the lattice. The clustering parameter A controls the average spatial distance of the connections, therefore controls the geographical constrains on the network topologies. For large A limit, e.g. A\sqrt{m}\gg L, the weight function will be trivial, and the network becomes a SF random (SFR) network, i.e., random in network connections. For small A, the network approaches lattice embedded SF (LESF) networks with nearest neighbor connections [12, 13]. Here, we assume that the time scales governing the dynamics are much smaller than that characterizing the network evolvement. Thus, the static geographical network models are suitable for discussing the problem under investigation. Figure 1 shows the direct chemical shell structure [12, 13], with different gray levels depicting different shells consisting of nodes with the same network distance from a given node, which is assumed to be the central node in each graph. Along with WLESF, the LESF model and the Scale-Free Random model (SFR) are also presented. Here, λ is fixed to 3.0 for all the three models, and A is varied as 1, 2, 3, and 5 in WLESF. As A goes larger, the shell boundary blurs and finally disappears as that of random graphs. The shell graph of WLESF shows an obvious structural transition from the LESF model to the SFR model.

When losing nodes of fraction p, the remaining nodes of a network may still have a spanning cluster that most of the nodes are on this cluster and there are paths from one node to another globally. However, when losing enough nodes, at a certain point (percolating threshold p_c), the spanning cluster breaks into small pieces, and no path exist for global information transmission, that is, the network breakdowns. The heterogeneity of the degrees often makes the scale-free networks sensitive to intentional attacks (nodes with largest degrees are removed from the network first) [28−30], while it is resilience to random breakdowns (node are removed with the same probability p) [30, 31]. Figure 2 shows the dependence of p_c on A for both intentional attack and random removals. As A increases, p_c becomes larger, means it needs to remove more nodes to break the spanning clusters. Therefore, as the network is more loosely connected (average spatial distance is larger), the network is more robust to losing nodes.

To better understand the numerical results, we employ the generating function method to determine the percolation threshold for networks with different clustering properties. Here the clustering properties can be simply depicted by the clustering coefficient, which counts for the triangles (3-cycles) in the network, and it can also be represented by the number of rectangles (4-cycles), and generally by the number of L-cycles. In the following, a general relation of the percolation threshold q_c = 1−p_c and the number of L-cycles for a random network with arbitrary degree distribution is determined. As an example, the dependence of q_c on the clustering coefficient is obtained.

For uniform occupations (or random failures), the percolation threshold of random tree-like networks is q_c =\langle k\rangle /\langle k(k-1)\rangle [31, 32]. It could be obtained by the condition that the average cluster size diverges, or equivalently, the average size of clusters that reached by following an edge diverges. A real network is usually clustered and contains certain amount of cycles. If the number of cycles is small, (e.g. each node belongs to at most one cycle) the generating function process can be extended to cope with the random percolation problem. In a recent paper [23], after lengthy deviation, we finally get the percolation threshold q_c:

\begin{array}{}\text{(1)}& q_{\text{c}}=\frac{\langle k\rangle }{\langle k(k-1)\rangle -2\langle k{n}_L(k)\rangle \left[1-\frac{2-q_{\text{c}}^{l_1}-q_{\text{c}}^{l_2}}{2(1-q_{\text{c}})}\frac{q_{\text{c}}\langle k(k-2)\rangle }{\langle k\rangle }\right]}\end{array}

When n_L = 0, this result degenerates to the known result of the tree-like networks:q_{\text{c}}=\langle k\rangle /\langle k(k-1)\rangle. In general q_c < 1, as L→∞, q_{\text{c}}^{l_1} and q_{\text{c}}^{l_2} limit to 0, Eq. (1) reduces to a second order equation for q_c. The root with physical meanings is q_{\text{c}}=\langle k\rangle /\langle k(k-1)\rangle, which is just the percolation threshold of the tree-like networks. This means that the cycles of infinite length do not affect the percolation thresholds. The numerical tests for several typical data values show that, for the same number of cycles, q_c is an increasing function of q_{\text{c}}^{l_1}+q_{\text{c}}^{l_2}. The higher the cycle order L is, the less influence it will be. Thus the most influential cycles are 3-cycles, which could be expressed by the clustering coefficients.

For L = 3, l₁ = l₂ = 1. If the clustering coefficient C=\langle C(k)\rangle is small enough, we may assume that two triangles could only have at most one common node. A node with degree k reached by an edge will belong to on average n₃(k) = (C(k)(k−1)(k−2) + C(k)(k−1))/2 =C(k)(k−1)²/2 triangles. Eq. (1) will reduce to

\begin{array}{}\text{(2)}& q_{\text{c}}=\frac{\langle k\rangle }{\langle k(k-1)\rangle -\left(1-q_{\text{c}}\frac{\langle k(k-2)\rangle }{\langle k\rangle }\right)\langle C(k)k{(k-1)}^2\rangle }\end{array}

The percolation threshold q_c increases monotonically with \langle C(k)k{(k-1)}^2\rangle. It is straightforward that when C(k) limits to 0, n₃→0, q_c returns to \langle k\rangle /\langle k(k-1)\rangle. On the other hand, if \langle C(k)k{(k-1)}^2\rangle diverges, q_c maximizes to \langle k\rangle /\langle k(k-2)\rangle.

Although Eq. (2) holds only for the case of small clustering coefficient C, the analysis above indicates that for large C, or if the network has higher order cycles, the fraction of edges that inter-connect existed nodes in a local cluster will further increase. Thus the number of efficient edges connecting to “new” nodes (in comparison to the nodes within the local cluster) may be even smaller, which results in a higher percolation threshold. Thus when a network is more clustered, or has more cycles—not only of order 3—it will be less robust.

Figure 3 shows the clustering coefficients for different A values. For each given degree exponent λ, the larger the A is, the looser the local cluster is, as a result, the smaller the clustering coefficient is. This is consistent with the result that networks with larger A is more robust to percolation.

In many realistic situations the flow of physical quantities in the network, as characterized by the loads on nodes, is important. For such networks where loads can redistribute among the nodes, a failure of a node can lead to a cascade of overload failures, which can in turn cause the entire or a substantial part of the network to collapse. Many real systems-e.g., power grid networks, traffic lines, Internet-are sensitive to cascading failures and are located on the two-dimensional global surface, the influence of geographical structures on cascading breakdowns is thus of high importance. Here, by studying the influence on the cascading behavior of the networks by varying A, we uncovered how the geographical structures affect cascading breakdowns [24].

To investigate the cascading breakdowns on networks, we employ the sandpile dynamics as follows: (i) At each time step, a grain is added at a randomly chosen node i. (ii) If the height at node i reaches or exceeds a prescribed threshold z_i = k_i, the degree of node i; then it becomes unstable and the grains topple to its adjacent nodes: h_i = h_i−k_i; and for each neighbor j: h_j = h_j + 1; during the transfer, there is a small fraction f of grains being lost, which plays the role of sinks without which the system becomes overloaded in the end. (iii) If this toppling causes any of the adjacent nodes to become unstable, subsequent topplings follow on those nodes in parallel until there is no unstable node left, forming an avalanche event (the cascadings). (iv) Repeat (i)−(iii).

The main feature of the BTW sandpile model is the emergence of a power law with an exponential cutoff in the avalanche area distribution,

\begin{array}{}\text{(3)}& p(a)\sim a^{-\tau }{\text{e}}^{-a/a_{\text{c}}}\end{array}

where a_c is the characteristic area, i.e., the number of distinct nodes that toppled in an avalanche event.

The avalanche area exponent for different A of WLESF network is shown in Fig. 4. As A goes larger, avalanche area exponent τ increases, and the curves of avalanche area distribution become sharper in the double-log plot (see inset of Fig. 4), which corresponds to fewer large avalanche events. This transition in τ illuminates that when the network is geographically more loosely connected, it will be harder for large cascading events to occur.

The range of an edge is the length of the shortest paths between the nodes it connected in the absence of itself. If an edge’s range is l, the shortest cycle it lies on is of length l + 1. Thus the distribution of range in a network sketches the distribution of shortest cycles. The inset of Fig. 5 shows that when the spatial constraint is slighter, as A goes larger, the range distribution drifts to larger ranges. It means that networks with loose spatial connections have fewer small order cycles but more higher order cycles. If there are many small order cycles, the toppling grains are more likely to meet, and the nodes with fewer grains, i.e., fewer than z−1, especially those with z−2 or z−3 grains, could also reach the toppling threshold z and topple. For example, let ABCD be a quadrangle, and A, B and D are all in their critical height z_A−1, z_B−1 and z_D−1, respectively; if A topples, then B and D will also topple cascadingly, thus C will receive 2 grains. So even if C has less grains than its critical height z_C−1, it could also topple. Larger order cycles contribute less to this effect. The main frame of Fig. 5 shows the fraction of nodes toppled in avalanches that have precisely z−1 grains. As the network is less geographically constrained and has fewer small order cycles, the fraction of toppling nodes with z−1 grains increases, substantiating our reasoning. This effect contributes to the large avalanche events of the densely connected networks and explains the decrease of avalanche area exponent τ as the network is more geographically constrained. Since many real networks that carry some kinds of loads-e.g., power, traffic, data packets–are imbedded in the 2D global surface and highly clustered, our results indicate that they will be at higher risk to suffer breakdowns when there are node failures.

Synchronization is important to many network functions. Now we investigate how the geographical constrains affect the synchronizability of the network. To be concrete, we consider the following general class of coupled-map networks:

\begin{array}{}\text{(4)}& {\mathit{x}}_{m+1}^i=\mathit{f}({\mathit{x}}_m^i)-\epsilon {\displaystyle \sum _j{G}_{ij}\mathit{H}[\mathit{f}({\mathit{x}}_m^j)]}\end{array}

where x_m+1 = f (x_m) is a d-dimensional map, ε is a global coupling parameter, G is the Laplacian matrix, and H is a coupling function. For convenience we choose G_ij =−A_ij/k_i for \begin{array}{ccc}j& \ne & i\\ & & \end{array} and G_ii = 1, where k_i is the degree of node i and A_ij is an element of the adjacent matrix A of the network. The eigenvalues of the coupling matrix G are real and nonnegative and can be sorted as 0={\lambda }_1⩽{\lambda }_2 ⩽\cdots ⩽{\lambda }_N. Since the rows of the coupling matrix G have zero sum, Eq. (4) permits an exact synchronized solution: {\mathit{x}}_m^1={\mathit{x}}_m^2=\cdots ={\mathit{x}}_m^N={\mathit{s}}_m, where s_m+1 = f (s_m). To gain insight, we set f(x) to be the one-dimensional logistic map and choose H(x) = x.

To characterize synchronization, we define synchronization error \sigma =\langle |x_m^i-\langle x_m^i\rangle |\rangle, where \langle \cdot \rangle means average over all nodes. It is observed that when the coupling strength ε is greater than a critical value ε_c, σ < 10⁻¹⁰, i.e., all the oscillators move identically and the system is synchronized. Figure 6 shows the dependence of critical coupling strength ε_c and the synchronization error on the clustering control parameter A. One can see that as A goes larger, both ε_c and σ decreases, indicates a higher synchronizability. That is, when nodes enlarge their circular connecting regions, the network is more synchronizable. The reason of this is that when A is large, a node can connect to a node faraway, thus the network is less locally constrained. This leads to a smaller network distance, as Fig. 7 (a) shows, which means the nodes in the network communicates better, resulting in a better synchronizability. Another factor is that as A increase, the network is more homogeneous in the sense that the maximum load, defined by the number of shortest pathes passing through a node, decreases [Fig. 7 (b)]. Thus the information communication is less jammed and makes for a better synchronizability.

Synchronization on random networks, i.e., each pair of nodes has a probability p to be connected, has been widely studied. Most results concentrates on numerical simulations, recently, using the master stability analysis and the eigenvalue analysis, we provided a theory predicting the synchronization region of the random network for a given dynamical parameter of the system [26].

The coupled system (4) is synchronizable only if the effective coupling strength K = ελ_i (i > 1) falls into a certain interval (K₁, K₂), or , where K₁ and K₂ depends on the dynamics of a single oscillator only [33]. For 1-D dynamical systems with Lyapunov exponent µ and linear coupling, K₁ = 1−e^−µ and K₂ = 1+e^−µ. The network is synchronizable if K₁ < ελ₂ and ελ_N < K₂. Via eigenvalue analysis, we obtained that

\begin{array}{}\text{(4)}& \begin{array}{l}{\lambda }_2\approx 1-2\sqrt{(1-p)/(Np)}\\ {\lambda }_2\approx 1+2\sqrt{(1-p)/(Np)}\end{array}\end{array}

Therefore, the synchronization condition is

[Since in most relevant cases, the upper limit (1 + e^−µ)(1 + 2\sqrt{(1-p)/(Np)}) is greater than 1, so in the following, we just discuss the lower limit \begin{array}{l}(1-{\text{e}}^{-\mu })(1-2\sqrt{(1-p)/(Np)})]\hfill \end{array}. Several conclusions are at hand for different limiting cases:

(1) pC1, Eq. (5) becomes

which is consistent with the result of globally coupled network (GCN).

(2) Keep p fixed, and let N→∞, Eq. (5) can also be rewritten as

which implies that in this limit, the behavior of this system would be equivalent to that of a GCN.

(3) Denote k = Np, Eq. (5) becomes

If N\gg k, then 1/N can be neglected, the above equation becomes

Set ε = 1, the synchronization condition becomes

\begin{array}{}\text{(10)}& k>K=4{\text{e}}^{2\mu }\end{array}

which implies that for ER random networks, one can have chaotic synchronization for arbitrary system size, if the coupling is strong enough, i.e. ε = 1, and if the average degree is larger than some threshold determined by the value of the maximal Lyapunov exponent of the individual dynamics.

Earlier works suggest that small-world and scale-free networks are generally more synchronizable than regular networks. While heterogeneous degree distributions can inhibit synchronization, adding suitable weights to the network elements can enhance their chances to synchronize with each other. In general, given a complex network with a fixed number of nodes, its synchronizability can be improved by increasing the number of links. This is intuitive as a denser linkage makes the network more tightly coupled or, “smaller,” thereby facilitating synchronization. A clustered network, which consists of M groups, where nodes within each group are densely connected with probability p_s, but the linkage among the groups is sparse (with probability p_l), however, has a different set of rules that determine the synchronizability [27]. Namely, the synchronizability of a clustered network is determined by the interplay between the inter-connections (links among clusters) and intra-connections (links within clusters) of the network. Strong synchronizability requires that the numbers of the inter-links and intra-links be approximately matched. In this case, increasing the number of links can indeed enhance the synchronizability. However, if the matching is deteriorated, synchronization can be severely suppressed or even totally destroyed.

The synchronization condition of system (4) is λ₂ > (1−e^−µ)/ε. For clustered networks, the normalized eigenvector e₂ corresponded to λ₂, e.g. Ge₂ = λ₂e₂, has a special structure that the components of the eigenvector e₂ have approximately the same value within any cluster, while they can vary among clusters. λ₂ can be expressed as {\lambda }_2=e_2^{\text{T}}G{e}_2. After lengthy deviation,

\begin{array}{}\text{(11)}& {\text{λ}}_2\approx \frac{N{p}_l}{n{p}_s+(N-n)p_l}\end{array}

λ₂ decreases as p_s (or the number of intra-cluster links) increases, which means, for the clustered network, more intra-cluster links, although makes the network smaller, deteriorates the synchronizability of the network.

The synchronization time T-average time required for the system to become synchronized from random initial valuescan be used to characterize the ability to synchronize. The less this time, the more synchronizable the system is. But if the system is unstable (unsynchronizable), it can not reach a synchronization state, which means this time equals infinity. Figure 8 shows this synchronization time T vs two control parameters p_l and p_s. This gives the synchronizable region (grey levels in Fig. 8) in the parameter space that the system becomes synchronized within a certain time, and unsynchronizable region (white in Fig. 8) that the time for the system to become synchronized limits to infinity. The lines of the boundaries of the synchronizable and unsynchronizable regions are determined by linear stability analysis (see below). The striking thing Fig. 8 revealed is that for a given p_l (inter-connection strength), e.g. p_l = 0.2 in Fig. 8 (a), as p_s (intra-connection strength) increases from p_s = 0.2, synchronization time T is also increased, and at a certain point (around 0.75 in this case), the system becomes unsynchronizable. So it turns out that if the connections within a cluster are too strong, it will destroy the global synchronization. This is reasonable since if the connections within a cluster increase, the cluster itself has stronger ability to synchronize, while relatively, the connections between clusters becomes weaker, and not strong enough to spur different almost synchronized clusters into the globally synchronization state. Thus the whole system is separated into different, almost freely oscillated synchronized clusters.

In conclusion, we shortly reviewed our recent progress on geographical complex networks with respect of statistics, modelling, robustness, and synchronizability. It has been shown that the geographical constrains have important influence on network properties, both topologically and dynamically. Synchronization on random networks and clustered networks is also studied.

References

[1] R. Albert and A.-L. Barabási, Rev. Mod. Phys., 2002, 74: 47; M. E. J. Newman, SIAM Rev., 2003, 45: 167

[2] S. N. Dorogovtsev and J. F. F. Mendes, Evolution of Networks, Oxford: Oxford University Press, 2003

[3] R. Pastor-Satorras and A. Vespignani, Evolution and Structure of the Internet, Cambridge: Cambridge University Press, 2004

[4] A. Vázquez, R. Pastor-Satorras, and A. Vespignani, Phys. Rev. E, 2002, 65: 066130

[5] C. von Ferber, Yu. Holovatch, and V. Palchykov, Condens. Matter Phys., 2005, 8: 225

[6] P. Sen, S. Dasgupta, A. Chatterjee, P. A. Sreeram, G. Mukherjee, and S. S. Manna, Phys. Rev. E, 2003, 67: 036106

[7] W. Li and X. Cai, Phys. Rev. E, 2003, 69: 046106

[8] R. Guimer`a, S. Mossa, A. Turtschi, and L. A. N. Amaral, Proc. Natl. Acad. Sci. USA, 2005, 102: 7794

[9] L. Dall’Asta, A. Barrat, M. Barthelemy, and A. Vespignani, Journal Statistical Mechanics, 2006, P04006

[10] B. J. Gluckman, T. I. Netoff, E. J. Neel, W. L. Ditto, M. L. Spano, and S. J. Schiff, Phys. Rev. Lett., 1996, 77: 4098

[11] A. Barrat, M. Barthélemy, R. Pastor-Satorras, and A. Vespignani, Proc. Natl. Acad. Sci. USA, 2004, 101: 3747

[12] A. F. Rozenfeld, R. Cohen, D. ben-Avraham, and S. Havlin, Phys. Rev. Lett., 2002, 89: 218701

[13] D. ben-Avraham, A. F. Rozenfeld, R. Cohen, and S. Havlin, Physica A, 2003, 330: 107

[14] C. P. Warren, L. M. Sander, and I. M. Sokolov, Phys. Rev. E, 2002, 66: 056105

[15] P. Sen and S. S. Manna, Phys. Rev. E, 2003, 68: 26104

[16] R. Xulvi-Brunet and I. M. Sokolov, Phys. Rev. E, 2002, 66: 026118

[17] J. Dall and M. Christensen, Phys. Rev. E, 2002, 66: 016121

[18] G. Nemeth and G. Vattay, Phys. Rev. E, 2003, 67: 036110

[19] C. Herrmann, M. Barthélemy, and P. Provero, Phys. Rev. E, 2003, 68: 26128

[20] W. Zhao, H. He, Z. Lin, and K. Yang, Acta Phys. Sin., 2006, 55: 3906

[21] K. Yang, L. Huang, and L. Yang, Phys. Rev. E, 2004, 70: 015102(R)

[22] L. Huang, L. Yang, and K. Yang, Europhys. Lett., 2005, 72: 144

[23] L. Huang, K. Yang, and L. Yang, Phys. Rev. E, 2007, 75: 036101

[24] L. Huang, L. Yang, and K. Yang, Phys. Rev. E, 2006, 73: 036102

[25] Z. Lin, L. Yang, and K. Yang, Chin. Phys. Lett., 2005, 22: 3214

[26] B. Gong, L. Yang, and K. Yang, Phys. Rev. E, 2005, 72: 037101

[27] L. Huang, K. Park, Y.-C. Lai, L. Yang, and K. Yang, Phys. Rev. Lett., 2006, 97: 164101

[28] R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, Phys. Rev. Lett., 2001, 86: 3682

[29] P. Holme, B. J. Kim, C. N. Yoon, and S. K. Han, Phys. Rev. E, 2002, 65: 056109

[30] D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys. Rev. Lett., 2000, 85: 5468

[31] R. Cohen, K. Erez, D. ben-Avraham, and S. Havlin, Phys. Rev. Lett., 2000, 85: 4626

[32] D. S. Callaway, M. E. J. Newman, S. H. Strogatz, and D. J. Watts, Phys. Rev. Lett., 2000, 85: 5468

[33] L. M. Pecora and T. L. Carroll, Phys. Rev. Lett., 1998, 80: 2109

Rights & permissions

Higher Education Press and Springer-Verlag 2008