First to market is not everything: an analysis of preferential attachment with fitness

ABSTRACT

The design of algorithms on complex networks, such as routing, ranking or recommendation algorithms, requires a detailed understanding of the growth characteristics of the networks of interest, such as the Internet,the web graph, social networks or online communities. To this end, preferential attachment, in which the popularity (or relevance) of a node is determined by its degree, is a well-known and appealing random graph model, whose predictions are in accordance with experiments on the web graph and several social networks. However, its central assumption, that the popularity of the nodes dependsonly on their degree, is not a realistic one, since every node has potentially some intrinsic quality which can differentiate its attractiveness from other nodes with similar degrees.

In this paper, we provide a rigorous analysis of preferential attachment with fitness, suggested by Bianconi and Barabási and studied by Motwani and Xu, in which the degree of a vertex is scaled by its quality to determine its attractiveness. Including quality considerations in the classical preferential attachment model provides a much more realistic description of many complex networks, such as the web graph, and allows toobserve a much richer behavior in the growth dynamics of these networks. Specifically, depending on the shape of the distributionfrom which the qualities of the vertices are drawn, we observe three distinct phases, namely a first-mover-advantage phase, afit-get-richer phase and an innovation-pays-offphase. We precisely characterize the properties of the quality distribution that result in each of these phases and we computethe exact growth dynamics for each phase. The dynamics provide rich information about the quality of the vertices, which can bevery useful in many practical contexts, including ranking algorithms for the web, recommendation algorithms, as well as thestudy of social networks.

REFERENCES

• 1: K.B. Athreya and P.E. Ney. Branching processes. Springer-Verlag, New York, 1972. Die Grundlehren der mathematischen Wissenschaften, Band 196.
• 2: Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286:509--512, 1999.
• 3: Noam Berger , Christian Borgs , Jennifer T. Chayes , Amin Saberi, On the spread of viruses on the internet, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 4: Ginestra Bianconi and Albert-László Barabási. Bose-einstein condensation in complex networks. Phys. Rev. Lett., 86(24):5632--5635, Jun 2001.
• 5: Béla Bollobás , Christian Borgs , Jennifer Chayes , Oliver Riordan, Directed scale-free graphs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 6: Bélaa Bollobás , Oliver Riordan, The Diameter of a Scale-Free Random Graph, Combinatorica, v.24 n.1, p.5-34, January 2004 [doi>10.1007/s00493-004-0002-2]
• 7: Béla Bollobás , Oliver Riordan , Joel Spencer , Gábor Tusnády, The degree sequence of a scale-free random graph process, Random Structures & Algorithms, v.18 n.3, p.279-290, May 2001 [doi>10.1002/rsa.1009]
• 8: Andrei Broder , Ravi Kumar , Farzin Maghoul , Prabhakar Raghavan , Sridhar Rajagopalan , Raymie Stata , Andrew Tomkins , Janet Wiener, Graph structure in the Web, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.33 n.1-6, p.309-320, June 2000
• 9: Colin Cooper and Alan Frieze. A general model of web graphs, 2001.
• 10: Derek J. de~Solla~Price. Networks of scientific papers. Science, 149(3683):510--515, July 30 1965.
• 11: Eleni Drinea, Mihaela Enachescu, and Michael Mitzenmacher. Variations on random graph models for the Web. Technical Report TR--06--01, Harvard University, 2001.
• 12: Michalis Faloutsos , Petros Faloutsos , Christos Faloutsos, On power-law relationships of the Internet topology, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.251-262, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 13: Abraham Flaxman, Alan M. Frieze, and Trevor I. Fenner. High degree vertices and eigenvalues in the preferential attachment graph. In RANDOM-APPROX, pages 264--274, 2003.
• 14: Nigel Gilbert. A simulation of the structure of academic science. Sociological Research Online, 2(2), 1997.
• 15: Svante Janson. Functional limit theorems for multitype branching processes and generalized Pólya urns. Stochastic Process. Appl., 110(2):177--245, 2004.
• 16: Jon Kleinberg. The emerging intersection of social and technological networks: Open questions and algorithmic challenges. In FOCS, 2006.
• 17: Jon M. Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins. The web as a graph: Measurements, models, and methods. In COCOON, pages 1--17, 1999.
• 18: P.L. Krapivsky and S. Redner. Organization of grwoing random networks. Physical Review E, 63(6):066123--1--066123--14, June 2001.
• 19: R. Kumar , P. Raghavan , S. Rajagopalan , D. Sivakumar , A. Tomkins , E. Upfal, Stochastic models for the Web graph, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.57, November 12-14, 2000
• 20: A.J. Lotka. The frequency distribution of scientific productivity. Journal of the Washington Academy of Science, 16(12):317--323, June 19 1926.
• 21: Michael Mitzenmacher. A brief history of generative models for power law and lognormal distributions. Internet Math., 1(2):226--251, 2004.
• 22: Rajeev Motwani , Ying Xu, Evolution of page popularity under random web graph models, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142372]
• 23: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 24: Prabhakar Raghavan, The changing face of web search: algorithms, auctions and advertising, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132535]
• 25: Herbert A. Simon. On a class of skew distribution functions. Biometrika, 42(4):425--440, December 1955.
• 26: G. Yule. A mathematical theory of evolution based on the conclusions of dr. j.c. willis. F.R.S. Philosophical Transactions of the Royal Society of London, 213(B):21--87, 1925.
• 27: George K. Zipf. Human Behavior and The Principles of Least Effort. Addison Wesley, Cambridge, MA, 1949.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

General Terms:
Theory

Keywords:
Bose-Einstein condensation, Pólya urns, preferential attachment, random graphs