Random walks are the simplest way to explore a graph. In
this talk we will discuss some of the properties of random
walks (such as equilibrium distributions, entropy rates, and
mean first-passage times) which might have relevant
applications to study traffic fluctuations in the Internet,
to design optimal diffusion processes on correlated or
uncorrelated networks, or to achieve the best
synchronization in a system of Kuramoto oscillators moving
on a graph. In particular, we will consider degree-biased
random walks with a jumping probability depending on some
power of the degree of the target node. Based on whether the
exponent is positive or negative, this can give rise to
walks that favor or disfavor high-degree vertices. Finally,
we will discuss a model of interacting random walkers which
compete for the nodes of a complex network. The
complementary roles of competition and motion produce a
variety of fixed points, whose stability depends mostly on
the structure of the underlying network. The model can be
useful to simulate processes which usually take place on
complex topologies and are characterized by strong
competition among orthogonal species, such as diffusion of
consumer products, competition of biotypes, and selections
of languages. |