Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T19:46:28.207Z Has data issue: false hasContentIssue false
  • English
  • Français

Distance between two random k-out digraphs, with and without preferential attachment

Part of: Limit theorems Graph theory Combinatorial probability

Published online by Cambridge University Press:  21 March 2016

Nicholas R. Peterson  and
Boris Pittel
Nicholas R. Peterson*
Affiliation:
The Ohio State University
Boris Pittel*
Affiliation:
The Ohio State University
*
∗ Postal address: Department of Mathematics, The Ohio State University, 100 Math Tower, 231 West 18th Avenue, Columbus, OH 43210, USA.
∗ Postal address: Department of Mathematics, The Ohio State University, 100 Math Tower, 231 West 18th Avenue, Columbus, OH 43210, USA.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

A random k-out mapping (digraph) on [n] is generated by choosing k random images of each vertex one at a time, subject to a 'preferential attachment' rule: the current vertex selects an image i with probability proportional to a given parameter α = α(n) plus the number of times i has already been selected. Intuitively, the larger α becomes, the closer the resulting k-out mapping is to the uniformly random k-out mapping. We prove that α = Θ(n1/2) is the threshold for α growing 'fast enough' to make the random digraph approach the uniformly random digraph in terms of the total variation distance. We also determine an exact limit for this distance for the α = βn1/2 case.

Keywords

Random graphsrandom digraphspreferential attachmentuniformk-out digraphstotal variation distancelocal limit theorem

MSC classification

Primary: 05C80: Random graphs
Secondary: 60C05: Combinatorial probability 60F05: Central limit and other weak theorems
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 47 , Issue 3 , September 2015 , pp. 858 - 879
Copyright
Copyright © Applied Probability Trust 2015 

Footnotes

The authors gratefully acknowledge support from the NSF (grant no. DMS-1101237).

References

Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286, 509–512.CrossRefGoogle ScholarPubMed
Bergeron, F., Flajolet, P. and Salvy, B. (1992). Varieties of increasing trees. In CAAP '92 (Lecture Notes Comput. Sci. 581), Springer, Berlin, pp. 24-48.CrossRefGoogle Scholar
Bhattacharya, R. N. and Rao, R. R. (1976). Normal Approximation and Asymptotic Expansions. John Wiley, New York.Google Scholar
Bollobás, B. and Riordan, O. (2004). The diameter of a scale-free random graph. Combinatorica 24, 5–34.CrossRefGoogle Scholar
Bollobás, B., Borgs, C., Chayes, J. and Riordan, O. (2003). Directed scale-free graphs. In Proc. 14th ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, pp. 132–139.Google Scholar
Bollobás, B., Riordan, O., Spencer, J. and Tusnády, G. (2001). The degree sequence of a scale-free random graph process. Random Structures Algorithms 18, 279–290.CrossRefGoogle Scholar
Buckley, P. G. and Osthus, D. (2004). Popularity based random graph models leading to a scale-free degree sequence. Discrete Math. 282, 53–68.CrossRefGoogle Scholar
Burtin, Y. D. (1980). On a simple formula for random mappings and its applications. J. Appl. Prob. 17, 403–414.CrossRefGoogle Scholar
Deijfen, M. (2010). Random networks with preferential growth and vertex death. J. Appl. Prob. 47, 1150–1163.CrossRefGoogle Scholar
Durrett, R. (2005). Probability: Theory and Examples, 3rd edn. Thomson Brooks/Cole, Belmont, CA.Google Scholar
Erdős, P. and Rényi, A. (1960). On the evolution of random graphs. Magyar. Tud. Akad. Kutató Int. Közl. 5, 17-61.Google Scholar
Gertsbakh, I. B. (1977). Epidemic process on a random graph: some preliminary results. J. Appl. Prob. 14, 427–438.CrossRefGoogle Scholar
Hansen, J. C. and Jaworski, J. (2008). Local properties of random mappings with exchangeable in-degrees. Adv. Appl. Prob. 40, 183–205.CrossRefGoogle Scholar
Hansen, J. C. and Jaworski, J. (2008). Random mappings with exchangeable in-degrees. Random Structures Algorithms 33, 105–126.CrossRefGoogle Scholar
Hansen, J. C. and Jaworski, J. (2009). A random mapping with preferential attachment. Random Structures Algorithms 34, 87–111.CrossRefGoogle Scholar
Mahmoud, H. M., Smythe, R. T. and Szymański, J. (1993). On the structure of random plane-oriented recursive trees and their branches. Random Structures Algorithms 4, 151–176.CrossRefGoogle Scholar
Pittel, B. (1983). On distributions related to transitive closures of random finite mappings. Ann. Prob. 11, 428–441.CrossRefGoogle Scholar
Pittel, B. (1994). Note on the heights of random recursive trees and random mary search trees. Random Structures Algorithms 5, 337–347.CrossRefGoogle Scholar
Pittel, B. (2010). On a random graph evolving by degrees. Adv. Math. 223, 619–671.CrossRefGoogle Scholar