The art of interconnections: Achieving maximum algebraic connectivity in multilayer networks

Abstract

The second smallest eigenvalue of the Laplacian matrix, known as algebraic connectivity, determines many network properties. This paper investigates the optimal design of interconnections that maximizes algebraic connectivity in multilayer networks. We identify an upper bound for maximum algebraic connectivity for total weight below a threshold, independent of interconnections pattern, and only attainable with a particular regularity condition. For efficient numerical approaches in regions of no analytical solution, we cast the problem into a convex framework and an equivalent graph embedding problem associated with the optimum diffusion phases in the multilayer. Allowing more general settings for interconnections entails regions of multiple transitions, giving more diverse diffusion phases than the more studied one-toone interconnection case. When there is no restriction on the interconnection pattern, we derive several analytical results characterizing the optimal weights using individual Fiedler vectors. We use the ratio of algebraic connectivity and layer sizes to explain the results. Finally, we study the placement of a limited number of interlinks heuristically, guided by each layer’s Fiedler vector components.

1. Introduction

We live in a world of networks that are seldom isolated and often function strongly based on each other (Boccaletti et al., 2006). Such interacting networks can be found in every discipline, with social (Cozzo et al., 2015; Estrada and Gómez-Gardeñes, 2014), biological (Sahneh et al., 2012), transportation (De Domenico et al., 2014; Estrada and Gómez-Gardeñes, 2014), supply chain (Borgatti and Li, 2009; Kim et al., 2011), engineering (Buldyrev et al., 2010; Mesbahi and Egerstedt, 2010), and sport game (Buldú et al., 2018) networks representing only a few examples of systems that can perform highly interconnected dynamics. The operation of such interdependent systems may be considered in multiple layers, thereby motivating their multilayer name. While studying multilayer networks, their interlayer structural property is a focal subject area (Kivelä et al., 2014; Boccaletti et al., 2014) due to its impact on different dynamical and functional features of such networks; for example, percolation (Buldyrev et al., 2010; Son et al., 2012; Yagan et al., 2012; Kryven and Bianconi, 2019), robustness (Gao et al., 2012; Min et al., 2014; Zhang and Yagan, 2019), epidemic spreading (Saumell-Mendiola et al., 2012; Dickison et al., 2012; Yagan and Gligor, 2012; Zhuang and Yagan, 2019), synchronization (Aguirre et al., 2014; Wang et al., 2019), diffusive behavior (de Arruda et al., 2018; Cencetti and Battiston, 2019), and controllability (Moothedath et al., 2019). Consequently, significant effort have spurred toward optimizing the design of inter-structures (Yagan et al., 2012; Li et al., 2015; Tejedor et al., 2018; Moothedath et al., 2019; Pan et al., 2019; Yang et al., 2019; Chattopadhyay et al., 2019).

The second smallest eigenvalue of Laplacian of the graph represents the connectivity of networks (Van Mieghem, 2010) and was appropriately coined by Fiedler (1973), the algebraic connectivity of a graph. Moreover, the eigenvector corresponding to algebraic connectivity is named Fiedler vector that plays a key role in spectral partitioning of networks (Van Mieghem, 2010). Algebraic connectivity increases monotonically by adding links (Fiedler, 1973) and can be considered as a measure of network robustness (Jamakovic and Uhlig, 2007).

When the interconnection follows a one-to-one interconnection, with varying interlink weights, the algebraic connectivity grows linearly with increasing weights up to a critical threshold, say $c^*$ , and then enters a nonlinear region afterward (Gomez et al., 2013a). The existence of such threshold gives rise to structural transition in interdependent networks (Radicchi and Arenas, 2013). Below the threshold $c^*$ the individual networks are structurally distinguishable, while above that the multilayer network acts as a whole (Radicchi and Arenas, 2013).

In this paper, we are searching for optimal inter-structures that maximize the algebraic connectivity. In a single-layer graph, with variable edge-weights subject to a total budget, Boyd et al. (2004) and Goring et al. (2008) show that maximizing algebraic connectivity corresponds to a dual semidefinite optimization problem and the optimal solutions of the dual are related to the eigenvectors of the optimal algebraic connectivity. Additionally, the dual problem can be interpreted as an embedding of the single-layer graph in $\mathbb{R}^n$ (optimal realization of the graph in Euclidean space), and the optimal embedding has structural properties tightly connected to the separators of the graph. We pose similar problems in multilayer networks and similarly, our goal is to allocate weights on the interlayer links so as to maximize the smallest positive eigenvalue of the Laplacian. In this paper, this is achieved by formulating the primal-dual program (Boyd and Vandenberghe, 2004) and deriving its properties, and then extracting the equivalent graph realization problem and identifying its features with respect to the multilayer network’s structure.

The significant part of above works on interdependent networks has been paid on a one-to-one interconnection between nodes of different layers. Particularly, the multilayer graph is usually a multiplex where the number of nodes in each layer is the same and the interconnection matrix $B = pI$ , with $I$ being the identity matrix and $p$ the coupling strength (Wang et al., 2019). However there are many real world examples breaking the especial one-to-one interconnection pattern so that a node in a layer may interact with multiple nodes from other layer (Van Mieghem, 2016; Rapisardi et al., 2018; Wang et al., 2019). However, the functionality of such special structures is very limited.

Furthermore, an effective strategy to make an interdependent system more robust is to bring the superposition of the layers as close as possible to an all-to-all topology (Radicchi and Arenas, 2013). These motivate the present research after the recent related work (Shakeri et al., 2020) where the authors investigated the special case of multilayer networks with one-to-one interconnection. We relax the assumptions regarding one-to-one structures and allow for multilayer structures where the number of nodes in each layer can be different in a more general interconnections pattern.

When there is no restriction on the interconnection pattern, we derive several analytical results for maximum algebraic connectivity and optimal weight distribution before threshold, as well as for different transition thresholds and the conditions under which supperdiffusion is possible. Furthermore, we find out a positive correlation between optimal weights and the components of subgraph Fiedler vectors after the initial transition. We observe the role of a quantity equal to the algebraic connectivity divided by number of nodes in a subgraph, which we call specific algebraic connectivity, in sorting different results. When interconnections are restricted to a given admissible set, we note the conditions under which optimal weights are not uniform before the transition $c^*$ . This is different from conditions of multilayer networks with one-to-one interconnection (Shakeri et al., 2016, 2020) where optimal weights before $c^*$ are always uniform. Another problem pursued in this work is well-interconnected networks where our design parameter changes from interlink weights to interconnection pattern, which plays a key role in characterizing multilayer spectral properties. Van Mieghem (2016) and Wang et al. (2019) investigate the multilayer spectra under some special inter-structures. However, it is not definite which interconnection pattern will lead to maximum algebraic connectivity for a given number of interlinks. We address this problem through a simple greedy approach (Ghosh and Boyd, 2006) and observe that nodes having substantially different components in a subgraph Fiedler vector are determinative in achieving well-interconnected multilayer networks.

This paper considers the problem of assigning edge weights over a given topology of network interconnections. In a separate line of recent work, empirical observations may lead to zero weights thus dropping those edges from the network (Doherty et al., 2022). Here the edge weights can be nonuniform but fixed, while these edges can be augmented to the network. This has also found several practical applications by developing exact and upper-bounding algorithms for the network design problem of maximizing algebraic connectivity (Nagarajan et al., 2015; Nagarajan et al., 2015; Somisetty et al., 2024).

The findings of our study possess extensive implications for the design and management of multilayer systems, particularly in contexts where resilience and robustness are paramount. Such systems are represented in the design of multimodal transportation networks. In these networks, the primary objective is to forge connections between two or more transportation networks, each characterized by distinct delivery modes, through strategic linking of their nodes (Aparicio et al., 2022; He et al., 2021; Baggag et al., 2018). This integration aims to enhance the overall efficiency and robustness of the transportation infrastructure. By optimizing the interconnections between different layers of the network—such as rail, road, and air transport—the study’s insights can guide the development of more resilient multimodal systems. This is crucial for ensuring that these networks can withstand disruptions, adapt to dynamic demands, and maintain high levels of service efficiency. Ultimately, the application of these findings in multimodal transportation system design facilitates smoother, more reliable transitions between different transportation modes.

Another intriguing example of integrating multiple networks arises in the context of airline mergers driven by economic circumstances or strategic considerations (Sugishita and Masuda, 2021; Shaw and Ivy, 1994; Ciliberto et al., 2019). Such a merger presents a unique challenge in the realm of unimodal transportation networks, necessitating a strategic integration of previously separate networks. This integration often involves the introduction of new routes that serve as bridges, linking the disparate segments into a cohesive whole. Such a method not only expands the operational reach of the newly merged airline but also enhances network connectivity, facilitating smoother travel paths for passengers across a broader geographic area. The process of adding these new routes requires meticulous planning to ensure that they not only connect high-demand nodes but also optimize the overall network efficiency and robustness. This approach not only capitalizes on the synergies between the merged airlines’ assets but also aims to improve service quality and competitiveness in a challenging economic landscape. By carefully designing these connecting routes, airlines can overcome the complexities associated with network integration, ultimately leading to a unified system that is greater than the sum of its parts, offering enhanced connectivity, improved resiliency against disruptions, and a more seamless travel experience for passengers.

The main contributions of the paper are outlined as follows:

1. - In Section 3, we extend the findings of (Shakeri et al., 2016, 2020) to a more general scenario that relaxes the assumption of one-to-one interconnections. We show that the uniform optimal weights identified for interconnection strengths less than a threshold $c^*$ in (Shakeri et al., 2016, 2020) are replaced with the regularity conditions formulated within the broader framework presented in this paper.

2. - In Sections 4 and 5, we embark on a thorough exploration of optimal weights, particularly as the interconnection strength surpasses $c^*$ . Here, we introduce the concept of specific algebraic connectivity, offering valuable insights into optimal weights and sorting out various diffusion phases. We uncover and study diffusion phases that remain elusive within the setting of one-to-one interconnection patterns (Shakeri et al., 2016, 2020). Additionally, employing perturbation analysis, we unravel the intricate relationship between optimal weights and the Fiedler vector, shedding further light on their correlation.

3. - In Section 6, we explore well-interconnected multilayer networks, where our design objective transitions from optimizing weights (Shakeri et al., 2016, 2020) to optimizing the inter-structure. Here, our emphasis lies in identifying the optimal interconnection structure within the constraints of a fixed number of interlinks and their associated weights. Leveraging the relationship with the Fiedler vectors of individual layers, we introduce a heuristic algorithm specifically tailored to address this combinatorial challenge. Through a series of illustrative examples, we showcase the effectiveness and efficiency of our proposed approach.

We organize the remainder of the paper as follows. Section 2 formulates multilayer networks based on the Laplacian matrix. We formulate the maximum algebraic connectivity problem in Section 3 and derive some of its main properties. In Section 4, we consider maximum algebraic connectivity of multilayers with all-pairs interconnection possibility. Furthermore, we investigate the condition when the interlinks can be chosen only from a given admissible set in Section 5. In Section 6, we change our optimum design parameter from interlink weights to interconnections pattern and suggest well-interconnected multilayer networks. Finally Section 7 is devoted to concluding remarks and a discussion on the applications.

2. Multilayer networks

Let $G=\left (V,E\right )$ represent an undirected network and by $V=\left \{ 1,\ldots,N\right \}$ and $E\subset{\tiny\left(\begin{array}{c}V\\ 2\end{array}\right)}$ , we denote the set of nodes and links. For a link $e$ between nodes $i$ and $j$ , that is, $e\,:\,\{i,j\}\in E$ , we define a nonnegative value $w_{ij}$ as the weight of the link. Given $G$ a multilayer network, let $G_1 = \left \{ V_1,E_1\right \}$ and $G_2=\left \{ V_2,E_2\right \}$ , $|V_1|=n$ , $| V_2|=m$ , represent the layers, and a bipartite graph $G_3=\left \{ V,E_3\right \}$ with $E_3\subseteq \{\{i,j\}\,:\, i\in V_1, j\in V_2\}$ are connecting the layers. The whole multilayer network holds total number of nodes $N=n+m$ . Throughout the paper, we use the term intralayer links for $E_1$ and $E_2$ , and interlayer links for $E_3$ .

The links in $G_3$ bridge $G_1$ and $G_2$ and should be chosen strategically, for instance in a way that minimizes the disruption of the flow of information, electric power or goods, or to avoid failures against attackers and possible errors that can fragment the system or cause cascading phenomena (Buldyrev et al., 2010). The edge weights of $G_3$ are design parameters.

The Laplacian matrix is defined as:

(1) \begin{equation} L(w)\,:\!=\, \sum _{\{i,j\}\in E_1\cup E_2}B_{ij}+\sum _{\{i,j\}\in E_3}w_{ij}B_{ij}, \end{equation}

where $B_{ij}\,:\!=\, (\delta _i-\delta _j)(\delta _i-\delta _j)^T$ , for each link $\{i,j\}$ , and $\delta _i$ is the delta function at vertex $i$ . In particular, we think of the Laplacian matrix of $G$ as a function of the interlayer weights $w$ . Enumerating the vertices in $V_1$ followed by the vertices in $V_2$ , we can write $L(w)$ in block form in terms of the Laplacian matrices of the layers, $L_1$ and $L_2$ , as follows:

(2) \begin{align} L(w)= \begin{bmatrix} L_1+\text{diag}\!\left (W\textbf{1}_m\right ) & \quad -W \\ -W^T & \quad L_2+\text{diag}\!\left(W^T\textbf{1}_n\right) \end{bmatrix} \end{align}

We will first assume that it is possible to connect any node of $G_1$ to any node in $G_2$ and $W_{n\times m}=\left [w_{ij}\right ]$ consists of nonnegative weights. We use $\textbf{1}_n$ and $\textbf{1}_m$ to denote the $n$ - and $m$ -dimensional all ones vectors, respectively. Recall that the Laplacian matrix $L(w)$ is positive semidefinite and has (at least for connected networks) one zero eigenvalue with eigenvector $\textbf{1}=[1,\dots,1]^{T}$ , the vector of all ones of appropriate length. The eigenvalues of $ L(w)$ are ordered as $ 0=\lambda _1(w)\leq \lambda _2(w)\leq \lambda _3(w)\leq \dots \leq \lambda _{N}(w)$ .

3. Maximum algebraic connectivity in multilayer networks

The smallest positive Laplacian eigenvalue is called the algebraic connectivity of graphs and is characterized as:

(3) \begin{equation} \lambda _2\!\left (L\right )=\underset{\substack{v^T\textbf{1}=0{v\neq 0}}}{\text{min}} \ \ \frac{v^TLv}{\| v\|^2} \end{equation}

We maximize $\lambda _2(L)$ by distributing a total budget $c$ over the interlayer edges, formulated as:

(4) \begin{equation} F\!\left (c\right )\,:\!=\,\underset{\substack{w\geq 0 \\ w^T\textbf{1}=c}}{\text{max}} \ \lambda _2\!\left [L\!\left (w\right )\right ] \end{equation}

Lemma 1. The maximum algebraic connectivity function $F\!\left (c\right )$ in (4) is upper-bounded as:

(5) \begin{equation} F\!\left (c\right )\leq \left (\frac{1}{n}+\frac{1}{m}\right )c \end{equation}

See A.1 for the proof.

The upper-bound in (5) is independent of the number and pattern of interconnections. In a multilayer with one-to-one interconnection (Shakeri et al., 2016), $n=m$ , the bound (5) is verified as $F\!\left (c\right )\leq \frac{2c}{n}$ .

Lemma 2. The upper-bound (5) is attainable only if the following regulatory conditions are satisfied

(6) \begin{equation} W\textbf{1}_m\in \text{span}\{\textbf{1}_n\}, \ \ W^T\textbf{1}_n\in \text{span}\{\textbf{1}_m\} \end{equation}

In other words, $W$ has constant row sum and column sum. See A.2 for the proof.

Remark 1. Knowing that the total budget $c$ satisfies $\textbf{1}_n^TW\textbf{1}_m=c$ , the regularity condition (6) implies

(7) \begin{equation} W\textbf{1}_m=\frac{c}{n}\textbf{1}_n, \ \ \ W^T\textbf{1}_n=\frac{c}{m}\textbf{1}_m \end{equation}

indicating the nodes in an individual layer are all assigned the same total interlayer weight (i.e., equal weighted interlayer degree for all nodes of a layer). This generally does not imply identical weights for all interlinks. Shakeri et al. (2016) show uniform optimal weights in a one-to-one interconnection structure when $c\leq c^*$ . Another case where regularity is feasible with uniform weights is an all-pairs interconnection pattern (Van Mieghem, 2016; Wang et al., 2019a). A more general case where regularity is accompanied with uniform interlink weights is when interlayer connectivity follows $k$ -to- $k$ coupling scheme ( $k$ integer) (Wang et al., 2019b).

To further clarify Remark 1 within a practical context, consider a transportation network characterized by bimodal or multimodal features, akin to the framework outlined by He et al. (2021). Here, the budget denoted as $c$ represents the capacity for transportation between nodes belonging to distinct modalities. According to Lemma 2, in conjunction with Remark 1, it becomes evident that achieving maximal algebraic connectivity within such a transportation network necessitates an equitable distribution of interlayer transportation capacity across nodes sharing the same transportation mode. In essence, nodes operating under identical delivery modes must possess equivalent capacities for shipping goods to nodes employing different delivery modes, thus achieving the network’s maximum algebraic connectivity.

Lemma 3. Suppose the regularity conditions given by (6) are feasible. For budget values $c$ not greater than a threshold $c^*$ , $c\leq c^*$ , the solution to the maximum algebraic connectivity problem (4) is $\lambda ^*=\left (\frac{1}{n}+\frac{1}{m}\right )c$ with corresponding eigenvector $\tiny\begin{bmatrix} m\textbf{1}_n \\ -n\textbf{1}_m \end{bmatrix}$ , that is only attainable by regularity conditions (6). See A.3 for the proof.

Further bounds can be derived based on the algebraic connectivity of the individual layers and their corresponding eigenvectors. Specifically, denoting by $\lambda _2^{(1)}$ and $\lambda _2^{(2)}$ the second smallest eigenvalue of $L_1$ and $L_2$ , respectively, and by $u_2^{(1)}$ and $v_2^{(2)}$ the corresponding Fiedler vectors we have (see Appendix B):

(8) \begin{align} \lambda _2\lt \lambda _2^{(1)}+{u_2^{(1)}}^T\text{diag}\!\left (W\textbf{1}_m\right )u_2^{(1)} \end{align}

(9) \begin{align} \lambda _2\lt \lambda _2^{(2)}+{v_2^{(2)}}^T\text{diag}\!\left(W^T\textbf{1}_n\right)v_2^{(2)} \end{align}

Attempting to maximize the minimum of the right-hand sides of (8), suggests assigning most weight to the node with largest entries in the corresponding Fiedler vectors. This signifies the importance of Fiedler vectors of the layers in determining the optimal weights that will be discussed further in the paper.

The problem in (4) is a convex optimization problem with a concave objective (Sun et al., 2006) and linear constraints. For $c\le c^*$ , with regularity feasible, the solution to (4) is determined analytically. However, for $c\gt c^*$ , the optimal weights are generally nonregular and numerical solutions of are required. To this end, we recast the problem defined by (3) and (4) as a primal semidefinite programming (SDP) (Vandenberghe and Boyd, 1996; Boyd and Vandenberghe, 2004) and investigate the associated dual problem. See Appendix C for the proposed primal and dual SDPs.

4. Multilayer networks with all-pairs interconnection possibility

In this section, we remove all topological constraints and allow all-to-all interconnection in multilayer networks.

4.1 Uniform weights

Consider uniform weights for the interlinks, $w_{ij}=c/nm$ and $W=\frac{c}{nm}J$ with $J$ the $n\times m$ all ones matrix.

Lemma 4. Consider the eigenvalue problem $L\begin{bmatrix} u \\ v \end{bmatrix}=\lambda \begin{bmatrix} u \\ v \end{bmatrix}$ . In the case of uniform weights, all eigenvalues increase linearly with $c$ . Furthermore, $n-1$ nonzero solutions are

(10) \begin{equation} \lambda =\lambda _i^{(1)}+\frac{c}{n}, \ \ \ \begin{bmatrix} u \\ v \end{bmatrix}=\begin{bmatrix} u_i^{(1)} \\ 0 \end{bmatrix} \end{equation}

and $m-1$ nonzero solutions are

(11) \begin{equation} \lambda =\lambda _j^{(2)}+\frac{c}{m}, \ \ \ \begin{bmatrix} u \\ v \end{bmatrix}=\begin{bmatrix} 0 \\ v_j^{(2)} \end{bmatrix} \end{equation}

where $\lambda _i^{(1)}$ , $i=2,\ldots,n$ , are nonzero eigenvalues of $L_1$ and $u_i^{(1)}$ are the corresponding eigenvectors, $\lambda _j^{(2)}$ is the $j$ -th eigenvector of $L_2$ and $v_j^{(2)}$ the corresponding eigenvector. The last nonzero eigenvalue and its corresponding eigenvector are

(12) \begin{equation} \lambda =\left (\frac{1}{n}+\frac{1}{m}\right )c, \ \ \ \begin{bmatrix} u \\ v \end{bmatrix}=\frac{1}{\sqrt{2nm}}\begin{bmatrix} m\textbf{1}_n \\ -n\textbf{1}_m \end{bmatrix} \end{equation}

See A.4 for the proof.

The second largest eigenvalue is obtained as

(13) \begin{equation} \lambda _2\!\left [L\right ]=\text{min}\!\left [\left (\frac{1}{n}+\frac{1}{m}\right )c, \ \lambda _2^{(1)}+\frac{c}{n}, \ \lambda _2^{(2)}+\frac{c}{m}\right ] \end{equation}

Varying $c$ results in transitions among the three linear functions in (13). Figure 1(a) illustrates a case, where $n\gt m$ , $\lambda _2\!\left [L_1\right ]\gt \lambda _2\!\left [L_2\right ]$ , and $\lambda _2\!\left [L_1\right ]\!/n\gt \lambda _2\!\left [L_2\right ]\!/m$ , with two transitions occurring in

(14) \begin{equation} c^*=n\lambda _2^{(2)}, \ \ \ c^{**}=\left (\frac{1}{m}-\frac{1}{n}\right )^{-1}\left (\lambda _2^{(1)}-\lambda _2^{(2)}\right ) \end{equation}

Figure 1 also illustrates Cases 2 and 3 where each holds only one transition. The transition in Case 3 is $c^*$ in (14), and the only transition in Case 2 is

(15) \begin{equation} c^*=m\lambda _2^{(1)} \end{equation}

For the special case of subgraphs with the same number of nodes, $n=m$ , the algebraic connectivity before $c^*$ is $2c/n$ , and after $c^*$ is equal to $\lambda _2^{(0)}+c/n$ where $\lambda _2^{(0)}$ denotes the minimum algebraic connectivity of subgraphs, $\lambda _2^{(0)}=\text{min}(\lambda _2^{(1)},\lambda _2^{(2)})$ . The threshold is $c^*=n\lambda _2^{(0)}$ , in this special case.

Figure 1. Algebraic connectivity of supra-Laplacian $L$ as function of total budget $c$ for uniform weight distribution. (a) Case 1: $n\gt m$ , $\lambda _2[L_1]/n\gt \lambda _2[L_2]/m$ (thus $\lambda _2[L_1]\gt \lambda _2[L_2]$ ), (b) Case 2: $n\gt m$ , $\lambda _2[L_1]\gt \lambda _2[L_2]$ , $\lambda _2[L_1]/n\lt \lambda _2[L_2]/m$ , (c) Case 3: $n\lt m$ , $\lambda _2[L_1]\gt \lambda _2[L_2]$ (thus $\lambda _2[L_1]/n\gt \lambda _2[L_2]/m$ ).

In all three cases illustrated in Figure 1, individual network components play no role on supra-Laplacian algebraic connectivity for $c\leq c^*$ . By increasing $c$ beyond the threshold $c\gt c^*$ , the algebraic connectivities of individual layers $G_1$ and $G_2$ per unit node, that is, $\lambda _2\!\left [L_1\right ]/n$ and $\lambda _2\!\left [L_2\right ]/m$ are the main parameters characterizing the algebraic connectivity of the whole network. We call the algebraic connectivity per unit node the specific algebraic connectivity. The term “specific” is motivated by its use in thermodynamics (Sonntag et al., 2009) where it refers to a quantity per unit mass. A specific quantity is an intensive property because it does not depend on substance amount. Here, for instance, a complete graph with $n$ nodes has algebraic connectivity equal to $n$ , while its specific algebraic connectivity is unity, thus independent of graph number of nodes $n$ . As a feature of three cases of Figure 1, the subgraph with larger specific algebraic connectivity determines the supra-Laplacian algebraic connectivity only in Case 1 when $c\gt c^{**}$ , and under all other circumstances of $c\gt c^*$ it is the subgraph with smaller specific connectivity that determines the supra-Laplacian algebraic connectivity.

Super-diffusion happens when diffusion in the interconnected network spreads faster than in each individual network if isolated. In multilayer networks with one-to-one interconnection, super-diffusion is possible only if the algebraic connectivity of the average Laplacian $L_{ave}=\frac{1}{2}\left (L_1+L_2\right )$ is greater than the algebraic connectivity values of individual networks (Gomez et al., 2013b). This is possible provided the Fiedler vectors of $G_1$ and $G_2$ are far from being parallel (close-to-orthogonal) (Darabi Sahneh et al., 2015). In contrast, in all-to-all interconnection configurations, since algebraic connectivity increases linearly with $c$ , super-diffusion always occurs for sufficiently large budgets, and no restriction is imposed on Fiedler vectors of individual networks. In fact, having close-to-orthogonal Fiedler vectors in one-to-one interconnected networks means that links of $G_2$ connect those nodes that are far from each other in $G_1$ , and vice versa (Darabi Sahneh et al., 2015). Since this condition is satisfied in all-to-all interconnection regime, super-diffusion is always feasible. However, to explore whether super-diffusion is possible before the threshold $c^*$ , we investigate if the following inequality is satisfied:

\begin{equation*}\lambda _2\!\left [L\right ]\gt \text {max}\!\left (\lambda _2^{\left (1\right )},\lambda _2^{\left (2\right )}\right )\end{equation*}

Figure 1 shows that in Cases 1 and 3,

(16) \begin{equation} \frac{\lambda _2^{\left (2\right )}}{m}\lt \frac{\lambda _2^{\left (1\right )}}{n}\lt \left (\frac{1}{n}+\frac{1}{m}\right )\lambda _2^{\left (2\right )} \end{equation}

and for Case 2,

(17) \begin{equation} \frac{\lambda _2^{\left (1\right )}}{n}\lt \frac{\lambda _2^{\left (2\right )}}{m}\lt \left (\frac{1}{n}+\frac{1}{m}\right )\lambda _2^{\left (1\right )} \end{equation}

The conditions (16) and (17) set restriction on the difference between the algebraic connectivity values of the network components, and thus correlation between structural properties of the layers is required to allow super-diffusion for $c\le c^*$ . Presence of significant difference between the algebraic connectivity values of individual networks postpones super-diffusion until large interconnection strengths. Conversely, for close values super-diffusion can occur for values of $c\lt c^*$ , where the network components function distinctly, thus allowing advantage of interconnections while preserving the autonomy of each subsystem (Darabi Sahneh et al., 2015).

4.2 Maximum algebraic connectivity: A perturbation analysis

Lemmas 1 and 2 explain that the maximum algebraic connectivity is upper-bounded and the upperbound (5) is attainable subject to the regularity conditions (6). Section 4.1 shows that with uniform weights—which satisfy the regularity conditions—the algebraic connectivity can reach its upper-bound (5) in $c\leq c^*$ . Therefore, for $c\le c^*$ , the uniform weight distribution is the solution of maximum eigenvalue problem (4). Although, Lemma 3 gives the solution of maximum algebraic connectivity analytically when $c\leq c^*$ and regularity is feasible, we resort to the solution of primal and dual SDP formulations for other situations (see Appendix C for SDP). To this end, we conduct a perturbation analysis to shed some light on how the maximum algebraic connectivity behaves after $c\gt c^*$ and then investigate the SDP results for all-to-all interconnection possibility in Sections 4.3 and 4.4.

For the perturbation analysis, we consider a nominal budget $c_0$ and the associated eigenvalue problem $L_0x_0=\lambda _0x_0$ where $L_0$ is the nominal Laplacian with an eigenvalue $\lambda _0$ and corresponding eigenvector $x_0$ . Then, consider the perturbed quantities $c=c_0+\epsilon c^{\prime}, L=L_0+\epsilon L^{\prime}, \lambda =\lambda _0+\epsilon \lambda ^{\prime}, x=x_0+\epsilon x^{\prime}$ , where $\epsilon$ is sufficiently small and the quantities with prime show the levels of perturbations. Now, the eigenvalue problem $Lx=\lambda x$ is written as:

(18) \begin{equation} \left (L_0+\epsilon L^{\prime}\right )\left (x_0+\epsilon x^{\prime}\right )=\left (\lambda _0+\epsilon \lambda ^{\prime}\right )\left (x_0+\epsilon x^{\prime}\right ) \end{equation}

Equating the coefficients of $\epsilon$ in both sides of (18), we have

(19) \begin{equation} L_0x^{\prime}+L^{\prime}x_0=\lambda _0x^{\prime}+\lambda ^{\prime}x_0 \end{equation}

Inner product of (19) by $x_0$ yields the following expression for the perturbed value $\lambda ^{\prime}$

(20) \begin{equation} \lambda ^{\prime}=\frac{x_0^TL^{\prime}x_0}{\|x_0\|^2} \end{equation}

Figure 1(a) shows the above analysis for Case 1 at the threshold budget, $c_0=c^*$ . We know that before $c^*$ the optimal weights are the uniform ones and that at threshold $c^*$ the second and third eigenvalues coalesce and the third eigenvalue (before $c^*$ ) becomes the algebraic connectivity (right after $c^*$ ). Therefore, we repeat the perturbation analysis for the third eigenvalue $\lambda _3$ at $c^*$ ; using the results of Section 4.1 for Case 1, for $c_0=c^*$ ,

\begin{equation*} \lambda _0=\lambda _3=\lambda _2^{\left (2\right )}+\frac {c^*}{m}, x_0=\begin {bmatrix} 0 \\ v_2^{\left (2\right )} \end {bmatrix}, L^{\prime}=\begin {bmatrix} \text {diag}\!\left (W^{\prime}\textbf{1}_m\right ) & -W^{\prime} \\ -{W^{\prime}}^T & \text {diag}\!\left ({W^{\prime}}^T\textbf{1}_n\right ) \end {bmatrix}. \end{equation*}

where $W^{\prime}$ is the perturbed weight matrix due to the perturbed budget $c^{\prime}$ . Substituting the above $x_0$ and $L_0$ into (20) and after normalizing the eigenvector $\|v_2^{\left (2\right )}\|=1$ , we obtain the following expression for the increment in algebraic connectivity beyond $c^*$

(21) \begin{equation} \lambda ^{\prime}_2={v_2^{\left (2\right )}}^T\text{diag}\!\left ({W^{\prime}}^T\textbf{1}_n\right )v_2^{\left (2\right )} \end{equation}

Considering $\lambda =\lambda _0+\epsilon \lambda ^{\prime}$ , we can approximate the algebraic connectivity for budget values just above $c^*$ . Therefore, maximizing the perturbed value (21) can be regarded as an equivalent problem for maximizing the algebraic connectivity for sufficiently small increments of $c$ beyond $c^*$ .

We mention two highlights in maximizing (21); first, diagonal elements of $\text{diag}\!\left ({W^{\prime}}^T\textbf{1}_n\right )$ represent the total weight assigned to each node in Layer 2 and thus $\lambda ^{\prime}_2$ only depends on the interlink weights of nodes in Layer 2. Thus, the optimization mechanism will make no difference between nodes in Layer 1 and continue allocating equal interlink weights to all nodes in this layer and the nodes in Layer 1 still experience uniform total interlink weights. Second, the increment in algebraic connectivity in (21) is correlated with the Fiedler vector of $L_2$ . Consequently, maximizing (21), require assigning the weights in vector ${W^{\prime}}^T\textbf{1}_n$ to nodes with larger $\left (v_2^{\left (2\right )}\left (i\right )\right )^2$ , or larger absolute value $|v_2^{\left (2\right )}\left (i\right )|$ .

In summary, for sufficiently small increments of budget beyond $c^*$ , while the optimal weights in the Layer with larger specific connectivity, remain uniform, the optimal weights in the other Layer are positively correlated with Fiedler vector. However, this situation turns conversely for larger budget values above the second threshold $c^{**}$ . This will be illustrated in next subsection.

We can get similar results for Cases 2 and 3 in Figure 1(b) and 1(c). In particular for Case 2, note that for $c_0=c^*=m\lambda _2^{\left (1\right )}$ the third eigenvalue is $\lambda _2^{\left (1\right )}+\frac{c}{n}$ . The corresponding eigenvector is $x_0=\begin{bmatrix} u_2^{\left (1\right )} \\ 0 \end{bmatrix}$ . Using the above perturbation approach, we get the following increment for algebraic connectivity just above $c^*$

(22) \begin{equation} \lambda ^{\prime}_2={u_2^{\left (1\right )}}^T\text{diag}\!\left (W^{\prime}\textbf{1}_m\right )u_2^{\left (1\right )} \end{equation}

Likewise, by increasing the total budget $c$ beyond $c^*$ in Case 2, the optimal weight distribution for nodes in the layer with smaller specific connectivity (Layer 1) will be positively correlated with Fiedler vector, and optimal weights for nodes in layer with larger specific connectivity (Layer 2) will remain uniform. For Case 3, we get the same relation given in (21).

In the context of a bimodal transportation system, where each layer represents a distinct network of transportation modes (for instance, one layer could be a network of bus routes, and the other could be a network of subway lines), the concept of algebraic connectivity elucidates the optimal strategy for allocating resources to enhance the overall efficiency and accessibility of the transportation system. Considering the budget as the capacity or intensity of the intermodal connections (i.e., the weight of interlayer edges that facilitate passenger transfers between bus and subway systems), perturbation analysis becomes a pivotal tool for determining how increments in the budget can optimally enhance the system’s connectivity. When the budget is below a certain threshold (denoted as $c^*$ ), an even distribution of resources across all intermodal links maximizes connectivity, ensuring that transfers between modes are uniformly facilitated. However, as the budget exceeds $c^*$ , the analysis indicates a nuanced shift in strategy; resources should be allocated in a manner that is directly influenced by the patterns of usage and demand within the system, as identified through the perturbation analysis. Specifically, enhancements should target connections that are critical to improving the system’s overall flow, as determined by the analysis of eigenvalues and eigenvectors of the system’s Laplacian matrix, signifying a move toward a more demand-driven allocation of intermodal resources. This approach not only maximizes the utility of additional resources beyond the budget threshold but also ensures that the bimodal transportation network adapts to evolving passenger needs and usage patterns, thereby enhancing its efficiency and service quality.

4.3 Primal problem

The SDP (31) can be solved efficiently using convex solvers, for example, CVX package by Grant and Boyd (2009). Figure 2 shows the optimal results for an example of Case 1. Figure 2(a) compares the maximum algebraic connectivity with uniform weights case.

In Figure 2(b) and 2(c), we observe while the optimal weights assigned to nodes in Layer 1 remain uniform for budgets up to $c^{**}$ , they start to become inhomogeneous in Layer 2 right above $c^*$ . Here, Layer 1 holds the larger specific algebraic connectivity and Layer 2 holds the smaller one. Figure 3(a) and 3(b), further clarify that, after $c^*$ , the optimal weights in Layer 2 are positively correlated with Fiedler vector components of this layer—these results are in accordance with our perturbation results in Subsection 4.2.

For $c\gt c^{**}$ , Figure 2(b) illustrates that weight distribution in Layer 1 becomes heterogeneous and many nodes experience zero interlink weights. Investigation of optimum weights in Figure 3(c) reveals that the nodes with no interlinks in Layer 1 are those with smallest components in Fiedler vector. On the contrary, optimal weights in Layer 2 again become (almost) uniform for some budget $c\gt c^{**}$ (see Figure 2(c)) where for strong coupling strength $c$ , the intralinks in the layer with smaller specific algebraic connectivity (here Layer 2) lose their significance against very strong interlinks. This causes the nodes in this layer to be not effectively discriminated by an optimal mechanism, and uniform weights are expected. Primal problems for Cases 2 and 3 in Figure 1 are solved similarly (see Appendix D.1).

Figure 2. SDP results for an example of Case 1 in Figure 1: (a) Algebraic connectivity of supra-Laplacian $L$ as function of total budget $c$ , (b) optimal interlayer weights assigned to nodes in Layer 1, and (c) optimal interlayer weights assigned to nodes in Layer 2, for two Geo networks with $n=30, m=15, \lambda _2^{(1)}=0.6798,\lambda _2^{(2)}=0.0712, c^*=2.1373, c^{**}=18.2554$ .

Figure 3. Optimal weights as function of Fiedler vector components corresponding to Figure 2 in (a) Layer 2 for $c=5$ , (b) Layer 2 for $c=20$ , and (c) Layer 1 for $c=30$ .

4.4 Dual problem and embedding

We investigate geometric dual problems of Case 1 in Figure 1 to show different diffusion phases in various regions of optimal weights. Similar problems for Cases 2 and 3, as well as one more example of Case 1, are discussed in D.2. For Case 1, Figure 4 shows the embedding of the examples that previously analyzed by solving the primal problem (Figure 3 and Figure 1(a)). For $c\lt c^*$ in Figure 4(a), we observe the clumped pattern predicted by Lemma 1. For the intermediate value $c^*\lt c\lt c^{**}$ in Figure 4(b), we note that while the nodes in Layer 1 with larger specific connectivity keep their clumped pattern, the nodes in Layer 2 with smaller specific connectivity become distributed around the clumped nodes. The conditions is reversed for larger $c\gt c^{**}$ in Figure 4(c) where nodes in Layer 2 are clumped together while in Layer 1 are distributed. Different embedding patterns illustrate different diffusion phases as discussed in Appendix E. The results are as follows. For small $c\lt c^*$ in Figure 4(a), we observe an intralayer phase of optimal diffusion in both layers. For intermediate budgets $c^*\lt c\lt c^{**}$ in Figure 4(b), while optimal diffusion in Layer 1 is still in intralayer phase, it is through both intralinks and interlinks in Layer 2. For large budget values $c\gt c^{**}$ in Figure 4(c), the situation is converse; while Layer 1 undergoes a combination of intralayer and interlayer diffusion phases, Layer 2 undergoes a single phase of interlayer.

Figure 4. Graph embeddings corresponding to Figure 2 for (a) $c=1$ , (b) $c=10$ , and (c) $c=30$ .

5. Interconnections constrained to an admissible set

In Section 4, we had constraint only on the total budget $c$ and no restriction on the number or patterns of interlinks. In this section, we consider a situation where the number of interlinks is limited and we can assign weights only to an admissible set $\left (i,j\right )\in E_a\subset E_3$ and all other edges $E_3/E_a$ have zero weight.

For $c\leq c^*$ and following Lemma 3, we know that regular weight distribution leads to maximum algebraic connectivity. The regularity condition (6) is generally not feasible for all interconnection patterns. When regular interconnection is not feasible for a given set of admissible interlinks, the bound $\lambda ^*_2=\left (\frac{1}{n}+\frac{1}{m}\right )c$ is not attainable and there is generally no region of optimal uniform weights. In such conditions, the region $c\leq c^*$ corresponding to uniform weights, and hence the associated transition fades away (see Figure 5). This means, with no regularity, there is no region for unified operation of individual network components. As a consequence, interlinks start to contribute to diffusion within each individual layer from small values of coupling strength $c$ .

Figure 5. Optimal weights for maximizing algebraic connectivity in a multilayer including two ER networks, each with 30 nodes, and 60 interlinks for (a) $k$ -to- $k$ interconnection with $k=2$ , and (b) random interconnections. In (a) regularity is feasible with uniform weights before $c^*$ , while in (b), without regularity feasible, optimal weights are always distributive (nonuniform) and there is no uniform optimal weights region. After $c^*$ , maximum algebraic connectivity in both patterns is attained by a weight distribution that does not satisfy the regularity conditions.

Lemma 3 implies that for a given set of admissible interlinks, regular interconnection is feasible, the maximum algebraic connectivity and the corresponding Fiedler vector are the same for all interconnection patterns for $c\leq c^*$ . Therefore, before the threshold there is no dependency of maximum algebraic connectivity on the number of interconnections or admissible set $E_a$ . However, what distinguishes between different interconnection patterns is the value of threshold $c^*$ that depends on the number and pattern of interlinks. We have shown that for the case of all-pairs interconnection, $c^*$ is computed by (14) and (15). However, there is no explicit expression for $c^*$ in general regular interconnections. For particular configurations, Darabi Sahneh et al. (2015); Van Mieghem (2016); Wang et al. (2019) provide some bounds, and for one-to-one interconnection pattern, the exact threshold budget is calculated in Darabi Sahneh et al. (2015), and in Shakeri et al. (2016) from different approaches.

Moreover, Wang et al. (2019) shows that for regular $k$ -to- $k$ interconnections, the transition threshold $c^*$ is upper-bounded by the minimum algebraic connectivity of subgraphs times $n$ , and lower-bounded by it times $n/2$ , that is, when $n=m$ it follows $\frac{n\lambda _2^{(0)}}{2}\leq c^*\leq n\lambda _2^{(0)}$ . The upper-bound is attained when $k=n$ . This implies that, the coupling is postponed as much as possible through a complete interconnection; or equivalently, for a given total budget $c$ the weakest coupling occurs with all-pairs interconnection.

Figure 6. Graph embedding of a $k$ -to- $k$ interconnected multilayer including two random ER networks, each with 30 nodes, and different values for $k$ , number of interlinks, and total budget $c$ . For the first, second, and third rows from above we have $k=1$ , $k=2$ , and $k=3$ , and the number of interlinks are 30, 60, and 90, respectively. the values of $c$ are as follows: (a) $c=10$ , (b) $c=100$ , (c) $c=1000$ , (d) $c=10$ , (e) $c=100$ , (f) $c=10^5$ , (g) $c=10$ , (h) $c=1000$ , (i) $c=10^6$ .

Among numerous inter-structures satisfying regularity, the class of $k$ -to- $k$ interconnectivity pattern, which is a generalization of the one-to-one scheme, is representative of more real interdependent networks (Wang et al., 2019). To unravel more facts about optimized $k$ -to- $k$ interconnections, Figure 6 shows embedding results for $k=1$ , $k=2$ , and $k=3$ , respectively. These figures use the same individual network components where $c\gt c^*$ . Figure 7 shows the corresponding maximum algebraic connectivity values. For the smaller budget $c=10$ in Figure 6(a), 6(d), and 6(g), we observe that the most unified embedding of individual network components is associated with $k=3$ , next followed by $k=2$ and $k=1$ . Therefore, for a given total budget $c$ , the larger the number of interconnections, the weaker the coupling. However, Figure 7 illustrates that the algebraic connectivity increases with increasing the number of interconnections for a given total budget. Therefore, despite the networks coupling is becoming weaker by increasing the number of interlinks for fixed total budget $c$ , the diffusion becomes faster in such a condition—the speed of diffusion and the modes of diffusion are two distinct properties (Darabi Sahneh et al., 2015).

For intermediate values of total budget $c$ , the main observation in Figure 6(b), 6(e), and 6(h) is that the one-to-one interconnection holds the minimum embedding space dimension of 2, which increases by 3 in two other cases $k=2$ and $k=3$ . For the larger budget $c$ in Figure 6(c), when $k=1$ , it is seen that each two interlinked nodes are embedded at the same point. Hence, the interlinked nodes are unified due to significant coupling strength $c$ . In such conditions, in one-to-one interconnected networks, the diffusion is connected with an average Laplacian (Radicchi and Arenas, 2013). An average network can also be concluded in Figure 6(i) where nodes from different networks are embedded in pairs at same point. However, here, for $k=3$ , the average network associated with intralinks is elaborated with a circle network of interlinks. This circle of interlinks will promote diffusion with respect to one-to-one interconnected. This is verified by comparing the cases $k=1$ and $k=3$ in Figure 7. For the odd interconnection pattern $k=2$ in Figure 6(f), the existence of an average network for large $c$ is not directly deducible.

Figure 7. Maximum algebraic connectivity for $k$ -to- $k$ interconnection of two ER networks with $n=m=30$ .

6. Well-interconnected multilayer networks

In Section 5, we observed the importance of the admissible set $E_a$ in final characterization of interdependent network. In this section we ask two questions; First, which interconnection pattern leads to the optimal performance. For multilayers with one-to-one interconnection, Gomez et al. (2013a) show that the super-diffusion occurs only if some definite condition is satisfied; namely, if the algebraic connectivity of the average Laplacian $L_{ave}=\frac{1}{2}\left (L_1+L_2\right )$ is greater than the algebraic connectivity values of individual network components. Second, if there is any other interlink connection strategy, other than the one-to-one connection strategy that with a given number of interlinks, can lead to super-diffusion without satisfying the condition proposed by Gomez et al., To answer these questions, we use an interlink connection strategy based on a greedy approach by means and show that the approach can result in super-diffusion without requiring the algebraic connectivity of average Laplacian greater than those of individual networks.

We investigate the situation where, for constant budget $c$ and number of interlinks $r$ , the weights $w_{ij}=w_0=c/r$ assigned to all interlinks are identical, and in turn interconnection pattern is the design parameter. The general optimization problem is combinatorially difficult. A heuristic is following the greedy method in Ghosh and Boyd (2006) that is developed for well-connected single-layer networks. By previous analyses, it is evident that, for small budgets $c$ , the optimal interconnection pattern is regular, if feasible. However, this is not the case for larger budget values, and we will see that, for a larger given total budget $c$ , the optimal interconnection pattern is generally not a regular one, such as a $k$ -to- $k$ coupling scheme—although it is feasible.

Our design parameter is choosing the inter-structure with given number of interlinks $r$ . Based on the greedy approach in Ghosh and Boyd (2006), we add $r$ edges one at a time, each time choosing the interlink $e\sim \{i,j\}$ , between nodes $i\in V_1$ and $j\in V_2$ , which has the largest value of $(v_i-v_j)^2$ with $v$ being a unit Fiedler vector of the current Laplacian. The motivation for this heuristic is that, when $\lambda _2$ is isolated, $w_0(v_i-v_j)^2$ gives the first order approximation of the increase in $\lambda _2$ , if edge $e\sim \{i,j\}$ with weight $w_0$ is added to the graph.

Figure 8 shows a small well-interconnected network. Here, supper-diffusion is not possible with a one-to-one interconnection since $\text{max}\!\left (\lambda _2\!\left [L_1\right ],\lambda _2\!\left [L_2\right ]\right )\gt \lambda _2\!\left [L_{ave}\right ]$ , and hence, the condition suggested by Gomez et al. (2013a) is not met. The one-to-one interconnected pattern used as reference case in this section follows a multiplex setting (Wang et al., 2019). However, it is observed that under a well-interconnected strategy, the diffusion in multilayer network immediately turns into super-diffusion after small values of budget $c$ . In fact, the well-interconnected multilayer is achieved only at the expense of one change with respect to a one-to-one interconnection pattern. This further highlights the impact of interconnection pattern on structural properties of interdependent networks.

Figures 9 and 10 unravel more properties of well-interconnected networks. In Figure 9, we note an interconnection pattern where nodes that are far from each other in an individual network component are bridged by nodes in the other layer. Therefore, overall interconnected network gains increased connectivity among its nodes compared to each isolated component. In a one-to-one interconnection setting, such condition is possible only by close-to-orthogonal Fiedler vectors (Darabi Sahneh et al., 2015). Moreover, Figure 10 unfolds an interconnection pattern that is essentially inhomogeneous as only few nodes in Layer 2 undergo interlinks. On the other hand, all nodes in Layer 1 are (equally) assigned interlink. What marks this situation is the large gap between algebraic connectivity values of individual network components, with Layer 2 holding the (very) larger algebraic connectivity. Furthermore, the Nodes 3 and 5 of Layer 2, that is, the nodes assigned most interlinks in subgraph with larger connectivity, hold the most negative and positive values in this subgraph Fiedler vector, and each bridges nodes with different signs in Fiedler vector of Layer 1.

Figure 11 shows the results for two Geo networks each with 30 nodes. The feature is that, while the numbers of interlinks assigned in Layer 2 with smaller algebraic connectivity are more uniform and most nodes are assigned one interlink, the nodes in Layer 1 with larger algebraic connectivity are assigned more different interlinks. In fact, the nodes with most interlinks in Layer 1 are those corresponding to the most negative and positive values in this layer Fiedler vector.

In all above examples, the well-interconnected graph is not regular for the given $c$ . To emphasize that the well-interconnected pattern depends on the budget $c$ given, we show in Figure 12 the situation where the interlinks may or may not be regular depending on $c$ .

Figure 8. (a) Small well-interconnected multilayer network for $c=10$ with $n=m=6$ and $\lambda _2[L_1]=1, \lambda _2[L_2]=0.4384$ , and (b) $\lambda _2$ as function of total budget $c$ .

Figure 9. (a) Small well-interconnected multilayer network for $c=10$ with $n=m=6$ and $\lambda _2[L_1]=1.2679, \lambda _2[L_2]=0.4384$ , and (b) $\lambda _2$ as function of total budget $c$ . The well-interconnected strategy bridges the nodes that are far from each other in a subgraph. Therefore, Nodes 4 and 5 that are far from each other in Layer 1 are interconnected to the common Node 6 in Layer 2. In the same manner, the Node 1 in Layer 1 is interconnected with two far Nodes 2 and 5 in Layer 2, and the Node 4 in Layer 1 is interconnected to far Nodes 1 and 6 in Layer 2. Moreover, the Nodes 1 and 4 that are far in Layer 1 are interlinked to Nodes 1 and 2 that are close in Layer 1. Therefore, the diffusion between nodes that are far from each other in an individual network component speeds up by interconnecting to a common node, or some closer nodes, within the other layer.

Figure 10. (a) Small well-interconnected multilayer network for $c=20$ with $n=m=10$ and $\lambda _2[L_1]=0.1338, \lambda _2[L_2]=1.4498$ , and (b) $\lambda _2$ as function of total budget $c$ . Figure indicates an unbalanced interlink assignment strategy where the nodes of the set {3, 5} in Layer 2, with the very larger algebraic connectivity, undergo the most interlinks in this layer and bridge the nodes that are far from each other in Layer 1, having the very smaller algebraic connectivity.

Figure 11. Well-interconnection of two Geo networks each with 30 nodes: (a) $\lambda _2$ as function of $c$ , and number of interlinks for each node in Layer (b) 1 with larger algebraic connectivity ( $\lambda _2=2.3621$ ), and (c) 2 with smaller algebraic connectivity ( $\lambda _2=0.2101$ ).

Figure 12. (a) Small well-interconnected multilayer network in Figure 8 revisited with $2n=12$ admissible interlinks: (a) for smaller budget $c=1$ the well-interconnected graph is a regular $k$ -to- $k$ interconnection with $k=2$ , and (b) for larger budget $c=2$ the well-interconnected graph is not regular.

In the context of a bimodal transportation system, where each layer represents a distinct mode of transportation—such as road networks for vehicles and pathways for cyclists—the optimization of interlayer connections emerges as a pivotal challenge. Given a fixed budget that dictates the capacity and number of intermodal links (e.g., bridges or tunnels that facilitate transitions between cycling paths and roads), our investigation adopts a strategic approach to determine the most effective pattern of interconnection. Leveraging the insights from the greedy approach outlined previously, we prioritize the establishment of intermodal links that promise the greatest increase in system-wide accessibility and fluidity of movement across transportation modes. This method entails the analytical selection of interlayer edges, where each link is appraised for its potential to significantly enhance the algebraic connectivity of the bimodal system. Such a strategy diverges from conventional uniform or one-to-one interconnection models, advocating instead for a nuanced allocation of resources. By focusing on strategic link placement based on the differential impact on the network’s connectivity, this approach aims to maximize the efficiency and cohesiveness of the transportation system within the constraints of a limited budget. This methodology underscores the critical role of targeted investments in intermodal infrastructure to facilitate superior connectivity and ensure the optimal integration of diverse transportation networks.

7. Conclusion and discussion

In this paper, we considered optimal interlayer weights and structure determination for maximizing the algebraic connectivity in multilayer networks. We first investigated optimal weight distribution subject to a total budget $c$ . Using an appropriate formulation of maximum algebraic connectivity problem, we showed analytically that before a known threshold budget $c^*$ , the maximum algebraic connectivity is attainable subject to a set of regularity conditions, which may or may not lead to uniform weights depending on inter-structure pattern. For efficient numerical solution of larger budget $c\gt c^*$ , we presented a convex formulation of the considered optimization problem. Under a primal-dual setting, we obtained a graph embedding problem that enables easier interpretations of some physical aspects. In particular, we found the graph embedding related to the phase of diffusion, as well as interlayer and intralayer interactions, over the multilayer graph. We showed that when $c\leq c^*$ , the graph embedding is one-dimensional and implies intralayer phase of optimum diffusion. When regularity is feasible in such a small budget condition, graph embedding involves nodes in same layers clumped together. The most apparent cases of this situation are the case of no restriction on interconnection pattern, that is, when all nodes in one layer are allowed to be connected to all nodes in the other layer, and the case of $k$ -to- $k$ interconnection pattern. For larger budgets beyond $c^*$ , interactions between interlayer and intralayer connections result in graph embeddings of higher dimensions, and more diverse versions of intralayer and interlayer phases of optimal diffusion emerge. It was observed that while in an all-to-all interconnection pattern any interlink is possible, the optimal inter-structure may include many interlinks with zero weights. Using a perturbation analysis, we found out a positive correlation between optimal weights and Fiedler vector components of subgraphs. When sorting several results, we also noted the role of specific algebraic connectivity, that is, algebraic connectivity divided by number of nodes in a subgraph. Additionally, we investigated determination of optimal inter-structure that, for a given number of interlinks with identical weights, yields the maximum algebraic connectivity. In this regard, we concluded another role of subgraphs Fiedler vectors in identifying optimized inter-structures, which may or may not be regular depending on weight per number of interlinks.

The findings of this study have far-reaching implications in designing and managing multilayer systems where resiliency and robustness are of concern. Two cases of such systems are exemplified by multimodal transportation networks and airline mergers. In multimodal networks, the goal is to enhance infrastructure efficiency and robustness by strategically connecting networks with different delivery modes, such as rail, road, and air transport. This ensures networks can withstand disruptions, adapt to changing demands, and maintain high service efficiency. Similarly, airline mergers, driven by economic or strategic needs, require careful integration of previously separate unimodal networks. This involves planning new routes to connect disparate segments, thereby expanding operational reach and enhancing network connectivity. Such strategic integration not only leverages synergies between the assets of merged airlines but also aims to bolster service quality and market competitiveness. Both examples underline the importance of optimizing network interconnections to create more resilient, efficient, and seamless transportation systems for users.