key: cord-0616784-rtwka9dz
authors: Tavasoli, Ali; Ardjmand, Ehsan; Shakeri, Heman
title: Maximizing the algebraic connectivity in multilayer networks with arbitrary interconnections
date: 2020-08-29
journal: nan
DOI: nan
sha: bd0d771ddcbf12607b115b385ab3eee92d11a791
doc_id: 616784
cord_uid: rtwka9dz

The second smallest eigenvalue of the Laplacian matrix is determinative in characterizing many network properties and is known as algebraic connectivity. In this paper, we investigate the problem of maximizing algebraic connectivity in multilayer networks by allocating interlink weights subject to a budget while allowing arbitrary interconnections. For budgets below a threshold, we identify an upper-bound for maximum algebraic connectivity which is independent of interconnections pattern and is reachable with satisfying a certain regularity condition. For efficient numerical approaches in regions of no analytical solution, we cast the problem into a convex framework that explores the problem from several perspectives and, particularly, transforms into a graph embedding problem that is easier to interpret and related to the optimum diffusion phase. Allowing arbitrary interconnections entails regions of multiple transitions, giving more diverse diffusion phases with respect to one-to-one interconnection case. When there is no limitation on the interconnections pattern, we derive several analytical results characterizing the optimal weights by individual Fiedler vectors. We use the ratio of algebraic connectivity and the layer sizes to explain the results. Finally, we study the placement of a limited number of interlinks by greedy heuristics, using the Fiedler vector components of each layer.

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; 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; , diffusive behavior (de Arruda et al., 2018; Cencetti and Battiston, 2019) , and controllability (Moothedath et al., 2019) . Consequently, significant effort have spurred towards optimizing the design of inter-structures 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 Lagrangian 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) . Moreover, various bounds in graph partitioning, optimal graph labeling, min-sum problems, or bandwidth optimization can be obtained using the second smallest eigenvalue as a key factor (Juvan and Mohar, 1993; Helmberg et al., 1995) . The convergence speed of various processes such as mixing Markov chains on graphs (Brémaud, 2013) , reaching consensus in multi-agent systems (Jadbabaie et al., 2003; Olfati-Saber and Murray, 2004; Olfati-Saber, 2006; Tanner et al., 2007) , synchronization of coupled oscillators (Strogatz, 2001; Arenas et al., 2008) , or diffusion dynamics on networks are controlled by the second smallest eigenvalue of the Laplacian.

Algebraic connectivity of multilayer networks has recently been topic of several works, with the effect of interlinks being studied more than any other thing. 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 afterwards . 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) . When at least one of the network components has vanishing algebraic connectivity, the structural transition disappears (Darabi Sahneh et al., 2015; and, hence, components of such interconnected network topologies become indistinguishable despite very weak coupling between them (Darabi Sahneh et al., 2015) . On the other hand, subgraphs are coupled more difficultly when their algebraic connectivity values are close to each other (Darabi Sahneh et al., 2015; Shakeri et al., 2020) . Some bounds (Radicchi and Arenas, 2013; Darabi Sahneh et al., 2015; and exact expressions (Darabi Sahneh et al., 2015) for the coupling threshold were derived. Radicchi (2014) compares the existence of transition threshold to thermodynamic behavior of substances in transition from normal to supercritical fluid. Moreover, discuss the physical meaning of c * in terms of the minimum cut. Abrupt structural transition is not limited to varying coupling strength as it can be equivalently observed, for instance, by varying the number of interconnections Martín-Hernández et al. (2014) or by layer degradation (Cozzo et al., 2019) .

Another characteristic phenomenon in interconnected networks is supper-diffusion , where under certain conditions the diffusion in the interconnected network takes place faster than in either of the networks separately. Darabi Sahneh et al. (2015) place the superdiffusion with respect to the coupling threshold and report diversified behaviors in interconnected networks. While diffusion is monotonic with respect to coupling strength in undirected networks , their directed counterparts (Tejedor et al., 2018) can exhibit a nonmonotonic behavior resulting in a faster diffusion at an intermediate degree of coupling than when the two layers are fully coupled.

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, 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 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 . 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; . However, the functionality of such special structures is very limited. Figure 1 shows a small multilayer network where only one change in interlayer graph with respect to a one-to-one interconnection impacts its spectral properties; in particular, supperdiffusion occurs by fairly small budgets, this is impossible in a corresponding multiplex network whatever the amount of budget. 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 and the pattern of interconnections is arbitrary.

Examining the algebraic connectivity in a primal-dual setting allows for a versatile approach that reflects a multi-sided view of the problem. This finds more importance when working under an interweaving environment where the presence of several nonlinear phenomena gives birth to diversified dynamical behaviors (Darabi Sahneh et al., 2015) . While our primal problem goes into diffusion speed over the multilayer, we show that its dual is related to characteristic valuation (Radicchi and Arenas, 2013) and, hence, informative of diffusion phase. This duality enables us to understand the optimal diffusion route in each region. Here, the primal and dual optimization problems are impacted by structural transition (Rapisardi et al., 2018) . Our analytical approach shows that primal problem gives a regular weight distribution (Van Mieghem, 2016; , whenever feasible, before the (first) transition threshold, where the dual problem reveals an intralayer optimal diffusion phase. For larger total budget values, the weight distribution becomes nonregular and different phases of interlayer diffusion are activated. This is related to interlink and intralink Fiedler cuts of the multilayer graph before and after transition (Martín-Hernández et al., 2014) . However, here, due to multiple structural transitions, we note more diverse optimal diffusion phases.

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 (Shakeri et al., , 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 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.

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

Let G = (V, E) represent an undirected network and by V = {1, . . . , n} and E ⊂ V 2 , we denote the set of nodes and links. For a link e between nodes i and j, i.e., e : {i, j} ∈ E, we define a nonnegative value w ij as the weight of the link. Given G a multilayer network, let G 1 = {V 1 , E 1 } and G 2 = {V 2 , E 2 }, |V 1 | = n, |V 2 | = m, represent the layers, and a bipartite graph G 3 = {V, E 3 } with E 3 ⊆ {{i, j} : i ∈ V 1 , j ∈ 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

where B ij := (δ i − δ j )(δ i − δ j ) T , for each link {i, j}, and δ 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

We will first assume that it is possible to connect any node of G 1 to any node in G 2 and W n×m = [w ij ] consists of nonnegative weights. We use 1 n and 1 m to denote the n-and mdimensional all ones vectors, respectively. Recall that the Laplacian matrix L(ω) is positive semidefinite and has (at least for connected networks) one zero eigenvalue with eigenvector 1 = [1, . . . , 1] T , the vector of all ones of appropriate length. The eigenvalues of L(ω) are ordered as 0 = λ 1 (ω) ≤ λ 2 (ω) ≤ λ 3 (ω) ≤ · · · ≤ λ n (ω).

Our goal is to allocate weights on the interlayer links, subject to a total budget c such that w ij = c, to maximize the smallest positive eigenvalue of the Laplacian. After formulating the primal-dual program and deriving its properties, the equivalent graph realization problem in is extracted and its features with respect to the multilayer network's structure are identified. One difference between the present research and the recent related work (Shakeri et al., 2020) is that there the authors considered a special case where both individual networks hold the same number of nodes and each node is interconnected exactly to one node in the other network (one-to-one interconnection). However, in this paper, we relax the assumptions regarding one-to-one interconnections and allow for multilayer structures where the number of nodes in each layer can be different and the pattern of interconnections is arbitrary.

3 Maximum algebraic connectivity in arbitrary multilayer networks

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

We maximize λ 2 (L) by distributing a total budget c over the interlayer edges, formulated as

We rewrite (3) by separating the components of v,

where v T 1 v T 2 T = v, v 1 ∈ R n and v 2 ∈ R m . We further decompose v 1 and v 2 ,

where α is a scalar. Substituting (6) in (5) gives the following inequality that is used in the subsequent lemmas.

Lemma 3.1. The maximum algebraic connectivity function F (c) in (4) is upper-bounded as

Proof. Since the inequality (7) must hold for every α, it follows the coefficient of α 2 must be nonnegative, so that 1 + n m c − nλ 2 ≥ 0 which is satisfied only for λ 2 ≤ 1 n + 1 m c. The upper-bound in (8) 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 (8) is verified as F (c) ≤ 2c n . Lemma 3.2. The upper-bound (8) is attainable only if the following regulatory conditions are satisfied W 1 m ∈ span{1 n }, W T 1 n ∈ span{1 m } (9)

In other words, W has constant row sum and column sum.

Proof. When the upper-bound is reached, i.e. λ 2 = 1 n + 1 m c, inequality (7) reads

Since this inequality must hold for every α, the coefficient of α must vanish

Setting u 2 = 0 in (10) yields u T 1 W 1 m = 0, which in addition to u T 1 1 n = 0 imply the vector W 1 m belongs to the space spanned by 1 n . Similarly, setting u 1 = 0 in (10) will yield 1 T n W u 2 = 0, and thus the vector 1 T n W belongs to the space spanned by 1 m .

Remark 3.3. Knowing that the total budget c satisfies 1 T n W 1 m = c, the regularity condition

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 ≤ c * . Another case where regularity is feasible with uniform weights is an all-pairs interconnection pattern (Van Mieghem, 2016; . A more general case where regularity is accompanied with uniform interlink weights is when interlayer connectivity follows k-to-k coupling scheme (k integer) .

When regularity is feasible, one can check that λ = 1 n + 1 m c is always an eigenvalue of L with eigenvector m1 n −n1 m . Recall that this eigenvalue is zero when c = 0, and that the algebraic connectivity is bounded by this eigenvalue (Lemma 3.1). In fact, a perturbation approach for sufficiently small values of budget c-starting from zero and increasing-indicates that the maximum algebraic connectivity is λ = 1 n + 1 m c with the corresponding Fiedler vector m1 n −n1 m . This eigenvalue increases linearly with c and by increasing the coupling budget and at some point, there exists a transition threshold c * where the second and third smallest eigenvalues coalesce 1 . After c * , the regularity conditions is broken and the optimal weights will be generally non-regular and the maximum algebraic connectivity is a nonlinear function of c; Lemma 3.4 summarizes this.

Lemma 3.4. Suppose the regularity conditions given by (9) are feasible. For budget values c not greater than the threshold c * , c ≤ c * , the solution to the maximum algebraic connectivity problem (4) is λ * = 1 n + 1 m c with corresponding eigenvector m1 n −n1 m , that is only attainable by regularity conditions (9).

Further bounds can be derived based on the algebraic connectivity of the individual layers and their corresponding eigenvectors. Specifically, denoting by λ (1) 2 and λ

(2) 2 the second smallest eigenvalue of L 1 and L 2 , respectively, and by u 

Attempting to maximize the minimum of the right hand sides of (12), 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 ≤ c * , with regularity feasible, the solution to (4) is determined analytically. However, for c > c * , the optimal weights are generally nonregular and numerical solutions of are required. Our approach in this section closely follows (Sun et al., 2006; Goring et al., 2008; Shakeri et al., 2020) .

We recast (4) as a semidefinite programming (SDP) problem (Goring et al., 2008 (Goring et al., , 2011 ,

where L 0 = ij∈E 1 ∪E 2 B ij is the Laplacian for the disjoint union of the layers. The semidefinite constraint ensures when the optimal solution (w

For nonnegative budget c, the feasible set of the primal problem is not empty, and the primal problem attains its optimal solution (Shakeri et al., 2020) .

The primal problem (4.1) maximizes the diffusion speed over the multilayer network. We study the Fiedler eigenspace to explore the route to this fastest spread over the network. The dual of (14) provides valuable information about the fastest diffusion mode. The dual is obtained by the usual Lagrangian approach (Vandenberghe and Boyd, 1996; Boyd and Vandenberghe, 2004) :

The feasible set of the dual problem is not empty, and strong duality holds for the primal and dual problems (14) and (15) (Shakeri et al., 2020) . Therefore the dual problem attains its optimal solution, and optimal values of the primal and dual problems are the same. Sun et al. (2006) use the Gram representation of the dual matrix X = U T U , where U ∈ R n×n to rewrite (15) as:

That is a realization of the graph in R n such that the distances between nodes are minimized and the barycenter is in the origin, but since the sum of the squared norms equals one, not all nodes can be embedded in the origin. By the following lemma some main structural properties of optimal graph can be derived from the geometric dual problem.

Lemma 4.1. The projections of optimal embedding onto (nonzero) one-dimensional subspaces yield eigenvectors for the algebraic connectivity.

The following proposition is a result of Lemmas 3.4 and 4.1.

Proposition 4.2. Assume the regularity condition (9) is feasible. For budget values up to the threshold c * , c ≤ c * , the optimal solution of the embedding problem is given as

The embedding (17) implies each layer clumps together at the opposite sides with respect to the other layer, while distanced from the origin inversely proportional to the number of its nodes. In this case, the Fiedler cut distinguishes the individual layers (Martín-Hernández et al., 2014) . The condition in (17) is similar to the momentum balance condition (Shames, 1996) of two masses attached to opposite sides of a rotating rigid uniform rod.

Lemma 4.1 is a result of the complementary condition in the primal-dual formulation (Boyd and Vandenberghe, 2004) , and is first established by Sun et al. (2006) for singlelayer networks and extended to multilayer networks by Shakeri et al. (2020) . It relates the solution of the dual problem to the eigenspace of maximum λ 2 and helps understanding how to improve diffusion speed , and how synchronization (Strogatz, 2001; Arenas et al., 2008) can happen faster. This is particularly of interest in multilayer networks where processes show richer dynamics (Buldyrev et al., 2010; Radicchi and Arenas, 2013; Zhang et al., 2015) .

Remark 4.3. The multiplicity of λ 2 (L) sets an upper-bound on the dimension of realization (Helmberg and Reiss, 2010) . This can be understood from Proposition 4.1 and the dimension of the eigenspace corresponding to λ 2 .

For connected single-layer networks, we scale the weights in (15) by cλ 2 = 0 and obtain a scaled version of the primal-dual problem for multilayer networks (Goring et al., 2008) 

whereŵ ij = w ij cλ 2 and the scaled dual (embedding) problem (16) is written as Goring et al. (2008) used the scaled primal-dual formulation to prove the Separator-Shadow Theorem. Moreover, Goring et al. (2011) introduced the rotational dimension of a graph which is the maximal minimum dimension of an optimal graph realization, and proved it is bounded based on the graph tree-width (Diestel, 2017) . The importance of these theorems is that they establish the existence of low dimensional optimal realizations.

In this section, we remove all topological constraints and allow all-to-all interconnection in multilayer networks. Firstly, we study the spectral properties for identical weights assigned to all interlinks and secondly, investigate the primal and dual problems. Furthermore, we explore the conditions under which the optimal weights are nonuniform and illustrate that the optimal strategy assigns zero weights to some edges despite possible all-pairs interconnections. Several results of this section emphasize the role of algebraic connectivity divided by number of nodes in a layer, which we call specific algebraic connectivity, and Fiedler vectors of subgraphs in optimum diffusion determination.

Considering uniform weights for the interlinks, w ij = c/nm and W = c nm J with J the n × m all ones matrix, results in the following eigenvalue problem

.., n, are nonzero eigenvalues of L 1 and u

(1) i are the corresponding eigenvectors. Indeed, for uniform weights W = c nm J = c nm 1 n 1 T m and by the Laplacian (2) we have

where I n and I m are respectively n × n and m × m identity matrices and we know that 1 T n u

(1) i = 0 for any eigenvector u

(1) i associated with a nonzero Laplacian eigenvalue in a connected graph. Similarly, m − 1 nonzero of L are given as

j is the j-th eigenvector of L 2 and v

(2) j the corresponding eigenvector. The remaining nonzero eigenvalue with its corresponding eigenvector are

hence, all eigenvalues increase linearly with c. The second largest eigenvalue is obtained as 

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 λ 

2 ). The threshold is c * = nλ In all three cases illustrated in Figure 2 , individual network components play no role on supra-Laplacian algebraic connectivity for c ≤ c * . By increasing c beyond the threshold c > c * , the algebraic connectivities of individual layers G 1 and G 2 per unit node, i.e. λ 2 [L 1 ] /n and λ 2 [L 2 ] /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  2 , the subgraph with larger specific algebraic connectivity determines the supra-Laplacian algebraic connectivity only in Case 1 when c > c * * , and under all other circumstances of c > 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 = 1 2 (L 1 + L 2 ) is greater than the algebraic connectivity values of individual networks . 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: Figure 2 shows that in cases 1 and 3,

and for Case 2, λ

The conditions (26) and (27) 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 ≤ c * . Presence of significant difference between the algebraic connectivity values of individual networks postpones super-diffusion until large interconnection strengths. Conversely, for close values superdiffusion can occur for values of c < c * , where the network components function distinctly, thus allowing advantage of interconnections while preserving the autonomy of each subsystem (Darabi Sahneh et al., 2015) .

Lemmas 3.1 and 3.2 explain that the maximum algebraic connectivity is upper-bounded and the upperbound (8) is attainable subject to the regularity conditions (9). Section 5.1 shows that with uniform weights-which satisfy the regularity conditions-the algebraic connectivity can reach its upper-bound (8) in c ≤ c * . Therefore, for c ≤ c * , the uniform weight distribution is the solution of maximum eigenvalue problem (4). Although, Lemma 3.4 gives the solution of maximum algebraic connectivity analytically when c ≤ c * and regularity is feasible, we resort to the solution of primal and dual SDP formulations discussed in Section 4 for other situations. To this end, we conduct a perturbation analysis to shed some light on how the maximum algebraic connectivity behaves after c > c * and then investigate the SDP results for all-to-all interconnection possibility in sections 5.3 and 5.4.

For the perturbation analysis, we consider a nominal budget c 0 and the associated eigenvalue problem L 0 x 0 = λ 0 x 0 where L 0 is the nominal Laplacian with an eigenvalue λ 0 and corresponding eigenvector x 0 . Then, consider the perturbed quantities c = c 0 + c , L = L 0 + L , λ = λ 0 + λ , x = x 0 + x , where is sufficiently small and the quantities with prime show the levels of perturbations. Now, the eigenvalue problem Lx = λx is written as

Equating the coefficients of in both sides of (28), we have

Inner product of (29) by x 0 yields the following expression for the perturbed value λ Figure 2a 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 λ 3 at c * ; using the results of Section 5.1 for Case 1, for c 0 = c * ,

where W is the perturbed weight matrix due to the perturbed budget c . Substituting the above x 0 and L 0 into (30) and after normalizing the eigenvector v

(2) 2 = 1, we obtain the following expression for the increment in algebraic connectivity beyond c *

Considering λ = λ 0 + λ , we can approximate the algebraic connectivity for budget values just above c * . Therefore, maximizing the perturbed value (31) 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 (31); first, diagonal elements of diag W T 1 n represent the total weight assigned to each node in Layer 2 and thus λ 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 (31) is correlated with the Fiedler vector of L 2 . Consequently, maximizing (31), require assigning the weights in vector W T 1 n to nodes with larger v 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 Figures 2b and 2c. In particular for Case 2, note that for c 0 = c * = mλ (1) 2 the third eigenvalue is λ (1) 2 + c n . The corresponding eigenvector is x 0 = u (1) 2 0 . Using the above perturbation approach, we get the following increment for algebraic connectivity just above c *

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 (31).

The SDP (14) can be solved efficiently using convex solvers, e.g. CVX package by Grant and Boyd (2009) . Figure 3 shows the optimal results for an example of Case 1. Figure  3a compares the maximum algebraic connectivity with uniform weights case. In Figures  3b and 3c , 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. Figures 4a and 4b , 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 5.2.

For c > c * * , Figure 3b illustrates that weight distribution in Layer 1 becomes heterogeneous and many nodes experience zero interlink weights. Investigation of optimum weights in Figure 4c 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 > c * * (see Figure 3c ) 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. Figure 5 shows the SDP results for Case 2. We observe that, while the weights in Layer 1 with smaller specific connectivity become inhomogeneous for budgets c > c * , they remain (almost) uniform in Layer 2 with larger specific connectivity. Figure 6 reports a positive correlation between the optimal weights in Layer 1 and the corresponding Fiedler vector components. Figures 7 and 8 show the results corresponding to Case 3. These results are the same of Case 2 by changing Layers 1 and 2.

We investigate geometric dual problems of each three cases in Figure 2 to show different diffusion phases in various regions of optimal weights. For Case 1, Figure 9 shows the em- Figure 9b , 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 > c * * in Figure 9c 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 A.2. The results are as follows. For small c < c * in Figure 9a , we observe an intralayer phase of optimal diffusion in both layers. For intermediate budgets c * < c < c * * in Figure 9b , 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 > c * * in Figure 9c , 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 10 shows embedding results for another example of Case 1 in Figure 2a . By Figure 10a , it is observed the embedding dimension at each c is equal to corresponding multiplicity of supra-Laplacian algebraic connectivity. Embedding for c ≤ c * has a clumped pattern similar to Figure 9a , thus one dimensional.

Examples of embedding results for Cases 2 and 3 in Figure 2 are shown in Figures  11 and 12 , respectively. When c > c * , in both cases, the optimal diffusion in subgraph with larger specific algebraic connectivity is prominently through intralinks, while through interlinks and intralinks in subgraph with smaller specific connectivity. 6 Interconnections constrained to an admissible set

In Section 5, 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 (i, j) ∈ E a ⊂ E 3 and all other edges E 3 /E a have zero weight.

For c ≤ c * and following Lemma 3.4, we know that regular weight distribution leads to maximum algebraic connectivity. The regularity condition (9) is generally not feasible for all interconnection patterns. When regular interconnection is not feasible for a given set of admissible interlinks, the bound λ * 2 = 1 n + 1 m c is not attainable and there is generally no region of optimal uniform weights. In such conditions, the region c ≤ c * corresponding to uniform weights, and hence the associated transition fades away (see Figure 13 ). This means, with no regularity, there is no region for unified operation of individual network components- Figure 14 shows the absence of the clumped pattern embedding. As a consequence, interlinks start to contribute to diffusion within each individual layer from small values of coupling strength c. It should be reemphasized that regularity and uniform weights are different; Figure 15 illustrates an example with regularity in optimal interlayer weights but nonuniform weights and thus, the bound λ * 2 = 1 n + 1 m c is attained.

Lemma 3.4 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 ≤ 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 pat- Figure 13 : 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. Figure 15 : Optimal weights in a multilayer including two ER networks, each with 30 nodes and total 60 random interlinks, as example of nonuniform regular optimal weights. (a) optimal interlayer weights assigned to nodes in Layer 1, (b) optimal interlayer weights assigned to nodes in Layer 2, and (3) optimal weight assigned to each interlink.

terns 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 (24) 

2 . 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.

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 . To unravel more facts about optimized k-to-k interconnections, Figures 16, 17, and 18 show embedding results for k = 1, k = 2, and k = 3, respectively. These figures use the same individual network components where c > c * . Figure 19 shows the corresponding maximum algebraic connectivity values. For the smaller budget c = 10 in Figures 16a, 17a, and 18a , we observe that the most unified embedding of individual network components is associated with k = 3, next followed by k = 2

Interlayer graph (c) Figure 16 : Graph embedding of a multilayer including two ER networks, each with 30 nodes, and 30 interlinks for k-to-k interconnection with k = 1 and budget values (a) c = 10, (b) c = 100, (c) c = 1000. and k = 1. Therefore, for a given total budget c, the larger the number of interconnections, the weaker the coupling. However, Figure 19 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 Figures 16b, 17b , and 18b 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 16c , 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 18c 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 19 . For the odd interconnection pattern k = 2 in Figure 17c , the existence of an average network for large c is not directly deducible. 

In Section 6, 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, show that the super-diffusion occurs only if some definite condition is satisfied; namely, if the algebraic connectivity of the average Laplacian L ave = 1 2 (L 1 + L 2 ) 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 ∼ {i, j}, between nodes i ∈ V 1 and j ∈ 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 λ 2 is isolated, w 0 (v i − v j ) 2 gives the first order approximation of the increase in λ 2 , if edge e ∼ {i, j} with weight w 0 is added to the graph. Figure 20 shows a small well-interconnected network. Here, supper-diffusion is not possible with a one-to-one interconnection since max (λ 2 [L 1 ] , λ 2 [L 2 ]) > λ 2 [L ave ], and hence, the condition suggested by is not met. The one-to-one interconnected pattern used as reference case in this section follows a multiplex setting . 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 21 and 22 unravel more properties of well-interconnected networks. In Figure  21 , 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 22 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, i.e. 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 23 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 24 the situation where the interlinks may or may not be regular depending on 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 20 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 wellinterconnected graph is not regular.

In this paper, we considered optimal interlayer weights and structure determination for maximizing the algebraic connectivity in multilayer networks with arbitrary interconnection pattern. 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 > 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 ≤ 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, i.e. 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, i.e. 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 multi-layer systems where resiliency and robustness are of concern. One such system is the supply networks of commodities, which are generally referred to as supply chains. Supply chains are typically composed of a layered sequence of firms whose mission is to serve a final consumer by supplying each other with the material, information, and financial instruments. By nature, and in its generic form, each layer of a supply chain encompasses entities that form a network and perform comparable tasks (e.g., a network of manufacturers versus a network of distributors). A well-studied and common goal in designing supply chains is to serve a market by connecting various layers of firms (i.e., networks) while minimizing logistics costs or the chain's susceptibility to disruptions. This study can be leveraged in devising resilient supply chains that are reasonably immune to supply disturbances and, hence, resistant against catastrophic cascading effects. The recent COVID-19 (SARS-CoV-2) outbreak, which was first documented in Wuhan, China, and the resulting supply disruptions, provide an enlightening example to elucidate the significance of this study in supply chains. In the aftermath of the Coronavirus pandemic, a staggering number of companies reported severe logistics-related disturbances. 94% of the Fortune 1000 firms described supply chain interruptions Ivanov (2020) . Moreover, COVID-19's quarantined areas are home to roughly 12,000 facilities of the world's largest 1000 supply chains Ivanov and Dolgui (2020) . Considering approximately five million companies with supply roots in Wuhan Ivanov (2020), one begins to realize the significance of the theoretical insights proposed in this study in relation to the supply chains' resilience-driven design.

Besides designing issues, supply chains offer a wealth of tactical and operational prob-lems, structured in a multi-layered fashion, that may benefit from this study. For example, one may consider a distribution problem where a network of warehouses (or fulfillment centers) is to serve a consumer base bound by a transportation network. Warehouses can be either independent or connected through transshipment. A common issue in this scenario is to identify the set of consumers supported by each warehouse, and similarly, the collection of warehouses that may serve a customer. The findings of this study can be utilized to connect the two warehouses and customers' networks, such that the consumers are best served in the face of inventory shortages or commodities' flow interruptions. Transportation planning problems are another fertile territory for applying the findings of this study. In this context, a decision-maker may be interested in connecting transportation networks of different modes. For example, one widely-studied shipment planning problem is to identify the set of nodes where two distribution networks with varying modes of delivery collide. A few examples of such a problem are connecting a subway system and networks of streets as well as adjoining a truckload and an air freight shipment system. In each of these scenarios, the current study can be utilized to improve the resiliency of the overall connected system by preserving the flow or limiting the disruptions under unforeseen circumstances. Figure 25 shows different diffusion phases corresponding to the conditions considered in Figure 9 . To better realize the interlinks effect, we have assumed identical initial conditions of nodes in same layers. In Figure 25a , when c < c * , each network operation is distinguishably unified. Indeed, for small c, the interconnection strength is too weak to affect the intralayer connections and break the individual networks unity. In such condition, the optimal diffusion process within each network component is prominently through its intralinks. For the intermediate value c = 10 in Figure 25b larger specific connectivity still operates as a unity, the network G 2 , with smaller specific connectivity, loses its operation unity due to being interconnected with G 1 . Thus, the subgraph with larger specific connectivity is more robust against intermediate couplings while the other with smaller specific connectivity is more vulnerable and loses unity in this region. As such, for intermediate c * < c < c * * in Figure 25b , the optimal diffusion within G 1 is mostly due to its intralinks while in G 2 it is through intralinks and interlinks. The situation turns conversely for the larger value c = 30 > c * * in Figure 25c where G 1 loses unity while G 2 becomes again unified. This time, the optimal interlinks strength is so high that it completely overcomes the intralink effects within G 2 . In fact, the strong interlinks may be thought of as powerful attracting forces that pull the nodes in G 2 toward each other from all sides, due to all-to-all interconnection possibility, thus making them unified. However, the interlinks are only strong enough to destroy G 1 unity but not strong enough to completely overcome the intralink effects in this subgraph. As such, diffusion within G 2 forms prominently through interlinks while it is through interlinks and intralinks in G 1 .

Synchronization of interconnected networks: The role of connector nodes

Synchronization in complex networks

The structure and dynamics of multilayer networks

Complex networks: Structure and dynamics

On social network analysis in a supply chain context

Fastest mixing markov chain on a graph

Convex optimization

Markov chains: Gibbs fields, Monte Carlo simulation, and queues

Using network science to analyse football passing networks: Dynamics, space, time, and the multilayer nature of the game

Catastrophic cascade of failures in interdependent networks

Diffusive behavior of multiplex networks

Maximization of robustness of interdependent networks under budget constraints

Layer degradation triggers an abrupt structural transition in multiplex networks

Structure of triadic relations in multiplex networks

Exact coupling threshold for structural transition reveals diversified behaviors in interconnected networks

Fundamentals of spreading processes in single and multilayer complex networks

Navigability of interconnected networks under random failures

Epidemics on interconnected networks

Springer Graduate Texts in Mathematics (GTM)

Communicability reveals a transition to coordinated behavior in multiplex networks

Algebraic connectivity of graphs. Czechoslovak mathematical journal

Robustness of a network formed by n interdependent networks with a one-to-one correspondence of dependent nodes

Growing well-connected graphs

Diffusion dynamics on multiplex networks

Diffusion dynamics on multiplex networks

Embedded in the shadow of the separator

The rotational dimension of a graph

Cvx: Matlab software for disciplined convex programming (web page and software)

A note on fiedler vectors interpreted as graph realizations

A spectral approach to bandwidth and separator problems in graphs

Predicting the impacts of epidemic outbreaks on global supply chains: A simulation-based analysis on the coronavirus outbreak (covid-19/sars-cov-2) case

Viability of intertwined supply networks: extending the supply chain resilience angles towards survivability. a position paper motivated by covid-19 outbreak

Coordination of groups of mobile autonomous agents using nearest neighbor rules

On the relationship between the algebraic connectivity and graph's robustness to node and link failures

Laplace eigenvalues and bandwidth-type invariants of graphs

Structural investigation of supply networks: A social network analysis approach

Multilayer networks

Enhancing the robustness of a multiplex network leads to multiple discontinuous percolation transitions

Robust allocation of weighted dependency links in cyberphysical networks

Algebraic connectivity of interdependent networks

Graph Theoretic Methods in Multiagent Networks

Network robustness of multiplex networks with interlayer degree correlations

Optimal selection of essential interconnections for structural controllability in heterogeneous subsystems

Flocking for multi-agent dynamic systems: algorithms and theory

Consensus problems in networks of agents with switching topology and time-delays

Optimal interlayer structure for promoting spreading of the susceptible-infected-susceptible model in two-layer networks

Driving interconnected networks to supercriticality

Abrupt transition in the structural formation of interconnected networks

Multiple structural transitions in interacting networks

On the existence of a threshold for preventive behavioral responses to suppress epidemic spreading

Epidemic spreading on interconnected networks

Maximizing algebraic connectivity in interconnected networks

Designing optimal multiplex networks for certain laplacian spectral properties

Engineering mechanics: statics and dynamics

Percolation theory on interdependent networks based on epidemic spreading

Fundamentals of Thermodynamics

Exploring complex networks

The fastest mixing markov process on a graph and a connection to a maximum variance unfolding problem

Flocking in fixed and switching networks

Diffusion dynamics and optimal coupling in multiplex networks with directed layers

Graph spectra for complex networks

Interconnectivity structure of a general interdependent network

Semidefinite programming

Synchronization of multilayer networks: From node-to-node synchronization to complete synchronization

Structural transition in interdependent networks with regular interconnections

Analysis of complex contagions in random multiplex networks

Optimal allocation of interconnecting links in cyber-physical systems: Interdependence, cascading failures, and robustness

Optimized inter-structure for enhancing the synchronizability of interdependent networks

Explosive synchronization in adaptive and multilayer networks

Robustness of interdependent cyber-physical systems against cascading failures

Multi-stage complex contagions in random multiplex networks

Since the condition in (33) must hold for every α, the coefficient of α 2 must be positive, which yields the following bound for algebraic connectivity

Decomposing v 1 and v 2 in (5) in various ways can yield various bounds for algebraic connectivity. For instance, consider the decomposition v 1 = αu2 is the eigenvector associated with the second smallest eigenvalue λ (1) 2 , or Fiedler vector, of L 1 , L 1 uInserting this decomposition of v 1 into (5), we can get