Normalized Laplacian of graph with empty rows

Question

Let $G = (V, W)$ be a graph, $V$ is the set of vertices and $W$ is the adjacency matrix. I want to compute the normalized Laplacian $ L_n = D^{-1/2} L D^{-1/2}$, where L is the combinatorial Laplacian $L = D - W$ and $D$ is the row sum diagonal matrix defined by $$ d_{ij} = \begin{cases} \sum_{j=1}^{n} w_{ij}, &i = j,\\ 0,&i \neq j. \end{cases} $$ The problem I have is that my adjacency matrix has some empty rows, which I cannot remove, since the corresponding columns are not empty, but if I allow $d_{ii}$ to be 0 for some $i$, then I cannot build $L_n$ anymore because $0^{-1/2}$ is not defined. Is there a standard trick to overcome this issue?

Answer 1

The Laplacian matrix (at least as you've written it) is usually only defined for undirected graphs - it loses a lot of nice properties when you move to directed graphs. In fact, Dan Spielman writes "there has been much less success in the study of the spectra of directed graphs, perhaps because the nonsymmetric matrices naturally associated with directed graphs are not necessarily diagonalizable." So I think that the normalized Laplacian wouldn't make a lot of sense to begin with in this setting.

However, Fan Chung defined a directed version of the Laplacian matrix in this paper where she derived something analogous to Cheeger's inequality for directed graphs. Unfortunately, I'm not super familiar with it.