Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-10T00:51:47.912Z Has data issue: false hasContentIssue false
  • English
  • Français

Directed preferential attachment models: Limiting degree distributions and their tails

Part of: Special processes Graph theory

Published online by Cambridge University Press:  04 May 2020

Tom Britton
Tom Britton*
Affiliation:
Stockholm University
*
*Postal address: Department of Mathematics, Stockholm University, SE-106 91 Stockholm, Sweden. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The directed preferential attachment model is revisited. A new exact characterization of the limiting in- and out-degree distribution is given by two independent pure birth processes that are observed at a common exponentially distributed time T (thus creating dependence between in- and out-degree). The characterization gives an explicit form for the joint degree distribution, and this confirms previously derived tail probabilities for the two marginal degree distributions. The new characterization is also used to obtain an explicit expression for tail probabilities in which both degrees are large. A new generalized directed preferential attachment model is then defined and analyzed using similar methods. The two extensions, motivated by empirical evidence, are to allow double-directed (i.e. undirected) edges in the network, and to allow the probability of connecting an ingoing (outgoing) edge to a specified node to also depend on the out-degree (in-degree) of that node.

Keywords

Preferential attachmentdirected networkbirth processestail distribution.

MSC classification

Primary: 60K40: Other physical applications of random processes
Secondary: 05C80: Random graphs
Type
Research Papers
Information
Journal of Applied Probability , Volume 57 , Issue 1 , March 2020 , pp. 122 - 136
Copyright
© Applied Probability Trust 2020

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Barabási, A.-L. and Albert, R. (1999). Emergence of scaling in random networks. Science 286, 509–512.CrossRefGoogle ScholarPubMed
Bollobás, B., Borgs, C., Chayes, J. and Riordan, O. (2003). Directed scale-free graphs. In Proc. 14th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA ’03), 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
Dorogovtsev, S. N., Mendes, J. F. F. and Samukhin, A. N. (2000). Structure of growing networks with preferential linking. Phys. Rev. Lett. 85, 4633.CrossRefGoogle ScholarPubMed
Ethier, S. N. and Kurtz, T. G. (2005). Markov Processes: Characterization and Convergence. John Wiley, Hoboken, NJ.Google Scholar
de La Fortelle, A. (2006). Yule process sample path asymptotics. Electron. Commun. Prob. 11, 193–199.CrossRefGoogle Scholar
Leskovec, J. and Krevl, A. (2014) SNAP datasets, Stanford Large Network Dataset Collection. Available at http://snap.stanford.edu/data.Google Scholar
Samorodnitsky, G., Resnick, S. I., Towsley, D., Davis, R., Willis, A. and Wan, P. (2016). Nonstandard regular variation of in-degree and out-degree in the preferential attachment model. J. Appl. Prob. 53, 146–161.10.1017/jpr.2015.15CrossRefGoogle Scholar
Spricer, K. and Britton, T. (2015). The configuration model for partially directed graphs J. Statist. Phys. 161, 965–985.Google Scholar
Wang, T. and Resnick, S. I. (2019). Degree growth rates and index estimation in a directed preferential attachment model. To appear in Stoch. Process. Appl. Available at https://doi.org/10.1016/j.spa.2019.03.021.CrossRefGoogle Scholar