An Asymmetric Laplacian and Commute Times for Directed Graphs.

Friday, October 28, 2011 - 11:30am - 12:30pm
Keller 3-180
Daniel Boley (University of Minnesota, Twin Cities)
Directed graphs are better than undirected graphs in capturing
the connectivity in many applications like the WWW and networks of
wireless devices. For undirected graphs, it is well known how to
obtain the expected inter-vertex average commute times from the graph
Laplacian matrix. We show the same formulas hold in the case of strongly
connected directed graphs. Our result is obtained by deriving a close
relation between the Laplacian with a particular scaling and the so-called
Fundamental matrix for an associated random walk over the graph. We find
that the commute times still form a metric and give bounds in terms of
the stationary probabilities for the random walk. Using a simple model
of wireless devices, we observe that these commute times can differ from
those obtained from a previously proposed symmetrized Laplacian derived
from a related weighted undirected graph.
MSC Code: