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

hp.com home

Local Search in Unstructured 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 A. Huberman

HP Laboratories
Palo Alto, CA 94304


We discuss a number of message-passing algorithms that can be efficiently used to search through power-law networks. Most of these algorithms are meant to be improvements for peer-to-peer file sharing systems, and some may also shed some light on how unstructured social networks with certain topologies might function relatively efficiently with local information. Like the networks that they are designed for, these algorithms are completely decentralized, and they exploit the power-law link distribution in the node degree. We demonstrate that some of these search algorithms can work well on real Gnutella networks, scale sub-linearly with the number of nodes, and may help reduce the network search traffic that tends to cripple such networks.

Full paper: reviewchap.pdf

To appear in: 'Handbook of Graphs and Networks:
From the Genome to the Internet', S. Bornholdt and H.G. Schuster (eds.), Wiley-VCH, Berlin, 2002.

» Information Dynamics Lab

» Research areas
» Results
» People
The Stanford Social Network, by Lada Adamic and Eytan Adar
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.