2
$\begingroup$

In graphs, found that two different normalization matrices exist for Laplacian and adiacency matrix. I will ask about the adjacency matrix (for the Laplacian matrix the questions are the same). The first normalization matrix of the adjacency matrix is known as walk adiacency matrix, and is defined as

$$N_{walk}=D^{-1}A$$

where $A$ is th adjacency matrix and $D$ is the degree matrix. The sum of each row of $N_{walk}$ is $1$, so I see the mean of the word "normalized" used in $N_{walk}$.

The second (and, strangely for me, most common version) instead is:

$$N_{norm}=D^{-1/2}A D^{-1/2}$$

so, for me, the following questions arise:

  1. For each row, the sum of $N_{norm}$ is still $1$? I don't think, so, why is it know as a "normalized" matrix? What is normalized in this matrix if the sums is not $1$?
  2. Why $N_{norm}$ is "better" than $N_{walk}$?
  3. Is there any intuitive explaination for $N_{norm}$? while I still can see $N_{walk}$ as a real "normalized" version of $A$, what is the meaning, in an intuitive way, of dividing each entry $a_{ij}$ for $\sqrt{d_i}\sqrt{d_j}$? Where it comes from?
Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ $N_{norm}$ is symmetric, while the other matrix is not. $\endgroup$
    – Dima Pasechnik
    Commented Dec 26, 2019 at 10:51
  • 1
    $\begingroup$ Ok, but why “normalised”? $\endgroup$
    – volperossa
    Commented Dec 26, 2019 at 11:05
  • 1
    $\begingroup$ Not sure if that is the official answer, but one sense in which it is 'normalized' is that its spectral radius is 1. $\endgroup$
    – Federico Poloni
    Commented Dec 26, 2019 at 12:40
  • 2
    $\begingroup$ For the Laplacian, the second normalization gives a matrix with all ones on the diagonal (if no isolated vertices). So that may be why it is referred to as the "normalized Laplacian". The name for the adjacency matrix may just be borrowed from this since I think that normalized Laplacians are much more studied than normalized adjacency matrices (I do not recall seeing the latter notion before). Also, as Dima pointed out, the second type of normalization preserves the symmetry of the matrix. In the case of the Laplacian, positive semidefiniteness is also preserved, which is probably desirable. $\endgroup$
    – David Roberson
    Commented Jan 3, 2020 at 10:13

0

Reset to default

You must log in to answer this question.