Commute times for a directed graph using an asymmetric Laplacian

Daniel Boley; Gyan Ranjan; Zhi Li Zhang

doi:10.1016/j.laa.2011.01.030

Commute times for a directed graph using an asymmetric Laplacian

Daniel Boley, Gyan Ranjan, Zhi Li Zhang

Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

49 Scopus citations

Abstract

The expected commute times for a strongly connected directed graph are related to an asymmetric Laplacian matrix as a direct extension to similar well known formulas for undirected graphs. We show the close relationships between the asymmetric Laplacian and the so-called Fundamental matrix. We give bounds for the commute times in terms of the stationary probabilities for a random walk over the graph together with the asymmetric Laplacian and show how this can be approximated by a symmetrized Laplacian derived from a related weighted undirected graph.

Original language	English (US)
Pages (from-to)	224-242
Number of pages	19
Journal	Linear Algebra and Its Applications
Volume	435
Issue number	2
DOIs	https://doi.org/10.1016/j.laa.2011.01.030
State	Published - Jul 15 2011

Bibliographical note

Funding Information:
Supported in part by NSF grants 0534286, 0626808, 0916750, DTRA grant HDTRA1-09-1-0050, and a Univ. of Minn. DTC DTI gr∗Corresponding author.ant. E-mail addresses: boley@cs.umn.edu (D. Boley), granjan@cs.umn.edu (G. Ranjan), zhzhang@cs.umn.edu (Z.-L. Zhang).

Keywords

Commute times
Directed graphs
Graph Laplacians
Wireless networks

Access

10.1016/j.laa.2011.01.030

OpenUrl availability

Full text

Cite this

@article{1c8e50de3f734d0bb2e25e9739869708,

title = "Commute times for a directed graph using an asymmetric Laplacian",

abstract = "The expected commute times for a strongly connected directed graph are related to an asymmetric Laplacian matrix as a direct extension to similar well known formulas for undirected graphs. We show the close relationships between the asymmetric Laplacian and the so-called Fundamental matrix. We give bounds for the commute times in terms of the stationary probabilities for a random walk over the graph together with the asymmetric Laplacian and show how this can be approximated by a symmetrized Laplacian derived from a related weighted undirected graph.",

keywords = "Commute times, Directed graphs, Graph Laplacians, Wireless networks",

author = "Daniel Boley and Gyan Ranjan and Zhang, {Zhi Li}",

note = "Funding Information: Supported in part by NSF grants 0534286, 0626808, 0916750, DTRA grant HDTRA1-09-1-0050, and a Univ. of Minn. DTC DTI gr∗Corresponding author.ant. E-mail addresses: boley@cs.umn.edu (D. Boley), granjan@cs.umn.edu (G. Ranjan), zhzhang@cs.umn.edu (Z.-L. Zhang).",

year = "2011",

month = jul,

day = "15",

doi = "10.1016/j.laa.2011.01.030",

language = "English (US)",

volume = "435",

pages = "224--242",

journal = "Linear Algebra and Its Applications",

issn = "0024-3795",

publisher = "Elsevier Inc.",

number = "2",

}

TY - JOUR

T1 - Commute times for a directed graph using an asymmetric Laplacian

AU - Boley, Daniel

AU - Ranjan, Gyan

AU - Zhang, Zhi Li

N1 - Funding Information: Supported in part by NSF grants 0534286, 0626808, 0916750, DTRA grant HDTRA1-09-1-0050, and a Univ. of Minn. DTC DTI gr∗Corresponding author.ant. E-mail addresses: boley@cs.umn.edu (D. Boley), granjan@cs.umn.edu (G. Ranjan), zhzhang@cs.umn.edu (Z.-L. Zhang).

PY - 2011/7/15

Y1 - 2011/7/15

N2 - The expected commute times for a strongly connected directed graph are related to an asymmetric Laplacian matrix as a direct extension to similar well known formulas for undirected graphs. We show the close relationships between the asymmetric Laplacian and the so-called Fundamental matrix. We give bounds for the commute times in terms of the stationary probabilities for a random walk over the graph together with the asymmetric Laplacian and show how this can be approximated by a symmetrized Laplacian derived from a related weighted undirected graph.

AB - The expected commute times for a strongly connected directed graph are related to an asymmetric Laplacian matrix as a direct extension to similar well known formulas for undirected graphs. We show the close relationships between the asymmetric Laplacian and the so-called Fundamental matrix. We give bounds for the commute times in terms of the stationary probabilities for a random walk over the graph together with the asymmetric Laplacian and show how this can be approximated by a symmetrized Laplacian derived from a related weighted undirected graph.

KW - Commute times

KW - Directed graphs

KW - Graph Laplacians

KW - Wireless networks

UR - http://www.scopus.com/inward/record.url?scp=79952766932&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79952766932&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2011.01.030

DO - 10.1016/j.laa.2011.01.030

M3 - Article

AN - SCOPUS:79952766932

SN - 0024-3795

VL - 435

SP - 224

EP - 242

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

IS - 2

ER -

Commute times for a directed graph using an asymmetric Laplacian

Abstract

Bibliographical note

Keywords

Access

OpenUrl availability

Other files and links

Fingerprint

Cite this