Search in power-law networks

Lada A. Adamic, Rajan M. Lukose, Amit R. Puniyani, and Bernardo A. Huberman
Phys. Rev. E 64, 046135 – Published 26 September 2001
PDFExport Citation

Abstract

Many communication and social networks have power-law link distributions, containing a few nodes that 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 that can be exploited when designing efficient search algorithms. We introduce a number of local search strategies that utilize high degree nodes in power-law graphs and that have costs scaling sublinearly with the size of the graph. We also demonstrate the utility of these strategies on the GNUTELLA peer-to-peer network.

  • Received 29 April 2001

DOI:https://doi.org/10.1103/PhysRevE.64.046135

©2001 American Physical Society

Authors & Affiliations

Lada A. Adamic1,*, Rajan M. Lukose1,†, Amit R. Puniyani2,‡, and Bernardo A. Huberman1,§

  • 1HP Labs, Palo Alto, California 94304
  • 2Department of Physics, Stanford University, 382 Via Pueblo Mall, Stanford, California 94305

  • *Email address: ladamic@hpl.hp.com
  • Email address: lukose@hpl.hp.com
  • Email address: amit8@stanford.edu
  • §Email address: huberman@hpl.hp.com

References (Subscription Required)

Click to Expand
Issue

Vol. 64, Iss. 4 — October 2001

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review E

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×