| A Generic Search Strategy for Large-Scale Real-World Networks (2006) | |||||||||||||
Abstract | |||||||||||||
| ACM International Conference Proceeding Series; Vol. 152 : Article No. 2. First International Conference on Scalable Information Systems (INFOSCALE 2006) : May 29 - June 1, 2006, Hong Kong. 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. | |||||||||||||
Publication details | |||||||||||||
| |||||||||||||