2003 | OriginalPaper | Buchkapitel
Impact of Local Topological Information on Random Walks on Finite Graphs
verfasst von : Satoshi Ikeda, Izumi Kubo, Norihiro Okumoto, Masafumi Yamashita
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
It is just amazing that both of the mean hitting time and the cover time of a random walk on a finite graph, in which the vertex visited next is selected from the adjacent vertices at random with the same probability, are bounded by O(n3) for any undirected graph with order n, despite of the lack of global topological information. Thus a natural guess is that a better transition matrix is designable if more topological information is available. For any undirected connected graph G = (V,E), let P(β) = (puv(β))u,v∈V be a transition matrix defined by $$ p_{uv}^{\left( \beta \right)} = \frac{{\exp \left[ { - \beta U\left( {u,v} \right)} \right]}} {{\sum _{w \in N\left( u \right)} \exp \left[ { - \beta U\left( {u,w} \right)} \right]}}foru \in V,v \in N\left( u \right), $$ where β is a real number, N(u) is the set of vertices adjacent to a vertex u, deg(u) = |N(u)|, and U(•, •) is a potential function defined as U(u, v) = log (max {deg(u), deg(v)}) for u ∈ V, v ∈ N(u). In this paper, we show that for any undirected graph with order n, the cover time and the mean hitting time with respect to P(1) are bounded by O(n2 log n) and O(n2), respectively. We further show that P(1) is best possible with respect to the mean hitting time, in the sense that the mean hitting time of a path graph of order n, with respect to any transition matrix, is Ω (n2).