title: Spanning connectivity in a multilayer network and its relationship to site-bond percolation.
abstract: We analyze the connectivity of an M-layer network over a common set of nodes that are active only in a fraction of the layers. Each layer is assumed to be a subgraph (of an underlying connectivity graph G) induced by each node being active in any given layer with probability q. The M-layer network is formed by aggregating the edges over all M layers. We show that when q exceeds a threshold q_{c}(M), a giant connected component appears in the M-layer network-thereby enabling far-away users to connect using "bridge" nodes that are active in multiple network layers-even though the individual layers may only have small disconnected islands of connectivity. We show that q_{c}(M)≲sqrt[-ln(1-p_{c})]/sqrt[M], where p_{c} is the bond percolation threshold of G, and q_{c}(1)≡q_{c} is its site-percolation threshold. We find q_{c}(M) exactly for when G is a large random network with an arbitrary node-degree distribution. We find q_{c}(M) numerically for various regular lattices and find an exact lower bound for the kagome lattice. Finally, we find an intriguingly close connection between this multilayer percolation model and the well-studied problem of site-bond percolation in the sense that both models provide a smooth transition between the traditional site- and bond-percolation models. Using this connection, we translate known analytical approximations of the site-bond critical region, which are functions only of p_{c} and q_{c} of the respective lattice, to excellent general approximations of the multilayer connectivity threshold q_{c}(M).
authors.affiliation: Raytheon BBN Technologies, Cambridge, Massachusetts 02138, USA.
authors.forename: Saikat
authors.initials: S
authors.lastname: Guha
authors.affiliation: University of Massachusetts, Amherst, Massachusetts 01003, USA.
authors.forename: Donald
authors.initials: D
authors.lastname: Towsley
authors.affiliation: Inria, 06902 Sophia Antipolis Cedex, France.
authors.forename: Philippe
authors.initials: P
authors.lastname: Nain
authors.affiliation: Ericsson Research, San Jose, California 95134, USA.
authors.forename: Çağatay
authors.initials: Ç
authors.lastname: Çapar
authors.affiliation: US Army Research Laboratory, Adelphi, Maryland 20783, USA.
authors.forename: Ananthram
authors.initials: A
authors.lastname: Swami
authors.affiliation: Raytheon BBN Technologies, Cambridge, Massachusetts 02138, USA.
authors.forename: Prithwish
authors.initials: P
authors.lastname: Basu