Search in power-law networks - art. no. 046135

Many communication and social networks have power-law link distributions, c ontaining 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 communicat ion and networking, a fact that can be exploited when designing efficient s earch algorithms. We introduce a number of local search strategies that uti lize high degree nodes in power-law graphs and that have costs scaling subl inearly with the size of the graph. We also demonstrate the utility of thes e strategies on the GNUTELLA peer-to-peer network.