Content deleted Content added
→Cluster analysis via Spectral Embedding: replaced the median with simpler sign-based, added explanations |
→Constructing graph Laplacian: explained connection between normalized Laplacian and adjacency matrices |
||
Line 69:
===Constructing graph Laplacian===
The graph Laplacian can be and commonly is constructed from the adjacency matrix. The construction can be performed matrix-free, i.e., without explicitly forming the matrix of the graph Laplacian and no AO. It can also be performed in-place of the adjacency matrix without increasing the memory footprint. Either way, the costs of constructing the graph Laplacian is essentially determined by the costs of constructing the <math>n</math>-by-<math>n</math> graph adjacency matrix.
Moreover, a normalized Laplacian has exactly the same eigenvectors as the normalized adjacency matrix, but with the order of the eigenvalues reversed. Thus, instead of computing the eigenvectors corresponding to the smallest eigenvalues of the normalized Laplacian, one can equivalently compute the eigenvectors corresponding to the largest eigenvalues of the normalized adjacency matrix, without even talking about the Laplacian matrix.
Naive constructions of the graph [[adjacency matrix]] make it dense, thus requiring <math>n^2</math> memory and <math>n^2</math> AO to determine each of the <math>n^2</math> entries of the matrix.
| |||