Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-25T17:55:28.313Z Has data issue: false hasContentIssue false
  • English
  • Français

On the Degree Sequence of an Evolving Random Graph Process and Its Critical Phenomenon

Part of: Graph theory

Published online by Cambridge University Press:  14 July 2016

Xian-Yuan Wu ,
Zhao Dong ,
Ke Liu  and
Kai-Yuan Cai
Xian-Yuan Wu*
Affiliation:
Capital Normal University
Zhao Dong*
Affiliation:
Capital Normal University
Ke Liu*
Affiliation:
Chinese Academy of Sciences
Kai-Yuan Cai*
Affiliation:
Beijing University of Aeronautics and Astronautics
*
∗Postal address: School of Mathematical Sciences, Institute of Mathematics and Interdisciplinary Science, Capital Normal University, Beijing, 100048, China. Email address: [email protected]
∗∗Postal address: Academy of Mathematics and System Sciences, Chinese Academy of Sciences, Beijing, 100190, China.
∗∗Postal address: Academy of Mathematics and System Sciences, Chinese Academy of Sciences, Beijing, 100190, China.
∗∗∗∗∗Postal address: National Key Laboratory of Science and Technology on Integrated Control, Department of Automatic Control, Beijing University of Aeronautics and Astronautics, Beijing, 100083, China. Email address: [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper we focus on the problem of the degree sequence for a random graph process with edge deletion. We prove that, while a specific parameter varies, the limit degree distribution of the model exhibits critical phenomenon.

Keywords

Degree sequencepower lawcritical phenomenonreal-world networks

MSC classification

Secondary: 05C07: Vertex degrees 05C80: Random graphs
Type
Research Article
Information
Journal of Applied Probability , Volume 46 , Issue 4 , December 2009 , pp. 1213 - 1220
Copyright
Copyright © Applied Probability Trust 2009 

Footnotes

Supported in part by the Foundation of Beijing Education Bureau under grant 09224010003 and the Natural Science Foundation of China under grant 10971143.

Supported in part by the Natural Science Foundation of China under grants 10671197 and 10721101.

Supported in part by the Natural Science Foundation of China and Microsoft Research Asia under grant 60633010.

References

[1] Albert, R. and Barabási, A.-L. (2002). Statistical mechanics of complex networks. Rev. Modern Phys. 74, 47–97.CrossRefGoogle Scholar
[2] Albert, R., Barabási, A. and Jeong, H. (1999). Diameter of the World Wide Web. Nature 401, 130–131.CrossRefGoogle Scholar
[3] Aiello, W., Chung, F. and Lu, L. (2002). Random evolution in massive graphs. In Handbook of Massive Data Sets, eds Abello, J. et al., Kluwer, Dordrecht, pp. 510–519.Google Scholar
[4] Amaral, L. A. N., Scala, A., Barthélémy, M. and Stanley, H. E. (2000). Classes of small-world networks. Proc. Nat. Acad. Sci. USA 97, 11149–11152.CrossRefGoogle ScholarPubMed
[5] Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286, 509–512.Google Scholar
[6] Bernard, H. R. et al. (1988). Studying social relations cross-culturally. Ethnology 27, 155–179.Google Scholar
[7] Bollobás, B. and Riordan, O. (2002). Mathematical results on scale-free random graphs. In Handbook of Graphs and Networks, John Wiley, Berlin, pp. 1–34.Google Scholar
[8] Bollobás, B. and Riordan, O. (2004). The diameter of a scale-free random graph. Combinatorica 4, 5–34.Google Scholar
[9] Bollobás, B., Riordan, O., Spencer, J. and Tusnády, G. (2001). The degree sequence of a scale-free random graph process. Random Structures Algorithms 18, 279–290.CrossRefGoogle Scholar
[10] Broder, A. et al. (2000). Graph structure in the Web. In Proc. 9th Internat. World Wide Web Conf. Comput. Networks, North-Holland, Amsterdam, pp. 309–320.Google Scholar
[11] Buckley, P. G. and Osthus, D. (2004). Popularity based random graph models leading to a scale-free degree sequence. Discrete Math. 282, 53–68.Google Scholar
[12] Chung, F. and Lu, L. (2004). Coupling online and offline analysis for random power law graphs. Internet Math. 1, 409–461.Google Scholar
[13] Cooper, C. and Frieze, A. (2003). A general model of undirected web graphs. Random Structures Algorithms 22, 311–335.CrossRefGoogle Scholar
[14] Cooper, C., Frieze, A. and Vera, J. (2004). Random deletion in a scale-free random graph process. Internet Math. 1, 463–483.Google Scholar
[15] Erdös, P. and Rényi, A. (1959). On random graphs. I. Publ. Math. Debrecen 6, 290–297.Google Scholar
[16] Gilbert, E. N. (1959). Random graphs. Ann. Math. Statist. 30, 1141–1144.Google Scholar
[17] Jordan, C. (1939). Calculus of Finite Differences. Hungarian Agent Eggenberger Book-Shop, Budapest.Google Scholar
[18] Kumar, R. et al. (2000). Stochastic models for the web graph. In 41st Annual Symp. Foundations Comput. Sci. (Redondo Beach, CA, 2000), IEEE Computer Society, Los Alamitos, CA, pp. 57–65.Google Scholar
[19] Lehmann, S., Lautrup, B. and Jackson, A. D. (2003). Citation networks in high energy physics. Phys. Rev. E 68, 026113.Google Scholar
[20] Newman, M. E. J. (2003). The structure and function of the complex networks. SIAM Rev. 45, 167–256.CrossRefGoogle Scholar
[21] Scala, A., Amaral, L. A. N. and Barthélémy, M. (2001). Small-world networks and the conformation space of a short lattice polymer chain. Europhys. Lett. 55, 594–600.CrossRefGoogle Scholar
[22] Strogatz, S. H. (2001). Exploring complex networks. Nature 410, 268–276.Google Scholar
[23] Stroock, D. W. (1984). An Introduction to the Theory of Large Deviations. Springer, New York.CrossRefGoogle Scholar
[24] Watts, D. J. (1999). Small Worlds. Princeton University Press.Google Scholar
[25] Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature 393, 440–442.Google Scholar
[26] Wu, X.-Y., Dong, Z., Liu, K. and Cai, K.-Y. (2008). On the degree sequence and its critical phenomenon of an evolving random graph process. Preprint. Available at http://arxiv.org/abs/0806.4684v1.Google Scholar