Phys. Rev. E 64, 046135 (2001) [8 pages]Search in power-law networksReceived 29 April 2001; revised 22 June 2001; published 26 September 2001 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. © 2001 The American Physical Society URL:
http://link.aps.org/doi/10.1103/PhysRevE.64.046135
DOI:
10.1103/PhysRevE.64.046135
PACS:
89.75.Fb, 05.50.+q, 05.40.-a, 89.75.Da
|
|
About | Terms and Conditions | Subscriptions | Search | Help
Use of the American Physical Society websites and journals implies that the user has read and agrees to our Terms and Conditions and any applicable Subscription Agreement. Physical Review®, Physical Review Letters®, Reviews of Modern Physics®, and Physical Review Special Topics® are trademarks of the American Physical Society.