Research Article
A generic search strategy for large-scale real-world networks
@INPROCEEDINGS{10.1145/1146847.1146849, author={Yuichi Kurumida and Tsukasa Ogata and Hirotaka Ono and Kunihiko Sadakane and Masafumi Yamashita}, title={A generic search strategy for large-scale real-world networks}, proceedings={1st International ICST Conference on Scalable Information Systems}, publisher={ACM}, proceedings_a={INFOSCALE}, year={2006}, month={6}, keywords={}, doi={10.1145/1146847.1146849} }- Yuichi Kurumida
Tsukasa Ogata
Hirotaka Ono
Kunihiko Sadakane
Masafumi Yamashita
Year: 2006
A generic search strategy for large-scale real-world networks
INFOSCALE
ACM
DOI: 10.1145/1146847.1146849
Abstract
We consider the following situation for a given large-scale network: Starting from an initial node we move to its neighbor node and repeat that until reaching a target node. How fast can we do this without any global topological information? This problem is considered "searching networks", and several approaches have been proposed. In this paper, we present a general framework of search strategies, under which all of these existing approaches can be formalized. Our framework characterizes random search strategies by the following three parameters: memory for previously-visited nodes, look-ahead property and transition probability. Through computational simulations for large-scale networks with small-worldness and scale-freeness, we investigate the relationship between the effect of parameters of the strategies and the coefficients of networks such as the clustering coefficient. The comparison result provides a guideline to obtain good parameters of the strategies according to the diameter and the clustering coefficients of networks.