Search in Power-Law Networks
<|reference_start|>Search in Power-Law Networks: 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.<|reference_end|>
@article{adamic2001search,
    title={Search in Power-Law Networks},
    author={L. A. Adamic (1), R. M. Lukose (2), A. R. Puniyani (1), B. A. Huberman
  (2) ((1) Stanford University, (2) HP Sand Hill Labs, Palo Alto, CA)},
    journal={Phys. Rev. E 64, 046135 (2001)},
    year={2001},
    doi={10.1103/PhysRevE.64.046135},
    archivePrefix={arXiv},
    eprint={cs/0103016},
    primaryClass={cs.NI cond-mat.dis-nn cond-mat.stat-mech cs.PF}
}