Growing multiplex networks

References

Appendix A Mean-field theory

In this section, using a mean-field approach, we discuss the time evolution of the degree of the nodes of a multiplex in the different layers and we derive long-time expressions for the degree distribution at each layer and for the inter-layer degree-degree correlations. We first consider the linear attachment case (A) and then proceed to the semi-linear case (B). We also provide a concise discussion of the case in which new nodes bring a random number of new edges (C).

According to the growth model discussed in the main text, the probability that a newly arrived node $i$ in the multiplex creates a link to node $j$ on layer $\alpha$ can be written as

where $F^{[\alpha]}_{j}(\bm{k}_{j})$ is a certain function of the degrees of the replicas of node $j$. If $F^{[\alpha]}_{j}(\bm{k}_{j})$ is a linear function of $\bm{k}_{j}$ $\forall\alpha$, and all the replicas of the new node arrive at the same time, the temporal evolution of the degree of a node on each layer is governed by the equations

with the constraints $c^{}+c^{}=1$ and $c^{}+c^{}=1$. Since the matrix elements are real and non-zeros, the maximal eigenvalue is real. Moreover since we have just two layers then both eigenvalues $\lambda_{1}$ and $\lambda_{2}$ are real. We notice that if we impose that each row of matrix $C$ must sum to $1$, and that the coefficients $c^{[r,s]}$ are non-negative (to ensure that $\Pi^{[\alpha]}_{i\rightarrow j}$ is a probability distribution $\forall\alpha$), then we can write

It is easy to verify that if $b-a+1\neq 0$ the matrix $C$ has eigenvalues $\lambda_{1}=1$ and $\lambda_{2}=(a-b)\neq 1$, with eigenvectors $\bm{u^{1}}=$ and $\bm{u^{2}}=[1,-b/(1-a)]$ (the degenerate case $b-a+1=0$ is considered below). Since the eigenvalues are distinct, then $C$ is diagonalizable, i.e. it is similar to the diagonal matrix

whose non-zero elements are the eigenvalues of $C$. The system in Eq. (S-2) can be also written in the form

where $\alpha(t)=\frac{1}{2t}$ is a scalar function, and $C$ is a constant matrix. This is a homogeneous time-varying linear dynamical system, whose temporal evolution is fully determined by the initial state $\bm{k}_{s}=m{\bf u^{1}}$ and by the state transition matrix $\Phi(t,s)$, where $s$ is the time at which a node is added to the graph

Since $C$ is diagonalizable, then the transition matrix can be written as

where $V$ is the matrix whose columns are the eigenvectors of $C$ and $\Lambda$ is the diagonal matrix of the eigenvalues of $C$. After some simple algebra we obtain

Let us now consider the degenerate case $b-a+1=0$. Since we imposed that each row of the matrix $C$ has to sum to $1$, then $b-a+1=0$ only if $a=1$ and $b=0$. In this case the two layers evolve independently, the matrix $C$ is diagonal and the time evolution of the degree on each layer reads

with $\alpha=1,2$. This means that in the case of linear attachment kernel on both layers without delay the degree distribution of each layer is a power-law $P(k)\sim k^{-\gamma}$ with exponent $\gamma=3$ and we have

A.2 Semi-linear attachment kernel

For the semi-linear attachment kernel we have

The system in Eq. (S-16) is a non-homogeneous time-varying linear dynamical system where $\bm{w}(t)$ represents an external forcing function. If we call $\Phi(t,s)$ the state transition matrix of the corresponding homogeneous system $\dot{\bm{k}}(t)=A(t)\bm{k}(t)$, it is possible to show that the unique solution of Eq. (S-16) is given by

The form of the transition matrix $\Phi(t,s)$ associated to the homogeneous system depends on the value of $a$. When $a\neq 0$ then $\Phi(t,s)$ reads

By plugging Eq. (S-18) into Eq. (S-17) one obtains the mean-field temporal evolution of $k_{s}^{}$ and $k_{s}^{}$:

In general, if $b\neq 0$ then for $t\rightarrow\infty$ we have $\left(\frac{t}{s}\right)^{\beta}\gg\left(\log(t)-\log(s)\right)$. Consequently, Eqs. (S-19) can be written as

so that the degree distribution on both layers reads

Instead, if $b=0$ the solution for the degree of nodes on the second layer reads

while $k_{s}^{}(t)$ is expressed by Eq. (S-20). In this case, the degree distribution on the first layer is the same as in Eq. (S-22), while for the second layer we have

and in the limit of large $k^{}(t),k^{}(t)$ we obtain

Eqs. (S-18—S-24) are valid when $a\neq 0$. When $a=0$ the state transition matrix reads

and the generic solutions for $k_{s}^{}(t)$ and $k_{s}^{}(t)$ are

In this case, the degree distribution on the first layer is exponential $P(k^{})\sim e^{-\frac{k}{m}}$. On the second layer, the functional form of the degree distribution depends on the value of $b$. It is easy to verify that when $b=0$ then $P(k^{})\sim e^{-\frac{k}{m}}$, and we have in the limit of large $k^{}(t),k^{}(t)$

Conversely, when $b>0$ the degree distribution on the second layer is

In this case, in the limit of large $k^{}(t),k^{}(t)$, we have

A.3 Fluctuations in the number of edges

In principle, the mean-field approach could be also applied to the case in which the number of edges brought on layer $\alpha$ by each new-born node is not fixed but is a random variable $\xi^{[\alpha]}$ drawn from a given distribution $P(\xi^{[\alpha]})$. In this case we should solve the system of stochastic differential equations:

The random variable $\xi^{[\alpha]}$ is a positive integer with average $\langle\xi^{[\alpha]}\rangle$ and the dominant term at large times of $\kappa^{[\alpha]}$ is then given by

This implies in particular that at large times, the effect of randomness in the number of edges is negligible, and the behavior of the system is governed by the average number of edges $\langle\xi^{[\alpha]}\rangle$ added in each layer.

Appendix B Master Equation approach for the model without delay

We provide here the derivation of exact expressions of $P(k)$ and $P(k,q)$ starting from the master equation of the system. We denote by $N_{k,q}(t)$ the average number of nodes that at time $t$ have degree $k$ in layer 1 and degree $q$ in layer 2. We start from a small connected network and at each time we add a node which brings, at same time, $m$ new edges in layer 1 and $m$ new edges in layer 2. We assume that, when we add the new node $i$ to the network, the expected number of new links in layer 1 attached to a node $j$ of degree $k$ in layer 1 and degree $q$ in layer 2 is given by $m\Pi^{}_{i\to j}=\frac{A_{k,q}}{t}$. Similarly, the expected number of new links in layer 2 attached to a node $j$ of degree $k$ in layer 1 and degree $q$ in layer 2 is given by $m\Pi^{}_{i\to j}=\frac{B_{k,q}}{t}$ . In addition to that, we work in the hypothesis that in the large $t$ limit, $t\gg 1$, we have $A_{k,q}/t\ll 1$ and $B_{k,q}/t\ll 1$ so that we can neglect the probability that a node acquires at the same time a link in both layers. In this hypothesis the master equation for evolving multiplex network is given by

for $k\geq m$ and $q\geq m$, as long as $N_{m-1,q}(t)=N_{k,m-1}(t)=0$. Assuming that $N_{k,q}=tP(k,q)$ is valid in the large time limit $t\gg 1$, we can solve for the combined degree distribution $P(k,q)$ indicating the probability that a node has at the same time degree $k$ in layer 1 and degree $q$ in layer 2. We get the master equations

(i) Linear attachment kernel – Let us first consider a linear preferential attachment kernel, in which $c^{}=c^{}=1$ and $c^{}=c^{}=0$. In this case we have

where $P(m,m)$ is fixed by the normalization condition $\sum_{k=m}^{\infty}\sum_{q=m}^{\infty}P(k,q)=1$. Using the relation

it can be proved recursively that $P(k,q)$ takes the following expression

Summing over the degree in layer 2 we can find the degree distribution $P(k)$ in layer 1, i.e. $P(k)=\sum_{q=m}^{\infty}P(k,q)$ obtaining the known result for a single layer,

The function $\langle k(q)\rangle$ is given by

Similar expressions are obtained for $P(q)$ and $\langle q(k)\rangle$, by summing Eq. (S-38) over $k$.

(ii) Uniform attachment kernel – Let us now consider a uniform attachment kernel, in which every target node $j$ is chosen with probability $\Pi^{}_{i\to j}=\frac{1}{t}$ in layer 1 and with probability $\Pi^{}_{i\to j}=\frac{1}{t}$ in layer 2, so that

In this case the recursive Eqs. (S-34) read

where $P(m,m)$ is again fixed by the normalization condition $\sum_{k=m}^{\infty}\sum_{q=m}^{\infty}P(k,q)=1$. Using again the relation provided in Eq. (S-37) it is easy to prove recursively that $P(k,q)$ is given in this case by

Moreover the degree distribution $P(k)=\sum_{q=m}^{\infty}P(k,q)$ and $P(q)=\sum_{k=m}^{\infty}P(k,q)$ of a single network are given by

while the function $\langle k(q)\rangle=\sum_{k=m}^{\infty}kP(k,q)/P(q)$ is given by

(iii) Semi-linear attachment kernel – Finally we analyze the case of semi-linear attachment with $c^{}=c^{}=1$ and $c^{}=c^{}=0$. We have:

where $P(m,m)$ is fixed by the normalization condition $\sum_{q=m}^{\infty}\sum_{k=m}^{\infty}P(k,q)=1$. It can be shown recursively that these equations have the following solution,

with the associated degree distributions $P(k)=\sum_{q=m}^{\infty}P(k,q)$ and $P(q)=\sum_{k=m}^{\infty}P(k,q)$ given by

Finally the function $\langle k(q)\rangle=\sum_{k=m}^{\infty}kP(k,q)/P(q)$ is given by

Appendix C Role of β\beta in the delayed arrival

In Fig. S-1 we show the time evolution of the maximum degree $k_{M}(t)$ on the first layer, for different values of $\beta$. Notice that $k_{M}(t)\sim(t/s)^{\delta}$. The effect of the exponent $\beta$ tuning the width of the delay distribution is evident: the larger the value of $\beta$, the closer $\delta$ is to $0.5$, the value observed in the case of synchronous arrival. Consequently, the rightmost part of the degree distribution is broader when $\beta$ is close to $1$ and becomes more similar to $P(k)\sim k^{-3}$ when $\beta$ increases.

Appendix D Finite size effects

It is interesting to investigate how the properties of the multiplexes generated using the model we propose depend on the number of nodes $N$. For instance, most of the mean-field predictions for the degree distributions and inter-layer degree correlations are valid in the limit of large $N$. However, as shown in Fig. S-2 and in Fig. S-3, the properties of the degree distributions and of inter-layer degree-degree correlations are similar to those predicted for large $N$ even for relatively small multiplexes, e.g. with $N=1000$.

Appendix E Time complexity

The most efficient algorithm for the construction of a simplex networks based on preferential attachment takes advantage of random sampling with rejection and runs in $\mathcal{O}(Nm^{2})$. However, in the case of a multiplex the procedure to sample a candidate neighbour $j$ of a newly-arrived node $i$ is a bit more complicated. Let us first consider a two-layer multiplex described by Eq. (S-2). When we sample the candidate neighbours of node $i$ at layer $1$ at time $t$, each node $j$ should be sampled with a probability proportional to $ak^{}_{j}+(1-a)k^{}_{j}$. The simplest way to implement such sampling is to construct a vector $\mathcal{S}$ whose $n$-th entry is equal to $\sum_{j=1}^{n}ak^{}_{j}+(1-a)k^{}_{j}$ (the first element $\mathcal{S}$ of the array is set equal to zero); then we sample a real number $\zeta$ in the interval $\left(0,\mathcal{S}[t]\right]$ and we choose the node $j$ such that $\zeta\leq\mathcal{S}[j]$ and $\zeta>\mathcal{S}[j-1]$. The construction of the vector $\mathcal{S}$ at each time $t$ requires $\mathcal{O}(t)$ operations while the sampling of a single node $j$ can be efficiently implemented by binary search, requiring at most $\mathcal{O}(\log(t))$ operations per edge, so that the sampling of $m$ edges requires at most $\mathcal{O}(m\log(t))$ steps. Thus, the total number of operations needed to sample a layer of a multiplex is:

It is easy to verify that the construction of a $M$-layer multiplex requires a number of steps

which, for $m$ fixed, is dominated by $\mathcal{O}(MN^{2})$. Therefore, the time complexity of this algorithm is linear in the number of layers and quadratic in the number of nodes. We notice that in principle it is possible to construct better algorithms to sample growing multiplexes by implementing a smart policy to update the array $\mathcal{S}$.

Appendix F Randomly-chosen master layer

In the main text we made the simplifying assumption that each node arrives first on the master layer and then on the other layers, after a certain delay. We call this assumption “Equal master layer” (EML). In this Section we briefly comment on the case in which this assumption does not hold, i.e. when a node first arrives either on the first or on the second layer, and then arrives on the other layer after a power-law distributed delay. We call this case “Randomly-chosen master layer” (RML), to stress the fact that the master layer of each node is chosen at random among the $M$ layers of the multiplex. In particular, we are interested in the case in which a newly arrived node selects one of the $M$ layers of the multiples as its master layer with uniform probability $p=1/M$. In Fig. S-4, S-5 and S-6 we report, respectively, the degree distributions, the temporal scaling of the degree of the largest hub and the distribution of shortest path lengths and node interdependence for RML with $M=2$. The plots suggest that the random choice of the master layer produces a more balanced distribution of super hubs between the two layers, which has a relevant impact on the distribution of shortest path lengths and node interdependence (Fig. S-6). Conversely, the degree distributions and the temporal scaling of the degree of the largest hub are practically indistinguishable from those observed in EML (Fig. S-4 and S-5).