Search in Power-Law Node Degree Networks

摘要

Graphs in which decentralized algorithms can find short paths efficiently by considering only local information are known as Searchable Networks [4], [5]. Jon Kleinberg studied decentralized search in a subtle variant of the Watts-Strogatz model [3] and showed that the structure of searchable networks has to meet some strict requirements [5]. The aim of this paper is to investigate how it would be decentralized search in small- world models which combine wide variation in node degrees with some kind of spatial embedding. Through simulations, we evaluate the performance of a decentralized greedy algorithm and compare its efficiency versus Kleinberg's results. Our results indicates that networks with wide variation in node degrees can allow decentralized algorithms to achieve better average delivery times than the ones obtained by Kleinberg in [4].