Related Experiment Videos
Search in power-law networks.
L A Adamic1, R M Lukose, A R Puniyani
1HP Labs, Palo Alto, California 94304, USA. ladamic@hpl.hp.com
Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|November 3, 2001
Summary
This study introduces efficient local search strategies for power-law networks by leveraging high-degree hub nodes. These methods offer sublinear scaling costs, improving search performance in large networks like Gnutella.
Area of Science:
- Network Science
- Computer Science
- Algorithm Design
Background:
- Many real-world networks, including social and communication systems, exhibit power-law distributions.
- These networks feature a few high-degree nodes (hubs) and numerous low-degree nodes.
- Hubs are critical for network connectivity and efficient information flow.
Purpose of the Study:
- To develop novel local search strategies that exploit the properties of hubs in power-law networks.
- To design algorithms with search costs that scale sublinearly with network size.
- To validate the effectiveness of these strategies on a practical peer-to-peer network.
Main Methods:
- Introduction of local search algorithms tailored for power-law graph structures.
- Analysis of algorithm costs to demonstrate sublinear scaling.
- Empirical evaluation using the Gnutella peer-to-peer network dataset.
Main Results:
- Proposed local search strategies effectively utilize high-degree nodes.
- Achieved sublinear cost scaling, indicating efficiency for large networks.
- Demonstrated practical utility and performance on the Gnutella network.
Conclusions:
- Leveraging hub nodes in power-law networks enables efficient search algorithms.
- The developed strategies offer a scalable approach for network searching.
- These findings have implications for designing efficient search mechanisms in distributed systems.