Multiple structural transitions in interacting networks
Giacomo Rapisardi Alex Arenas Guido Caldarelli Giulio Cimini


 


giacomo.rapisardi@imtlucca.it
IMT School for Advanced Studies, 55100 Lucca, Italy

Departament d'Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, 43007 Tarragona, Spain

IMT School for Advanced Studies, 55100 Lucca, Italy
Istituto dei Sistemi Complessi (ISC)-CNR, 00185 - Rome, Italy

IMT School for Advanced Studies, 55100 Lucca, Italy
Istituto dei Sistemi Complessi (ISC)-CNR, 00185 - Rome, Italy



Many real-world systems can be modeled as interconnected multilayer networks, namely a set of networks interacting with each other. 
Here we present a perturbative approach to study the properties of a general class of interconnected networks as inter-network interactions are established. 
We reveal multiple structural transitions for the algebraic connectivity of such systems, between regimes in which each network layer keeps its independent identity 
or drives diffusive processes over the whole system, thus generalizing previous results reporting a single transition point. 
Furthermore we show that, at first order in perturbation theory, the growth of the algebraic connectivity of each layer depends only 
on the degree configuration of the interaction network (projected on the respective Fiedler vector), and not on the actual interaction topology. 
Our findings can have important implications in the design of robust interconnected networked system, 
particularly in the presence of network layers whose integrity is more crucial for the functioning of the entire system. 
We finally show results of perturbation theory applied to the adjacency matrix of the interconnected network, 
which can be useful to characterize percolation processes on such systems.


Multiple structural transitions in interacting networks
    Giulio Cimini
    December 30, 2023
=======================================================






§ INTRODUCTION


Interconnected (or interdependent) networks describe complex systems composed by a set of networks interacting with each other 
<cit.>. 
The presence of such interactions makes these systems structurally and dynamically different from isolated networks <cit.>. 
Dissimilar properties have been reported, for instance, in navigability <cit.>, communicability <cit.>,
robustness <cit.>, percolation <cit.>, 
epidemics <cit.>, and synchronization <cit.>. 

In the study of interconnected networks, much attention has been devoted to the Laplacian operator 
<cit.>. 
The Laplacian matrix ℒ of an undirected graph is defined as 𝒟-𝒜, 
where 𝒜 is the adjacency matrix (its generic element A_ij=1 if i and j are connected, and A_ij=0 otherwise) 
and 𝒟=(𝒜|1⟩) is the diagonal matrix of degrees (we use the bra-ket notation, hence |1⟩ denotes the column vector with all entries equal to 1).  
ℒ is positive semidefinite, meaning that all of its eigenvalues are non-negative. 
Since, by definition, row/column sums of ℒ are all zero, the Laplacian always admits λ_1(ℒ)=0 as the smallest eigenvalue, corresponding to the eigenvector |1⟩.  
The second-smallest eigenvalue of the spectrum, λ_2(ℒ), is the algebraic connectivity of the graph, and reflects how much connected the overall graph is <cit.>. 
Indeed, λ_2(ℒ) is different from zero if and only if the graph is connected; otherwise, its degeneracy equals the number of disconnected components of the graph. 
The value of λ_2(ℒ) is determined as:

    λ_2 (ℒ) = min_|v⟩∈𝖵⟨v| ℒ |v|⟩
 
where |v⟩∈𝖵 is such that ⟨v|1|=⟩0 and ⟨v|v|=⟩ 1.

The spectrum of the graph Laplacian is typically used to characterize both structural properties of the networked system, 
such as connectivity, diameter and number of spanning trees <cit.>, 
as well as dynamical properties, such as diffusion and synchronization <cit.>. 
Recently, Radicchi and Arenas <cit.> showed that the process of building independent network layers into a multiplex network—which is 
a specific type of multilayer interconnected network in which nodes replicate at each layer—undergoes a structural transition in the algebraic connectivity as interconnections are formed. 
Specifically, if q is the interaction strength between the network layers, for q<q_c these networks are structurally distinguishable 
(and the system behavior is not affected by their detailed topology but depends only on the interconnection structure), 
whereas, for q>q_c the interconnected network functions as a whole (and topological effects do play a role). 
Later, Darabi Sahneh <cit.> found an exact solution for q_c. Moreover, they observed that the structural transition disappears 
when one of the network layers has vanishing algebraic connectivity: layers of such interconnected network topologies become indistinguishable, despite very weak coupling between them.
Martín-Hernández <cit.> further showed that, for a multiplex, there exists a critical number of diagonal interlinks beyond which 
any further inclusion does not enhance the algebraic connectivity of the system at all, whereas, for a randomly interconnected system, 
there exists a critical number of random interlinks beyond which algebraic connectivity increments at half of the original rate. 
Van Mieghem <cit.> further computed the nontrivial eigenmode of the Laplacian for a regular topological structure of interconnections. 

Here we blend this research line of studying structural transitions in interacting networks. 
We adopt a perturbative approach in order to tackle general topologies of both network layers and interconnections. 
Perturbation theory has already found application in network science, for instance 
to study the Laplacian eigenvalues of scale-free networks <cit.>, 
to analyze spectral properties of networks with community structure <cit.>, 
to identify important nodes within communities <cit.>, 
to find the relation between eigenvector and topological perturbations <cit.>, 
to analyze the localization properties of Laplacian eigenvectors on random networks <cit.> and, 
in the context of multiplex networks, to unveil the time scales of diffusive processes <cit.>. 
The underlying idea of perturbation theory is to treat an operator acting on the system as the sum of an unperturbed part, 
which in our context refers to isolated network layers and for which the exact solution may exist, 
and a perturbation, given by the interconnections between these layers.

Our proposal constitutes a general framework for the analysis of structural transitions in the most wide scope of interconnected/interdependent multilayer networks. The analytical 
characterization of such transitions represents a step forward in the direction of having a closed theory of multilayer networks.



§ PERTURBATIVE APPROACH FOR THE SPECTRUM OF THE GRAPH LAPLACIAN


We focus on studying the variation of the Laplacian matrix spectrum when the perturbation is introduced. 
We start with the simplest case of two connected, undirected unweighted networks 𝒜 and ℬ, with N and M nodes each, respectively. 
Interconnections are randomly established between these networks, and are described by a generic N× M adjacency matrix 𝒬. 
The supra-Laplacian of the whole system can be represented with the four-blocks (N+M)× (N+M) matrix <cit.>:

    ℒ = (
    [ ℒ_𝒜 + 𝒦_𝒜        -𝒬;      -𝒬^𝖳 ℒ_ℬ + 𝒦_ℬ ]),

where ℒ_𝒜 and ℒ_ℬ are the Laplacian matrices of each network, 
while 𝒦_𝒜=(𝒬|1⟩) and 𝒦_ℬ=(𝒬^𝖳|1⟩) are the diagonal matrices of inter-degrees. 
To apply perturbation theory, we split ℒ into an unperturbed part ℒ_0 and a perturbation 𝒱:

    ℒ = ℒ_0 + 𝒱 =
    (
    [ ℒ_𝒜   0;   0 ℒ_ℬ ])+
    (
    [  𝒦_𝒜   -𝒬; -𝒬^𝖳  𝒦_ℬ ]).
 
We denote, for ℒ_0, the unperturbed spectrum of eigenvalues as E_n^(0) and its associated orthonormal basis of eigenvectors as |n^(0)⟩. 
In the hypothesis of E_n^(0) being non-degenerate, the first-order correction ϵ^(1)_n induced by the perturbation is

    ϵ^(1)_n = ⟨n^(0)|𝒱|n^(0)|,⟩

so that the spectrum of ℒ at first order would be simply given by:

    E^(1)_n = E^(0)_n + ⟨n^(0)|𝒱|n^(0)|.⟩


However we have to resolve the (at least) 2-fold degeneracy in the 0 eigenvalue for ℒ_0, 
since there are at least two independent connected layers (networks 𝒜 and ℬ). 
Assuming for simplicity that both 𝒜 and ℬ are connected, the degeneracy is exactly 2. 
We can then use the unperturbed eigenstates: 

    |+^(0)⟩   =   1/√(N+M)|1⟩|1⟩
    |-^(0)⟩   =   1/√(N+M)√(M/N)|1⟩-√(N/M)|1⟩

as the orthonormal basis for such a degenerate sub-space <cit.>. 
Since the perturbation 𝒱 becomes diagonal when represented in this basis (, ⟨+^(0)|𝒱|-^(0)|=⟩⟨-^(0)|𝒱|+^(0)|=⟩0), 
we immediately get the eigenvalues corresponding to |+^(0)⟩ and |-^(0)⟩:

    ϵ^(1)_+ =   ⟨+^(0)|𝒱|+^(0)|   ⟩= 0, 
    ϵ^(1)_- =   ⟨-^(0)|𝒱|-^(0)|   ⟩= τ(𝒬)/μ,

where τ(𝒬) = ⟨1|𝒬|1|≡⟩∑_ijQ_ij and μ=NM/(N+M). 
Naturally, eq. (<ref>) reminds of the classical two-body problem of two masses N and M mutually interacting 
by means of a coupling force of intensity τ(𝒬) <cit.>: 
ϵ^(1)_+ gives the acceleration for the center of mass while  ϵ^(1)_- is the relative acceleration between the two masses. 

We then consider the smallest non-zero eigenvalues of the unperturbed state ℒ_0 given by the algebraic connectivities of either network 𝒜 or ℬ. 
Denoting as |v_𝒜⟩ the normalized eigenvector corresponding to λ_2(ℒ_𝒜), 
that is ℒ_𝒜|v_𝒜⟩=λ_2(ℒ_𝒜)|v_𝒜⟩, 
we pose |v_𝒜^(0)⟩=|v_𝒜⟩|0⟩. The first order correction to λ_2(ℒ_𝒜) is, according to eq. (<ref>): 

    ϵ^(1)_𝒜 = ⟨v_𝒜^(0)|𝒱|v_𝒜^(0)|≡⟩⟨v_𝒜|𝒦_𝒜|v_𝒜|.⟩

Analogously, denoting as |v_ℬ⟩ the normalized eigenvector corresponding to λ_2(ℒ_ℬ), 
and posing |v_ℬ^(0)⟩=|0⟩|v_ℬ⟩, we have: 

    ϵ^(1)_ℬ = ⟨v_ℬ^(0)|𝒱|v_ℬ^(0)|≡⟩⟨v_ℬ|𝒦_ℬ|v_ℬ|.⟩

Hence, the first order correction to the algebraic connectivity of 𝒜 and ℬ is given only by the degree configuration of the perturbation term
projected on the Fiedler vector of ℒ_𝒜 and ℒ_ℬ respectively, independently on the particular topology of this perturbation term. 

Overall, at first order in perturbation theory we have: 


    λ_2(ℒ) = min{τ(𝒬)/μ,  λ_2(ℒ_𝒜)+⟨v_𝒜|𝒦_𝒜|v_𝒜|,⟩ λ_2(ℒ_ℬ)+⟨v_ℬ|𝒦_ℬ|v_ℬ|⟩}.


Since ϵ^(1)_- is the correction to the zero eigenvalue, we have that if τ(𝒬) is small enough then λ_2(ℒ) = ϵ^(1)_-. 
In this phase the algebraic connectivity depends only on the sizes of the two interacting networks 𝒜 and ℬ, meaning that it is not affected by their topology. 
However, when τ(𝒬) grows, the second and third smallest eigenvalues of the interacting network might swap <cit.>. 
This happens when τ(𝒬)/μ=min{λ_2(ℒ_𝒜)+⟨v_𝒜|𝒦_𝒜|v_𝒜|,⟩λ_2(ℒ_ℬ)+⟨v_ℬ|𝒦_ℬ|v_ℬ|⟩}.
Note that if one of the networks 𝒜 and ℬ has a vanishing algebraic connectivity, the transition point disappears <cit.>. 
This happens, , for a class of networks where λ_2(ℒ_𝒜)∼ (ln N)^-2 <cit.>. 
Importantly, an additional swapping may also occur for the algebraic connectivities of the two network layers, , when and if 
λ_2(ℒ_𝒜)+⟨v_𝒜|𝒦_𝒜|v_𝒜|=⟩λ_2(ℒ_ℬ)+⟨v_ℬ|𝒦_ℬ|v_ℬ|$⟩. 
To get a qualitative insight on the system behavior, in the following we consider two particular situations, diagonal and random interactions. 




 §.§ Diagonal interactions (Multiplex)


In a multiplex networks,𝒜andℬhave the same number of nodes (N=M) and𝒬=qℐis proportional to theN×Nidentity matrix. 
While the minimization problem of eq. (<ref>) can be solved exactly in this case <cit.>, using perturbation theory leads to:

    λ_2(ℒ) = q+min{ q,  λ_2(ℒ_𝒜), λ_2(ℒ_ℬ) }.

Since the ordering ofλ_2(ℒ_𝒜)andλ_2(ℒ_ℬ)is fixed, 
there is only one eigenvalue swapping atq_c≃min{ λ_2(ℒ_𝒜),  λ_2(ℒ_ℬ) }. 

When the two networks𝒜andℬare identical, thenλ_2(ℒ_𝒜)=λ_2(ℒ_ℬ). 
Resolving this additional degeneracy with eigenvectors1/√(2)|v_𝒜⟩|v_𝒜⟩and1/√(2)|v_𝒜⟩-|v_𝒜⟩leads to first order corrections forλ_2(ℒ_𝒜)equal to0and2q, henceq_c≃λ_2(ℒ_𝒜)/2(it is halved with respect to the non-degenerate case) <cit.>. 



 §.§ Random interactions


A more general situation is described by an interaction matrix𝒬assuming the form of an  random graph with connection probabilityq. 
This setting resembles that of an individual network with two communities𝒜andℬwhich are randomly interconnected <cit.>. 
In order to proceed, we use a mean field approximation by replacing all matrix elementsQ_ijwith their expectation valueq. Hence eq. (<ref>) becomes:

    E[λ_2(ℒ)] = min{ (N+M)q,  λ_2(ℒ_𝒜)+qM,  λ_2(ℒ_ℬ)+qN }.


Again in the special case of𝒜andℬidentical (which also impliesN=M), resolving the degeneracyλ_2(ℒ_𝒜)=λ_2(ℒ_ℬ)with eigenvectors1/√(2)|v_𝒜⟩|v_𝒜⟩and1/√(2)|v_𝒜⟩-|v_𝒜⟩leads to first order corrections 
both equal toNq, so that also in this case there is only one eigenvalue swapping atq_c≃λ_2(ℒ_𝒜)/N<cit.>. 
Under the mean-field approximation, these conclusions hold also if the two networks are identical on expectation. 
For instance, consider𝒜andℬto be  random graphs with the same number of nodes and connection probabilityp. 
Dropping terms belowO(√(NlogN)), we haveE[λ_2(ℒ_𝒜)]=E[λ_2(ℒ_ℬ)]≃Np-√(2p(1-p)NlogN)<cit.>, hence

    q_c ≈ p - √(2p(1-p)(logN)/N)

(see Fig. <ref>). In the limitN→∞,q_c→pas√(logN/N): the transition atq_cis therefore well defined even in the thermodynamic limit. 

To discuss the more general setting of𝒜andℬhaving different sizes and topologies, 
without loss of generality we setM<N. Then ifλ_2(ℒ_𝒜)<λ_2(ℒ_ℬ), 
eq. (<ref>) tells us that the algebraic connectivity of𝒜grows at a slower rate than that ofℬ, and they never become equal: 
only one eigenvalue swapping is possible, occurring again at

    q_c = λ_2(ℒ_𝒜)/N.

Instead ifλ_2(ℒ_𝒜)>λ_2(ℒ_ℬ), the first eigenvalue swapping occurs atq_c =min{λ_2(ℒ_𝒜)/N,λ_2(ℒ_ℬ)/M}. 
Moreover, also the two algebraic connectivities of𝒜andℬswap at

    q_c' = λ_2(ℒ_𝒜)-λ_2(ℒ_ℬ)/N-M.

Such a transition is actually observed forλ_2(ℒ)only whenq_c<q_c', implyingλ_2(ℒ_𝒜)/N>λ_2(ℒ_ℬ)/Mand whenq_c'<1, implyingλ_2(ℒ_𝒜)+M<λ_2(ℒ_ℬ)+N. Figure <ref> illustrates the different situations. 
Note that the second transition happens even forλ_2(ℒ_ℬ)→0(, whenℬis a  network):q_c→0butq_c'≠0, 
providedλ_2(ℒ_𝒜)remains finite yet smaller thanN-M. 
The phase diagram of Fig. <ref> refers instead to𝒜andℬbeing  random graphs with connection probabilitiesp_Aandp_Brespectively. 
In the thermodynamic limit and forr=M/N<1finite, forp_A<p_Bone transitions is observed atq_c≃p_A, whereas, forp_A>p_Btwo transitions are observed 
atq_c≃p_Bandq_c'≃(p_A-rp_B)(1-r), providedq_c'<1. The triple point obtains atp_A=p_B=q, , when the whole system is homogeneous.



The double transition of the algebraic connectivity described above is extremely important in the context of diffusion processes, 
sinceλ_2^-1(ℒ)is equal to the relaxation timeτfor the diffusion equationẋ⃗̇=-ℒx⃗<cit.>.
In the regime of smallq, diffusion on the system depends only on the interconnection structure. 
The first transition occurs when the layer with the smallest normalized algebraic connectivity (be itλ_2(A)/Norλ_2(B)/M) starts determining the diffusion process. 
The second transition then occurs when the other layer becomes dominant, and can be observed because the two algebraic connectivities grow at different rates (N≠M) asqincreases. 
Note that the system becomes completely homogeneous only at the triple pointq_t, when neitherAnorBnor interconnections are dominant. 
Figure <ref> shows that values ofτ^-1obtained from numerical simulations of such diffusion processes 
on random interacting networks do agree well with first order mean field approximation ofλ_2.



§ PERTURBATIVE APPROACH FOR THE SPECTRUM OF THE ADJACENCY MATRIX


We now apply perturbation theory in the computation of the leading eigenvalue of the adjacency matrix of two interacting networks, which can be decomposed as:

    𝒞 = 𝒞_0 + 𝒲 =
    (
    [ 𝒜 0; 0 ℬ ])+
    (
    [   0   𝒬; 𝒬^𝖳   0 ]).
 
We denote by{α_i}_i=1^Nand{|a_i⟩}_i=1^Nthe set of eigenvalues and eigenvectors of𝒜, ordered such thatα_1>α_2≥…≥α_N, 
and by{β_j}_j=1^Mand{|b_j⟩}_j=1^Mthe set of eigenvalues and eigenvectors ofℬ, again ordered such thatβ_1>β_2≥…≥β_M.
We assume both networks to be strongly connected, so that bothα_1andβ_1are not degenerate in their respective spectrum. 
We also suppose, without loss of generality,α_1≥β_1. 
The sets{Γ_c^(0)}_c=1^N+M={{α_i}_i=1^N,{β_j}_j=1^M}and{|c^(0)⟩}_c=1^N+M={{|a_i⟩|0⟩}_i=1^N,{|0⟩|b_j⟩}_j=1^M}are thus the unperturbed spectrum of eigenvalues and its associated orthonormal basis of eigenvectors for𝒞_0. 

Ifα_1=β_1, we have to resolve the degeneracy with the unperturbed eigenstates|+^(0)⟩=1/√(2)|a_1⟩|b_1⟩and|-^(0)⟩=1/√(2)|a_1⟩-|b_1⟩. 
We have⟨+^(0)|𝒲|-^(0)|=⟩⟨-^(0)|𝒲|+^(0)|=⟩0, and:

    γ^(1)_+ =   ⟨+^(0)|𝒲|+^(0)|   ⟩= ⟨a_1|𝒬|b_1|,⟩
    γ^(1)_- =   ⟨-^(0)|𝒲|-^(0)|   ⟩= -⟨a_1|𝒬|b_1|.⟩

There is no degeneracy instead whenα_1>β_1. In this case, however, first-order corrections to all eigenvalues induced by the perturbation vanish: 

    γ^(1)_c = ⟨c^(0)|𝒲|c^(0)|=⟩0,

and we have to resort to second-order corrections. Forα_1we have:

    γ^(2)_1 = ∑_j=1^M|⟨a_1|𝒬|b_j||⟩^2/α_1-β_j,

where we used⟨b_j|𝒬^𝖳|a_i|=⟩⟨a_i|𝒬|b_j|$⟩ ∀ i,j. 
If also β_1 is non degenerate, then 

    γ^(2)_N+1 = ∑_i=1^N|⟨a_i|𝒬|b_1||⟩^2/β_1-α_i.

It turns out, however, that second-order corrections fail to capture the behavior of Γ_1 (see Figure <ref>). 
In order to obtain a non-vanishing first-order correction, we have to define the unperturbed system and the perturbation as 

    𝒞 = 𝒞̃_0 + 𝒲̃ =
    (
    [      𝒜      0;      0 ℬ + Δℐ ])
    +
    (
    [   0   𝒬; 𝒬^𝖳 -Δℐ ]),

where Δ = α_1 - β_1: we shift the whole unperturbed spectrum of ℬ by Δ, so that α_1 is now a degenerate eigenvalue for 𝒞̃_̃0̃ 
with respect to the same eigenvectors |a_1⟩ and |b_1⟩. Resolving the degeneracy with the same unperturbed eigenstates |+^(0)⟩ and |-^(0)⟩ as above, 
we obtain ⟨+^(0)|𝒲̃|-^(0)|=⟩⟨-^(0)|𝒲̃|+^(0)|=⟩Δ/2, 
⟨+^(0)|𝒲̃|+^(0)|=⟩⟨a_1|𝒬|b_1|-⟩Δ/2 and ⟨-^(0)|𝒲̃|-^(0)|=⟩-⟨a_1|𝒬|b_1|-⟩Δ/2, hence

    γ̃^(1)_± = -Δ/2±√(Δ^2/4 + [⟨a_1 | 𝒬 | b_1|]⟩^2),

which correctly reduces to eq. (<ref>) if Δ = 0, and to γ̃^(1)_+=0 and γ̃^(1)_-=-Δ if 𝒬 vanishes (which is trivially correct).

All of the above formulas can be further specified for simple instances of the interaction matrix. 
For a multiplex network, N=M and 𝒬=qℐ, hence:

    ⟨a_i|𝒬|b_j|=⟩q⟨a_i|b_j|.⟩

Instead for two randomly interacting networks, 𝒬 is an random graph with connectivity q. 
Using the mean field approximation 𝒬=q|1⟩⟨1| leads to:

    ⟨a_i|𝒬|b_j|=⟩q⟨a_i|1|⟨%s|%s⟩⟩1|b_j.




 §.§ Random regular and network layers


More can be said when both 𝒜 and ℬ are d-regular graphs. 
In this case, it is α_1=d_A, |a_1⟩=1/√(N)|1⟩, β_1=d_B, |b_1⟩=1/√(M)|1⟩. 
Besides, for sufficiently large network sizes, most d-regular graphs have all their other eigenvalues bounded above by 2√(d-1)+ε (with ε>0) <cit.>. 
Thus, provided d_B≫ 2√(d_A-1), α_1 and β_1 are by far the largest eigenvalues of the unperturbed system. 
Finally, eigenvectors corresponding to other eigenvalues are orthogonal to |1⟩, hence ⟨1|a_i|=⟩⟨1|b_j|=⟩0 for ≠ 1 and j≠ 1.

Thus in a multiplex framework where N=M it is |a_1⟩≡|b_1⟩. Using eq. (<ref>) and the eigenvectors orthogonality relations, 
we have ⟨a_1|𝒬|b_j|=⟩qδ_1j and ⟨a_i|𝒬|b_1|=⟩qδ_i1. 
In the degenerate case we get γ^(1)_±=± q, whereas, in the non-degenerate case it is
γ̃^(1)_± = -Δ/2 ±√(Δ^2/4 + q^2) and γ^(2)_1 =q^2/(α_1-β_1)=-γ^(2)_N+1.

In the random interaction framework instead, using eq. (<ref>) and again the eigenvectors orthogonality relations, 
we have ⟨a_1|𝒬|b_j|=⟩q√(NM)δ_1j and ⟨a_i|𝒬|b_1|=⟩q√(NM)δ_i1. 
In the degenerate case we get γ^(1)_±=± q√(NM), and in the non-degenerate one 
γ̃^(1)_± = -Δ/2 ±√(Δ^2/4 + q^2NM) and γ^(2)_1 =q^2NM/(α_1-β_1)=-γ^(2)_N+1.

Finally note that a d-regular graph of size N is, under the mean field approximation, equivalent to an random graph with same size and connectivity p=d/(N-1). 
Hence, the above results approximately hold also for 𝒜 and ℬ being random graphs, in particular by posing α_1=p_A(N-1) and β_1=p_B(M-1) (see Fig. <ref>).



This approach can be rather useful for estimating the bond percolation threshold f_c of two strongly interacting random networks, where the magnitude of the interaction is given by the value of q. 
As a matter of fact when the value of q is very small the two layers are in a regime of weak interaction, therefore two percolation thresholds are observed 
depending on the different topologies of the two layers <cit.><cit.>.
On the other hand, while for an individual network layer f_c is given by the inverse of the largest eigenvalue of adjacency matrix Γ_1 <cit.> 
(or in general is lower-bounded by Γ_1^-1 <cit.>), Figure <ref> shows
that for two strongly interacting layers, where q is not negligible, the percolation threshold is actually determined by eq. (<ref>).






§ CONCLUSIONS


In this work we have presented a perturbative approach to study the connectivity properties for a general class of interacting multilayer networks. 
We generalized previous results <cit.> 
showing the presence of multiple structural transitions for interacting networks as interconnections are formed. 
This fact has a direct consequence on many physical dynamical systems which are governed by the laplacian spectrum, , diffusive processes. 
We have shown that beyond the first eigenvalue crossing, there might be as much as Z-1 additional transitions, where Z is the number of network layers. 
In each of these regimes, the relaxation time of a diffusive processes on the entire system is set by a single layer. 
We further show that, at first order in perturbation theory, the growth of the algebraic connectivity of each network layer depends only on the degree sequence of the interactions 
(projected on the respective Fiedler vector), and not on the actual interaction topology.
We finally show results of perturbation theory applied to the adjacency matrix of the interconnected network, 
which can be rather useful to identify percolation transitions on strongly interacting networks. 
Our findings have, therefore, important implications in the design of robust interconnected networked system, 
particularly when the functioning of the entire system crucially depends on one or a few network layers. 
Moreover, they allow to better understand diffusion of epidemics, habits adoption, information, opinions in our multilayer-structured societies. 
Overall, our results constitute a step forward to a better understanding of linear and nonlinear processes on top of interacting network structures, 
in the direction of having a closed mathematical theory of interacting multilayer networks.


A. A. acknowledges the Spanish MINECO, Grant No. FIS2015-71582-C2-1. A. A acknowledges funding also from ICREA Academia and the James S. McDonnell Foundation. 
G.C. and G.C. acknowledge support from the EU projects DOLFINS (640772), CoeGSS (676547), Shakermaker (687941) and SoBigData (654024).










46
fxundefined [1]
 ifx#1

fnum [1]
 #1firstoftwo
 secondoftwo
 
fx [1]
 #1firstoftwo
 secondoftwo
 





noop [0]secondoftwo

ref[1]@startlink#1@href
href[1]#1@endlink
anitize@url [0]`
12`$12`&12`#12`1̂2`_12`%12
startlink[1]
endlink[0]

rl [1]href #1












@bib@innerbibempty

[De Domenico et al.(2013)De Domenico, Solé-Ribalta, Cozzo,
  Kivelä, Moreno, Porter,
  Gómez, and Arenas]dedomenico2013mathe
  author author M. De Domenico, author A. Solé-Ribalta, author E. Cozzo, author M. Kivelä,
  author Y. Moreno, author M. A. Porter, author
  S. Gómez,  and author
  A. Arenas, 10.1103/PhysRevX.3.041022 journal journal
  Physical Review X volume 3, pages
  041022 (year 2013)NoStop
[Kivelä et al.(2014)Kivelä, Arenas, Barthelemy, Gleeson, Moreno, and Porter]kivela2014multilayer
  author author M. Kivelä, author A. Arenas,
  author M. Barthelemy, author J. P. Gleeson, author
  Y. Moreno,  and author
  M. A. Porter, 10.1093/comnet/cnu016 journal journal Journal of
  Complex Networks volume 2, pages 203
  (year 2014)NoStop
[Boccaletti et al.(2014)Boccaletti, Bianconi, Criado, del Genio, nes, Romance, na Nadal, Wang, and Zanin]boccaletti2014structure
  author author S. Boccaletti, author G. Bianconi, author R. Criado,
  author C. del Genio, author J. G.-G. nes, author
  M. Romance, author I. S. na Nadal, author Z. Wang,  and author M. Zanin, 10.1016/j.physrep.2014.07.001
  journal journal Physics Reports volume 544, pages 1 (year
  2014)NoStop
[Garas(2016)]garas2016interconnected
  editor A. Garas, ed., 10.1007/978-3-319-23947-7 title Interconnected
  Networks, Understanding Complex Systems (publisher Springer
  International Publishing, year 2016)NoStop
[Radicchi(2014)]radicchi2014driving
  author author F. Radicchi, 10.1103/PhysRevX.4.021014 journal journal Physical Review X volume 4, pages 021014 (year
  2014)NoStop
[De Domenico et al.(2016)De Domenico, Granell, Porter, and  Arenas]dedomenico2016physics
  author author M. De Domenico, author C. Granell, author M. A. Porter,
   and author A. Arenas, 10.1038/nphys3865 journal journal
  Nature Physics volume 12, pages 901
  (year 2016)NoStop
[De Domenico et al.(2014)De Domenico, Solé-Ribalta, Gómez, and  Arenas]dedomenico2014navigability
  author author M. De Domenico, author A. Solé-Ribalta, author S. Gómez,  and author A. Arenas, 10.1073/pnas.1318469111 journal
  journal Proceedings of the National Academy of Sciences  volume 111, pages 8351 (year
  2014)NoStop
[Estrada and Gómez-Gardeñes(2014)]estrada2014communicability
  author author E. Estrada and author J. Gómez-Gardeñes, 10.1103/PhysRevE.89.042819
  journal journal Physical Review E volume 89, pages 042819 (year
  2014)NoStop
[Buldyrev et al.(2010)Buldyrev, Parshani, Paul, Stanley, and Havlin]buldyrev2010catastrophic
  author author S. V. Buldyrev, author R. Parshani,
  author G. Paul, author
  H. E. Stanley,  and author
  S. Havlin, 10.1038/nature08932 journal journal Nature  volume 464, pages 1025 (year
  2010)NoStop
[Gao et al.(2011)Gao,
  Buldyrev, Havlin, and Stanley]gao2011robustness
  author author J. Gao, author S. V. Buldyrev,
  author S. Havlin,  and author H. E. Stanley, 10.1103/PhysRevLett.107.195701 journal journal
  Physical Review Letters volume 107, pages 195701 (year 2011)NoStop
[Gómez-Gardeñes et al.(2015)Gómez-Gardeñes, De Domenico, Gutiérrez, Arenas, and  Gómez]gomezgardenes2015layer
  author author J. Gómez-Gardeñes, author M. De Domenico, author G. Gutiérrez, author A. Arenas,  and author S. Gómez, @noop  journal journal
  Philosophical Transactions of the Royal Society of London A volume 373 (year 2015)NoStop
[Hu et al.(2011)Hu,
  Ksherim, Cohen, and Havlin]hu2011percolation
  author author Y. Hu, author B. Ksherim,
  author R. Cohen,  and author S. Havlin, 10.1103/PhysRevE.84.066116 journal journal
  Physical Review E volume 84, pages
  066116 (year 2011)NoStop
[Bianconi and Dorogovtsev(2014)]bianconi2014multiple
  author author G. Bianconi and author S. N. Dorogovtsev, 10.1103/PhysRevE.89.062814 journal journal Physical Review E volume 89, pages 062814 (year
  2014)NoStop
[Hackett et al.(2016)Hackett, Cellai, Gómez, Arenas, and Gleeson]hackett2016bond
  author author A. Hackett, author D. Cellai,
  author S. Gómez, author A. Arenas,  and author
  J. P. Gleeson, 10.1103/PhysRevX.6.021002 journal journal
  Physical Review X volume 6, pages
  021002 (year 2016)NoStop
[Saumell-Mendiola et al.(2012)Saumell-Mendiola, Serrano, and Boguñá]saumell2012epidemic
  author author A. Saumell-Mendiola, author M. A. Serrano,  and author M. Boguñá, 10.1103/PhysRevE.86.026106 journal journal Physical Review E volume 86, pages 026106 (year
  2012)NoStop
[Dickison et al.(2012)Dickison, Havlin, and Stanley]dickison2012epidemics
  author author M. Dickison, author S. Havlin,   and author H. E. Stanley,  10.1103/PhysRevE.85.066109 journal journal Physical Review E volume 85, pages 066109 (year 2012)NoStop
[Wang and Xiao(2012)]wang2012epidemics
  author author Y. Wang and author G. Xiao,  10.1016/j.physleta.2012.07.037 journal
  journal Physics Letters A volume
  376, pages 2689 (year 2012)NoStop
[Granell et al.(2013)Granell, Gómez, and Arenas]granell2013dynamical
  author author C. Granell, author S. Gómez,   and author A. Arenas, 10.1103/PhysRevLett.111.128701 journal journal Physical Review Letters volume 111,  pages 128701 (year 2013)NoStop
[Huang et al.(2006)Huang,
  Park, Lai, Yang, and  Yang]huang2006abnormal
  author author L. Huang, author K. Park,
  author Y.-C. Lai, author L. Yang,  and author
  K. Yang, 10.1103/PhysRevLett.97.164101 journal journal
  Physical Review Letters volume 97, pages 164101 (year 2006)NoStop
[Aguirre et al.(2014)Aguirre, Sevilla-Escoboza, Gutiérrez,
  Papo, and Buldú]aguirre2014syncronization
  author author J. Aguirre, author R. Sevilla-Escoboza, author R. Gutiérrez, author D. Papo,   and author J. M. Buldú,  10.1103/PhysRevLett.112.248701 journal
  journal Physical Review Letters volume
  112, pages 248701 (year 2014)NoStop
[Radicchi and Arenas(2013)]radicchi2013abrupt
  author author F. Radicchi and author A. Arenas, 10.1038/nphys2761 journal
  journal Nature Physics volume 9,  pages 717 (year 2013)NoStop
[Gómez et al.(2013)Gómez, Díaz-Guilera, Gómez-Gardeñes, Pérez-Vicente, Moreno, and Arenas]gomez2013diffusion
  author author S. Gómez, author A. Díaz-Guilera, author J. Gómez-Gardeñes, author C. J. Pérez-Vicente, author Y. Moreno,  and author A. Arenas, 10.1103/PhysRevLett.110.028701 journal journal Physical Review Letters volume 110, pages 028701 (year
  2013)NoStop
[Solé-Ribalta et al.(2013)Solé-Ribalta, De Domenico, Kouvaris,
  Díaz-Guilera, Gómez, and  Arenas]sole2013spectral
  author author A. Solé-Ribalta, author M. De Domenico, author N. E. Kouvaris, author A. Díaz-Guilera, author S. Gómez,  and author A. Arenas, 10.1103/PhysRevE.88.032807 journal journal Physical Review E volume 88, pages 032807 (year
  2013)NoStop
[Martín-Hernández et al.(2014)Martín-Hernández, Wang,
  Mieghem, and D'Agostino]martinez2014algebraic
  author author J. Martín-Hernández, author H. Wang, author P. V. Mieghem,   and author G. D'Agostino,  10.1016/j.physa.2014.02.043 journal journal Physica A: Statistical Mechanics and its Applications volume 404, pages 92 (year
  2014)NoStop
[Sánchez-García et al.(2014)Sánchez-García, Cozzo,  and Moreno]sanchez2014dimensionality
  author author R. J. Sánchez-García, author E. Cozzo,  and author Y. Moreno, 10.1103/PhysRevE.89.052815 journal journal Physical Review E volume 89, pages 052815 (year
  2014)NoStop
[Darabi Sahneh et al.(2015)Darabi Sahneh, Scoglio, and Van Mieghem]darabi2015exact
  author author F. Darabi Sahneh, author C. Scoglio,  and author P. Van Mieghem, 10.1103/PhysRevE.92.040801 journal journal Physical Review E volume 92, pages 040801 (year
  2015)NoStop
[Shakeri et al.(2016)Shakeri, Albin, Darabi Sahneh,
  Poggi-Corradini, and Scoglio]shakeri2016maximizing
  author author H. Shakeri, author N. Albin,
  author F. Darabi Sahneh, author P. Poggi-Corradini,  and author C. Scoglio, 10.1103/PhysRevE.93.030301 journal journal
  Physical Review E volume 93, pages
  030301 (year 2016)NoStop
[Van Mieghem(2016)]van2016interconnectivity
  author author P. Van Mieghem, 10.1103/PhysRevE.93.042305 journal journal Physical Review E volume 93, pages 042305 (year
  2016)NoStop
[Fielder(1975)]fieldedr1975prop
  author author M. Fielder, @noop  journal journal
  Czech. Math. J. volume 25 (year
  1975)NoStop
[Mohar(1991)]mohar1991laplacian
  author author B. Mohar, in @noop  booktitle Graph Theory,
  Combinatorics, and Applications, series and number
  Proceedings of the Sixth Quadrennial International Conference on the Theory
  and Applications of Graphs, editor edited by editor
  Y. Alavi, editor G. Chartrand, editor O. R.  Oellermann,  and editor A. J.  Schwenk (publisher Wiley, New York, year 1991) pp. pages 871–898NoStop
[Jamakovic and Van Mieghem(2008)]jamakovic2008robustness
  author author A. Jamakovic and author P. Van Mieghem, title On the robustness of complex
  networks by using the algebraic connectivity, in 10.1007/978-3-540-79549-0_16 booktitle NETWORKING 2008
  Ad Hoc and Sensor Networks, Wireless Networks, Next Generation Internet: 7th
  International IFIP-TC6 Networking Conference Singapore, May 5-9, 2008
  Proceedings, editor edited by editor
  A. Das, editor H. K. Pung, editor F. B. S.  Lee,  and editor L. W. C.  Wong (publisher Springer, Berlin Heidelberg,  year 2008) pp. pages 183–194NoStop
[Almendral and Díaz-Guilera(2007)]almendral2007dynamical
  author author J. A. Almendral and author A. Díaz-Guilera, 10.1088/1367-2630/9/6/187 journal journal New Journal of Physics volume 9, pages 187 (year 2007)NoStop
[Arenas et al.(2008)Arenas,
  Díaz-Guilera, Kurths, Moreno, and Zhou]arenas2008syncronization
  author author A. Arenas, author A. Díaz-Guilera, author J. Kurths, author Y. Moreno,   and author C. Zhou, 10.1016/j.physrep.2008.09.002 journal journal Physics Reports volume 469, pages 93 (year 2008)NoStop
[Samukhin et al.(2008)Samukhin, Dorogovtsev, and Mendes]samukin2008laplacian
  author author A. N. Samukhin, author S. N. Dorogovtsev,  and author J. F. F.  Mendes, 10.1103/PhysRevE.77.036115
  journal journal Physical Review E volume 77, pages 036115 (year
  2008)NoStop
[Kim and Motter(2007)]kim2007ensemble
  author author D.-H. Kim and author A. E. Motter, 10.1103/PhysRevLett.98.248701 journal journal Physical Review Letters volume 98, pages 248701 (year
  2007)NoStop
[Chauhan et al.(2009)Chauhan, Girvan, and Ott]chauhan2009spectral
  author author S. Chauhan, author M. Girvan,   and author E. Ott, 10.1103/PhysRevE.80.056114 journal journal Physical Review E volume 80, pages 056114 (year 2009)NoStop
[Wang et al.(2011)Wang,
  Di, and Fan]wang2011identifying
  author author Y. Wang, author Z. Di,  and  author Y. Fan, 10.1371/journal.pone.0027418 journal journal
  PLoS ONE volume 6, pages 1 (year 2011)NoStop
[Yan et al.(2014)Yan,
  Wu, Li, Li, and  Hu]yan2014eigenvector
  author author X. Yan, author Y. Wu, author X. Li, author
  C. Li,  and author
  Y. Hu, 10.1016/j.physa.2014.04.018 journal journal
  Physica A: Statistical Mechanics and its Applications volume 408, pages 106 (year
  2014)NoStop
[Hata and Nakao(2017)]hata2017localization
  author author S. Hata and author H. Nakao,  10.1038/s41598-017-01010-0 journal journal Scientific Reports volume 7, pages 1121 (year 2017)NoStop
[Bollobás(1981)]bollobas1981degree
  author author B. Bollobás, 10.1016/0012-365X(81)90253-3 journal journal Discrete Mathematics volume 33, pages 1 (year 1981)NoStop
[Delvenne et al.(2015)Delvenne, Lambiotte, and Rocha]delvenne2015diffusion
  author author J.-C. Delvenne, author R. Lambiotte,
   and author L. E. C. Rocha,  10.1038/ncomms8366 journal journal Nature Communications volume 6,  pages 7366 (year 2015)NoStop
[Masuda et al.(2017)Masuda,
  Porter, and Lambiotte]masuda2017random
  author author N. Masuda, author M. A. Porter,
   and author R. Lambiotte,  10.1016/j.physrep.2017.07.007 journal
  journal Physics Reports volume
  716-717, pages 1 (year 2017)NoStop
[Friedman(2003)]friedman2003proof
  author author J. Friedman, in 10.1145/780542.780646 booktitle Proceedings of the Thirty-fifth Annual ACM Symposium on Theory
  of Computing, series and number STOC '03 (publisher ACM, address New York, NY, USA, year
  2003) pp. pages 720–724NoStop
[Colomer-de Simón and Boguñá(2014)]simon2014doubleperc
  author author P. Colomer-de Simón and author M. Boguñá, 10.1103/PhysRevX.4.041020
  journal journal Phys. Rev. X volume 4, pages 041020 (year
  2014)NoStop
[Bollobás et al.(2010)Bollobás, Borgs, Chayes, and  Riordan]bollobas2010percolation
  author author B. Bollobás, author C. Borgs,
  author J. Chayes,  and author O. Riordan, 10.1214/09-aop478 journal journal The Annals of
  Probability volume 38, pages 150
  (year 2010)NoStop
[Radicchi and Castellano(2016)]radicchi2016beyond
  author author F. Radicchi and author C. Castellano, 10.1103/PhysRevE.93.030302 journal journal Physical Review E volume 93, pages 030302 (year
  2016)NoStop


