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 metadatas

Cited literature [35 references]  Display  Hide  Download

https://hal.inria.fr/hal-01257188
Contributor : Philippe Nain <>
Submitted on : Tuesday, June 21, 2016 - 2:39:16 PM
Last modification on : Thursday, February 7, 2019 - 4:48:41 PM
Long-term archiving on : Thursday, September 22, 2016 - 2:45:04 PM

File

PRE2016.pdf
Publisher files allowed on an open archive

Identifiers

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

Citation

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⟩

Share

Metrics

Record views

377

Files downloads

235