1. Search in Power-Law Networks
- Author
-
Adamic, L. A., Lukose, R. M., Puniyani, A. R., and Huberman, B. A.
- Subjects
Computer Science - Networking and Internet Architecture ,Condensed Matter - Disordered Systems and Neural Networks ,Condensed Matter - Statistical Mechanics ,Computer Science - Performance ,C.2.1 - Abstract
Many communication and social networks have power-law link distributions, containing a few nodes which 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 which can be exploited when designing efficient search algorithms. We introduce a number of local search strategies which utilize high degree nodes in power-law graphs and which have costs which scale sub-linearly with the size of the graph. We also demonstrate the utility of these strategies on the Gnutella peer-to-peer network., Comment: 17 pages, 14 figures
- Published
- 2001
- Full Text
- View/download PDF