The influence of search engines on preferential attachment

Abstract

There is much current interest in the evolution of social networks, especially, the Web graph, through time. "Preferential attachment" and the "copying model" are well-known models which explain the observed degree distribution of the Web graph reasonably closely. We claim that the presence of highly popular search engines like Google substantially mediate the act of hyperlink creation by limiting the author's attention to a small set of "celebrity" URLs. Page authors (who are also Web surfers) frequently (with probability p) locate pages using a search engine. Then they link to popular pages among those they visit. We initiate an analysis of this more realistic process and show that the celebrity nodes eventually accumulate a constant fraction of all links created whp, and that the degrees of the other nodes still follow a power-law distribution, but with a steeper power: Pr(degree = k) ∝ k^-0+2/(1-p)) whp. Our analysis adds evidence to the recent concern that search engines offer new Web pages a steep, selfsustaining barrier to entry to well-connected, entrenched Web communities.