Trade-offs between robustness and small-world effect in complex networks

Abstract

Robustness and small-world effect are two crucial structural features of complex networks and have attracted increasing attention. However, little is known about the relation between them. Here we demonstrate that, there is a conflicting relation between robustness and small-world effect for a given degree sequence. We suggest that the robustness-oriented optimization will weaken the small-world effect and vice versa. Then, we propose a multi-objective trade-off optimization model and develop a heuristic algorithm to obtain the optimal trade-off topology for robustness and small-world effect. We show that the optimal network topology exhibits a pronounced core-periphery structure and investigate the structural properties of the optimized networks in detail.

Figure 1. Degree-preserving rewiring process.

Figure 2. The change of the robustness and small-world effect E versus iterations t in single-objective optimization in different model networks.

(a) and (b) correspond to scale-free network with its power-law exponent γ = 3, while (c) and (d) correspond to ER random network with its connection probability p = 0.05. The network size is N = 100.

Figure 3. The correlation profiles of the -optimized network and the E-optimized network based on scale-free network and ER random network.

The Z score value is normalized to a range of −1 to 1 and indicated by the color. The higher the value of Z(d_i, d_j) score is, the more links between d_i-degree nodes and d_j-degree nodes the network has.

Figure 4. Optimization results on a real network.

(a) The degree distribution of the real network. (b) The values of (red) and E (blue) before and after the optimization. The real network is the social network in a karate club at a US university in the 1970s. It has 34 nodes and 78 links. The length of column with red line corresponds to the value of axis, while the column with blue shading corresponds to the E axis. The results are averaged over 100 independent realizations.

Figure 5. The visualization of original network and the optimized networks and their topological properties.

(a) original network, (b) E-optimized and (c) -optimized network have the same degree sequence. The degree of node is proportional to its size. The radar graphs show the values of topology metrics including assortativity coefficient r, clustering coefficient C, network diameter D, standard deviation of distance distribution σ_d and spectral gap SG.

Figure 6. Pareto-optimal fronts in the multi-objective optimization for and E.

The red points represent the optimized networks, and the blue points represent the original networks. The size of population is 50. Each solution in population is a scale-free network with 100 nodes, 179 links and power-law exponent γ = 3.

Figure 7. The correlation profiles and the visualization of selected networks in Pareto-optimal solutions set.

(a) The network with high E and low . (b) The network with both relatively high and E. (c) The network with high and low E. The Z score value is normalized to a range of −1 to 1 and indicated by the color. The higher the value of Z(d_i, d_j) score is, the more links between d_i-degree nodes and d_j-degree nodes the network has.

Figure 8. Topological properties of the optimized networks in Pareto-optimal solutions set.

The assortativity coefficient r, clustering coefficient C, network diameter D, standard deviation of distance distribution σ_d and spectral gap SG are listed to understand their relation to robustness and small-world effect. These topological properties of networks are in ascending order of their value of .

Figure 9. The process of crossover operator.

Firstly, two networks G_r1 and G_r2 are randomly selected for crossover operator. Suppose V_i(G_r1) is the set of neighbors of node i in G_r1. And is the set of nodes which connect to node i in G_r1 but disconnect to node i in G_r2. Similarly, V_i(G_r2) and can be obtained. Here and . Then randomly select a node m in G_r2 which connects to node j but disconnects to node k. In G_r1, links e_ij and e_kl are removed, and links e_ik and e_jl are added. In G_r2, links e_ik and e_jm are removed, and links e_ij and e_km are added. The green dot lines represent the selected links for cross operator in original network. The red dot lines represent the generated links after cross operator.