Extended-range percolation in complex networks

Abstract

Classical percolation theory underlies many processes of information transfer along the links of a network. In these standard situations, the requirement for two nodes to be able to communicate is the presence of at least one uninterrupted path of nodes between them. In a variety of more recent data transmission protocols, such as the communication of noisy data via error-correcting repeaters, both in classical and quantum networks, the requirement of an uninterrupted path is too strict: two nodes may be able to communicate even if all paths between them have interruptions/gaps consisting of nodes that may corrupt the message. In such a case a different approach is needed. We develop the theoretical framework for extended-range percolation in networks, describing the fundamental connectivity properties relevant to such models of information transfer. We obtain exact results, for any range $R$, for infinite random uncorrelated networks and we provide a message-passing formulation that works well in sparse real-world networks. The interplay of the extended range and heterogeneity leads to novel critical behavior in scale-free networks.

5 pages, 3 figures + appendices

References in corpus (7)

• Percolation on complex networks: Theory and application
• Percolation on sparse networks
• Implementation of a 46-node quantum metropolitan area network
• Entanglement Distribution in Pure-State Quantum Networks
• Breaking of the site-bond percolation universality in networks
• Mapping the Structure of Directed Networks: Beyond the "Bow-tie" Diagram
• Simple cubic random-site percolation thresholds for neighborhoods containing fourth-nearest neighbors

Cited by in corpus (10)

• Complex Quantum Networks: a Topical Review
• Shortest-path percolation on random networks
• General theory for extended-range percolation on simple and multiplex networks
• Quantum Communication Networks Enhanced by Distributed Quantum Memories
• Strongly clustered random graphs via triadic closure: An exactly solvable model
• Universality of random-site percolation thresholds for two-dimensional complex non-compact neighborhoods
• Scaling and universality for percolation in random networks: A unified view
• No-exclaves percolation on random networks
• Shortest-path percolation on scale-free networks
• How universal is the mean-field universality class for percolation in complex networks?