Specral Graph Theory and its Applications: Lecture 1
Matrices for Graphs [#z4dd8a4e]
- adjacency matrix $A_G$
- Laplacian matrix $L_G$, where $l_{i,j} = \{ -1, d_i, 0 \} $
$A_G$, $L_G$ の固有値，固有ベクトルに何か意味があるのか？実際には，マジで色々な意味がある！（教授はグラフ見たらまず固有値と固有ベクトルを計算するらしいｗ）
Random Graphs [#ya5f7ad7]
「グラフを構成するには，代数的に構成するかランダムにつくるかだ」現実世界のグラフに興味が無すぎてイラッとする
ランダムグラフの固有値の分布をプロットして終わった．これは証明できるらしい．
The Spectral Gap [#y159ba72]
Fiedler value [#z5fe5f05]
$\lambda_2$ of Laplacian．Fiedler value とも呼ばれる．smallest non-zero eigenvalue．
例 [#x5384f97]
- path: $\Theta(1/n^2)$
- grid: $\Theta(1/n)$
- 3d grid: $\Theta(1/n^{2/3})$
- expander: $\Theta(1)$
- binary tree: $\Theta(1/n)$
- dumbell: $\Theta(1/n)$ （２つの expander を１本の辺で結んだ）
カットとの関係 [#p16b41e8]
何故これが面白いか？グラフのカットと関係あるからだ！
カット$S$の ratio $\phi(S)$ とは
$$
\phi(S) := \frac{|E(S, \overline{S})|}{\min(S, \overline{S})}
$$
（これは sparsest cut のやつ？）
グラフの isoperimetric number $\phi(G) = \min_S \phi(S)$．
定理 1.6.1 (Cheeger's inequality): $\phi \geq \lambda_2 \geq \phi^2 / 2d$
したがって，$\lambda_2$ が小さい → グラフを２つに簡単に切れるかも．でかいと，切るのが難しいかも．
Graph approximation and preconditioning [#r8a4eec9]
任意の $x \in R^n$ に対して $x^T L_G x$ と $x^T L_H x$ の値が近いことでグラフが似ていると定義する
