Maximizing algebraic connectivity in interconnected networks

Algebraic connectivity, the second eigenvalue of the Laplacian matrix, is a measure of node and link connectivity on networks. When studying interconnected networks it is useful to consider a multiplex model, where the component networks operate together with interlayer links among them. In order to have a well-connected multilayer structure, it is necessary to optimally design these interlayer links considering realistic constraints. In this work, we solve the problem of finding an optimal weight distribution for one-to-one interlayer links under budget constraint. We show that for the special multiplex configurations with identical layers, the uniform weight distribution is always optimal. On the other hand, when the two layers are arbitrary, increasing the budget reveals the existence of two different regimes. Up to a certain threshold budget, the second eigenvalue of the supra-Laplacian is simple, the optimal weight distribution is uniform, and the Fiedler vector is constant on each layer. Increasing the budget past the threshold, the optimal weight distribution can be nonuniform. The interesting consequence of this result is that there is no need to solve the optimization problem when the available budget is less than the threshold, which can be easily found analytically.

Figure 1

A schematic of a multiplex network $\mathcal{G}$ with two layers ${\mathcal{G}}_1,{\mathcal{G}}_2$, connecting through an interlayer one-to-one structure ${\mathcal{G}}_3$.

Figure 2

(a) and (b) Plots of ${\lambda }_2\left(L\right)$ with different amount of available budget. The solid (red) line is for the optimal weights, and the dashed (black) line is for uniform weights. The threshold budget and upper bound are shown with vertical (green) dotted and horizontal (blue) dot-dashed lines, respectively. The upper bound is from Eq. (12), and the threshold is from Eq. (10). (a) A structure of two Erdös-Renyi networks each with 30 nodes and (b) a structure of two scale-free networks each with 30 nodes. (c) First five eigenvalues of Laplacian matrix of $\mathcal{G}$ considering a uniform distribution of weights for the multiplex in (b). (d) First five eigenvalues of Laplacian matrix of $\mathcal{G}$ considering an optimal distribution of weights for the multiplex in (b).

Figure 3

Optimal weight distribution for different amount of budgets. The stucture of a multiplex with two scale-free network layers, with $N=100$ nodes and $|{\mathcal{E}}_1|=196$ and $|{\mathcal{E}}_2|=291$. In (a) the budget is lower than threshold and uniform distribution is optimal. In this example, the threshold budget $c^{*}$ is $51.4$.

Figure 4

Optimal weight distribution for different amount of budgets. The structure of a multiplex with two scale-free network layers, with $N=100$ nodes and $|{\mathcal{E}}_1|=358$ and $|{\mathcal{E}}_2|=362$. In (a) budget is lower than threshold and uniform distribution is optimal. In this example, the threshold budget $c^{*}$ is 64.