Diameters in preferential attachment models. (English) Zbl 1191.82020
Summary: We investigate the diameter in preferential attachment (PA-) models, thus quantifying the statement that these models are small worlds. The models studied here are such that edges are attached to older vertices proportional to the degree plus a constant, i.e., we consider affine PA-models. There is a substantial amount of literature proving that, quite generally, PA-graphs possess power-law degree sequences with a power-law exponent \(\tau >2\).
We prove that the diameter of the PA-model is bounded above by a constant times \(\log t\), where \(t\) is the size of the graph. When the power-law exponent \(\tau \) exceeds 3, then we prove that \(\log t\) is the right order, by proving a lower bound of this order, both for the diameter as well as for the typical distance. This shows that, for \(\tau >3\), distances are of the order \(\log t\). For \(\tau \in (2,3)\), we improve the upper bound to a constant times \(\log \log t\), and prove a lower bound of the same order for the diameter. Unfortunately, this proof does not extend to typical distances. These results do show that the diameter is of order \(\log \log t\).
These bounds partially prove predictions by physicists that the typical distance in PA-graphs are similar to the ones in other scale-free random graphs, such as the configuration model and various inhomogeneous random graph models, where typical distances have been shown to be of order \(\log \log t\) when \(\tau \in \)(2,3), and of order \(\log t\) when \(\tau >3\).
We prove that the diameter of the PA-model is bounded above by a constant times \(\log t\), where \(t\) is the size of the graph. When the power-law exponent \(\tau \) exceeds 3, then we prove that \(\log t\) is the right order, by proving a lower bound of this order, both for the diameter as well as for the typical distance. This shows that, for \(\tau >3\), distances are of the order \(\log t\). For \(\tau \in (2,3)\), we improve the upper bound to a constant times \(\log \log t\), and prove a lower bound of the same order for the diameter. Unfortunately, this proof does not extend to typical distances. These results do show that the diameter is of order \(\log \log t\).
These bounds partially prove predictions by physicists that the typical distance in PA-graphs are similar to the ones in other scale-free random graphs, such as the configuration model and various inhomogeneous random graph models, where typical distances have been shown to be of order \(\log \log t\) when \(\tau \in \)(2,3), and of order \(\log t\) when \(\tau >3\).
MSC:
| 82B41 | Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics |
| 05C82 | Small world graphs, complex networks (graph-theoretic aspects) |
Keywords:
small-world networks; preferential attachment models; distances in random graphs; universalityReferences:
| [1] | Abramowitz, M., Stegun, I.A. (eds.): Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables. US Government Printing Office, Washington (1964) · Zbl 0171.38503 |
| [2] | Aiello, W., Chung, F., Lu, L.: Random evolution in massive graphs. In: Handbook of Massive Data Sets. Massive Comput., vol. 4, pp. 97–122. Kluwer Acad., Dordrecht (2002) · Zbl 1024.68073 |
| [3] | Albert, R., Barabási, A.-L.: Statistical mechanics of complex networks. Rev. Mod. Phys. 74(1), 47–97 (2002) · Zbl 1205.82086 · doi:10.1103/RevModPhys.74.47 |
| [4] | Alon, N., Spencer, J.H.: The Probabilistic Method, 2nd edn. Wiley, New York (2000) |
| [5] | Barabási, A.-L.: Linked: The New Science of Networks. Perseus, Cambridge (2002) |
| [6] | Barabási, A.-L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999) · Zbl 1226.05223 · doi:10.1126/science.286.5439.509 |
| [7] | Berger, N., Bollobás, B., Borgs, C., Chayes, J., Riordan, O.: Degree distribution of the FKP network model. In: Automata, Languages and Programming. Lecture Notes in Comput. Sci., vol. 2719, pp. 725–738. Springer, Berlin (2003) · Zbl 1039.68510 |
| [8] | Bhamidi, S.: Universal techniques to analyze preferential attachment trees: Global and local analysis. In preparation. Version August 19, 2007 available from http://www.unc.edu/\(\sim\)bhamidi/preferent.pdf |
| [9] | Bollobás, B.: Random Graphs, 2nd edn. Cambridge Studies in Advanced Mathematics, vol. 73. Cambridge University Press, Cambridge (2001) · Zbl 0979.05003 |
| [10] | Bollobás, B., Riordan, O.: Mathematical results on scale-free random graphs. In: Handbook of Graphs and Networks, pp. 1–34. Wiley, Weinheim (2003) · Zbl 1062.05080 |
| [11] | Bollobás, B., Riordan, O.: Robustness and vulnerability of scale-free random graphs. Internet Math. 1(1), 1–35 (2003) · Zbl 1062.05080 · doi:10.1080/15427951.2004.10129080 |
| [12] | Bollobás, B., Riordan, O.: Coupling scale-free and classical random graphs. Internet Math. 1(2), 215–225 (2004) · Zbl 1061.05084 · doi:10.1080/15427951.2004.10129084 |
| [13] | Bollobás, B., Riordan, O.: The diameter of a scale-free random graph. Combinatorica 24(1), 5–34 (2004) · Zbl 1047.05038 · doi:10.1007/s00493-004-0002-2 |
| [14] | Bollobás, B., Riordan, O.: Shortest paths and load scaling in scale-free trees. Phys. Rev. E. 69, 036114 (2004) · Zbl 1047.05038 |
| [15] | Bollobás, B., Riordan, O., Spencer, J., Tusnády, G.: The degree sequence of a scale-free random graph process. Random Struct. Algorithms 18(3), 279–290 (2001) · Zbl 0985.05047 · doi:10.1002/rsa.1009 |
| [16] | Bollobás, B., Borgs, C., Chayes, J., Riordan, O.: Directed scale-free graphs. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, 2003, pp. 132–139. New York (2003) · Zbl 1094.68605 |
| [17] | Bollobás, B., Janson, S., Riordan, O.: The phase transition in inhomogeneous random graphs. Random Struct. Algorithms 31(1), 3–122 (2007) · Zbl 1123.05083 · doi:10.1002/rsa.20168 |
| [18] | Chung, F., Lu, L.: The average distances in random graphs with given expected degrees. Proc. Natl. Acad. Sci. USA 99(25), 15879–15882 (2002) (electronic) · Zbl 1064.05137 · doi:10.1073/pnas.252631999 |
| [19] | Chung, F., Lu, L.: The average distance in a random graph with given expected degrees. Internet Math. 1(1), 91–113 (2003) · Zbl 1065.05084 · doi:10.1080/15427951.2004.10129081 |
| [20] | Chung, F., Lu, L.: Coupling online and offline analyses for random power law graphs. Internet Math. 1(4), 409–461 (2004) · Zbl 1089.05021 · doi:10.1080/15427951.2004.10129094 |
| [21] | Chung, F., Lu, L.: Complex Graphs and Networks. CBMS Regional Conference Series in Mathematics, vol. 107. Published for the Conference Board of the Mathematical Sciences, Washington (2006) · Zbl 1114.90071 |
| [22] | Cooper, C., Frieze, A.: A general model of web graphs. Random Struct. Algorithms 22(3), 311–335 (2003) · Zbl 1018.60007 · doi:10.1002/rsa.10084 |
| [23] | Deijfen, M., van den Esker, H., van der Hofstad, R., Hooghiemstra, G.: A preferential attachment model with random initial degrees. Arkiv Mat. 47(1), 41–72 (2009) · Zbl 1182.05107 · doi:10.1007/s11512-007-0067-4 |
| [24] | Dorogovtsev, S.N., Mendes, J.F.F.: Evolution of networks. Adv. Phys. 51, 1079–1187 (2002) · doi:10.1080/00018730110112519 |
| [25] | Durrett, R.: Random Graph Dynamics. Cambridge University Press, Cambridge (2007) · Zbl 1116.05001 |
| [26] | Feller, W.: An Introduction to Probability Theory and Its Applications, vol. II. Wiley, London (1970) · Zbl 0077.12201 |
| [27] | Fernholz, D., Ramachandran, V.: The diameter of sparse random graphs. Random Struct. Algorithms 31(4), 482–516 (2007) · Zbl 1129.05046 · doi:10.1002/rsa.20197 |
| [28] | Hagberg, O., Wiuf, C.: Convergence properties of the degree distribution of some growing network models. Bull. Math. Biol. 68, 1275–1291 (2006) · Zbl 1334.92158 · doi:10.1007/s11538-006-9085-9 |
| [29] | Janson, S., Łuczak, T., Ruciński, A.: Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (2000) · Zbl 0968.05003 |
| [30] | Jordan, J.: The degree sequences and spectra of scale-free random graphs. Random Struct. Algorithms 29(2), 226–242 (2006) · Zbl 1108.05083 · doi:10.1002/rsa.20101 |
| [31] | Móri, T.F.: On random trees. Studia Sci. Math. Hungar. 39(1–2), 143–155 (2002) · Zbl 1026.05095 |
| [32] | Móri, T.F.: The maximum degree of the Barabási-Albert random tree. Comb. Probab. Comput. 14(3), 339–348 (2005) · Zbl 1078.05077 · doi:10.1017/S0963548304006133 |
| [33] | Newman, M.E.J.: The structure and function of complex networks. SIAM Rev. 45(2), 167–256 (2003) (electronic) · Zbl 1029.68010 · doi:10.1137/S003614450342480 |
| [34] | Norros, I., Reittu, H.: On a conditionally Poissonian graph process. Adv. Appl. Probab. 38(1), 59–75 (2006) · Zbl 1096.05047 · doi:10.1239/aap/1143936140 |
| [35] | Oliveira, R., Spencer, J.: Connectivity transitions in networks with super-linear preferential attachment. Internet Math. 2(2), 121–163 (2005) · Zbl 1097.68016 · doi:10.1080/15427951.2005.10129101 |
| [36] | Pittel, B.: Note on the heights of random recursive trees and random m-ary search trees. Random Struct. Algorithms 5(2), 337–347 (1994) · Zbl 0790.05077 · doi:10.1002/rsa.3240050207 |
| [37] | Reittu, H., Norros, I.: On the power law random graph model of massive data networks. Perform. Eval. 55(1–2), 3–23 (2004) · doi:10.1016/S0166-5316(03)00097-X |
| [38] | Rudas, A., Tóth, B., Valkó, B.: Random trees and general branching processes. Random Struct. Algorithms 31(2), 186–202 (2007) · Zbl 1144.60051 · doi:10.1002/rsa.20137 |
| [39] | van den Esker, H., van der Hofstad, R., Hooghiemstra, G., Znamenski, D.: Distances in random graphs with infinite mean degrees. Extremes 8, 111–140 (2006) · Zbl 1120.05086 |
| [40] | van den Esker, H., van der Hofstad, R., Hooghiemstra, G.: Universality for the distance in finite variance random graphs. J. Stat. Phys. 133(1), 169–202 (2008) · Zbl 1152.82008 · doi:10.1007/s10955-008-9594-z |
| [41] | van der Hofstad, R.: Random graphs and complex networks. In preparation, (2009). Available on http://www.win.tue.nl/\(\sim\)rhofstad/NotesRGCN.pdf · Zbl 1361.05002 |
| [42] | van der Hofstad, R., Hooghiemstra, G., Van Mieghem, P.: Distances in random graphs with finite variance degrees. Random Struct. Algorithms 26, 76–123 (2005) · Zbl 1074.05083 |
| [43] | van der Hofstad, R., Hooghiemstra, G., Znamenski, D.: Distances in random graphs with finite mean and infinite variance degrees. Electron. J. Probab. 12(25), 703–766 (2007) (electronic) · Zbl 1126.05090 |
| [44] | van der Hofstad, R., Hooghiemstra, G., Znamenski, D.: A phase transition for the diameter of the configuration model. Internet Math. 4(1), 113–128 (2008) · Zbl 1167.05048 |
| [45] | Wadsworth, G.P., Bryan, J.G.: Introduction to Probability and Random Variables. McGraw-Hill, New York (1960) · Zbl 0094.11904 |
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.
