Skip to Main content Skip to Navigation
Journal articles

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

Abstract : We consider multiple networks formed by a common set of users connected via M different means of connectivity, where each user (node) is active, independently, in any given network with probability q. We show that when q exceeds a threshold q_c(M), a giant connected component appears in the M-layer network— thereby enabling faraway 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) < (ln(1 − p_c)/M)^{1/2}, where p_c is the bond percolation threshold of the underlying connectivity graph 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 show a way to translate analytical approximations of the site-bond critical region developed in the 1990s, which are functions only of p_c and q_c of the respective lattice, to excellent general approximations of q_c(M).
Document type :
Journal articles
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download
Contributor : Philippe Nain Connect in order to contact the contributor
Submitted on : Tuesday, June 21, 2016 - 2:39:16 PM
Last modification on : Thursday, January 20, 2022 - 5:28:15 PM
Long-term archiving on: : Thursday, September 22, 2016 - 2:45:04 PM


Publisher files allowed on an open archive


  • HAL Id : hal-01257188, version 1
  • ARXIV : 1402.7057


Saikat Guha, Donald Towsley, Philippe Nain, Cagatay Capar, Ananthram Swami, et al.. Spanning connectivity in a multilayer network and its relationship to site-bond percolation. Physical Review E , American Physical Society (APS), 2016. ⟨hal-01257188⟩



Les métriques sont temporairement indisponibles