Decentralized Search in Networks Using Homophily and Degree Disparity
Simsek, Ö. and D. Jensen (2005). Decentralized search in networks using homophily and degree disparity. Proceedings of the 19th International Joint Conference on Artificial Intelligence.
- 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.
- Text
- A PDF version of this paper is available.
Fineprint