# 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.

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:

05C20

Keywords: