Forest Search: A Paradigm for Faster Exploration of Scale-Free Networks

摘要

Scale-free networks naturally model wide area networks like the WWW. We consider the problem of fast exploration of huge scale-free networks using small memory space. Although there are many search algorithms for exploring an unknown graph, they require much space or time. For example, the depth first search requires some memory for all the nodes in the worst case, and the average number of steps in the random walk is O(n~3), where n is the size of the graph. Under assumptions reflecting WWW applications, we propose a new exploration paradigm called forest search particularly designed for scale-free networks, and theoretically evaluate its space complexity. We also demonstrate its superiority over random walk based search algorithms by conducting simulations.