Analytic method for calculating properties of random walks on networks

Publisher Website
Google Scholar
Abstract
Unlike the case of regular networks, such as lattices, no method of general applicability exists for dealing with random walks on complex networks. We propose a method, which is based on the identification of certain types of walks on a one-dimensional segment as basic. Generating functions for complex networks or for complex types of walks can all be constructed from the generating functions corresponding to these basic walks. We also define basic walks corresponding to a network. The properties of walks in a network composed of ‘‘black boxes,’’ each containing a network by itself, can be expressed in terms of the basic walks defined for the single black box. This result can be compared to the way the Kirchhoff rules allow one to calculate properties of a network of ‘‘elements’’ in terms of the impedances of each of the elements. In the present case the combination rules are more complex than in the electrical case. Our method is demonstrated by calculating mean first-passage times on several structures: a segment, a segment with a single dangling bond, a segment with many dangling bonds, and a looplike structure. The results are analyzed and related to the question of applicability of the Einstein relation between conductance and diffusion.