Evolution of page popularity under random web graph models

ABSTRACT

The link structure of the Web can be viewed as a massive graph. The preferential attachment model and its variants are well-known random graph models that help explain the evolution of the web graph. However, those models assign more links to older pages without reference to the quality of web pages, which does not capture the real-world evolution of the web graph and renders the models inappropriate for studying the popularity evolution of new pages.We extend the preferential attachment model with page quality, where the probability of a page getting new links depends not only on its current degree but also on its quality. We study the distribution of degrees among different quality values, and prove that under discrete quality distributions, the degree sequence still follows a power law distribution. Then we use the model to study the evolution of page popularity. We show that for pages with the same quality, the older pages are more popular; if a younger page is better than an older page, then eventually the younger-and-better page will become more popular. We also use the model to study a randomized ranking scheme proposed earlier [18] and show that it accelerates popularity evolution of new pages.

REFERENCES

• 1: A-L. Barabasi and R. Albert. Emergence of scaling in random networks. Science, 286(15), pp. 509--512, 1999.
• 2: G.Bianconi and A-L. Barabasi. Competition and Multiscaling in evolving Networks. Europhysics Letters, 54(4), pp. 436--442, 2001.
• 3: 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
• 4: S. Brin, R. Motwani, L. Page, and T. Winograd. What can you do with a Web in your Pocket? Data Engineering Bulletin, 21: 37--47, 1998.
• 5: B. Bollobas and O. Riordan. Robustness and vulnerability of scale-free random graphs. Internet Mathematics, 1: 1--35, 2003.
• 6: Colin Cooper , Alan Frieze, A general model of web graphs, Random Structures & Algorithms, v.22 n.3, p.311-335, May 2003 [doi>10.1002/rsa.10084]
• 7: C. Cooper, A. Frieze and J. Vera. Random deletion in a scale-free random graph process. Internet Mathematics, 1: 463--483, 2003.
• 8: Soumen Chakrabarti , Alan Frieze , Juan Vera, The influence of search engines on preferential attachment, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 9: Junghoo Cho , Sourashis Roy, Impact of search engines on page popularity, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988676]
• 10: Junghoo Cho , Sourashis Roy , Robert E. Adams, Page quality: in search of an unbiased web ranking, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066220]
• 11: E. Drinea, M. Enachescu and M. Mitzenmacher. Variations on random graph models of the Web. Harvard Computer Science Technical Report TR-06-01.
• 12: Eleni Drinea , Alan Frieze , Michael Mitzenmacher, Balls and bins models with feedback, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.308-315, January 06-08, 2002, San Francisco, California
• 13: J. Kleinberg, R. Kumar, P. Raghavan, S. Rajagopalan and A.S. Tomkins. The Web as a Graph: measurements, models and methods. Proceedings of the 5th Annual International Conference on Computing and Combinatorics, 1999.
• 14: 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
• 15: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 16: L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank Citation Ranking: Bringing Order to the Web. Technical Report, Stanford Digital Libraries, 1998.
• 17: Gopal Pandurangan , Prabhakar Raghavan , Eli Upfal, Using PageRank to Characterize Web Structure, Proceedings of the 8th Annual International Conference on Computing and Combinatorics, p.330-339, August 15-17, 2002
• 18: Sandeep Pandey , Sourashis Roy , Christopher Olston , Junghoo Cho , Soumen Chakrabarti, Shuffling a stacked deck: the case for partially randomized ranking of search engine results, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.m MISCELLANEOUS

General Terms:
Theory

Keywords:
page popularity, random graph, web graph