Laplacian Matrix
Bir grafın derece ve komşuluk bilgisini L = D - A biçiminde birleştirerek bağlantı yapısını spektral olarak incelemeyi sağlayan matris.
Graf Laplasyeni, adjacency matrix'in başka bir gösterimi değildir. Özdeğer ve özvektörleri grafın bağlı bileşenleri, kesimleri ve yayılım davranışı hakkında doğrudan yapısal bilgi taşır.
Yönsüz bir grafta sıfır özdeğerinin çokluğu bağlı bileşen sayısıyla ilişkilidir. İkinci küçük özdeğer ve karşılık gelen Fiedler vektörü spectral partitioning için kullanılır.
Sayısal Taraf
Büyük sparse graflarda dense eigendecomposition yapmak doğru ölçeklenmez. Uygulama çoğu zaman yalnız birkaç ekstrem eigenpair ister; sparse iterative solver seçimi, normalization biçimi ve graf ağırlıklarının ölçeği sonucu etkiler.
Spectral clustering'de unnormalized, symmetric normalized ve random-walk Laplacian aynı matris değildir.
Kaynak
- https://fanchung.ucsd.edu/research/cb/ch1.pdf