Speaker: Zvi Lotker, Ben Gurion University
Title: Simple Random Walks on Radio Networks (Simple Random Walks on
HyperGraphs)
Abstract:
In recent years, protocols that are based on the properties of random
walks on graphs have found many applications in communication and
information networks, such as wireless networks, peertopeer networks
and the Web. For wireless networks (and other networks), graphs are
actually not the correct model of the communication; instead
hypergraphs better capture the communication over a wireless shared
channel. Motivated by this example, we study in this paper random
walks on hypergraphs. First, we formalize the random walk process on
hypergraphs and generalize key notions from random walks on graphs.
We then give the novel definition of radio cover time, namely, the
expected time of a random walk to be heard (as opposed to visit) by
all nodes. We then provide some basic bounds on the radio cover, in
particular, we show that while on graphs the radio cover time is
O(mn), in hypergraphs it is O(mnr) where n, m and r are the number of
nodes, the number of edges and the rank of the hypergraph,
respectively. In addition, we define radio hitting times and give a
polynomial algorithm to compute them. We conclude the paper with
results on specific hypergraphs that model wireless networks in one
and two dimensions.
