Spanning connectivity in a multilayer network and its relationship to site-bond percolation

Saikat Guha, Donald Towsley, Philippe Nain, Çaǧatay Çapar, Ananthram Swami, Prithwish Basu

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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 qc(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 qc(M)?-ln(1-pc)/M, where pc is the bond percolation threshold of G, and qc(1)≡qc is its site-percolation threshold. We find qc(M) exactly for when G is a large random network with an arbitrary node-degree distribution. We find qc(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 pc and qc of the respective lattice, to excellent general approximations of the multilayer connectivity threshold qc(M).

Original languageEnglish (US)
Article number062310
JournalPhysical Review E
Issue number6
StatePublished - Jun 14 2016

ASJC Scopus subject areas

  • Statistical and Nonlinear Physics
  • Statistics and Probability
  • Condensed Matter Physics


Dive into the research topics of 'Spanning connectivity in a multilayer network and its relationship to site-bond percolation'. Together they form a unique fingerprint.

Cite this