Synchronization in weighted uncorrelated complex networks in a noisy environment: Optimization and connections with transport efficiency

Motivated by synchronization problems in noisy environments, we study the Edwards-Wilkinson process on weighted uncorrelated scale-free networks. We consider a specific form of the weights, where the strength (and the associated cost) of a link is proportional to $(k_i{k}_j{)}^{\beta }$ with $k_i$ and $k_j$ being the degrees of the nodes connected by the link. Subject to the constraint that the total edge cost is fixed, we find that in the mean-field approximation on uncorrelated scale-free graphs, synchronization is optimal at ${\beta }^{*}=-1$. Numerical results, based on exact numerical diagonalization of the corresponding network Laplacian, confirm the mean-field results, with small corrections to the optimal value of ${\beta }^{*}$. Employing our recent connections between the Edwards-Wilkinson process and resistor networks, and some well-known connections between random walks and resistor networks, we also pursue a naturally related problem of optimizing performance in queue-limited communication networks utilizing local weighted routing schemes.

Figure 1

(Color online) Height fluctuations as a function of the degree of the nodes for $N=1000$, $⟨k⟩=20$, and for (a) $\beta =-2.00$, (b) $\beta =-1.50$, (c) $\beta =-1.00$, and (d) $\beta =0.00$. Data, represented by filled symbols, are averaged over all nodes with degree $k$. Scatter plot (dots) for individual nodes is also shown from ten network realizations. Solid lines correspond to the $\mathrm{MF}+\mathrm{UC}$ scaling $⟨(\mathrm{\Delta }h{)}^2{⟩}_k\sim k^{-(\beta +1)}$.

Figure 2

(Color online) (a) Steady-state width of the EW synchronization landscape as a function of the weighting parameter $\beta$ for the BA networks for $N=1000$ with various average degree $\overline{k}\simeq ⟨k⟩\simeq 2m$. Solid curves are the approximate $(\mathrm{MF}+\mathrm{UC})$ results [Eq. (24)] for the same degree. For comparison, numerical results for SW networks with the same degree (with the respective open symbols) are also shown. Also, see Table for actual numerical values for $\beta =-1$. (b) Scaled width as a function of the weighting parameter $\beta$. The solid curve is the scaled approximate $(\mathrm{MF}+\mathrm{UC})$ result [Eq. (24)]. The horizontal dashed line indicates the (similarly scaled) absolute lower bound, as achieved by the fully connected network with the same cost $N⟨k⟩∕2$.

Figure 3

(Color online) Steady-state width of the EW synchronization landscape as a function of $1∕m$ for the BA networks for $\beta =0.00$ (solid symbols) and $\beta =-1.00$ (respective open symbols), for three different system sizes. Straight lines (solid for $\beta =0$ and dashed for $\beta =-1$) correspond to the $\mathrm{MF}+\mathrm{UC}$ approximation Eq. (24).

Figure 4

(Color online) Normalized RW node betweenness on BA networks with $m=3$ as a function of the degree of the nodes for four system sizes [$N=$ 200 (dotted), 400 (dashed), 1000 (long-dashed), 2000 (solid)] for (a) $\beta =-2.00$, (b) $\beta =-1.00$, (c) $\beta =0.00$, and (d) $\beta =1.00$. Data point represented by lines are averaged over all nodes with degree $k$. Data for different system sizes are essentially indistinguishable. Scatter plot (dots) for the individual nodes is also shown from ten network realizations for $N=1000$. Solid curves, corresponding to the $\mathrm{MF}+\mathrm{UC}$ scaling $B\left(k\right)\sim k^{\beta +1}$ [Eq. (35)], are also shown.

Figure 5

(Color online) Cumulative distributions of the normalized RW node betweenness for BA networks with $m=3$, for four values of $\beta$, each with four system sizes. The four families of cumulative distributions correspond to the four different values of $\beta$, from left to right in the figure, $\beta =-1.00$, $-2.00$, $0.00$, and $1.00$. Each family has four system sizes: $N=200$ (dotted), 400 (dashed), 1000 (long-dashed), and 2000 (solid curves). Finite-size effects are only significant for $\beta =0.00$ and $\beta =1.00$. Straight dashed lines correspond to the predicted power-law tail of the cumulative distribution for $\beta >-1$, $P_{>}\left(B\right)\sim B^{(1-\gamma )∕(1+\beta )}$.

Figure 6

(Color online) Critical network throughput per node as a function of the weighting parameter $\beta$ for BA networks (solid symbols) for various system size for (a) $m=3$ and for (b) $m=10$. Figure (a) also shows the same observable for SW networks (the same respective open symbols) for the same system sizes.

Figure 7

(Color online) Scaled critical network throughput per node for different system sizes [as suggested by Eq. (43)] for BA networks $(\gamma =3)$ as a function of the weighting parameter $\beta$ in the $\beta >-1$ region for (a) $m=3$ and (b) $m=10$.