2011 | OriginalPaper | Chapter
The Cover Times of Random Walks on Hypergraphs
Authors : Colin Cooper, Alan Frieze, Tomasz Radzik
Published in: Structural Information and Communication Complexity
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Random walks in graphs have been applied to various network exploration and network maintenance problems. In some applications, however, it may be more natural, and more accurate, to model the underlying network not as a graph but as a hypergraph, and solutions based on random walks require a notion of random walks in hypergraphs. At each step, a random walk on a hypergraph moves from its current position
v
to a random vertex in a randomly selected hyperedge containing
v
. We consider two definitions of cover time of a hypergraph
H
. If the walk sees only the vertices it moves between, then the usual definition of cover time,
C
(
H
), applies. If the walk sees the complete edge during the transition, then an alternative definition of cover time, the inform time
I
(
H
) is used. The notion of inform time models passive listening which fits the following types of situations. The particle is a rumor passing between friends, which is overheard by other friends present in the group at the same time. The particle is a message transmitted randomly from location to location by a directional transmission in an ad-hoc network, but all receivers within the transmission range can hear.
In this paper we give an expression for
C
(
H
) which is tractable for many classes of hypergraphs, and calculate
C
(
H
) and
I
(
H
) exactly for random
r
-regular,
s
-uniform hypergraphs. We find that for such hypergraph
whp
C
(
H
)/
I
(
H
) = Θ(
s
) for large
s
.