Evolution of scale-free random graphs: Potts model formulation
Nuclear Physics BPublished 7 July 2004Open access
Deok‐Sun Lee, K.-I. Goh, B. Kahng, D. Kim
Citations77
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
We study the bond percolation problem in random graphs of $N$ weighted vertices, where each vertex $i$ has a prescribed weight $P_i$ and an edge can connect vertices $i$ and $j$ with rate $P_iP_j$. The problem is solved by the $q\to 1$ limit of the $q$-state Potts model with inhomogeneous interactions for all pairs of spins. We apply this approach to the static model having $P_i\propto i^{-\mu} (03$ and $2 < \lambda <3$. While for the former, the giant cluster forms abruptly at the percolation transition, for the latter, however, the formation of the giant cluster is gradual and the mean cluster size for finite $N$ shows double peaks.
Keywords
Physics and Astronomy
ScienceEmergence of Scaling in Random Networks
36,366 Citations1999Albert-Ĺaszló Barabási, Réka Albert
A model based on these two ingredients reproduces the observed stationary scale-free distributions, which indicates that the development of large networks is governed by robust self-organizing phenomena that go beyond the particulars of the individual systems.
Reviews of Modern PhysicsStatistical mechanics of complex networks
20,607 Citations2002Réka Albert, Albert-Ĺaszló Barabási
A simple model based on these two principles was able to reproduce the power-law degree distribution of real networks, indicating a heterogeneous topology in which the majority of the nodes have a small degree, but there is a significant fraction of highly connected nodes that play an important role in the connectivity of the network.
SIAM ReviewThe Structure and Function of Complex Networks
18,742 Citations2003Michael Newman
Developments in this field are reviewed, including such concepts as the small-world effect, degree distributions, clustering, network correlations, random graph models, models of network growth and preferential attachment, and dynamical processes taking place on networks.
Physics Today<i>Introduction to Percolation Theory</i>
6,684 Citations1993Dietrich Stauffer, Amnon Aharony +1 more
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsRandom graphs with arbitrary degree distributions and their applications
3,644 Citations2001M. E. J. Newman, Steven H. Strogatz +1 more
It is demonstrated that in some cases random graphs with appropriate distributions of vertex degree predict with surprising accuracy the behavior of the real world, while in others there is a measurable discrepancy between theory and reality, perhaps indicating the presence of additional social structure in the network that is not captured by the random graph.
Advances In PhysicsEvolution of networks
3,140 Citations2002S. N. Dorogovt︠s︡ev, J. F. F. Mendes
The recent rapid progress in the statistical physics of evolving networks is reviewed, and how growing networks self-organize into scale-free structures is discussed, and the role of the mechanism of preferential linking is investigated.
American Journal of PhysicsMathematical Methods for Physicists
2,697 Citations1967George B. Arfken, Albert A. Mullin
Advances In PhysicsAn introduction to percolation theory
2,466 Citations1971V. K. S. Shante, Scott Kirkpatrick
Physical Review LettersNetwork Robustness and Fragility: Percolation on Random Graphs
2,422 Citations2000Duncan S. Callaway, M. E. J. Newman +2 more
This paper studies percolation on graphs with completely general degree distribution, giving exact solutions for a variety of cases, including site percolators, bond percolations, and models in which occupation probabilities depend on vertex degree.
Random Structures and AlgorithmsA critical point for random graphs with a given degree sequence
2,401 Citations1995Michael Molloy, Bruce Reed
It is shown that if Σ i(i - 2)λi > 0, then such graphs almost surely have a giant component, while if λ0, λ1… which sum to 1, then almost surely all components in such graphs are small.
Physical Review LettersResilience of the Internet to Random Breakdowns
2,327 Citations2000Reuven Cohen, Keren Erez +2 more
This work shows analytically and numerically that for alpha0.99.
PhysicaOn the random-cluster model
1,772 Citations1972C.M. Fortuin, Piet Kasteleyn
It is shown that the function which for the random-cluster model plays the role of a partition function, is a generalization of the dichromatic polynomial earlier introduced by Tutte, and related polynomials.
Physical Review LettersBreakdown of the Internet under Intentional Attack
1,423 Citations2001Reuven Cohen, Keren Erez +2 more
It is argued that, near criticality, the average distance between sites in the spanning (largest) cluster scales with its mass, M, as square root of [M], rather than as log (k)M, as expected for random networks away from criticality.
Physical Review LettersUniversal Behavior of Load Distribution in Scale-Free Networks
1,257 Citations2001K.-I. Goh, B. Kahng +1 more
It is conjecture that the load exponent is a universal quantity to characterize scale-free networks and valid for both undirected and directed cases.
Annals of CombinatoricsConnected Components in Random Graphs with Given Expected Degree Sequences
963 Citations2002Fan Chung, Linyuan Lü
Handbook of Graphs and Networks
945 Citations2002Stefan Bornholdt, Heinz Georg Schuster
This book defines the field of complex interacting networks in its infancy and presents the dynamics of networks and their structure as a key concept across disciplines and offers concepts to model network structures and dynamics, focussed on approaches applicable across disciplines.
Combinatorics Probability ComputingThe Size of the Giant Component of a Random Graph with a Given Degree Sequence
828 Citations1998Michael Molloy, Bruce Reed
The size of the giant component in the former case, and the structure of the graph formed by deleting that component is analyzed, which is basically that of a random graph with n′=n−∣C∣ vertices, and with λ′in′ of them of degree i.
Physical Review LettersScale-Free Networks from Varying Vertex Intrinsic Fitness
786 Citations2002Guido Caldarelli, Andrea Capocci +2 more
A new mechanism leading to scale-free networks is proposed, which is called a good-get-richer mechanism, in which sites with larger fitness are more likely to become hubs (i.e., to be highly connected).
Journal of the Royal Statistical Society Series A (General)The Theory of Branching Processes.
491 Citations1964M. S. Bartlett, T. E. Harris
Experimental MathematicsA Random Graph Model for Power Law Graphs
418 Citations2001William Aiello, Fan Chung +1 more
A random graph model is proposed which is a special case of sparserandom graphs with given degree sequences which satisfy a power law and involves only a small number of parameters, called logsize and log-log growth rate, which capture some universal characteristics of massive graphs.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsPercolation critical exponents in scale-free networks
302 Citations2002Reuven Cohen, Daniel ben‐Avraham +1 more
It is shown that for networks with 3<lambda<4, known to undergo a transition at a finite threshold of dilution, the critical exponents are different than the expected mean-field values of regular percolation in infinite dimensions.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsGeneral formalism for inhomogeneous random graphs
250 Citations2002Bo Söderberg
An extension of the classical random graph to a general class of inhomogeneous random graph models, where vertices come in different types, and the probability of realizing an edge depends on the types of its terminal vertices is investigated.
Electronics LettersNew fast method for generating discrete random numbers with arbitrary frequency distributions
250 Citations1974A.J. Walker
A new method for generating discrete random numbers with arbitrary amplitude/frequency distributions is presented, which consists essentially of amplitude manipulation of uniformly distributed, statistically independent sequential numbers.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsStatistical ensemble of scale-free random graphs
175 Citations2001Z. Burda, João D. G. Correia +1 more
A thorough discussion of the statistical ensemble of scale-free connected random tree graphs is presented: methods borrowed from field theory are used to define the ensemble and its properties are studied analytically and possible generalizations are discussed.
Physical Review LettersCorrelated Random Networks
169 Citations2002Johannes Berg, Michael Lässig
More general interactions H(c) are studied which lead to correlations, for example, between the connectivities of adjacent vertices which are argued to be a crucial signature of evolutionary design in biological networks.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsUncorrelated random networks
91 Citations2003Z. Burda, A. Krzywicki
It is found that in the absence of dynamical internode correlations the degree distribution is cut at a degree value scaling like N(gamma), with gamma=min[1/2,1/(beta-1)], where N is the total number of nodes.
Nuclear Physics BPrinciples of statistical mechanics of uncorrelated random networks
79 Citations2003S.N. Dorogovtsev, J.F.F. Mendes +1 more
It is shown that in equilibrium uncorrelated networks, fat-tailed degree distributions may exist only starting from some critical average number of connections of a vertex, in a phase with a condensate of edges.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsScale-free networks from a Hamiltonian dynamics
50 Citations2003Marco Baiesi, S. S. Manna
This work presents a model with fixed number of nodes and links, where a dynamics favoring the formation of links between nodes with degree of connectivity as different as possible is introduced and finds nontrivial hierarchical clustering.