Phys. Rev. E 64, 046135 (2001) [8 pages]Search in power-law networks
Lada A. Adamic1 *, Rajan M. Lukose1 †, Amit R. Puniyani2 ‡, and Bernardo A. Huberman1 § Received 29 April 2001; revised 22 June 2001; published 26 September 2001 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. ©2001 The American Physical Society
URL: http://link.aps.org/abstract/PRE/v64/e046135
* Email address: ladamic@hpl.hp.com
[ Abstract | Previous article | Next article | Issue 4 ] |
A new free weekly publication from APS 
Read the latest from Physics:
Viewpoint: Undoing a quantum measurement
This Week's Milestone Letters are from 1994: |
About PROLA | Terms and Conditions | Subscriptions | Search | Help
Content in PROLA © 2008 by The American Physical Society All rights reserved. PROLA™ is a trademark of The American Physical Society. Use of APS online journals implies that the user has read and agrees to the Terms and Conditions in the Subscription Agreement.