On localization/phase transition phenomena of Laplacian eigenfunctions on graphs and networks

Naoki Saito
University of California, Davis (UC Davis)

We describe our current understanding on the phase transition phenomenon of the graph Laplacian eigenvectors constructed on a certain type of unweighted trees, which we previously observed through our numerical experiments.
The eigenvalue distribution for such a tree is a smooth bell-shaped curve starting from the eigenvalue 0 up to 4. Then, at the eigenvalue 4, there is a sudden jump. Interestingly, the eigenvectors corresponding to the eigenvalues below 4 are semi-global oscillations (like Fourier modes) over the entire tree or one of the branches; on the other hand, those corresponding to the eigenvalues above 4 are much more localized and concentrated (like wavelets) around junctions/branching vertices.
For a special class of trees called starlike trees, we obtained a complete understanding of such phase transition phenomenon. For a general graph, we proved the number of the eigenvalues larger than 4 is bounded from above by the number of vertices whose degrees is strictly larger than 2.
Moreover, we also proved that if a graph contains a branching path, then the magnitudes of the components of any eigenvector corresponding to the eigenvalue greater than 4 decay exponentially from the center toward the leaf of that branch. We have also identified a unique class of trees that can have an eigenvalue exactly equal to 4.
If time permits, I will also discuss some applications, e.g., data analysis and missing data recovery.

Back to Large Scale Multimedia Search