×

Penalising transmission to hubs in scale-free spatial random graphs. (English) Zbl 1483.05161

Summary: We study the spread of information in finite and infinite inhomogeneous spatial random graphs. We assume that each edge has a transmission cost that is a product of an i.i.d. random variable \(L\) and a penalty factor: edges between vertices of expected degrees \(w_1\) and \(w_2\) are penalised by a factor of \((w_1w_2)^{\mu}\) for all \(\mu > 0\). We study this process for scale-free percolation, for (finite and infinite) Geometric Inhomogeneous Random Graphs, and for Hyperbolic Random Graphs, all with power law degree distributions with exponent \(\tau > 1\). For \(\tau < 3\), we find a threshold behaviour, depending on how fast the cumulative distribution function of \(L\) decays at zero. If it decays at most polynomially with exponent smaller than \((3-\tau)/(2\mu)\) then explosion happens, i.e., with positive probability we can reach infinitely many vertices with finite cost (for the infinite models), or reach a linear fraction of all vertices with bounded costs (for the finite models). On the other hand, if the cdf of \(L\) decays at zero at least polynomially with exponent larger than \((3-\tau)/(2\mu)\), then no explosion happens. This behaviour is arguably a better representation of information spreading processes in social networks than the case without penalising factor, in which explosion always happens unless the cdf of \(L\) is doubly exponentially flat around zero. Finally, we extend the results to other penalty functions, including arbitrary polynomials in \(w_1\) and \(w_2\). In some cases the interesting phenomenon occurs that the model changes behaviour (from explosive to conservative and vice versa) when we reverse the role of \(w_1\) and \(w_2\). Intuitively, this could corresponds to reversing the flow of information: gathering information might take much longer than sending it out.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C82 Small world graphs, complex networks (graph-theoretic aspects)
60C05 Combinatorial probability
94A05 Communication theory

References:

[1] M. A. Abdullah, N. Fountoulakis and M. Bode. Typical distances in a geometric model for complex networks. Internet Math. 1 (2017). (electronic). · Zbl 1491.05163
[2] E. Adriaans and J. Komjáthy. Weighted distances in scale-free configuration models. J. Stat. Phys. 173 (3) (2018) 1082-1109. · Zbl 1404.05187 · doi:10.1007/s10955-018-1957-5
[3] R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Rev. Modern Phys. 74 (1) (2002) 47-97. · Zbl 1205.82086 · doi:10.1103/RevModPhys.74.47
[4] O. Amini, L. Devroye, S. Griffiths and N. Olver. On explosions in heavy-tailed branching random walks. Ann. Probab. 41 (3B) (2013) 1864-1899. · Zbl 1304.60093 · doi:10.1214/12-AOP806
[5] P. Bajardi, A. Barrat, F. Natale, L. Savini and V. Colizza. Dynamical patterns of cattle trade movements. PLoS ONE 6 (5) (2011) e19869.
[6] E. Baroni, R. van der Hofstad and J. Komjáthy. Nonuniversality of weighted random graphs with infinite variance degree. J. Appl. Probab. 54 (1) (2017) 146-164. · Zbl 1396.05098 · doi:10.1017/jpr.2016.92
[7] N. H. Bingham, C. M. Goldie and J. L. Teugels. Regular Variation. Encyclopedia of Mathematics and Its Applications 27. Cambridge University Press, Cambridge, 1989. · Zbl 0667.26003
[8] M. Biskup. On the scaling of the chemical distance in long-range percolation models. Ann. Probab. 32 (4) (2004) 2938-2977. · Zbl 1072.60084 · doi:10.1214/009117904000000577
[9] T. Bläsius, T. Friedrich, M. Katzmann, U. Meyer, M. Penschuck and C. Weyand. Efficiently generating geometric inhomogeneous and hyperbolic random graphs. In Proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019) 21:1-21:14. Leibniz International Proceedings in Informatics (LIPIcs) 144, 2019. Dagstuhl, Germany. · Zbl 07525458
[10] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez and D.-U. Hwang. Complex networks: Structure and dynamics. Phys. Rep. 424 (4-5) (2006) 175-308. · Zbl 1371.82002 · doi:10.1016/j.physrep.2005.10.009
[11] M. Bode, N. Fountoulakis and T. Müller. On the largest component of a hyperbolic model of complex networks. Electron. J. Combin. 22 (2015) 1-43. · Zbl 1327.05301 · doi:10.37236/4958
[12] M. Boguñá, F. Papadopoulos and D. Krioukov. Sustaining the Internet with hyperbolic mapping. Nat. Commun. 1 (6) (2010) 62.
[13] M. Boguñá and R. Pastor-Satorras. Class of correlated random networks with hidden variables. Phys. Rev. E 68 (2003) 036112. · Zbl 1132.92338
[14] M. Boguñá, R. Pastor-Satorras, A. Díaz-Guilera and A. Arenas. Models of social networks based on social distance attachment. Phys. Rev. E 70 (2004) 056122.
[15] B. Bollobás. Random Graphs, 2nd edition. Cambridge Studies in Advanced Mathematics 73. Cambridge University Press, Cambridge; New York, 2001. · Zbl 0979.05003 · doi:10.1017/CBO9780511814068
[16] B. Bollobás, S. Janson and O. Riordan. The phase transition in inhomogeneous random graphs. Random Structures Algorithms 31 (1) (2007) 3-122. · Zbl 1123.05083 · doi:10.1002/rsa.20168
[17] K. Bringmann, R. Keusch and J. Lengler. Average distance in a general class of scale-free networks with underlying geometry, 2016. Available at arXiv:1602.05712.
[18] K. Bringmann, R. Keusch and J. Lengler. Sampling geometric inhomogeneous random graphs in linear time. In 25th Annual European Symposium on Algorithms (ESA 2017) 20:1-20:15. Leibniz International Proceedings in Informatics (LIPIcs) 87, 2017. Dagstuhl, Germany. · Zbl 1442.05204
[19] K. Bringmann, R. Keusch and J. Lengler. Geometric inhomogeneous random graphs. Theoret. Comput. Sci. 760 (2019) 35-54. · Zbl 1414.05264 · doi:10.1016/j.tcs.2018.08.014
[20] K. Bringmann, R. Keusch, J. Lengler, Y. Maus and A. R. Molla. Greedy routing and the algorithmic small-world phenomenon. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC ’17 371-380. ACM, New York, NY, USA, 2017. · Zbl 1380.68024
[21] E. Candellero and N. Fountoulakis. Clustering and the hyperbolic geometry of complex networks. In Algorithms and Models for the Web Graph 1-12. Springer International Publishing, Cham, 2014. · Zbl 1342.05155 · doi:10.1007/978-3-319-13123-8_1
[22] E. Candellero and N. Fountoulakis. Bootstrap percolation and the geometry of complex networks. Stochastic Process. Appl. 126 (1) (2016) 234-264. · Zbl 1335.60180 · doi:10.1016/j.spa.2015.08.005
[23] E. Candellero and A. Stauffer. Coexistence of competing first passage percolation on hyperbolic graphs, 2018. Available at arXiv:18210.04593.
[24] D. Centola. The spread of behavior in an online social network experiment. Science 329 (5996) (2010) 1194-1197.
[25] M. Deijfen, R. van der Hofstad and G. Hooghiemstra. Scale-free percolation. Ann. Inst. Henri Poincaré Probab. Stat. 49 (3) (2013) 817-838. · Zbl 1274.60290 · doi:10.1214/12-AIHP480
[26] P. Deprez and M. V. Wüthrich. Scale-free percolation in continuum space. Commun. Math. Stat. (2018). · Zbl 1436.60079 · doi:10.1007/s40304-018-0142-0
[27] S. N. Dorogovtsev, A. V. Goltsev and J. F. Mendes. Critical phenomena in complex networks. Rev. Modern Phys. 80 (4) (2008) 1275.
[28] J. Feldman and J. Janssen. High degree vertices and spread of infections in spatially modelled social networks. In International Workshop on Algorithms and Models for the Web-Graph 60-74. Springer, Cham, 2017. · Zbl 1504.92127 · doi:10.1007/978-3-319-67810-8_5
[29] N. Fountoulakis and T. Müller. Law of large numbers for the largest component in a hyperbolic model of complex networks. Ann. Appl. Probab. 28 (1) (2018) 607-650. · Zbl 1387.05236 · doi:10.1214/17-AAP1314
[30] A. Gandolfi, M. S. Keane and C. M. Newman. Uniqueness of the infinite component in a random graph with applications to percolation and spin glasses. Probab. Theory Related Fields 92 (4) (1992) 511-527. · Zbl 0767.60098 · doi:10.1007/BF01274266
[31] C. Giuraniuc, J. Hatchett, J. Indekeu, M. Leone, I. P. Castillo, B. Van Schaeybroeck and C. Vanderzande. Criticality on networks with topology-dependent interactions. Phys. Rev. E 74 (3) (2006) 036108.
[32] D. Grey. Explosiveness of age-dependent branching processes. Probab. Theory Related Fields 28 (2) (1974) 129-137. · Zbl 0264.60055 · doi:10.1007/BF00533364
[33] D. Gruhl, R. Guha, D. Liben-Nowell and A. Tomkins. Information diffusion through blogspace. In Proceedings of the 13th International Conference on World Wide Web 491-501. ACM, New York, 2004.
[34] L. Gugelmann, K. Panagiotou and U. Peter. Random hyperbolic graphs: Degree sequence and clustering. In 39th International Colloquium on Automata, Languages, and Programming (ICALP) 573-585, 2012. · Zbl 1369.68270
[35] J. M. Hammersley and D. J. Welsh. First-passage percolation, subadditive processes, stochastic networks, and generalized renewal theory. In Bernoulli 1713, Bayes 1763, Laplace 1813 61-110. Springer, New York, 1965. · Zbl 0143.40402
[36] M. Heydenreich, T. Hulshof and J. Jorritsma. Structures in supercritical scale-free percolation. Ann. Appl. Probab. 27 (4) (2017) 2569-2604. · Zbl 1373.60158 · doi:10.1214/16-AAP1270
[37] V. Isham, J. Kaczmarska and M. Nekovee. Spread of information and infection on finite random networks. Phys. Rev. E 83 (4) (2011) 046128.
[38] S. Janson, T. Łuczak and A. Rucinski. Random Graphs. Wiley, New York, 2000. · Zbl 0968.05003 · doi:10.1002/9781118032718
[39] J. Janssen and A. Mehrabian. Rumors spread slowly in a small-world spatial network. SIAM J. Discrete Math. 31 (4) (2017) 2414-2428. · Zbl 1373.05185 · doi:10.1137/16M1083256
[40] J. Jorritsma. Random graph visualizations (version v0.1.0). Zenodo, 2020. · doi:10.5281/zenodo.3735853
[41] M. Karsai, R. Juhász and F. Iglói. Nonequilibrium phase transitions and finite-size scaling in weighted scale-free networks. Phys. Rev. E 73 (3) (2006) 036116.
[42] M. Karsai, M. Kivelä, R. K. Pan, K. Kaski, J. Kertész, A.-L. Barabási and J. Saramäki. Small but slow world: How network topology and burstiness slow down spreading. Phys. Rev. E 83 (2) (2011) 025102.
[43] M. Kiwi and D. Mitsche. Spectral gap of random hyperbolic graphs and related parameters. Ann. Appl. Probab. 28 (2) (2018) 941-989. · Zbl 1391.60022 · doi:10.1214/17-AAP1323
[44] C. Koch and J. Lengler. Bootstrap percolation on geometric inhomogeneous random graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) 147:1-147:15. Leibniz International Proceedings in Informatics (LIPIcs) 55, 2016. Dagstuhl, Germany. · Zbl 1388.68234
[45] J. Komjáthy and B. Lodewijks. Explosion in weighted hyperbolic random graphs and geometric inhomogeneous random graphs. In Stochastic Processes and Their Applications, 2019. · Zbl 1440.60011 · doi:10.1016/j.spa.2019.04.014
[46] D. Krioukov, F. Papadopoulos, M. Kitsak, A. Vahdat and M. Boguná. Hyperbolic geometry of complex networks. Phys. Rev. E 82 (3) (2010) 036106. · doi:10.1103/PhysRevE.82.036106
[47] J. Lengler and L. Todorovic. Existence of small separators depends on geometry for geometric inhomogeneous random graphs, 2017. Available at arXiv:1711.03814. · Zbl 1414.05264 · doi:10.1016/j.tcs.2018.08.014
[48] T. Mattfeldt. Stochastic geometry and its applications. J. Microsc. 183 (3) (1996) 257.
[49] R. Meester and R. Roy. Continuum Percolation. Cambridge Tracts in Mathematics 119. Cambridge University Press, Cambridge, 1996. · Zbl 1146.60076 · doi:10.1017/CBO9780511895357
[50] S. Merler, M. Ajelli, L. Fumanelli, M. F. Gomes, A. P. Y. Piontti, L. Rossi, D. L. Chao, I. M. Longini Jr., M. E. Halloran and A. Vespignani. Spatiotemporal spread of the 2014 outbreak of Ebola virus disease in Liberia and the effectiveness of non-pharmaceutical interventions: A computational modelling analysis. Lancet Infect. Dis. 15 (2) (2015) 204-211.
[51] G. Miritello, E. Moro, R. Lara, R. Martínez-López, J. Belchamber, S. G. Roberts and R. I. Dunbar. Time as a limited resource: Communication strategy in mobile phone networks. Soc. Netw. 35 (1) (2013) 89-95.
[52] M. Newman. Networks. Oxford University Press, Oxford, 2018. · Zbl 1391.94006 · doi:10.1093/oso/9780198805090.001.0001
[53] M. Newman, A.-L. Barabasi and D. J. Watts. The Structure and Dynamics of Networks, 19. Princeton University Press, Princeton, 2011.
[54] M. K. Nordvik and F. Liljeros. Number of sexual encounters involving intercourse and the transmission of sexually transmitted infections. Sex. Transm. Dis. 33 (6) (2006) 342-349.
[55] F. Papadopoulos, D. Krioukov, M. Boguñá and A. Vahdat. Greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. In Proceedings of the International Conference on Computer Communications (INFOCOM 2010) 1-9. IEEE, Los Alamitos, 2010.
[56] R. Pastor-Satorras, C. Castellano, P. Van Mieghem and A. Vespignani. Epidemic processes in complex networks. Rev. Modern Phys. 87 (3) (2015) 925-979. · doi:10.1103/RevModPhys.87.925
[57] R. Pastor-Satorras and A. Vespignani. Evolution and Structure of the Internet: A Statistical Physics Approach. Cambridge University Press, Cambridge, 2007.
[58] M. A. Serrano, D. Krioukov and M. Boguñá. Self-similarity of complex networks and hidden metric spaces. Phys. Rev. Lett. 100 (2008) 078701.
[59] P. Trapman. The growth of the infinite long-range percolation cluster. Ann. Probab. 38 (4) (2010) 1583-1608. · Zbl 1196.60171 · doi:10.1214/09-AOP517
[60] R. van der Hofstad and J. Komjathy. Explosion and distances in scale-free percolation, 2017. Available at arXiv:1706.02597. · Zbl 1386.60041
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.