The power of choice combined with preferential attachement

Yury Malyshkin (Moscow State University)
Elliot Paquette (Weizmann Institute of Science)

Abstract


We prove almost sure convergence of the maximum degree in an evolving tree model combining local choice and preferential attachment. At each step in the growth of the graph, a new vertex is introduced. A fixed, finite number of possible neighbors are sampled from the existing vertices with probability proportional to degree. Of these possibilities, the new vertex attaches to the vertex from the sample that has the highest degree. The maximal degree in this model has linear or near-linear behavior. This behavior contrasts sharply with the behavior in the same choice model with uniform attachment as well as the preferential attachment model without choice. The proof is based on showing the tree has a persistent hub by comparison with the standard preferential attachment model, as well as martingale and stochastic approximation arguments.


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

Pages: 1-13

Publication Date: July 12, 2014

DOI: 10.1214/ECP.v19-3461

References

  • Barabasi, Albert-Laszlo; Albert, Reka. Emergence of scaling in random networks. Science 286 (1999), no. 5439, 509--512. MR2091634
  • Benaim, Michel. Dynamics of stochastic approximation algorithms. Seminaire de Probabilites, XXXIII, 1--68, Lecture Notes in Math., 1709, Springer, Berlin, 1999. MR1767993
  • Chen, May-Ru; Wei, Ching-Zong. A new urn model. J. Appl. Probab. 42 (2005), no. 4, 964--976. MR2203815
  • Dereich, Steffen; Morters, Peter. Random networks with sublinear preferential attachment: degree evolutions. Electron. J. Probab. 14 (2009), no. 43, 1222--1267. MR2511283
  • Dommers, Sander; van der Hofstad, Remco; Hooghiemstra, Gerard. Diameters in preferential attachment models. J. Stat. Phys. 139 (2010), no. 1, 72--107. MR2602984
  • D'Souza, R. M.; Krapivsky, P. L.; Moore, C. The power of choice in growing trees. Eur. Phys. J. B 59 (2007), no. 4, 535--543. MR2358054
  • Flaxman, Abraham; Frieze, Alan; Fenner, Trevor. High degree vertices and eigenvalues in the preferential attachment graph. Internet Math. 2 (2005), no. 1, 1--19. MR2166274
  • Galashin, P. A., phExistence of a persistent hub in the convex preferential attachment model, arXiv:1310.7513.
  • Krapivsky, P. L. and Redner, S., phChoice-Driven Phase Transition in Complex Networks, arXiv:1312.7803.
  • Krapivsky, P. L., Redner, S., and Leyvraz, F. phConnectivity of growing random networks, Phys. Rev. Lett. 85 (2000), 4629--4632, URL: doi:10.1103/PhysRevLett.85.4629.
  • Kuba, Markus; Mahmoud, Hosam; Panholzer, Alois. Analysis of a generalized Friedman's urn with multiple drawings. Discrete Appl. Math. 161 (2013), no. 18, 2968--2984. MR3126664
  • Kushner, Harold J.; Clark, Dean S. Stochastic approximation methods for constrained and unconstrained systems. Applied Mathematical Sciences, 26. Springer-Verlag, New York-Berlin, 1978. x+261 pp. ISBN: 0-387-90341-0 MR0499560
  • Malyshkin, Y. and Paquette, E., phThe power of 2 choices over preferential attachment, arXiv:1311.1091.
  • bysame, phThe power of choice combined with preferential attachment, arXiv:1403.4301v1.
  • Mori, Tamas F. The maximum degree of the Barabasi-Albert random tree. Combin. Probab. Comput. 14 (2005), no. 3, 339--348. MR2138118
  • Peköz, E. A., Ross, N., and Röllin, A., phJoint degree distributions of preferential attachment random graphs, arXiv:1402.4686.
  • Pemantle, Robin. A survey of random processes with reinforcement. Probab. Surv. 4 (2007), 1--79. MR2282181
  • Robbins, Herbert; Monro, Sutton. A stochastic approximation method. Ann. Math. Statistics 22, (1951). 400--407. MR0042668
Bookmark and Share


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