1
|
Chen Y, Yuan Z, Gao L, Peng J. Optimizing search processes with stochastic resetting on the pseudofractal scale-free web. Phys Rev E 2023; 108:064109. [PMID: 38243504 DOI: 10.1103/physreve.108.064109] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/04/2023] [Accepted: 11/15/2023] [Indexed: 01/21/2024]
Abstract
The pseudofractal scale-free web (PSFW) is a well-known model for a scale-free network with small-world characteristics. Understanding the dynamic properties of this network can provide valuable insights into dynamic processes occurring in general scale-free and small-world networks. In this study we investigate search processes using discrete-time random walks on the PSFW to reveal the impact of the resetting position on optimizing search efficiency, as measured by the mean first-passage time (MFPT). At each step the walker has two options: with a probability of 1-γ, it moves to one of the neighboring sites, and with a probability of γ, it resets to the predefined resetting position. We explore various choices for the resetting position, present rigorous results for the MFPT to a given node of the network, determine the optimal resetting probability γ^{*} where the MFPT reaches its minimum, and evaluate the ratio of the minimum for MFPT to the MFPT without resetting for each case. Results show that, in large PSFWs, both the degree of the resetting position and the distance between the target and the resetting position significantly affect the search efficiency. A higher degree of the resetting position leads to a slower convergence of the walker to the target, while a greater distance between the target and the resetting position also results in a slower convergence. Additionally, we observe that resetting to a vertex randomly selected from the stationary distribution can significantly expedite the process of the walker reaching the target. The findings presented in this study shed light on optimizing stochastic search processes on large networks, offering valuable insights into improving search efficiency in real-world applications, where the target node's location is unknown.
Collapse
Affiliation(s)
- Yongjin Chen
- School of Mathematics and Information Science, Guangzhou University, Guangzhou 510006, China; Guangdong Provincial Key Laboratory of Information Security Technology, Guangzhou University, Guangzhou 510006, China; and Guangzhou Center for Applied Mathematics, Guangzhou University, Guangzhou 510006, China
| | - Zhenhua Yuan
- School of Mathematics and Information Science, Guangzhou University, Guangzhou 510006, China; Guangdong Provincial Key Laboratory of Information Security Technology, Guangzhou University, Guangzhou 510006, China; and Guangzhou Center for Applied Mathematics, Guangzhou University, Guangzhou 510006, China
| | - Long Gao
- School of Mathematics and Information Science, Guangzhou University, Guangzhou 510006, China; Guangdong Provincial Key Laboratory of Information Security Technology, Guangzhou University, Guangzhou 510006, China; and Guangzhou Center for Applied Mathematics, Guangzhou University, Guangzhou 510006, China
| | - Junhao Peng
- School of Mathematics and Information Science, Guangzhou University, Guangzhou 510006, China; Guangdong Provincial Key Laboratory of Information Security Technology, Guangzhou University, Guangzhou 510006, China; and Guangzhou Center for Applied Mathematics, Guangzhou University, Guangzhou 510006, China
| |
Collapse
|
2
|
A general model of hierarchical fractal scale-free networks. PLoS One 2022; 17:e0264589. [PMID: 35312679 PMCID: PMC8936503 DOI: 10.1371/journal.pone.0264589] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/06/2021] [Accepted: 02/11/2022] [Indexed: 11/19/2022] Open
Abstract
We propose a general model of unweighted and undirected networks having the scale-free property and fractal nature. Unlike the existing models of fractal scale-free networks (FSFNs), the present model can systematically and widely change the network structure. In this model, an FSFN is iteratively formed by replacing each edge in the previous generation network with a small graph called a generator. The choice of generators enables us to control the scale-free property, fractality, and other structural properties of hierarchical FSFNs. We calculate theoretically various characteristic quantities of networks, such as the exponent of the power-law degree distribution, fractal dimension, average clustering coefficient, global clustering coefficient, and joint probability describing the nearest-neighbor degree correlation. As an example of analyses of phenomena occurring on FSFNs, we also present the critical point and critical exponents of the bond-percolation transition on infinite FSFNs, which is related to the robustness of networks against edge removal. By comparing the percolation critical points of FSFNs whose structural properties are the same as each other except for the clustering nature, we clarify the effect of the clustering on the robustness of FSFNs. As demonstrated by this example, the present model makes it possible to elucidate how a specific structural property influences a phenomenon occurring on FSFNs by varying systematically the structures of FSFNs. Finally, we extend our model for deterministic FSFNs to a model of non-deterministic ones by introducing asymmetric generators and reexamine all characteristic quantities and the percolation problem for such non-deterministic FSFNs.
Collapse
|
3
|
Diggans CT, Bollt EM, Ben-Avraham D. Spanning trees of recursive scale-free graphs. Phys Rev E 2022; 105:024312. [PMID: 35291180 DOI: 10.1103/physreve.105.024312] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/14/2021] [Accepted: 02/09/2022] [Indexed: 06/14/2023]
Abstract
We present a link-by-link rule-based method for constructing all members of the ensemble of spanning trees for any recursively generated, finitely articulated graph, such as the Dorogovtsev-Goltsev-Mendes (DGM) net. The recursions allow for many large-scale properties of the ensemble of spanning trees to be analytically solved exactly. We show how a judicious application of the prescribed growth rules selects for certain subsets of the spanning trees with particular desired properties (small world, extended diameter, degree distribution, etc.), and thus approximates and/or provides solutions to several optimization problems on undirected and unweighted networks. The analysis of spanning trees enhances the usefulness of recursive graphs as sophisticated models for everyday life complex networks.
Collapse
Affiliation(s)
- C Tyler Diggans
- Clarkson Center for Complex Systems Science, Clarkson University, Potsdam, New York 13699, USA
- Department of Physics, Clarkson University, Potsdam, New York 13699, USA
- Air Force Research Laboratory: Information Directorate, Rome, New York 13441, USA
| | - Erik M Bollt
- Clarkson Center for Complex Systems Science, Clarkson University, Potsdam, New York 13699, USA
- Department of Electrical and Computer Engineering, Clarkson University, Potsdam, New York 13699, USA
| | - Daniel Ben-Avraham
- Clarkson Center for Complex Systems Science, Clarkson University, Potsdam, New York 13699, USA
- Department of Physics, Clarkson University, Potsdam, New York 13699, USA
| |
Collapse
|
4
|
Meng X, Gao J, Havlin S. Concurrence Percolation in Quantum Networks. PHYSICAL REVIEW LETTERS 2021; 126:170501. [PMID: 33988406 DOI: 10.1103/physrevlett.126.170501] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 07/13/2020] [Accepted: 03/24/2021] [Indexed: 06/12/2023]
Abstract
Establishing long-distance quantum entanglement, i.e., entanglement transmission, in quantum networks (QN) is a key and timely challenge for developing efficient quantum communication. Traditional comprehension based on classical percolation assumes a necessary condition for successful entanglement transmission between any two infinitely distant nodes: they must be connected by at least a path of perfectly entangled states (singlets). Here, we relax this condition by explicitly showing that one can focus not on optimally converting singlets but on establishing concurrence-a key measure of bipartite entanglement. We thereby introduce a new statistical theory, concurrence percolation theory (ConPT), remotely analogous to classical percolation but fundamentally different, built by generalizing bond percolation in terms of "sponge-crossing" paths instead of clusters. Inspired by resistance network analysis, we determine the path connectivity by series and parallel rules and approximate higher-order rules via star-mesh transforms. Interestingly, we find that the entanglement transmission threshold predicted by ConPT is lower than the known classical-percolation-based results and is readily achievable on any series-parallel networks such as the Bethe lattice. ConPT promotes our understanding of how well quantum communication can be further systematically improved versus classical statistical predictions under the limitation of QN locality-a "quantum advantage" that is more general and efficient than expected. ConPT also shows a percolationlike universal critical behavior derived by finite-size analysis on the Bethe lattice and regular two-dimensional lattices, offering new perspectives for a theory of criticality in entanglement statistics.
Collapse
Affiliation(s)
- Xiangyi Meng
- Center for Polymer Studies and Department of Physics, Boston University, Boston, Massachusetts 02215, USA
- Center for Complex Network Research and Department of Physics, Northeastern University, Boston, Massachusetts 02115, USA
| | - Jianxi Gao
- Department of Computer Science, Rensselaer Polytechnic Institute, Troy, New York 12180, USA
| | - Shlomo Havlin
- Center for Polymer Studies and Department of Physics, Boston University, Boston, Massachusetts 02215, USA
- Department of Physics, Bar-Ilan University, 52900 Ramat-Gan, Israel
| |
Collapse
|
5
|
Diggans CT, Bollt EM, Ben-Avraham D. Stochastic and mixed flower graphs. Phys Rev E 2020; 101:052315. [PMID: 32575335 DOI: 10.1103/physreve.101.052315] [Citation(s) in RCA: 6] [Impact Index Per Article: 1.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/14/2020] [Accepted: 03/31/2020] [Indexed: 11/07/2022]
Abstract
Stochasticity is introduced to a well studied class of recursively grown graphs: (u,v)-flower nets, which have power-law degree distributions as well as small-world properties (when u=1). The stochastic variant interpolates between different (deterministic) flower graphs thus adding flexibility to the model. The random multiplicative growth process involved, however, leads to a spread ensemble of networks with finite variance for the number of links, nodes, and loops. Nevertheless, the degree exponent and loopiness exponent attain unique values in the thermodynamic limit of infinitely large graphs. We also study a class of mixed flower networks, closely related to the stochastic flowers, but which are grown recursively in a deterministic way. The deterministic growth of mixed flower-nets eliminates ensemble spreads, and their recursive growth allows for exact analysis of their (uniquely defined) mixed properties.
Collapse
Affiliation(s)
- C Tyler Diggans
- Clarkson Center for Complex Systems Science (C3S2), Clarkson University, Potsdam, New York 13699, USA.,Department of Physics, Clarkson University, Potsdam, New York 13699, USA.,Air Force Research Laboratory: Information Directorate, Rome, New York 13441, USA
| | - Erik M Bollt
- Clarkson Center for Complex Systems Science (C3S2), Clarkson University, Potsdam, New York 13699, USA.,Department of Electrical and Computer Engineering, Clarkson University, Potsdam, New York 13699, USA
| | - Daniel Ben-Avraham
- Clarkson Center for Complex Systems Science (C3S2), Clarkson University, Potsdam, New York 13699, USA.,Department of Physics, Clarkson University, Potsdam, New York 13699, USA
| |
Collapse
|
6
|
Zhang Z, Lin Y, Guo X. Eigenvalues for the transition matrix of a small-world scale-free network: Explicit expressions and applications. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2015; 91:062808. [PMID: 26172755 DOI: 10.1103/physreve.91.062808] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 12/30/2014] [Indexed: 06/04/2023]
Abstract
The eigenvalues of the transition matrix for random walks on a network play a significant role in the structural and dynamical aspects of the network. Nevertheless, it is still not well understood how the eigenvalues behave in small-world and scale-free networks, which describe a large variety of real systems. In this paper, we study the eigenvalues for the transition matrix of a network that is simultaneously scale-free, small-world, and clustered. We derive explicit simple expressions for all eigenvalues and their multiplicities, with the spectral density exhibiting a power-law form. We then apply the obtained eigenvalues to determine the mixing time and random target access time for random walks, both of which exhibit unusual behaviors compared with those for other networks, signaling discernible effects of topologies on spectral features. Finally, we use the eigenvalues to count spanning trees in the network.
Collapse
Affiliation(s)
- Zhongzhi Zhang
- School of Computer Science, Fudan University, Shanghai 200433, China and Shanghai Key Laboratory of Intelligent Information Processing, Fudan University, Shanghai 200433, China
| | - Yuan Lin
- School of Computer Science, Fudan University, Shanghai 200433, China and Shanghai Key Laboratory of Intelligent Information Processing, Fudan University, Shanghai 200433, China
| | - Xiaoye Guo
- School of Computer Science, Fudan University, Shanghai 200433, China and Shanghai Key Laboratory of Intelligent Information Processing, Fudan University, Shanghai 200433, China
| |
Collapse
|
7
|
Controllability of deterministic networks with the identical degree sequence. PLoS One 2015; 10:e0127545. [PMID: 26020920 PMCID: PMC4447402 DOI: 10.1371/journal.pone.0127545] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/10/2015] [Accepted: 04/16/2015] [Indexed: 12/02/2022] Open
Abstract
Controlling complex network is an essential problem in network science and engineering. Recent advances indicate that the controllability of complex network is dependent on the network's topology. Liu and Barabási, et.al speculated that the degree distribution was one of the most important factors affecting controllability for arbitrary complex directed network with random link weights. In this paper, we analysed the effect of degree distribution to the controllability for the deterministic networks with unweighted and undirected. We introduce a class of deterministic networks with identical degree sequence, called (x,y)-flower. We analysed controllability of the two deterministic networks ((1, 3)-flower and (2, 2)-flower) by exact controllability theory in detail and give accurate results of the minimum number of driver nodes for the two networks. In simulation, we compare the controllability of (x,y)-flower networks. Our results show that the family of (x,y)-flower networks have the same degree sequence, but their controllability is totally different. So the degree distribution itself is not sufficient to characterize the controllability of deterministic networks with unweighted and undirected.
Collapse
|
8
|
Hwang S, Lee DS, Kahng B. Fast algorithm for relaxation processes in big-data systems. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 90:043303. [PMID: 25375619 DOI: 10.1103/physreve.90.043303] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/19/2014] [Indexed: 06/04/2023]
Abstract
Relaxation processes driven by a Laplacian matrix can be found in many real-world big-data systems, for example, in search engines on the World Wide Web and the dynamic load-balancing protocols in mesh networks. To numerically implement such processes, a fast-running algorithm for the calculation of the pseudoinverse of the Laplacian matrix is essential. Here we propose an algorithm which computes quickly and efficiently the pseudoinverse of Markov chain generator matrices satisfying the detailed-balance condition, a general class of matrices including the Laplacian. The algorithm utilizes the renormalization of the Gaussian integral. In addition to its applicability to a wide range of problems, the algorithm outperforms other algorithms in its ability to compute within a manageable computing time arbitrary elements of the pseudoinverse of a matrix of size millions by millions. Therefore our algorithm can be used very widely in analyzing the relaxation processes occurring on large-scale networked systems.
Collapse
Affiliation(s)
- S Hwang
- Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea
| | - D-S Lee
- Department of Physics and Department of Natural Medical Sciences, Inha University, Incheon 402-751, Korea
| | - B Kahng
- Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea
| |
Collapse
|
9
|
Lin Y, Zhang Z. Controlling the efficiency of trapping in a scale-free small-world network. Sci Rep 2014; 4:6274. [PMID: 25199481 PMCID: PMC4158604 DOI: 10.1038/srep06274] [Citation(s) in RCA: 15] [Impact Index Per Article: 1.5] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/06/2014] [Accepted: 08/07/2014] [Indexed: 12/02/2022] Open
Abstract
Designing appropriate techniques to effectively control the trapping process in complex systems towards desirable efficiency is of paramount importance in the study of trapping problem. In this paper, we present three different methods guiding trapping process in a scale-free small-world network with a deep trap positioned at an initial node. All the proposed approaches dominate the trapping process by varying the transition probability of random walks. In the first two techniques, the transition probability is modified by an introduced weight parameter and a stochastic parameter, respectively. And the third scheme is a combination of the first two approaches, controlled by both parameters synchronously. For all the three control strategies, we derive both analytically and numerically the average trapping time (ATT) as the measure of the trapping efficiency, with the obtained explicit expressions being in good agreement with their corresponding exact numerical solutions. Our results indicate that the weight parameter changes simultaneously the dominating scaling of ATT and its prefactor. Different from the weight parameter, the stochastic parameter only modifies the prefactor, keeping the leading scaling unchanged. Finally, compared with the first two manners, the third strategy is a fine control, possessing the advantages of the first two ones. This work deepens the understanding of controlling trapping process in complex systems.
Collapse
Affiliation(s)
- Yuan Lin
- School of Computer Science, Fudan University, Shanghai 200433, China
- Shanghai Key Lab of Intelligent Information Processing, Fudan University, Shanghai 200433, China
| | - Zhongzhi Zhang
- School of Computer Science, Fudan University, Shanghai 200433, China
- Shanghai Key Lab of Intelligent Information Processing, Fudan University, Shanghai 200433, China
| |
Collapse
|
10
|
Zhang Z, Guo X, Lin Y. Full eigenvalues of the Markov matrix for scale-free polymer networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 90:022816. [PMID: 25215790 DOI: 10.1103/physreve.90.022816] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/06/2014] [Indexed: 06/03/2023]
Abstract
Much important information about the structural and dynamical properties of complex systems can be extracted from the eigenvalues and eigenvectors of a Markov matrix associated with random walks performed on these systems, and spectral methods have become an indispensable tool in the complex system analysis. In this paper, we study the Markov matrix of a class of scale-free polymer networks. We present an exact analytical expression for all the eigenvalues and determine explicitly their multiplicities. We then use the obtained eigenvalues to derive an explicit formula for the random target access time for random walks on the studied networks. Furthermore, based on the link between the eigenvalues of the Markov matrix and the number of spanning trees, we confirm the validity of the obtained eigenvalues and their corresponding degeneracies.
Collapse
Affiliation(s)
- Zhongzhi Zhang
- School of Computer Science and Shanghai Key Lab of Intelligent Information Processing, Fudan University, Shanghai 200433, China
| | - Xiaoye Guo
- School of Computer Science and Shanghai Key Lab of Intelligent Information Processing, Fudan University, Shanghai 200433, China
| | - Yuan Lin
- School of Computer Science and Shanghai Key Lab of Intelligent Information Processing, Fudan University, Shanghai 200433, China
| |
Collapse
|
11
|
Singh V, Boettcher S. Scaling of clusters near discontinuous percolation transitions in hyperbolic networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 90:012117. [PMID: 25122261 DOI: 10.1103/physreve.90.012117] [Citation(s) in RCA: 5] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/25/2014] [Indexed: 06/03/2023]
Abstract
We investigate the onset of the discontinuous percolation transition in small-world hyperbolic networks by studying the systems-size scaling of the typical largest cluster approaching the transition, p ↗ p(c). To this end, we determine the average size of the largest cluster 〈s(max)〉 ∼ N(Ψ(p)) in the thermodynamic limit using real-space renormalization of cluster-generating functions for bond and site percolation in several models of hyperbolic networks that provide exact results. We determine that all our models conform to the recently predicted behavior regarding the growth of the largest cluster, which found diverging, albeit subextensive, clusters spanning the system with finite probability well below p(c) and at most quadratic corrections to unity in Ψ(p) for p ↗ p(c). Our study suggests a large universality in the cluster formation on small-world hyperbolic networks and the potential for an alternative mechanism in the cluster formation dynamics at the onset of discontinuous percolation transitions.
Collapse
Affiliation(s)
- Vijay Singh
- Department of Physics, Emory University, Atlanta, Georgia 30322, USA
| | - Stefan Boettcher
- Department of Physics, Emory University, Atlanta, Georgia 30322, USA
| |
Collapse
|
12
|
Lee HK, Shim PS, Noh JD. Degree-ordered percolation on a hierarchical scale-free network. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 89:062816. [PMID: 25019842 DOI: 10.1103/physreve.89.062816] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 03/09/2014] [Indexed: 06/03/2023]
Abstract
We investigate the critical phenomena of the degree-ordered percolation (DOP) model on the hierarchical (u,v) flower network with u ≤ v. Highest degree nodes are linked directly without intermediate nodes for u=1, while this is not the case for u ≠ 1. Using the renormalization-group-like procedure, we derive the recursion relations for the percolating probability and the percolation order parameter, from which the percolation threshold and the critical exponents are obtained. When u ≠ 1, the DOP critical behavior turns out to be identical to that of the bond percolation with a shifted nonzero percolation threshold. When u=1, the DOP and the bond percolation have the same vanishing percolation threshold but the critical behaviors are different. Implication to an epidemic spreading phenomenon is discussed.
Collapse
Affiliation(s)
- Hyun Keun Lee
- Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea and School of Physics, Korea Institute for Advanced Study, Seoul 130-722, Korea
| | - Pyoung-Seop Shim
- Department of Physics, University of Seoul, Seoul 130-743, Korea
| | - Jae Dong Noh
- School of Physics, Korea Institute for Advanced Study, Seoul 130-722, Korea and Department of Physics, University of Seoul, Seoul 130-743, Korea
| |
Collapse
|
13
|
Nogawa T, Hasegawa T. Transition-type change between an inverted Berezinskii-Kosterlitz-Thouless transition and an abrupt transition in bond percolation on a random hierarchical small-world network. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2014; 89:042803. [PMID: 24827289 DOI: 10.1103/physreve.89.042803] [Citation(s) in RCA: 6] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 12/17/2013] [Indexed: 06/03/2023]
Abstract
We study the bond percolation on a one-parameter family of a hierarchical small-world network and find the metatransition between an inverted Berezinskii-Kosterlitz-Thouless (iBKT) transition and an abrupt transition driven by changing the network topology. It is found that the order parameter is continuous and the fractal exponent is discontinuous in the iBKT transition, and oppositely, the former is discontinuous and the latter is continuous in the abrupt transition. The gaps of the order parameter and the fractal exponent in each transition vanish as they approach the metatransition point. This point corresponds to a marginal power-law transition. In the renormalization group formalism, this metatransition corresponds to the transition between transcritical and saddle-node bifurcations of the fixed point via a pitchfork bifurcation.
Collapse
Affiliation(s)
- Tomoaki Nogawa
- Faculty of Medicine, Toho University, 5-21-16, Omori-Nishi, Ota-ku, Tokyo 143-8540, Japan
| | - Takehisa Hasegawa
- Graduate School of Information Science, Tohoku University, 6-3-09, Aramaki-Aza-Aoba, Sendai, Miyagi 980-8579, Japan
| |
Collapse
|
14
|
Hasegawa T, Nemoto K. Hierarchical scale-free network is fragile against random failure. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2013; 88:062807. [PMID: 24483511 DOI: 10.1103/physreve.88.062807] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/19/2013] [Indexed: 06/03/2023]
Abstract
We investigate site percolation in a hierarchical scale-free network known as the Dorogovtsev-Goltsev-Mendes network. We use the generating function method to show that the percolation threshold is 1, i.e., the system is not in the percolating phase when the occupation probability is less than 1. The present result is contrasted to bond percolation in the same network of which the percolation threshold is zero. We also show that the percolation threshold of intentional attacks is 1. Our results suggest that this hierarchical scale-free network is very fragile against both random failure and intentional attacks. Such a structural defect is common in many hierarchical network models.
Collapse
Affiliation(s)
- Takehisa Hasegawa
- Graduate School of Information Science, Tohoku University, 6-3-09, Aramaki-Aza-Aoba, Sendai, Miyagi 980-8579, Japan
| | - Koji Nemoto
- Department of Physics, Hokkaido University, Kita 10 Nisi 8, Kita-ku, Sapporo, Hokkaido 060-0810, Japan
| |
Collapse
|
15
|
Hwang S, Lee DS, Kahng B. Origin of the hub spectral dimension in scale-free networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2013; 87:022816. [PMID: 23496577 DOI: 10.1103/physreve.87.022816] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 11/13/2012] [Indexed: 06/01/2023]
Abstract
The return-to-origin probability and the first-passage-time distribution are essential quantities for understanding transport phenomena in diverse systems. The behaviors of these quantities typically depend on the spectral dimension d(s). However, it was recently revealed that in scale-free networks these quantities show a crossover between two power-law regimes characterized by d(s) and the so-called hub spectral dimension d(s)((hub)) due to the heterogeneity of connectivities of each node. To understand the origin of d(s)((hub)) from a theoretical perspective, we study a random walk problem on hierarchical scale-free networks by using the renormalization group (RG) approach. Under the RG transformation, not only the system size but also the degree of each node changes due to the scale-free nature of the degree distribution. We show that the anomalous behavior of random walks involving the hub spectral dimension d(s)((hub)) is induced by the conservation of the power-law degree distribution under the RG transformation.
Collapse
Affiliation(s)
- S Hwang
- Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea
| | | | | |
Collapse
|
16
|
Zhang Z, Sheng Y, Hu Z, Chen G. Optimal and suboptimal networks for efficient navigation measured by mean-first passage time of random walks. CHAOS (WOODBURY, N.Y.) 2012; 22:043129. [PMID: 23278064 DOI: 10.1063/1.4768665] [Citation(s) in RCA: 9] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 06/01/2023]
Abstract
For a random walk on a network, the mean first-passage time from a node i to another node j chosen stochastically, according to the equilibrium distribution of Markov chain representing the random walk is called the Kemeny constant, which is closely related to the navigability on the network. Thus, the configuration of a network that provides optimal or suboptimal navigation efficiency is a question of interest. It has been proved that complete graphs have the exact minimum Kemeny constant over all graphs. In this paper, by using another method we first prove that complete graphs are the optimal networks with a minimum Kemeny constant, which grows linearly with the network size. Then, we study the Kemeny constant of a class of sparse networks that exhibit remarkable scale-free and fractal features as observed in many real-life networks, which cannot be described by complete graphs. To this end, we determine the closed-form solutions to all eigenvalues and their degeneracies of the networks. Employing these eigenvalues, we derive the exact solution to the Kemeny constant, which also behaves linearly with the network size for some particular cases of networks. We further use the eigenvalue spectra to determine the number of spanning trees in the networks under consideration, which is in complete agreement with previously reported results. Our work demonstrates that scale-free and fractal properties are favorable for efficient navigation, which could be considered when designing networks with high navigation efficiency.
Collapse
Affiliation(s)
- Zhongzhi Zhang
- School of Computer Science, Fudan University, Shanghai 200433, China.
| | | | | | | |
Collapse
|
17
|
DeDeo S, Krakauer DC. Dynamics and processing in finite self-similar networks. J R Soc Interface 2012; 9:2131-44. [PMID: 22378750 PMCID: PMC3405736 DOI: 10.1098/rsif.2011.0840] [Citation(s) in RCA: 12] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Key Words] [MESH Headings] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/01/2011] [Accepted: 02/07/2012] [Indexed: 11/12/2022] Open
Abstract
A common feature of biological networks is the geometrical property of self-similarity. Molecular regulatory networks through to circulatory systems, nervous systems, social systems and ecological trophic networks show self-similar connectivity at multiple scales. We analyse the relationship between topology and signalling in contrasting classes of such topologies. We find that networks differ in their ability to contain or propagate signals between arbitrary nodes in a network depending on whether they possess branching or loop-like features. Networks also differ in how they respond to noise, such that one allows for greater integration at high noise, and this performance is reversed at low noise. Surprisingly, small-world topologies, with diameters logarithmic in system size, have slower dynamical time scales, and may be less integrated (more modular) than networks with longer path lengths. All of these phenomena are essentially mesoscopic, vanishing in the infinite limit but producing strong effects at sizes and time scales relevant to biology.
Collapse
Affiliation(s)
- Simon DeDeo
- Santa Fe Institute, Santa Fe, NM 87501, USA.
| | | |
Collapse
|
18
|
Hwang S, Lee DS, Kahng B. Effective trapping of random walkers in complex networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2012; 85:046110. [PMID: 22680541 DOI: 10.1103/physreve.85.046110] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 07/18/2011] [Revised: 02/16/2012] [Indexed: 06/01/2023]
Abstract
Exploring the World Wide Web has become one of the key issues in information science, specifically in view of its application to the PageRank-like algorithms used in search engines. The random walk approach has been employed to study such a problem. The probability of return to the origin (RTO) of random walks is inversely related to how information can be accessed during random surfing. We find analytically that the RTO probability for a given starting node shows a crossover from a slow to a fast decay behavior with time and the crossover time increases with the degree of the starting node. We remark that the RTO probability becomes almost constant in the early-time regime as the degree exponent approaches two. This result indicates that a random surfer can be effectively trapped at the hub and supports the necessity of the random jump strategy empirically used in the Google's search engine.
Collapse
Affiliation(s)
- S Hwang
- Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea
| | | | | |
Collapse
|
19
|
Meyer B, Agliari E, Bénichou O, Voituriez R. Exact calculations of first-passage quantities on recursive networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2012; 85:026113. [PMID: 22463285 DOI: 10.1103/physreve.85.026113] [Citation(s) in RCA: 34] [Impact Index Per Article: 2.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 12/01/2011] [Indexed: 05/31/2023]
Abstract
We present general methods to exactly calculate mean first-passage quantities on self-similar networks defined recursively. In particular, we calculate the mean first-passage time and the splitting probabilities associated to a source and one or several targets; averaged quantities over a given set of sources (e.g., same-connectivity nodes) are also derived. The exact estimate of such quantities highlights the dependency of first-passage processes with respect to the source-target distance, which has recently revealed to be a key parameter in characterizing transport in complex media. We explicitly perform calculations for different classes of recursive networks [finitely ramified fractals, scale-free (trans)fractals, nonfractals, mixtures between fractals and nonfractals, nondecimable hierarchical graphs] of arbitrary size. Our approach unifies and significantly extends the available results in the field.
Collapse
Affiliation(s)
- B Meyer
- Laboratoire de Physique Théorique de la Matière Condensée, CNRS UMR 7600, Case Courrier 121, Université Paris 6, 4 Place Jussieu, FR-75255 Paris Cedex, France
| | | | | | | |
Collapse
|
20
|
Hasegawa T, Sato M, Nemoto K. Phase transition without global ordering in a hierarchical scale-free network. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2012; 85:017101. [PMID: 22400706 DOI: 10.1103/physreve.85.017101] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 09/18/2011] [Revised: 10/20/2011] [Indexed: 05/31/2023]
Abstract
We study the site-bond percolation on a hierarchical scale-free network, namely, the decorated (2,2)-flower, by using the renormalization group technique. The phase diagram essentially depends on the fraction of occupied sites. Surprisingly, when each site is unoccupied even with a small probability, the system permits neither the percolating phase nor the nonpercolating phase, but rather only critical phases. Although the order parameter always remains zero, a transition still exists between the critical phases that is characterized by the value of the fractal exponent, which measures the degree of criticality; the system changes from one critical state to another with the jump of the fractal exponent at the transition point. The phase boundary depends on the fraction of occupied sites. When the fraction of unoccupied sites exceeds a certain value, the transition line between the critical phases disappears, and a unique critical phase remains.
Collapse
Affiliation(s)
- Takehisa Hasegawa
- Graduate School of Information Sciences, Tohoku University, 6-3-09, Aramaki-Aza-Aoba, Sendai 980-8579, Japan.
| | | | | |
Collapse
|
21
|
Hwang S, Yun CK, Lee DS, Kahng B, Kim D. Spectral dimensions of hierarchical scale-free networks with weighted shortcuts. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2010; 82:056110. [PMID: 21230548 DOI: 10.1103/physreve.82.056110] [Citation(s) in RCA: 8] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/17/2010] [Revised: 09/07/2010] [Indexed: 05/30/2023]
Abstract
Spectral dimensions have been widely used to understand transport properties on regular and fractal lattices. However, they have received little attention with regard to complex networks such as scale-free and small-world networks. Here, we study the spectral dimension and the return-to-origin probability of random walks on hierarchical scale-free networks, which can be either fractal or nonfractal depending on the weight of the shortcuts. Applying the renormalization-group (RG) approach to a Gaussian model, we obtain the exact spectral dimension. While the spectral dimension varies between 1 and 2 for the fractal case, it remains at 2, independent of the variation in the network structure, for the nonfractal case. The crossover behavior between the two cases is studied by carrying out the RG flow analysis. The analytical results are confirmed by simulation results and their implications for the architecture of complex systems are discussed.
Collapse
Affiliation(s)
- S Hwang
- Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea
| | | | | | | | | |
Collapse
|
22
|
Hasegawa T, Sato M, Nemoto K. Generating-function approach for bond percolation in hierarchical networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2010; 82:046101. [PMID: 21230339 DOI: 10.1103/physreve.82.046101] [Citation(s) in RCA: 5] [Impact Index Per Article: 0.4] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/26/2010] [Indexed: 05/30/2023]
Abstract
We study bond percolations on hierarchical scale-free networks with the open bond probability of the shortcuts p and that of the ordinary bonds p. The system has a critical phase in which the percolating probability P takes an intermediate value 0 < P < 1. Using generating function approach, we calculate the fractal exponent ψ of the root clusters to show that ψ varies continuously with p in the critical phase. We confirm numerically that the distribution n(s) of cluster size s in the critical phase obeys a power law n(s) ∝ s(-τ), where τ satisfies the scaling relation τ=1+ψ(-1). In addition the critical exponent β(p) of the order parameter varies as p, from β ≃ 0.164694 at p=0 to infinity at p=p(c)=5/32.
Collapse
Affiliation(s)
- Takehisa Hasegawa
- Graduate School of Information Science and Technology, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo, Japan.
| | | | | |
Collapse
|
23
|
Hasegawa T, Nemoto K. Critical phase of bond percolation on growing networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2010; 81:051105. [PMID: 20866183 DOI: 10.1103/physreve.81.051105] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 11/06/2009] [Indexed: 05/29/2023]
Abstract
The critical phase of bond percolation on the random growing tree is examined. It is shown that the root cluster grows with the system size N as N ψ and the mean number of clusters with size s per node follows a power function n s ∝ s(-τ) in the whole range of open bond probability p . The exponent τ and the fractal exponent ψ are also derived as a function of p and the degree exponent γ and are found to satisfy the scaling relation τ=1+ψ(-1). Numerical results with several network sizes are quite well fitted by a finite-size scaling for a wide range of p and γ, which gives a clear evidence for the existence of a critical phase.
Collapse
Affiliation(s)
- Takehisa Hasegawa
- Graduate School of Information Science and Technology, The University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo, Japan.
| | | |
Collapse
|
24
|
Zhang Z, Xie W, Zhou S, Li M, Guan J. Distinct scalings for mean first-passage time of random walks on scale-free networks with the same degree sequence. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2009; 80:061111. [PMID: 20365122 DOI: 10.1103/physreve.80.061111] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 08/05/2009] [Revised: 09/25/2009] [Indexed: 05/29/2023]
Abstract
In general, the power-law degree distribution has profound influence on various dynamical processes defined on scale-free networks. In this paper, we will show that power-law degree distribution alone does not suffice to characterize the behavior of trapping problems on scale-free networks, which is an integral major theme of interest for random walks in the presence of an immobile perfect absorber. In order to achieve this goal, we study random walks on a family of one-parameter (denoted by q) scale-free networks with identical degree sequence for the full range of parameter q, in which a trap is located at a fixed site. We obtain analytically or numerically the mean first-passage time (MFPT) for the trapping issue. In the limit of large network order (number of nodes), for the whole class of networks, the MFPT increases asymptotically as a power-law function of network order with the exponent obviously different for different parameter q, which suggests that power-law degree distribution itself is not sufficient to characterize the scaling behavior of MFPT for random walks at least trapping problem, performed on scale-free networks.
Collapse
Affiliation(s)
- Zhongzhi Zhang
- School of Computer Science, Fudan University, Shanghai 200433, China.
| | | | | | | | | |
Collapse
|
25
|
|
26
|
Berker AN, Hinczewski M, Netz RR. Critical percolation phase and thermal Berezinskii-Kosterlitz-Thouless transition in a scale-free network with short-range and long-range random bonds. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2009; 80:041118. [PMID: 19905284 DOI: 10.1103/physreve.80.041118] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/22/2009] [Indexed: 05/28/2023]
Abstract
Percolation in a scale-free hierarchical network is solved exactly by renormalization-group theory in terms of the different probabilities of short-range and long-range bonds. A phase of critical percolation, with algebraic [Berezinskii-Kosterlitz-Thouless (BKT)] geometric order, occurs in the phase diagram in addition to the ordinary (compact) percolating phase and the nonpercolating phase. It is found that no connection exists between, on the one hand, the onset of this geometric BKT behavior and, on the other hand, the onsets of the highly clustered small-world character of the network and of the thermal BKT transition of the Ising model on this network. Nevertheless, both geometric and thermal BKT behaviors have inverted characters, occurring where disorder is expected, namely, at low bond probability and high temperature, respectively. This may be a general property of long-range networks.
Collapse
Affiliation(s)
- A Nihat Berker
- Faculty of Engineering and Natural Sciences, Sabanci University, Orhanli, Tuzla, 34956 Istanbul, Turkey
| | | | | |
Collapse
|
27
|
Zhang Z, Zhou S, Zou T, Chen L, Guan J. Different thresholds of bond percolation in scale-free networks with identical degree sequence. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2009; 79:031110. [PMID: 19391905 DOI: 10.1103/physreve.79.031110] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 11/05/2008] [Indexed: 05/27/2023]
Abstract
Generally, the threshold of percolation in complex networks depends on the underlying structural characterization. However, what topological property plays a predominant role is still unknown, despite the speculation of some authors that degree distribution is a key ingredient. The purpose of this paper is to show that power-law degree distribution itself is not sufficient to characterize the threshold of bond percolation in scale-free networks. To achieve this goal, we first propose a family of scale-free networks with the same degree sequence and obtain by analytical or numerical means several topological features of the networks. Then, by making use of the renormalization-group technique we determine the threshold of bond percolation in our networks. We find an existence of nonzero thresholds and demonstrate that these thresholds can be quite different, which implies that power-law degree distribution does not suffice to characterize the percolation threshold in scale-free networks.
Collapse
Affiliation(s)
- Zhongzhi Zhang
- School of Computer Science, Fudan University, Shanghai 200433, China.
| | | | | | | | | |
Collapse
|
28
|
Gülpinar G, Berker AN. Quenched-vacancy induced spin-glass order. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2009; 79:021110. [PMID: 19391709 DOI: 10.1103/physreve.79.021110] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 10/31/2008] [Revised: 01/01/2009] [Indexed: 05/27/2023]
Abstract
The ferromagnetic phase of an Ising model in d=3 , with any amount of quenched antiferromagnetic bond randomness, is shown to undergo a transition to a spin-glass phase under sufficient quenched bond dilution. This result, demonstrated here with the numerically exact global renormalization-group solution of a d=3 hierarchical lattice, is expected to hold true generally, for the cubic lattice and for quenched site dilution. Conversely, in the ferromagnetic-spin-glass-antiferromagnetic phase diagram, the spin-glass phase expands under quenched dilution at the expense of the ferromagnetic and antiferromagnetic phases. In the ferromagnetic-spin-glass phase transition induced by quenched dilution, reentrance as a function of temperature is seen, as previously found in the ferromagnetic-spin-glass transition induced by increasing the antiferromagnetic bond concentration.
Collapse
Affiliation(s)
- Gül Gülpinar
- Department of Physics, Dokuz Eylül University, Buca 35160, Izmir, Turkey
| | | |
Collapse
|
29
|
Baek SK, Minnhagen P, Kim BJ. Percolation on hyperbolic lattices. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2009; 79:011124. [PMID: 19257018 DOI: 10.1103/physreve.79.011124] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/12/2008] [Revised: 11/28/2008] [Indexed: 05/27/2023]
Abstract
The percolation transitions on hyperbolic lattices are investigated numerically using finite-size scaling methods. The existence of two distinct percolation thresholds is verified. At the lower threshold, an unbounded cluster appears and reaches from the middle to the boundary. This transition is of the same type and has the same finite-size scaling properties as the corresponding transition for the Cayley tree. At the upper threshold, on the other hand, a single unbounded cluster forms which overwhelms all the others and occupies a finite fraction of the volume as well as of the boundary connections. The finite-size scaling properties for this upper threshold are different from those of the Cayley tree and two of the critical exponents are obtained. The results suggest that the percolation transition for the hyperbolic lattices forms a universality class of its own.
Collapse
Affiliation(s)
- Seung Ki Baek
- Department of Theoretical Physics, Umeå University, 901 87 Umeå, Sweden.
| | | | | |
Collapse
|
30
|
Carmi S, Krapivsky PL, Ben-Avraham D. Partition of networks into basins of attraction. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2008; 78:066111. [PMID: 19256909 DOI: 10.1103/physreve.78.066111] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 08/05/2008] [Indexed: 05/27/2023]
Abstract
We study partition of networks into basins of attraction based on a steepest ascent search for the node of highest degree. Each node is associated with, or "attracted" to its neighbor of maximal degree, as long as the degree is increasing. A node that has no neighbors of higher degree is a peak, attracting all the nodes in its basin. Maximally random scale-free networks exhibit different behavior based on their degree distribution exponent gamma : For small gamma (broad distribution) networks are dominated by a giant basin, whereas for large gamma (narrow distribution) there are numerous basins, with peaks attracting mainly their nearest neighbors. We derive expressions for the first two moments of the number of basins. We also obtain the complete distribution of basin sizes for a class of hierarchical deterministic scale-free networks that resemble random nets. Finally, we generalize the problem to regular networks and lattices where all degrees are equal, and thus the attractiveness of a node must be determined by an assigned weight, rather than the degree. We derive the complete distribution of basins of attraction resulting from randomly assigned weights in one-dimensional chains.
Collapse
Affiliation(s)
- Shai Carmi
- Center for Polymer Studies, Boston University, Boston, Massachusetts 02215, USA
| | | | | |
Collapse
|
31
|
Auto DM, Moreira AA, Herrmann HJ, Andrade JS. Finite-size effects for percolation on Apollonian networks. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2008; 78:066112. [PMID: 19256910 DOI: 10.1103/physreve.78.066112] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 08/04/2008] [Indexed: 05/27/2023]
Abstract
We study the percolation problem on the Apollonian network model. The Apollonian networks display many interesting properties commonly observed in real network systems, such as small-world behavior, scale-free distribution, and a hierarchical structure. By taking advantage of the deterministic hierarchical construction of these networks, we use the real-space renormalization-group technique to write exact iterative equations that relate percolation network properties at different scales. More precisely, our results indicate that the percolation probability and average mass of the percolating cluster approach the thermodynamic limit logarithmically. We suggest that such ultraslow convergence might be a property of hierarchical networks. Since real complex systems are certainly finite and very commonly hierarchical, we believe that taking into account finite-size effects in real-network systems is of fundamental importance.
Collapse
Affiliation(s)
- Daniel M Auto
- Departamento de Física, Universidade Federal do Ceará, Campus do Pici, 60451-970 Fortaleza, Ceará, Brazil
| | | | | | | |
Collapse
|
32
|
Güven C, Berker AN, Hinczewski M, Nishimori H. Reentrant and forward phase diagrams of the anisotropic three-dimensional Ising spin glass. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2008; 77:061110. [PMID: 18643220 DOI: 10.1103/physreve.77.061110] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 02/06/2008] [Indexed: 05/26/2023]
Abstract
The spatially uniaxially anisotropic d=3 Ising spin glass is solved exactly on a hierarchical lattice. Five different ordered phases, namely, ferromagnetic, columnar, layered, antiferromagnetic, and spin-glass phases, are found in the global phase diagram. The spin-glass phase is more extensive when randomness is introduced within the planes than when it is introduced in lines along one direction. Phase diagram cross sections, with no Nishimori symmetry, with Nishimori symmetry lines, or entirely imbedded into Nishimori symmetry, are studied. The boundary between the ferromagnetic and spin-glass phases can be either reentrant or forward, that is either receding from or penetrating into the spin-glass phase, as temperature is lowered. However, this boundary is always reentrant when the multicritical point terminating it is on the Nishimori symmetry line.
Collapse
Affiliation(s)
- Can Güven
- Department of Physics, Koç University, Sariyer, Istanbul, Turkey
| | | | | | | |
Collapse
|
33
|
Kownacki JP. Site percolation on planar Phi(3) random graphs. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2008; 77:021121. [PMID: 18352001 DOI: 10.1103/physreve.77.021121] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 06/29/2007] [Revised: 12/17/2007] [Indexed: 05/26/2023]
Abstract
In this paper, site percolation on random Phi(3) planar graphs is studied by Monte Carlo numerical techniques. The method consists in randomly removing a fraction q = 1-p of vertices from graphs generated by Monte Carlo simulations, where p is the occupation probability. The resulting graphs are made of clusters of occupied sites. By measuring several properties of their distribution, it is shown that percolation occurs for an occupation probability above a percolation threshold p(c) = 0.7360(5) . Moreover, critical exponents are compatible with those analytically known for bond percolation.
Collapse
Affiliation(s)
- J-P Kownacki
- Laboratoire de Physique Théorique et Modélisation, CNRS-Université de Cergy-Pontoise-UMR8089, Cergy-Pontoise Cedex, France.
| |
Collapse
|
34
|
Kaplan CN, Berker AN. Quantum-mechanically induced asymmetry in the phase diagrams of spin-glass systems. PHYSICAL REVIEW LETTERS 2008; 100:027204. [PMID: 18232916 DOI: 10.1103/physrevlett.100.027204] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 09/22/2007] [Revised: 10/27/2007] [Indexed: 05/25/2023]
Abstract
The spin-1/2 quantum Heisenberg spin-glass system is studied in all spatial dimensions d by renormalization-group theory. Strongly asymmetric phase diagrams in temperature and antiferromagnetic bond probability p are obtained in dimensions d>or=3. The asymmetry at high temperatures approaching the pure ferromagnetic and antiferromagnetic systems disappears as d is increased. However, the asymmetry at low but finite temperatures remains in all dimensions, with the antiferromagnetic phase receding from the ferromagnetic phase. A finite-temperature second-order phase boundary directly between the ferromagnetic and antiferromagnetic phases occurs in d>or=6, resulting in a new multicritical point. In d=3, 4, 5, a paramagnetic phase reaching zero temperature intervenes asymmetrically between the ferromagnetic and reentrant antiferromagnetic phases. There is no spin-glass phase in any dimension.
Collapse
Affiliation(s)
- C Nadir Kaplan
- Department of Physics, Koç University, Sariyer 34450, Istanbul, Turkey
| | | |
Collapse
|
35
|
|
36
|
Chremos A, Camp PJ. Neighbor network in a polydisperse hard-disk fluid: degree distribution and assortativity. PHYSICAL REVIEW. E, STATISTICAL, NONLINEAR, AND SOFT MATTER PHYSICS 2007; 76:056108. [PMID: 18233719 DOI: 10.1103/physreve.76.056108] [Citation(s) in RCA: 3] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/05/2007] [Indexed: 05/25/2023]
Abstract
The neighbor network in a two-dimensional polydisperse hard-disk fluid with diameter distribution p(sigma) approximately sigma(-4) is examined using constant-pressure Monte Carlo simulations. Graphs are constructed from vertices (disks) with edges (links) connecting each vertex to k neighboring vertices defined by a radical tessellation. At packing fractions in the range 0.24< or =eta< or =0.36, the decay of the network degree distribution is observed to be consistent with the power law k(-gamma) where the exponent lies in the range 5.6< or =gamma< or =6.0 . Comparisons with the predictions of a maximum-entropy theory suggest that this apparent power-law behavior is not the asymptotic one and that p(k) approximately k(-4) in the limit k-->infinity. This is consistent with the simple idea that for large disks, the number of neighbors is proportional to the disk diameter. A power-law decay of the network degree distribution is one of the characteristics of a scale-free network. The assortativity of the network is measured and is found to be positive, meaning that vertices of equal degree are connected more often than in a random network. Finally, the equation of state is determined and compared with the prediction from a scaled-particle theory. Very good agreement between simulation and theory is demonstrated.
Collapse
Affiliation(s)
- Alexandros Chremos
- School of Chemistry, University of Edinburgh, West Mains Road, Edinburgh EH9 3JJ, United Kingdom
| | | |
Collapse
|