Search in power-law networks

✍ Scribed by Adamic, Lada A.; Lukose, Rajan M.; Puniyani, Amit R.; Huberman, Bernardo A.

• Book ID: 125529308
• Publisher: The American Physical Society
• Year: 2001
• Tongue: English
• Weight: 431 KB
• Volume: 64
• Category: Article
• ISSN: 1063-651X
• DOI: 10.1103/PhysRevE.64.046135

✦ Synopsis

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.