×

When is a scale-free graph ultra-small? (English) Zbl 1386.60041

Summary: In this paper we study typical distances in the configuration model, when the degrees have asymptotically infinite variance. We assume that the empirical degree distribution follows a power law with exponent \(\tau \in (2,3)\), up to value \(n^{{\beta_n}}\) for some \({\beta_n}\gg (\log n)^{-\gamma}\) and \(\gamma \in (0,1)\). This assumption is satisfied for power law i.i.d. degrees, and also includes truncated power-law empirical degree distributions where the (possibly exponential) truncation happens at \(n^{{\beta_n}}\). These examples are commonly observed in many real-life networks. We show that the graph distance between two uniformly chosen vertices centers around \(2 \log \log (n^{{\beta_n}}) / |\log (\tau -2)| + 1/({\beta_n}(3-\tau))\), with tight fluctuations. Thus, the graph is an ultrasmall world whenever \(1/{\beta_n}=o(\log \log n)\). We determine the distribution of the fluctuations around this value, in particular we prove these form a sequence of tight random variables with distributions that show \(\log \log \)-periodicity, and as a result it is non-converging. We describe the topology and number of shortest paths: We show that the number of shortest paths is of order \(n^{f_n{\beta_n}}\), where \(f_n \in (0,1)\) is a random variable that oscillates with \(n\). We decompose shortest paths into three segments, two ’end-segments’ starting at each of the two uniformly chosen vertices, and a middle segment. The two end-segments of any shortest path have length \(\log \log (n^{{\beta_n}}) / |\log (\tau -2)|\)+tight, and the total degree is increasing towards the middle of the path on these segments. The connecting middle segment has length \(1/({\beta_n}(3-\tau))\)+tight, and it contains only vertices with degree at least of order \(n^{(1-f_n){\beta_n}}\), thus all the degrees on this segment are comparable to the maximal degree. Our theorems also apply when instead of truncating the degrees, we start with a configuration model and we remove every vertex with degree at least \(n^{{\beta_n}}\), and the edges attached to these vertices. This sheds light on the attack vulnerability of the configuration model with infinite variance degrees.

MSC:

60C05 Combinatorial probability
05C80 Random graphs (graph-theoretic aspects)
90B15 Stochastic network models in operations research

Software:

plfit
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Achard, S., Salvador, R., Whitcher, B., Suckling, J., Bullmore, E.: A resilient, low-frequency, small-world human brain functional network with highly connected association cortical hubs. J. Neurosci. 26(1), 63-72 (2006) · doi:10.1523/JNEUROSCI.3874-05.2006
[2] 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
[3] Albert, R., Jeong, H., Barabási, A.-L.: Error and attack tolerance of complex networks. Nature 406(6794), 378-382 (2000) · doi:10.1038/35019019
[4] Amaral, L.A.N., Scala, A., Barthélémy, M., Stanley, H.E.: Classes of small-world networks. Proc. Natl. Acad. Sci. USA 97, 11149-11152 (2000) · doi:10.1073/pnas.200327197
[5] 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
[6] Baroni, E., Hofstad, R.v d, Komjáthy., J.: Fixed speed competition on the configuration model with infinite variance degrees: unequal speeds. Electron. J. Probab. 20(116), 1-48 (2015) · Zbl 1328.60017
[7] Bhamidi, S., Hofstad, R.v d, Hooghiemstra, G.: First passage percolation on random graphs with finite mean degrees. Ann. Appl. Probab. 20(5), 1907-1965 (2010) · Zbl 1213.60157 · doi:10.1214/09-AAP666
[8] Bhamidi, S., Hofstad, R. v. d., Hooghiemstra, G.: Universality for first passage percolation on sparse random graphs. to appear. Ann. Probab. arXiv:1210.6839 (2012) · Zbl 1376.60018
[9] Bingham, N.H., Goldie, C.M., Teugels, J.L.: Regular Variation, vol. 27. Cambridge University Press, Cambridge (1989) · Zbl 0667.26003
[10] Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., Wiener, J.: Graph structure in the web. Comput. Netw. 33(1), 309-320 (2000) · doi:10.1016/S1389-1286(00)00083-9
[11] Chung, F., Lu, L.: The diameter of sparse random graphs. Adv. Appl. Math. 26(4), 257-279 (2001) · Zbl 0977.05127 · doi:10.1006/aama.2001.0720
[12] Chung, F., Lu, L.: The average distance in a random graph with given expected degrees. Internet Math. 1(1), 91-113 (2004) · Zbl 1065.05084 · doi:10.1080/15427951.2004.10129081
[13] Clauset, A., Shalizi, C., Newman, M.E.J.: Power-law distributions in empirical data. SIAM Rev. 51(4), 661-703 (2009) · Zbl 1176.62001 · doi:10.1137/070710111
[14] Cohen, R., Erez, K., ben Avraham, D., Havlin, S.: Breakdown of the internet under intentional attack. Phys. Rev. Lett. 86, 3682-3685 (2001) · doi:10.1103/PhysRevLett.86.3682
[15] Cohen, R., Havlin, S.: Scale-free networks are ultrasmall. Phys. Rev. Lett. 90, 058701 (2003) · doi:10.1103/PhysRevLett.90.058701
[16] Davies, P.L.: The simple branching process: a note on convergence when the mean is infinite. J. Appl. Probab. 15(3), 466-480 (1978) · Zbl 0387.60093 · doi:10.1017/S0021900200045848
[17] Dodds, P., Muhamad, R., Watts, D.: An experimental study of search in global social networks. Science 301(5634), 827-829 (2003) · doi:10.1126/science.1081058
[18] Dommers, S., Hofstad, R v d, Hooghiemstra, G.: Diameters in preferential attachment graphs. J. Stat. Phys 139(72), 107 (2010) · Zbl 1191.82020
[19] Dorogovtsev, S.N., Mendes, J.F.F., Samukhin, A.N.: Metric structure of random networks. Nucl. Phys. B 653(3), 307-338 (2003) · Zbl 1010.05073 · doi:10.1016/S0550-3213(02)01119-7
[20] Eckhoff, M., Mörters, P., et al.: Vulnerability of robust preferential attachment networks. Electron. J. Probab. 19 (2014) · Zbl 1300.05282
[21] Faloutsos, M., Faloutsos, P., Faloutsos, C.: On power-law relationships of the internet topology. ACM SIGCOMM Comput. Commun. Rev. 29(4), 251-262 (1999) · Zbl 0889.68050 · doi:10.1145/316194.316229
[22] Federico, L., van der Hofstad, R.: Critical window for connectivity in the configuration model. Comb. Probab. Comput. pp. 1-21 (2017) · Zbl 1371.05263
[23] 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
[24] Fronczak, A., Fronczak, P., Hołyst, P.: How to calculate the main characteristics of random graphs-a new approach. arXiv:cond-mat/0308629 [cond-mat.stat-mech] (2003) · Zbl 1126.82318
[25] Fronczak, A., Fronczak, P., Hołyst, J.A.: Average path length in random networks. Phys. Rev. E 70, 056110 (2004) · Zbl 1189.91180 · doi:10.1103/PhysRevE.70.056110
[26] Gao, P., Wormald, N.: Enumeration of graphs with a heavy-tailed degree sequence. Adv. Math. 287, 412-450 (2016) · Zbl 1327.05155 · doi:10.1016/j.aim.2015.09.002
[27] Guimera, R., Mossa, S., Turtschi, A., Amaral, L.N.: The worldwide air transportation network: anomalous centrality, community structure, and cities’ global roles. Proc. Natl. Acad. Sci. USA 102(22), 7794-7799 (2005) · Zbl 1135.90309 · doi:10.1073/pnas.0407994102
[28] Hofstad, R.V.D.: Random Graphs and Complex Networks, vol. 1. Cambridge University Press, Cambridge (2016)
[29] van der Hofstad, R.: Random Graphs and Complex Networks, vol. 2. Cambridge University Press, Cambridge (2016) · Zbl 1361.05002
[30] Hofstad, R.V.D., Hooghiemstra, G., van Mieghem, P.: Distances in random graphs with finite variance degrees. Random Struct. Algorithms 27(1), 76-123 (2005) · Zbl 1074.05083
[31] Hofstad, R.V.D., Hooghiemstra, G., Znamenski, D.: Distances in random graphs with finite mean and infinite variance degrees. Electron. J. Probab 12(25), 703-766 (2007) · Zbl 1126.05090 · doi:10.1214/EJP.v12-420
[32] Holme, P., Kim, B.J., Yoon, C.N., Han, S.K.: Attack vulnerability of complex networks. Phys. Rev. E 65, 056109 (2002) · doi:10.1103/PhysRevE.65.056109
[33] Hołyst, J.A., Sienkiewicz, J., Fronczak, A., Fronczak, P., Suchecki, K.: Universal scaling of distances in complex networks. Phys. Rev. E 72, 026108 (2005) · doi:10.1103/PhysRevE.72.026108
[34] Janson, S., Luczak, M.J.: A new approach to the giant component problem. Random Struct. Algorithms 34(2), 197-216 (2009) · Zbl 1177.05110 · doi:10.1002/rsa.20231
[35] Jeong, H., Tombor, B., Albert, R., Oltvai, Z.N., Barabási, A.-L.: The large-scale organization of metabolic networks. Nature 407(6804), 651-654 (2000) · doi:10.1038/35036627
[36] Jordano, P., Bascompte, J., Olesen, J.M.: Invariant properties in coevolutionary networks of plantanimal interactions. Ecol. Lett. 6(1), 69-81 (2003) · doi:10.1046/j.1461-0248.2003.00403.x
[37] Kumar, R., Raghavan, P., Rajagopalan, S., Tomkins, A.: Trawling the web for emerging cyber-communities. Comput. Netw. 31(1116), 1481-1493 (1999) · doi:10.1016/S1389-1286(99)00040-7
[38] Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Society, Providence (2009) · Zbl 1160.60001
[39] Liljeros, F., Edling, C.R., Amaral, L.A.N., Stanley, H.E.: The web of human sexual contacts. Nature 411, 907 (2001) · doi:10.1038/35082140
[40] McKay, B.D., Wormald, N.C.: Asymptotic enumeration by degree sequence of graphs with degreeso(n1/2). Combinatorica 11(4), 369-382 (1991) · Zbl 0742.05047 · doi:10.1007/BF01275671
[41] Milgram, S.: The small world problem. Psychol Today 1, 60-67 (1967)
[42] Molloy, M., Reed, B.: A critical point for random graphs with a given degree sequence. Random Struct. Algorithms 6(2-3), 161-180 (1995) · Zbl 0823.05050 · doi:10.1002/rsa.3240060204
[43] Molloy, M., Reed, B.: The size of the giant component of a random graph with a given degree sequence. Comb. Probab. Comput. 7(3), 295-305 (1998) · Zbl 0916.05064 · doi:10.1017/S0963548398003526
[44] Montoya, J.M., Pimm, S.L., Solé, R.V.: Ecological networks and their fragility. Nature 442(7100), 259-264 (2006) · doi:10.1038/nature04927
[45] Mossa, S., Barthélémy, M., Stanley, H.E., Amaral, L.A.: Truncation of power law behavior in scale-free network models due to information filtering. Phys. Rev. Lett. 88, 138701 (2002) · doi:10.1103/PhysRevLett.88.138701
[46] Nanavati, A.A., Gurumurthy, S., Das, G., Chakraborty, D., Dasgupta, K., Mukherjea, S., Joshi, A.: On the structural properties of massive telecom call graphs: findings and implications. In: Proceedings of the 15th ACM International Conference on Information and Knowledge Management, CIKM ’06, pp. 435-444, New York, NY, USA . ACM (2006)
[47] Newman, M .E .J.: Scientific collaboration networks. I and II. Phys. Rev. E 64(1), 016131-016132 (2001) · doi:10.1103/PhysRevE.64.016131
[48] Newman, M.E.J.: The structure of scientific collaboration networks. Proc. Natl. Acad. Sci. USA 98(2), 404-409 (2001) · Zbl 1065.00518 · doi:10.1073/pnas.98.2.404
[49] M. E. J, Newman: The structure and function of complex networks. SIAM Rev. 45(2), 167-256 (2003). (electronic) · Zbl 1029.68010 · doi:10.1137/S003614450342480
[50] Newman, M.E.J.: Power laws, Pareto distributions and Zipf’s law. Contemp. Phys. 46(5), 323-351 (2005) · doi:10.1080/00107510500052444
[51] Newman, M.E.J., Strogatz, S., Watts, D.: Random graphs with arbitrary degree distribution and their application. Phys. Rev. E 64(026118), 1-17 (2000)
[52] Norros, I., Reittu, H.: On a conditionally Poissonian graph process. Adv. in Appl. Probab. 38(1), 59-75 (2006) · Zbl 1096.05047 · doi:10.1017/S000186780000080X
[53] Norros, I., Reittu, H.: Network models with a ’soft hierarchy’: a random graph construction with loglog scalability. IEEE Netw. 22(2) (2008) · Zbl 1184.68360
[54] Ostilli, M.: Fluctuation analysis in complex networks modeled by hidden-variable models: necessity of a large cutoff in hidden-variable models. Phys. Rev. E 89, 022807 (2014) · doi:10.1103/PhysRevE.89.022807
[55] Pool, I d S, Kochen, M.: Contacts and influence. Soc. Netw. 1(5), 51 (1978)
[56] Seneta, E.: The simple branching process with infinite mean. J. Appl. Probab. 10(1), 206-212 (1973) · Zbl 0258.60058 · doi:10.1017/S0021900200042212
[57] Seneta, E.: Regularly varying functions in the theory of simple branching processes. Adv. Appl. Probab. 6(3), 408-420 (1974) · Zbl 0291.60043 · doi:10.1017/S0001867800039902
[58] Strogatz, S.H.: Exploring complex networks. Nature 410(6825), 268-276 (2001) · Zbl 1370.90052 · doi:10.1038/35065725
[59] Travers, J., Milgram, S.: An experimental study of the small world problem. Sociometry 32, 425-443 (1969) · doi:10.2307/2786545
[60] Ugander, J., Karrer, B., Backstrom, L., Marlow, C.: The anatomy of the Facebook social graph. arXiv:1111.4503 (2011)
[61] Watts, D.J.: Small Worlds: The Dynamics of Networks Between Order and Randomness Princeton Studies in Complexity. Princeton University Press, Princeton (1999)
[62] Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393, 440-442 (1998) · Zbl 1368.05139 · doi:10.1038/30918
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.