|
Lada A. Adamic, Rajan M. Lukose, Bernardo
Huberman (HP Labs) and Amit R. Puniyani (Stanford
University)
Abstract
Many communication and social networks have power-law link
distributions, containing a few nodes which have a very high
degree and many with low degree. The high connectivity nodes play
the important role of hubs in communication and networking, a fact
which can be exploited when designing efficient search algorithms.
We introduce a number of local search strategies which utilize
high degree nodes in power-law graphs and which have costs which
scale sub-linearly with the size of the graph. We also demonstrate
the utility of these strategies on the Gnutella peer-to-peer network.
Full paper: PDF
Phys. Rev. E, 64 46135 (2001)
|
printable version
