A stochastic model for the evolution of the Web allowing link deletion

ABSTRACT

Recently several authors have proposed stochastic evolutionary models for the growth of the Web graph and other networks that give rise to power-law distributions. These models are based on the notion of preferential attachment, leading to the “rich get richer” phenomenon. We present a generalization of the basic model by allowing deletion of individual links and show that it also gives rise to a power-law distribution. We derive the mean-field equations for this stochastic model and show that, by examining a snapshot of the distribution at the steady state of the model, we are able to determine the extent to which link deletion has taken place and estimate the probability of deleting a link. Applying our model to actual Web graph data provides evidence of the extent to which link deletion has occurred. We also discuss a problem that frequently arises in estimating the power-law exponent from empirical data and a few possible methods for dealing with this, indicating our preferred approach. Using this approach our analysis of the data suggests a power-law exponent of approximately 2.15 for the distribution of inlinks in the Web graph, rather than the widely published value of 2.1.

REFERENCES

• 1: Lada A. Adamic , Bernardo A. Huberman, The Web's hidden order, Communications of the ACM, v.44 n.9, p.55-60, Sept. 2001 [doi>10.1145/383694.383707]
• 2: Albert, R. and Barabási, A.-L. 2002. Statistical mechanics of complex networks. Rev. Mod. Phys. 74, 47--97.
• 3: Barabási, A.-L. and Albert, R. 1999. Emergence of scaling in random networks. Science 286, 509--512.
• 4: Bornholdt, S. and Ebel, H. 2001. World Wide Web scaling exponent from Simon's 1955 model. Phys. Rev. E 64, 035104-1--035104-4.
• 5: 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
• 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: Stephen Dill , Ravi Kumar , Kevin S. Mccurley , Sridhar Rajagopalan , D. Sivakumar , Andrew Tomkins, Self-similarity in the web, ACM Transactions on Internet Technology (TOIT), v.2 n.3, p.205-223, August 2002 [doi>10.1145/572326.572328]
• 8: Dorogovtsev, S. and Mendes, J. 2001. Scaling properties of scale-free evolving networks: Continuous approach. Phys. Rev. E 35, 056125.
• 9: Dorogovtsev, S. and Mendes, J. 2002. Evolution of networks. Adv. Phys. 51, 1079--1187.
• 10: Drees, H., de Haan, L., and Resnick, S. 2000. How to make a Hill plot. Ann. Stat. 28, 254--274.
• 11: Fenner, T., Levene, M., and Loizou, G. 2005. A stochastic evolutionary model exhibiting power-law behaviour with an exponential cutoff. Physica A 335, 641--656.
• 12: Krapivsky, P. and Redner, S. 2002. A statistical physics perspective on Web growth. Comput. Netw. 39, 261--276.
• 13: Levene, M., Fenner, T., Loizou, G., and Wheeldon, R. 2002. A stochastic model for the evolution of the Web. Comput. Netw. 39, 277--287.
• 14: Newman, M. 2003. The structure and function of complex networks. SIAM Rev. 45, 167--256.
• 15: Nicholls, P. 1989. Bibliometric modeling processes and the empirical validity of Lotka's law. J. Amer. Soc. Inform. Sci. 40, 379--385.
• 16: Notess, G. 2002. The wayback machine: The Web's archive. Online 26, 59--61.
• 17: Pennock, D., Flake, G., Lawrence, S., Glover, E., and Giles, C. 2002. Winners don't take all: Characterizing the competition for links on the web. Proc. Nat. Acad. Sci. U.S.A. 99, 5207--5211.
• 18: Sheldon M. Ross, Introduction to Stochastic Dynamic Programming: Probability and Mathematical, Academic Press, Inc., Orlando, FL, 1983
• 19: Schroeder, M. 1991. Fractals, Chaos, Power Laws: Minutes from an Infinite Paradise. W. H. Freeman, New York, NY.
• 20: Simon, H. 1955. On a class of skew distribution functions. Biometrika 42, 425--440.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General

General Terms:
Measurement, Theory

Keywords:
Power-law distribution, Web graph, evolutionary models, link deletion, preferential attachment