Large Deviations, Gibbs Measures, and Topologically Conjugate Transforms in Network Dynamics

Abstract

A chaotic piecewise linear map whose statistical properties are identical to those of a random walk on directed graphs such as the world wide web (WWW) is constructed, and the dynamic quantity is analyzed in the framework of large deviation statistics. Gibbs measures include the weight factor appearing in the weighted average of the dynamic quantity, which can also quantitatively measure the importance of web sites. Currently used levels of importance in the commercial search engines are independent of search terms, which correspond to the stationary visiting frequency of each node obtained from a random walk on the network or equivalent chaotic dynamics. Levels of importance based on the Gibbs measure depend on each search term which is specified by the searcher. The topological conjugate transformation between one dynamical system with a Gibbs measure and another dynamical system whose standard invariant probability measure is identical to the Gibbs measure is also discussed.