Decentralized Search in Networks Using Homophily and Degree Disparity
Abstract
We propose a new algorithm for finding a target node in a network whose topology is known only locally. We formulate this task as a problem of decision making under uncertainty and use the statistical properties of the graph to guide this decision. This formulation uses the homophily and degree structure of the network simultaneously, differentiating our algorithm from those previously proposed in the literature. Because homophily and degree disparity are characteristics frequently observed in real-world networks, the algorithm we propose is applicable to a wide variety of networks, including two families that have received much recent attention: small-world and scale-free networks.
Cite
Text
Simsek and Jensen. "Decentralized Search in Networks Using Homophily and Degree Disparity." International Joint Conference on Artificial Intelligence, 2005.Markdown
[Simsek and Jensen. "Decentralized Search in Networks Using Homophily and Degree Disparity." International Joint Conference on Artificial Intelligence, 2005.](https://mlanthology.org/ijcai/2005/simsek2005ijcai-decentralized/)BibTeX
@inproceedings{simsek2005ijcai-decentralized,
title = {{Decentralized Search in Networks Using Homophily and Degree Disparity}},
author = {Simsek, Özgür and Jensen, David D.},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2005},
pages = {304-310},
url = {https://mlanthology.org/ijcai/2005/simsek2005ijcai-decentralized/}
}