Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-14T07:29:14.506Z Has data issue: false hasContentIssue false
  • English
  • Français

Coexistence in Preferential Attachment Networks

Part of: Combinatorial probability Stochastic processes Graph theory

Published online by Cambridge University Press:  09 February 2016

TONĆI ANTUNOVIĆ ,
ELCHANAN MOSSEL  and
MIKLÓS Z. RÁCZ
TONĆI ANTUNOVIĆ
Affiliation:
University of California, Los Angeles, CA 90025, USA (e-mail: [email protected])
ELCHANAN MOSSEL
Affiliation:
The Wharton School of the University of Pennsylvania, Philadelphia, PA 19104, USA and University of California, Berkeley, CA 94720, USA (e-mail: [email protected])
MIKLÓS Z. RÁCZ
Affiliation:
University of California, Berkeley, CA 94720, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce a new model of competition on growing networks. This extends the preferential attachment model, with the key property that node choices evolve simultaneously with the network. When a new node joins the network, it chooses neighbours by preferential attachment, and selects its type based on the number of initial neighbours of each type. The model is analysed in detail, and in particular, we determine the possible proportions of the various types in the limit of large networks. An important qualitative feature we find is that, in contrast to many current theoretical models, often several competitors will coexist. This matches empirical observations in many real-world networks.

MSC classification

Primary: 05C80: Random graphs
Secondary: 60C05: Combinatorial probability 60G99: None of the above, but in this section
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 25 , Issue 6 , November 2016 , pp. 797 - 822
Copyright
Copyright © Cambridge University Press 2016 

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

[1] Antunović, T., Dekel, Y., Mossel, E. and Peres, Y. (2011) Competing first passage percolation on random regular graphs. arXiv:1109.2575 Google Scholar
[2] Arthur, W. B. (1990) Positive feedbacks in the economy. Sci. Am. 262 92–99.Google Scholar
[3] Arthur, W. B. (1994) Increasing Returns and Path Dependence in the Economy, The University of Michigan Press.Google Scholar
[4] Banerjee, A. and Fudenberg, D. (2004) Word-of-mouth learning. Game. Econ. Behav. 46 1–22.Google Scholar
[5] Barabási, A. L. and Albert, R. (1999) Emergence of scaling in random networks. Science 286 (5439) 509–512.Google Scholar
[6] Barrat, A., Barthélemy, M. and Vespignani, A. (2008) Dynamical Processes on Complex Networks, Cambridge University Press.Google Scholar
[7] Benaïm, M. (1999) Dynamics of stochastic approximation algorithms. In Séminaire de Probabilités XXXIII, Vol. 1709 of Lecture Notes in Mathematics, Springer, pp. 1–68.Google Scholar
[8] Benaïm, M., Benjamini, I., Chen, J. and Lima, Y. (2015) A generalized Pólya's urn with graph based interactions. Random Struct. Alg. 46 614–634.Google Scholar
[9] Benaïm, M. and Hirsch, M. W. (1996) Asymptotic pseudotrajectories and chain recurrent flows, with applications. J. Dynam. Differential Equations 8 141–176.Google Scholar
[10] 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.Google Scholar
[11] Bollobás, B. and Riordan, O. (2004) The diameter of a scale-free random graph. Combinatorica 24 5–34.Google Scholar
[12] Deijfen, M. and van der Hofstad, R. (2013) The winner takes it all. arXiv:1306.6467.Google Scholar
[13] Gross, T. and Blasius, B. (2008) Adaptive coevolutionary networks: A review. J. Roy. Soc. Interface 5 259–271.Google Scholar
[14] Hill, B. M., Lane, D. and Sudderth, W. (1980) A strong law for some generalized urn processes. Ann. Probab. 8 214–226.Google Scholar
[15] Hirsch, M. W., Smale, S. and Devaney, R. L. (2004) Differential Equations, Dynamical Systems, and An Introduction to Chaos, Academic Press.Google Scholar
[16] Holme, P. and Saramäki, J. (2012) Temporal networks. Phys. Rep. 519 97–125.CrossRefGoogle Scholar
[17] Lelarge, M. (2012) Diffusion and cascading behavior in random networks. Games and Economic Behavior 75 752–775.Google Scholar
[18] Nevelson, M. B. and Hasminskii, R. Z. (1976) Stochastic Approximation and Recursive Estimation , Vol. 47 of Translations of Mathematical Monographs, AMS.Google Scholar
[19] Ohtsuki, H., Hauert, C., Lieberman, E. and Nowak, M. A. (2006) A simple rule for the evolution of cooperation on graphs and social networks. Nature 441 (7092) 502–505.Google Scholar
[20] Pastor-Satorras, R. and Vespignani, A. (2001) Epidemic spreading in scale-free networks. Phys. Rev. Lett. 86 3200–3203.Google Scholar
[21] Pemantle, R. (1990) A time-dependent version of Pólya's urn. J. Theoret. Probab. 3 627–637.Google Scholar
[22] Pemantle, R. (1990) Non-convergence to unstable points in urn models and stochastic approximations. Ann. Probab. 18 698–712.Google Scholar
[23] Pemantle, R. (1991) When are touchpoints limits for generalized Pólya urns? Proc. Amer. Math. Soc. 113 235–243.Google Scholar
[24] Pemantle, R. (2007) A survey of random processes with reinforcement. Probab. Surv. 4 1–79.Google Scholar
[25] Prakash, B. A., Beutel, A., Rosenfeld, R. and Faloutsos, C. (2012) Winner takes all: competing viruses or ideas on fair-play networks. In Proc. 21st Int. Conf. World Wide Web (WWW), ACM, pp. 1037–1046.Google Scholar
[26] Redner, S. (1998) How popular is your paper? An empirical study of the citation distribution. Eur. Phys. J. B 4 131–134.Google Scholar
[27] Robbins, H. and Monro, S. (1951) A stochastic approximation method. Ann. Math. Statist. 22 400–407.Google Scholar
[28] Shaked, M. and Shanthikumar, J. G. (2007) Stochastic Orders, Springer.Google Scholar
[29] Skyrms, B. and Pemantle, R. (2000) A dynamic model of social network formation. Proc. Nat. Acad. Sci. USA 97 9340–9346.Google Scholar
[30] Watts, D. J. (2002) A simple model of global cascades on random networks. Proc. Nat. Acad. Sci. USA 99 5766–5771.Google Scholar