1
|
Cirigliano L, Castellano C, Timár G. Extended-range percolation in complex networks. Phys Rev E 2023; 108:044304. [PMID: 37978626 DOI: 10.1103/physreve.108.044304] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/17/2023] [Accepted: 09/20/2023] [Indexed: 11/19/2023]
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 or 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.
Collapse
Affiliation(s)
- Lorenzo Cirigliano
- Dipartimento di Fisica Università "Sapienza, P.le A. Moro, 2, I-00185 Rome, Italy
- Centro Ricerche Enrico Fermi, Piazza del Viminale, 1, I-00184 Rome, Italy
| | - Claudio Castellano
- Centro Ricerche Enrico Fermi, Piazza del Viminale, 1, I-00184 Rome, Italy
- Istituto dei Sistemi Complessi (ISC-CNR), Via dei Taurini 19, I-00185 Rome, Italy
| | - Gábor Timár
- Departamento de Física da Universidade de Aveiro & I3N, Campus Universitário de Santiago, 3810-193 Aveiro, Portugal
| |
Collapse
|
2
|
Mitra S, Sensharma A. Site percolation in distorted square and simple cubic lattices with flexible number of neighbors. Phys Rev E 2023; 107:064127. [PMID: 37464708 DOI: 10.1103/physreve.107.064127] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/22/2023] [Accepted: 06/06/2023] [Indexed: 07/20/2023]
Abstract
This paper exhibits a Monte Carlo study on site percolation using the Newmann-Ziff algorithm in distorted square and simple cubic lattices where each site is allowed to be directly linked with any other site if the Euclidean separation between the pair is at most a certain distance d, called the connection threshold. Distorted lattices are formed from regular lattices by a random but controlled dislocation of the sites with the help of a parameter α, called the distortion parameter. The distinctive feature of this study is the relaxation of the restriction of forming bonds with only the nearest neighbors. Owing to this flexibility and the intricate interplay between the two parameters α and d, the site percolation threshold may either increase or decrease with distortion. The dependence of the percolation threshold on the average degree of a site has been explored to show that the obtained results are consistent with those on percolation in regular lattices with an extended neighborhood and continuum percolation.
Collapse
Affiliation(s)
- Sayantan Mitra
- Department of Physics, University of Gour Banga, Malda 732103, West Bengal, India
| | - Ankur Sensharma
- Department of Physics, University of Gour Banga, Malda 732103, West Bengal, India
| |
Collapse
|
3
|
Mitra S, Saha D, Sensharma A. Percolation in a simple cubic lattice with distortion. Phys Rev E 2022; 106:034109. [PMID: 36266842 DOI: 10.1103/physreve.106.034109] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/08/2022] [Accepted: 08/22/2022] [Indexed: 06/16/2023]
Abstract
Site percolation in a distorted simple cubic lattice is characterized numerically employing the Newman-Ziff algorithm. Distortion is administered in the lattice by systematically and randomly dislocating its sites from their regular positions. The amount of distortion is tunable by a parameter called the distortion parameter. In this model, two occupied neighboring sites are considered connected only if the distance between them is less than a predefined value called the connection threshold. It is observed that the percolation threshold always increases with distortion if the connection threshold is equal to or greater than the lattice constant of the regular lattice. On the other hand, if the connection threshold is less than the lattice constant, the percolation threshold first decreases and then increases steadily as distortion is increased. It is shown that the variation of the percolation threshold can be well explained by the change in the fraction of occupied bonds with distortion. The values of the relevant critical exponents of the transition strongly indicate that percolation in regular and distorted simple cubic lattices belong to the same universality class. It is also demonstrated that this model is intrinsically distinct from the site-bond percolation model.
Collapse
Affiliation(s)
- Sayantan Mitra
- Department of Physics, University of Gour Banga, Malda - 732103, West Bengal, India
| | - Dipa Saha
- Department of Physics, University of Gour Banga, Malda - 732103, West Bengal, India
| | - Ankur Sensharma
- Department of Physics, University of Gour Banga, Malda - 732103, West Bengal, India
| |
Collapse
|
4
|
Cirigliano L, Cimini G, Pastor-Satorras R, Castellano C. Cumulative merging percolation: A long-range percolation process in networks. Phys Rev E 2022; 105:054310. [PMID: 35706250 DOI: 10.1103/physreve.105.054310] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/02/2022] [Accepted: 04/25/2022] [Indexed: 06/15/2023]
Abstract
Percolation on networks is a common framework to model a wide range of processes, from cascading failures to epidemic spreading. Standard percolation assumes short-range interactions, implying that nodes can merge into clusters only if they are nearest neighbors. Cumulative merging percolation (CMP) is a percolation process that assumes long-range interactions such that nodes can merge into clusters even if they are topologically distant. Hence, in CMP clusters do not coincide with the topologically connected components of the network. Previous work has shown that a specific formulation of CMP features peculiar mechanisms for the formation of the giant cluster and allows one to model different network dynamics such as recurrent epidemic processes. Here we develop a more general formulation of CMP in terms of the functional form of the cluster interaction range, showing an even richer phase transition scenario with competition of different mechanisms resulting in crossover phenomena. Our analytic predictions are confirmed by numerical simulations.
Collapse
Affiliation(s)
- Lorenzo Cirigliano
- Dipartimento di Fisica, Università Sapienza, Piazzale Aldo Moro 2, 00185 Rome, Italy
- Centro Ricerche Enrico Fermi, Piazza del Viminale 1, 00184 Rome, Italy
| | - Giulio Cimini
- Centro Ricerche Enrico Fermi, Piazza del Viminale 1, 00184 Rome, Italy
- Dipartimento di Fisica and INFN, Università di Roma Tor Vergata, 00133 Rome, Italy
| | - Romualdo Pastor-Satorras
- Departament de Física, Universitat Politècnica de Catalunya, Campus Nord B4, 08034 Barcelona, Spain
| | - Claudio Castellano
- Centro Ricerche Enrico Fermi, Piazza del Viminale 1, 00184 Rome, Italy
- Istituto dei Sistemi Complessi (ISC-CNR), Via dei Taurini 19, 00185 Rome, Italy
| |
Collapse
|
5
|
Xun Z, Hao D, Ziff RM. Site and bond percolation thresholds on regular lattices with compact extended-range neighborhoods in two and three dimensions. Phys Rev E 2022; 105:024105. [PMID: 35291074 DOI: 10.1103/physreve.105.024105] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/30/2021] [Accepted: 01/13/2022] [Indexed: 06/14/2023]
Abstract
Extended-range percolation on various regular lattices, including all 11 Archimedean lattices in two dimensions and the simple cubic (sc), body-centered cubic (bcc), and face-centered cubic (fcc) lattices in three dimensions, is investigated. In two dimensions, correlations between coordination number z and site thresholds p_{c} for Archimedean lattices up to 10th nearest neighbors (NN) are seen by plotting z versus 1/p_{c} and z versus -1/ln(1-p_{c}) using the data of d'Iribarne et al. [J. Phys. A 32, 2611 (1999)JPHAC50305-447010.1088/0305-4470/32/14/002] and others. The results show that all the plots overlap on a line with a slope consistent with the theoretically predicted asymptotic value of zp_{c}∼4η_{c}=4.51235, where η_{c} is the continuum threshold for disks. In three dimensions, precise site and bond thresholds for bcc and fcc lattices with 2nd and 3rd NN, and bond thresholds for the sc lattice with up to the 13th NN, are obtained by Monte Carlo simulations, using an efficient single-cluster growth method. For site percolation, the values of thresholds for different types of lattices with compact neighborhoods also collapse together, and linear fitting is consistent with the predicted value of zp_{c}∼8η_{c}=2.7351, where η_{c} is the continuum threshold for spheres. For bond percolation, Bethe-lattice behavior p_{c}=1/(z-1) is expected to hold for large z, and the finite-z correction is confirmed to satisfy zp_{c}-1∼a_{1}z^{-x}, with x=2/3 for three dimensions as predicted by Frei and Perkins [Electron. J. Probab. 21, 56 (2016)1083-648910.1214/16-EJP6] and by Xu et al. [Phys. Rev. E 103, 022127 (2021)2470-004510.1103/PhysRevE.103.022127]. Our analysis indicates that for compact neighborhoods, the asymptotic behavior of zp_{c} has universal properties, depending only on the dimension of the system and whether site or bond percolation but not on the type of lattice.
Collapse
Affiliation(s)
- Zhipeng Xun
- School of Material Sciences and Physics, China University of Mining and Technology, Xuzhou 221116, China
| | - Dapeng Hao
- School of Material Sciences and Physics, China University of Mining and Technology, Xuzhou 221116, China
| | - Robert M Ziff
- Center for the Study of Complex System and Department of Chemical Engineering, University of Michigan, Ann Arbor, Michigan 48109-2800, USA
| |
Collapse
|
6
|
Hu Y, Charbonneau P. Percolation thresholds on high-dimensional D_{n} and E_{8}-related lattices. Phys Rev E 2021; 103:062115. [PMID: 34271715 DOI: 10.1103/physreve.103.062115] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/22/2021] [Accepted: 05/28/2021] [Indexed: 11/07/2022]
Abstract
The site and bond percolation problems are conventionally studied on (hyper)cubic lattices, which afford straightforward numerical treatments. The recent implementation of efficient simulation algorithms for high-dimensional systems now also facilitates the study of D_{n} root lattices in n dimensions as well as E_{8}-related lattices. Here, we consider the percolation problem on D_{n} for n=3 to 13 and on E_{8} relatives for n=6 to 9. Precise estimates for both site and bond percolation thresholds obtained from invasion percolation simulations are compared with dimensional series expansion based on lattice animal enumeration for D_{n} lattices. As expected, the bond percolation threshold rapidly approaches the Bethe lattice limit as n increases for these high-connectivity lattices. Corrections, however, exhibit clear yet unexplained trends. Interestingly, the finite-size scaling exponent for invasion percolation is found to be lattice and percolation-type specific.
Collapse
Affiliation(s)
- Yi Hu
- Department of Chemistry, Duke University, Durham, North Carolina 27708, USA
| | - Patrick Charbonneau
- Department of Chemistry, Duke University, Durham, North Carolina 27708, USA.,Department of Physics, Duke University, Durham, North Carolina 27708, USA
| |
Collapse
|
7
|
Xu W, Wang J, Hu H, Deng Y. Critical polynomials in the nonplanar and continuum percolation models. Phys Rev E 2021; 103:022127. [PMID: 33736116 DOI: 10.1103/physreve.103.022127] [Citation(s) in RCA: 9] [Impact Index Per Article: 3.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/21/2020] [Accepted: 01/15/2021] [Indexed: 11/07/2022]
Abstract
Exact or precise thresholds have been intensively studied since the introduction of the percolation model. Recently, the critical polynomial P_{B}(p,L) was introduced for planar-lattice percolation models, where p is the occupation probability and L is the linear system size. The solution of P_{B}=0 can reproduce all known exact thresholds and leads to unprecedented estimates for thresholds of unsolved planar-lattice models. In two dimensions, assuming the universality of P_{B}, we use it to study a nonplanar lattice model, i.e., the equivalent-neighbor lattice bond percolation, and the continuum percolation of identical penetrable disks, by Monte Carlo simulations and finite-size scaling analysis. It is found that, in comparison with other quantities, P_{B} suffers much less from finite-size corrections. As a result, we obtain a series of high-precision thresholds p_{c}(z) as a function of coordination number z for equivalent-neighbor percolation with z up to O(10^{5}) and clearly confirm the asymptotic behavior zp_{c}-1∼1/sqrt[z] for z→∞. For the continuum percolation model, we surprisingly observe that the finite-size correction in P_{B} is unobservable within uncertainty O(10^{-5}) as long as L≥3. The estimated threshold number density of disks is ρ_{c}=1.43632505(10), slightly below the most recent result ρ_{c}=1.43632545(8) of Mertens and Moore obtained by other means. Our work suggests that the critical polynomial method can be a powerful tool for studying nonplanar and continuum systems in statistical mechanics.
Collapse
Affiliation(s)
- Wenhui Xu
- School of Physics and Materials Science, Anhui University, Hefei, Anhui 230601, China.,Hefei National Laboratory for Physical Sciences at the Microscale and Department of Modern Physics, University of Science and Technology of China, Hefei, Anhui 230026, China
| | - Junfeng Wang
- School of Electronic Science and Applied Physics, Hefei University of Technology, Hefei, Anhui 230009, China
| | - Hao Hu
- School of Physics and Materials Science, Anhui University, Hefei, Anhui 230601, China
| | - Youjin Deng
- Hefei National Laboratory for Physical Sciences at the Microscale and Department of Modern Physics, University of Science and Technology of China, Hefei, Anhui 230026, China.,MinJiang Collaborative Center for Theoretical Physics, College of Physics and Electronic Information Engineering, Minjiang University, Fuzhou 350108, China
| |
Collapse
|
8
|
Xun Z, Hao D, Ziff RM. Site percolation on square and simple cubic lattices with extended neighborhoods and their continuum limit. Phys Rev E 2021; 103:022126. [PMID: 33735955 DOI: 10.1103/physreve.103.022126] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/20/2020] [Accepted: 01/22/2021] [Indexed: 06/12/2023]
Abstract
By means of extensive Monte Carlo simulation, we study extended-range site percolation on square and simple cubic lattices with various combinations of nearest neighbors up to the eighth nearest neighbors for the square lattice and the ninth nearest neighbors for the simple cubic lattice. We find precise thresholds for 23 systems using a single-cluster growth algorithm. Site percolation on lattices with compact neighborhoods of connected sites can be mapped to problems of lattice percolation of extended objects of a given shape, such as disks and spheres, and the thresholds can be related to the continuum thresholds η_{c} for objects of those shapes. This mapping implies zp_{c}∼4η_{c}=4.51235 in two dimensions and zp_{c}∼8η_{c}=2.7351 in three dimensions for large z for circular and spherical neighborhoods, respectively, where z is the coordination number. Fitting our data for compact neighborhoods to the form p_{c}=c/(z+b) we find good agreement with this prediction, c=2^{d}η_{c}, with the constant b representing a finite-z correction term. We also examined results from other studies using this fitting formula. A good fit of the large but finite-z behavior can also be made using the formula p_{c}=1-exp(-2^{d}η_{c}/z), a generalization of a formula of Koza, Kondrat, and Suszcayński [J. Stat. Mech.: Theor. Exp. (2014) P110051742-546810.1088/1742-5468/2014/11/P11005]. We also study power-law fits which are applicable for the range of values of z considered here.
Collapse
Affiliation(s)
- Zhipeng Xun
- School of Material Sciences and Physics, China University of Mining and Technology, Xuzhou 221116, China
| | - Dapeng Hao
- School of Material Sciences and Physics, China University of Mining and Technology, Xuzhou 221116, China
| | - Robert M Ziff
- Center for the Study of Complex Systems and Department of Chemical Engineering, University of Michigan, Ann Arbor, Michigan 48109-2800, USA
| |
Collapse
|