Effective spectral dimension of hub in scale-free networks

Exploring the World Wide Web has become one of the key issues in information science, specifically in context of its application to the PageRank-like algorithms used in search engine. The random walk approach has been employed to study such a problem. The probability of the return to the origin (RTO) of random walks is inversely related to how information can be accessed during random surfing. We find analytically that the RTO probability for a given starting node shows a crossover from a slow to a fast decay behavior with time and the crossover time increases with the degree of the starting node. Furthermore, the RTO probability is almost constant in the early-time regime as the degree exponent approaches two. This result indicates that a random surfer can be effectively trapped at the hub and supports the necessity of the random jump strategy empirically used in the Google's search engine.