11
$\begingroup$

I seem to see three different things that are being called the Laplacian of a graph,

  • One is the matrix $L_1 = D - A$ where $D$ is a diagonal matrix consisting of degrees of all the vertices and $A$ is the (possibly signed) adjacency matrix.

  • The other is to say that the matrix $L_2$ is a $\vert V \vert \times \vert V \vert$ matrix such that $(L_2)_{ii} = deg(v_i)$ and $(L_2)_{ij} = -\frac{1}{\sqrt{deg(v_i)deg(v_j) } }$

  • The third is to say that $L_3 = BB^T$ (where $B$ is the incidence matrix)

Can someone kindly clarify what is the relation between these three pictures (and or may be all these are the same somehow!?). [..for example for which of them would the positive-semi-definiteness and the the heat-equation intuition hold?...]

$\endgroup$
  • $\begingroup$ What's a reference for the third? Are you sure you don't want $A$ to be the incidence matrix? $\endgroup$ – Qiaochu Yuan Nov 28 '14 at 23:02
  • $\begingroup$ oh - sorry - changed it! $\endgroup$ – user6818 Nov 28 '14 at 23:02
  • 2
    $\begingroup$ In the middle option you want the diagonal entries to be $1$ (or $0$ in the case of degree $0$ vertices, if any) The Wikipedia article en.wikipedia.org/wiki/Laplacian_matrix explains the connections. $L_1=L_3$ and $L_2=SL_1S$ where $S=\sqrt{D}$ is the diagonal matrix with (non-negative) entries $\sqrt{\deg(v_i)}.$ $\endgroup$ – Aaron Meyerowitz Nov 29 '14 at 0:22
  • $\begingroup$ @AaronMeyerowitz So $L_2$ is not a graph Laplacian - right? $\endgroup$ – user6818 Nov 29 '14 at 1:08
  • 1
    $\begingroup$ $L_2$ is not the same kind of graph Laplacian as $L_1$. When one is going to be using both kinds, it is common to call $L_2$ the normalized Laplacian matrix and $L_1$ the standard Laplacian matrix. With certain exceptions (find them!) a normalized Laplacian is not a standard Laplacian. Read the article to see some common properties. $\endgroup$ – Aaron Meyerowitz Nov 29 '14 at 1:56
17
$\begingroup$

These are usually known as the Laplacian, the normalized Laplacian and the unsigned Laplaian. All three are positive semidefinite. If the graph is regular, they all provide the same information.

If the graph is not regular they are, in general, independent. The normalized Laplacian is the right tool for the analysis of random walks. The spectral information provided by the unsigned Laplacian is equivalent to what you get from the spectrum of the line graph of the original graph.

To expand on the last comment: if $B$ is the vertex-edge incidence matrix, then $BB^T$ is the unsigned Laplacian and $B^TB=2I+A(L(G))$. This appears for example on page 16 of the first edition of Cvetkovic et al "Spectra of Graphs", but it is older. (I know I did not learn it from there.) Note that it follows that $BB^T$ and $B^TB$ have the same non-zero eigenvalues with the same multiplicities.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I was not aware of the correspondence in your last sentence. Can you give me a reference? $\endgroup$ – Delio Mugnolo Dec 1 '14 at 20:16
  • $\begingroup$ @Delio Mugnolo: I've edited my answer to provide this. $\endgroup$ – Chris Godsil Dec 1 '14 at 22:00
  • $\begingroup$ I see. So when you talked about the "spectrum of the line graph" you were actually thinking of the adjacency spectrum of the line graph? I was always wondering whether there is a natural interpretation of the Laplacian of the line graphh for non-regular graphs. Anyway, the result you mention did certainly appear already in Harary's book (Thm. 13.3) and in Biggs' book (Lemma 3.6). $\endgroup$ – Delio Mugnolo Dec 2 '14 at 1:38
  • $\begingroup$ Recently, Steve Butler wrote a very nice article "A Gentle Introduction to the Normalized Laplacian" in IMAGE, The Bulletin of the International Linear Algebra Society. This article describes some of the similarities and differences between these matrices and their eigenvalues. It is available here: ilasic.org/IMAGE/IMAGES/image53.pdf $\endgroup$ – Sebi Cioaba Dec 8 '14 at 13:34
2
$\begingroup$

Let me comment a bit on Chris Godsil's answer. The fact that $L_1\ne L_3$ follows from the easy-to-check fact that $L_1=\mathcal I\mathcal I^T$, where $\mathcal I$ is the incidence matrix of an arbitrary orientation of the graph. The nullity of $\mathcal I^T$ is the number of connected components of the graph, whereas the nullity of the transpose of the signless incidence matrix (which is what you presumably denote by $B^T$) is the number of bipartite connected components. So these matrices are clearly different. However, as pointed out by Chris Godsil, they yield the same information in the regular case: the difference is that the upper end of the spectrum of $L_3$ corresponds to the lower end of the spectrum of $L_1$, and vice versa: This was in fact, as far as I can judge, the main reasons for the introduction of $L_3$ in a 1994 paper by Desai and Rao.

The fact that the nullities of $L_1,L_2$ coincide can be seen by an argument that might be interesting for your purposes: $L_2$ (or at least the matrix $L_2:=D^{-\frac12}L_1 D^{-\frac12} $ suggested in the comment by Aaron Meyerowitz) is similar to $\tilde{L}_2:=D^{-1}L_1$, which is often called normalized Laplacian as well. It turns out that both $L_1,\tilde{L}_2$ can be seen as Fréchet derivatives of the same energy functional $\mathcal E:f\mapsto\|\mathcal I^T f\|_{\ell^2(E)}^2$, but with respect to two different Hilbert spaces -- more precisely, to the vector space $\mathbb R^V$ endowed with the inner products $$ (f|g):=\sum_{v\in V}f(v)g(v) $$ and $$ (f|g):=\sum_{v\in V}f(v)g(v)\deg(v) $$ respectively (obvious modifications are needed in the case of infinite graphs).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The fact that the nullities of $L_1$ and $L_2$ coincide can also be seen from $L_2 := P^T L_1 P$ for trivially invertible $P := D^{-1/2}$, hence $L_1$ and $L_2$ are congruent. Thus, Sylvester's law of inertia gives that their numbers of positive, negative, and zero eigenvalues coincide, respectively. $\endgroup$ – cubic lettuce Jun 15 '15 at 17:30
1
$\begingroup$

For analyzing spectral properties (spectral gap for instance), it is more convenient to use the normalized version since the spectra are kind of independent of the number of vertices.

| cite | improve this answer | |
$\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.