Abstract
We introduce a simple algorithm that constructs scale-free random graphs efficiently: each vertexi has a prescribed weight Pi ∝ i-μ (0 < μ< 1) and an edge can connect verticesi andj with rateP i P j . Corresponding equilibrium ensemble is identified and the problem is solved by theq → 1 limit of the q-state Potts model with inhomogeneous interactions for all pairs of spins. The number of loops as well as the giant cluster size and the mean cluster size are obtained in the thermodynamic limit as a function of the edge density. Various critical exponents associated with the percolation transition are also obtained together with finite-size scaling forms. The process of forming the giant cluster is qualitatively different between the cases of λ > 3 and 2 < λ < 3, whereλ = 1 +μ -1 is the degree distribution exponent. 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 finiteN shows double peaks.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P Erdos and A Rényi,Publ. Math. Inst. Hung. Acad. Sci. 5, 17 (1960);Bull. Inst. Int. Stat. 38, 343 (1961)
A-L Barabási and R Albert,Science 286, 509 (1999)
R Albert and A-L Barabási,Rev. Mod. Phys. 74, 47 (2002)
S N Dorogovtsev and J F F Mendes,Adv. Phys. 51, 1079 (2002)
M E J Newman,SIAM Rev. 45, 167 (2003)
J Berg and M Lässig,Phys. Rev. Lett. 89, 228701 (2002)
M Baiesi and S S Manna,Phys. Rev. E68, 047103 (2003)
Z Burda, J D Correia and A Krzywicki,Phys. Rev. E64, 046118 (2001) Z Burda and A Krzywicki,Phys. Rev. E67, 046118 (2003)
S N Dorogovtsev, J F F Mendes and A N Samukhin,Nucl. Phys. B666, 396 (2003)
I Farkas, I Derenyi, G Palla and T Viscek, in Lecture notes in Physics:Networks: structure, dynamics, and function edited by E Ben-Naim, H Frauenfelder and Z Toroczkai (Springer, 2004)
M Molloy and B Reed,Random Struct. Algorithms 6, 161 (1995);Combinatorics, Probab. Comput. 7, 295 (1998)
M E J Newman, S H Strogatz and D J Watts,Phys. Rev. E64, 026118 (2001)
K-I Goh, B Kahng and D Kim,Phys. Rev. Lett. 87, 278701 (2001)
G Caldarelli, A Capocci, P De Los Rios and M A Muñoz,Phys. Rev. Lett. 89, 258702 (2002)
B Söderberg,Phys. Rev. E66, 066121 (2002)
F Chung and L Lu,Ann. Combinatorics 6, 125 (2002)
W Aiello, F Chung and L Lu,Exp. Math. 10, 53 (2001)
J Park and M E J Newman,Phys. Rev. E68, 026112 (2003);Phys. Rev. E70, 066117 (2004)
D-S Lee, K-I Goh, B Kahng and D Kim,Nucl. Phys. B696, 351 (2004)
P W Kasteleyn and C M Fortuin,J. Phys. Soc. Jpn. Suppl. 16, 11 (1969)
C M Fortuin and P W Kasteleyn,Physica 57, 536 (1972) Also see F Y Wu,Rev. Mod. Phys. 54, 235 (1982)
S S Manna and P Sen,Phys. Rev. E66, 066114 (2002) P Sen, K Banerjee and T Biswas,Phys. Rev. E66, 037102 (2002)
R Cohen, D ben-Avraham and S Havlin,Phys. Rev. E66, 036113 (2002)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Lee, D.S., Goh, K.I., Kahng, B. et al. Scale-free random graphs and Potts model. Pramana - J Phys 64, 1149–1159 (2005). https://doi.org/10.1007/BF02704176
Issue Date:
DOI: https://doi.org/10.1007/BF02704176