0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ Is the graph unoriented? If so the fact that you have an empty row means that the graph is not connected, and I think that in that case you should work on each connected component separately. $\endgroup$ Oct 16, 2016 at 13:49
  • $\begingroup$ The graph is oriented, otherwise I could remove the row and the corresponding column. There is no point in defining the Laplacian in this setting, maybe? $\endgroup$
    – gosbi
    Oct 16, 2016 at 14:32
  • 1
    $\begingroup$ See my answer below for more on this. Why are you using a graph laplacian here? Perhaps there's something else you can use to solve your problem. $\endgroup$ Oct 18, 2016 at 22:31

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.