Decentralized Search in Networks Using Homophily and Degree Disparity

Özgür Simsek, David D. JensenIJCAI 2005 · OpenReview

Introduction

Decentralized search is the challenge of finding a target node in a large network using only local information. This problem, famously illustrated by the "Small World" experiment, is critical in fields ranging from social network analysis to distributed computing. Traditional search strategies typically rely on one of two heuristics: homophily (moving toward nodes similar to the target) or degree (moving toward high-connectivity hubs). However, real-world networks often exhibit both structures, and single-heuristic methods frequently fail or prove inefficient.

The Expected-Value Navigation (EVN) Algorithm

This paper introduces Expected-Value Navigation (EVN), a probabilistic approach that treats decentralized search as a decision-making task under uncertainty. Unlike previous methods that prioritize either similarity or degree, EVN integrates both by estimating the probability $p_{st}$ that a neighbor $s$ is directly connected to the target $t$.

The algorithm calculates this probability using the formula: $$p_{st} = 1 - (1 - q_{st})^k$$ where $q_{st}$ represents the probability of a single link from $s$ reaching $t$ based on their similarity, and $k$ is the degree of neighbor $s$. This formulation allows EVN to naturally balance its search: a neighbor is prioritized if it is either highly similar to the target or possesses a sufficiently high degree to likely bridge the gap.

Experimental Evaluation

The researchers evaluated EVN against traditional similarity-based, degree-based, and random search methods using both synthetic and real-world datasets:

  • Synthetic Networks: Scale-free networks (characterized by massive hubs) and Poisson networks (more uniform degree distributions) were tested across a range of homophily parameters.
  • Real-World Citation Network: A graph of 833 scientific papers from the arXiv hep-th section, where similarity was derived from TF-IDF analysis of titles and abstracts.

Results and Discussion

EVN demonstrated significant performance gains across all tested scenarios. In synthetic scale-free networks, EVN maintained a success rate near 100%, even as traditional methods faltered under varying homophily conditions.

Success rate of different search strategies as a function of the homophily parameter.

Beyond success rates, EVN proved highly efficient in terms of path length. In the arXiv citation graph, EVN achieved a 99% success rate with a median path length of just 4 hops, closely approaching the theoretical optimal path length.

Mean path length of successful searches, showing EVN's efficiency relative to other methods.

The results highlight that degree and similarity are complementary features. Hubs facilitate rapid traversal across the network, while homophily enables precise "zooming in" once the search is in the target's vicinity. EVN's robustness is particularly evident in Poisson networks, where the absence of major hubs causes degree-based methods to fail, yet EVN remains effective by leveraging similarity.

Conclusion

Expected-Value Navigation provides a robust framework for decentralized search by effectively combining structural and attribute-based information. By requiring only local knowledge and a general statistical understanding of the network's construction, EVN offers a practical and near-optimal solution for navigating complex real-world graphs. Future research may focus on dynamic estimation of network properties to allow the algorithm to adapt to entirely unknown environments.

Summary updated

BibTeX
@inproceedings{simsek2005decentralized,
  author = {Özgür Simsek and David D. Jensen},
  title = {{Decentralized Search in Networks Using Homophily and Degree Disparity}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
  url = {https://openreview.net/forum?id=rOjepM0Rqz_},
}
Figure