×

Spatial preferential attachment networks: power laws and clustering coefficients. (English) Zbl 1310.05185

Summary: We define a class of growing networks in which new nodes are given a spatial position and are connected to existing nodes with a probability mechanism favoring short distances and high degrees. The competition of preferential attachment and spatial clustering gives this model a range of interesting properties. Empirical degree distributions converge to a limit law, which can be a power law with any exponent \(\tau>2\). The average clustering coefficient of the networks converges to a positive limit. Finally, a phase transition occurs in the global clustering coefficients and empirical distribution of edge lengths when the power-law exponent crosses the critical value \(\tau=3\). Our main tool in the proof of these results is a general weak law of large numbers in the spirit of M. D. Penrose and J. E. Yukich [Ann. Appl. Probab. 13, No. 1, 277–303 (2003; Zbl 1029.60008)].

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C82 Small world graphs, complex networks (graph-theoretic aspects)
60C05 Combinatorial probability
90B15 Stochastic network models in operations research

Citations:

Zbl 1029.60008
PDFBibTeX XMLCite
Full Text: DOI arXiv Euclid

References:

[1] Aiello, W., Bonato, A., Cooper, C., Janssen, J. and Prałat, P. (2009). A spatial web graph model with local influence regions. Internet Math. 5 175-196. · Zbl 1206.68221 · doi:10.1080/15427951.2008.10129305
[2] 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
[3] 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
[4] Berger, N., Borgs, C., Chayes, J. T. and Saberi, A. (2014). Asymptotic behavior and distributional limits of preferential attachment graphs. Ann. Probab. 42 1-40. · Zbl 1296.60010 · doi:10.1214/12-AOP755
[5] Bollobás, B., Janson, S. and Riordan, O. (2011). Sparse random graphs with clustering. Random Structures Algorithms 38 269-323. · Zbl 1220.05117 · doi:10.1002/rsa.20322
[6] Bollobás, B. and Riordan, O. M. (2003). Mathematical results on scale-free random graphs. In Handbook of Graphs and Networks 1-34. Wiley-VCH, Weinheim. · Zbl 1062.05080
[7] Cooper, C., Frieze, A. and Prałat, P. (2014). Some typical properties of the spatial preferred attachment model. Internet Math . 10 116-136. · Zbl 1342.05160 · doi:10.1080/15427951.2013.796301
[8] Dereich, S. and Mörters, P. (2009). Random networks with sublinear preferential attachment: Degree evolutions. Electron. J. Probab. 14 1222-1267. · Zbl 1185.05127 · doi:10.1214/EJP.v14-647
[9] Dereich, S. and Mörters, P. (2011). Random networks with concave preferential attachment rule. Jahresber. Dtsch. Math.-Ver. 113 21-40. · Zbl 1217.05206 · doi:10.1365/s13291-010-0011-6
[10] Dereich, S. and Mörters, P. (2013). Random networks with sublinear preferential attachment: The giant component. Ann. Probab. 41 329-384. · Zbl 1260.05143 · doi:10.1214/11-AOP697
[11] Flaxman, A. D., Frieze, A. M. and Vera, J. (2006). A geometric preferential attachment model of networks. Internet Math. 3 187-205. · Zbl 1124.05081 · doi:10.1080/15427951.2006.10129124
[12] Flaxman, A. D., Frieze, A. M. and Vera, J. (2007). A geometric preferential attachment model of networks. II. In Algorithms and Models for the Web-graph. Lecture Notes in Computer Science 4863 41-55. Springer, Berlin. · Zbl 1137.68014 · doi:10.1007/978-3-540-77004-6_4
[13] Janssen, J., Prałat, P. and Wilson, R. (2013). Geometric graph properties of the spatial preferred attachment model. Adv. in Appl. Math. 50 243-267. · Zbl 1255.90027 · doi:10.1016/j.aam.2012.09.001
[14] Jordan, J. (2010). Degree sequences of geometric preferential attachment graphs. Adv. in Appl. Probab. 42 319-330. · Zbl 1210.05158 · doi:10.1239/aap/1275055230
[15] Jordan, J. (2013). Geometric preferential attachment in nonuniform metric spaces. Electron. J. Probab. 18 1-15. · Zbl 1283.05249 · doi:10.1214/EJP.v18-2271
[16] Jordan, J. and Wade, A. (2013). Phase transitions for random geometric preferential attachment graphs. Preprint. Available at . arXiv:1311.3776
[17] Penrose, M. (2003). Random Geometric Graphs. Oxford Studies in Probability 5 . Oxford Univ. Press, Oxford. · Zbl 1029.60007
[18] Penrose, M. D. and Yukich, J. E. (2003). Weak laws of large numbers in geometric probability. Ann. Appl. Probab. 13 277-303. · Zbl 1029.60008 · doi:10.1214/aoap/1042765669
[19] Rudas, A., Tóth, B. and Valkó, B. (2007). Random trees and general branching processes. Random Structures Algorithms 31 186-202. · Zbl 1144.60051 · doi:10.1002/rsa.20137
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.