Jump to content United States-English
HP.com Home Products and Services Support and Drivers Solutions How to Buy
» Contact HP

hp.com home

Search in Power-Law Networks

printable version

HP Labs

» Research
» News and events
» Technical reports
» About HP Labs
» Careers @ HP Labs
» Worldwide sites
» Downloads
Content starts here

Lada A. Adamic, Rajan M. Lukose, Bernardo Huberman (HP Labs) and Amit R. Puniyani (Stanford University)


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)

» Information Dynamics Lab

» Research areas
» Results
» People
Finland: a cyberview, by Lada A. Adamic, 2000.
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.