A Stochastic Evolutionary Model Exhibiting Power-Law Behaviour with an Exponential Cutoff

Preprint
Publisher Website
Google Scholar
  • 19 September 2002
Abstract
Recently several authors have proposed stochastic evolutionary models for the growth of the Web graph and other graphs that give rise to power-law distributions. These models are based on the notion of preferential attachment leading to the ``rich get richer'' phenomenon. Despite the generality of the proposed stochastic models, there are still some unexplained phenomena, which may arise due to the limited size of networks such as the World-Wide-Web. Such networks may in fact exhibit an exponential cutoff in the power-law scaling, although this cutoff may only be observable in the tail of the distribution for extremely large networks. We propose a modification of the basic stochastic model, so that after, for example, a Web page is chosen preferentially, say according to the number of its outlinks, there is a small probability that this page will be discarded. We show that as a result of this modification, by viewing the stochastic process in terms of an urn transfer model, we obtain a power-law distribution with an exponential cutoff. Unlike many other models, the current model can capture instances where the exponent of the distribution is less than or equal to two. As a proof of concept, we demonstrate the consistency of our model with empirical findings regarding collaboration graphs whose distributions are known to follow power-laws with exponential cutoff.

This publication has 0 references indexed in Scilit: