On the degree sequence of an evolving random graph process and its critical phenomenon. (English) Zbl 1228.05123
Summary: 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.
References:
| [1] | Albert, R. and Barabási, A.-L. (2002). Statistical mechanics of complex networks. Rev. Modern Phys. 74 , 47–97. · Zbl 1205.82086 · doi:10.1103/RevModPhys.74.47 |
| [2] | Albert, R., Barabási, A. and Jeong, H. (1999). Diameter of the World Wide Web. Nature 401 , 130–131. |
| [3] | Aiello, W., Chung, F. and Lu, L. (2002). Random evolution in massive graphs. In Handbook of Massive Data Sets , eds J. Abello et al. , Kluwer, Dordrecht, pp. 510–519. · Zbl 1024.68073 |
| [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. |
| [5] | Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286 , 509–512. · Zbl 1226.05223 · doi:10.1126/science.286.5439.509 |
| [6] | Bernard, H. R. et al . (1988). Studying social relations cross-culturally. Ethnology 27 , 155–179. |
| [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. · Zbl 1047.05038 |
| [8] | Bollobás, B. and Riordan, O. (2004). The diameter of a scale-free random graph. Combinatorica 4 , 5–34. · Zbl 1047.05038 · doi:10.1007/s00493-004-0002-2 |
| [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. · Zbl 0985.05047 · doi:10.1002/rsa.1009 |
| [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. |
| [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. · Zbl 1042.05089 · doi:10.1016/j.disc.2003.10.020 |
| [12] | Chung, F. and Lu, L. (2004). Coupling online and offline analysis for random power law graphs. Internet Math. 1 , 409-461. · Zbl 1089.05021 · doi:10.1080/15427951.2004.10129094 |
| [13] | Cooper, C. and Frieze, A. (2003). A general model of undirected web graphs. Random Structures Algorithms 22 , 311–335. · Zbl 1018.60007 |
| [14] | Cooper, C., Frieze, A. and Vera, J. (2004). Random deletion in a scale-free random graph process. Internet Math. 1 , 463–483. · Zbl 1080.60006 · doi:10.1080/15427951.2004.10129095 |
| [15] | Erdös, P. and Rényi, A. (1959). On random graphs. I. Publ. Math. Debrecen 6 , 290–297. · Zbl 0092.15705 |
| [16] | Gilbert, E. N. (1959). Random graphs. Ann. Math. Statist. 30 , 1141–1144. · Zbl 0168.40801 · doi:10.1214/aoms/1177706098 |
| [17] | Jordan, C. (1939). Calculus of Finite Differences . Hungarian Agent Eggenberger Book-Shop, Budapest. · Zbl 0060.12309 |
| [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. |
| [19] | Lehmann, S., Lautrup, B. and Jackson, A. D. (2003). Citation networks in high energy physics. Phys. Rev. E 68 , 026113. |
| [20] | Newman, M. E. J. (2003). The structure and function of the complex networks. SIAM Rev. 45 , 167–256. · Zbl 1029.68010 · doi:10.1137/S003614450342480 |
| [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. |
| [22] | Strogatz, S. H. (2001). Exploring complex networks. Nature 410 , 268–276. · Zbl 1370.90052 |
| [23] | Stroock, D. W. (1984). An Introduction to the Theory of Large Deviations . Springer, New York. · Zbl 0552.60022 |
| [24] | Watts, D. J. (1999). Small Worlds . Princeton University Press. · Zbl 1046.00006 |
| [25] | Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature 393 , 440–442. · Zbl 1368.05139 |
| [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. · Zbl 1134.68020 · doi:10.1016/j.ins.2007.10.024 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
