Description
For the simple case, nodes are never deleted. At each step we create a new node with a single edge emanating from it. Let u be a page chosen uniformly at random from the pages in existence before this step.
(I) With probability, the only parameter of the model, the new edge points to u.
(II) With probability, the new edge points to the destination of u's (sole) out-link; the new node attains its edge by copying.
The second process increases the probability of high-degree nodes' receiving new incoming edges. In fact, since u is selected randomly, the probability that a webpage with degree will receive a new hyperlink is proportional with, indicating that the copying mechanism effectively amounts to a linear preferential attachment. Kumar et al. prove that the expectation of the incoming degree distribution is, thus follows a power-law with an exponent which varies between 2 (for ) and (for ).
Above is the linear growth copying model. Since the web is currently growing exponentially, there is the exponential growth copying model. At each step a new epoch of vertices arrives whose size is a constant fraction of the current graph. Each of these vertices may link only to vertices from previous epochs.
The evolving models above are by no means complete. They can be extended in several ways. First of all, the tails in the models are either static, chosen uniformly from the new vertices, or chosen from the existing vertices proportional to their out-degrees. This process could be made more sophisticated to account for the observed deviations of the out-degree distribution from the power-law distribution. Similarly, the models can be extended to include death processes, which cause vertices and edges to disappear as time evolves. A number of other extensions are possible, but we seek to determine the properties of this simple model, in order to understand which extensions are necessary to capture the complexity of the web.
Read more about this topic: Copying Mechanism
Famous quotes containing the word description:
“He hath achieved a maid
That paragons description and wild fame;
One that excels the quirks of blazoning pens.”
—William Shakespeare (1564–1616)
“I was here first introduced to Joe.... He was a good-looking Indian, twenty-four years old, apparently of unmixed blood, short and stout, with a broad face and reddish complexion, and eyes, methinks, narrower and more turned up at the outer corners than ours, answering to the description of his race. Besides his underclothing, he wore a red flannel shirt, woolen pants, and a black Kossuth hat, the ordinary dress of the lumberman, and, to a considerable extent, of the Penobscot Indian.”
—Henry David Thoreau (1817–1862)
“I fancy it must be the quantity of animal food eaten by the English which renders their character insusceptible of civilisation. I suspect it is in their kitchens and not in their churches that their reformation must be worked, and that Missionaries of that description from [France] would avail more than those who should endeavor to tame them by precepts of religion or philosophy.”
—Thomas Jefferson (1743–1826)