title: Search in power-law networks.
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.
authors.affiliation: HP Labs, Palo Alto, California 94304, USA. ladamic@hpl.hp.com
authors.forename: L A
authors.initials: LA
authors.lastname: Adamic
authors.forename: R M
authors.initials: RM
authors.lastname: Lukose
authors.forename: A R
authors.initials: AR
authors.lastname: Puniyani
authors.forename: B A
authors.initials: BA
authors.lastname: Huberman