Local Degree Distribution in Scale Free Random Graphs

Agnes Backhausz (Eotvos Lorand University)
Tamas F. Mori (Eotvos Lorand University)

Abstract


In several scale free graph models the asymptotic degree distribution and the characteristic exponent change when only a smaller set of vertices is considered. Looking at the common properties of these models, we present sufficient conditions for the almost sure existence of an asymptotic degree distribution constrained to the set of selected vertices, and identify the chararteristic exponent belonging to it.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1465-1488

Publication Date: August 19, 2011

DOI: 10.1214/EJP.v16-916

References

  1. A. Backhausz. Local degree distributions: examples and counterexamples. Accepted in: Periodica Mathematica Hungarica Math. Review number not available.
  2. A-L. Barabasi, R. Albert. Emergence of scaling in random networks. Science 286 (1999), 509-512. Math. Review 2091634
  3. N. H. Bingham. Regular variation. Encyclopedia of Mathematics and its Applications 27 (1987) Cambridge University Press. Math. Review 0898871
  4. R. Bojanic, E. Seneta. Slowly varying functions and asymptotic relations. J. Math. Anal. Appl. 34 (1971), 302-315. Math. Review 0274676
  5. B. Bollobas. Random graphs. (2001) Cambridge University Press. Math. Review 1864966
  6. S. Dereich, P. Morters. Random networks with sublinear preferential attachment: degree evolutions. Electron. J. Probab. 14 (2009), no. 43, 1222-1267. Math. Review 2511283
  7. M. Drmota. Random trees. (2009) Springer-Verlag/Wien. Math. Review 2484382
  8. R. Durrett. Random graph dynamics. (2007) Cambridge University Press. Math. Review 2271734
  9. J. Galambos, E. Seneta. Regularly varying sequences. Proc. Amer. Math. Soc. 41 (1973), 110-116. Math. Review 0323963
  10. Zs. Katona, T. F. Mori. A new class of scale free random graphs. Statist. Probab. Lett. 76 (2006), 1587-1593. Math. Review 2248845
  11. T. F. Mori. On random trees. Studia Sci. Math. Hungar. 39 (2002), 143-155. Math. Review 1909153
  12. T. F. Mori. A surprising property of the Barabasi-Albert random tree. Studia Sci. Math. Hungar. 43 (2006), 265-273. Math. Review 2229623
  13. T. F. Mori. Degree distribution nearby the origin of a preferential attachment graph. Electron. Comm. Probab. 12 (2007), 276-282. Math. Review 2342706
  14. T. F. Mori. On a 2-parameter class of scale free random graphs. Acta Math. Hungar. 114 (2007), 37-48. Math. Review 2294512
  15. T. F. Mori. Random multitrees. Studia Sci. Math. Hungar. 47 (2010), 59-80. Math. Review 2654228
  16. J. Neveu. Discrete-parameter martingales. (1975) North-Holland, Amsterdam. Math. Review 0402915
  17. B. Pittel. Note on the heights of random recursive trees and random m-ary search trees. Random Struct. Algorithms 5 (1994), 337-347. Math. Review 1262983
  18. A. Rudas, B. Toth, B. Valko. Random trees and general branching processes. Random Struct. Algorithms 31 (2) (2007), 186-202. Math. Review 2343718
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.