Questions tagged [graph-laplacian]

A simple graph has a symmetric matrix L = D - A associated with it called the Laplacian matrix, where D is the diagonal matrix of degrees and A is the adjacency matrix, often studied for its spectrum (eigenvalues).

The Laplacian matrix for simple graphs is positive semi-definite. Variations using indegree or outdegree can be defined for directed graphs.

277 questions

votes

1 answer

Commute time distance in a graph

Let $G=(V,E)$ be a graph, with node set $V$ and edge set $E$, along with a weighted adjacency matrix $W$. In this context, I'm interested by the commute-time distance between nodes of the graph. For undirected graphs, it is known to be defined…

graph-laplacian

asked Jun 11 '15 at 13:07

davcha

1,745

votes

2 answers

Is the Laplacian matrix of a directed graph positive semi-definite?

Define the Laplacian matrix as $L = D - A$. Here $A$ is the adjacency matrix of the directed graph so that the entries $A_{ij}$ of $A$ are equal to $1$ if there is an arrow form the vertex $j$ to $i$ and $0$ otherwise, and $D =…

graph-laplacian

asked Jun 07 '15 at 15:47

MarcosDNMaia

vote

0 answers

Why does the normalized graph Laplacian give negative square root at off-diagonal cells?

The normalized graph Laplacian fits the relationship $L=D^{-1/2}(D-A)D^{-1/2}=I-D^{-1/2}AD^{-1/2}$, where $I$ is the identity matrix, $D^{-1/2}$ is the diagonal matrix with $D(i,i)=\frac{-1}{\sqrt{n_{i}}}$, and $A$ is the $n \times n$ adjacency…

graph-laplacian