グラフと熱 回歴

ハイパーグラフなどの話。

参考文献はこちら。

スペクトル・クラスタリング

グラフとそのグラフから導かれる

ベクトル、座標、行列、内積、

用意するもの

隣接行列（重みつき）

次数（重みつき）

次数行列（対角行列で、対角成分が次数であるもの）

無効グラフのラプラシアン行列（次数行列ー隣接行列）

ランダムウォーク正規化ラプラシアン（単位行列ー隣接行列/次数行列）

ラプラシアンは対称行列なので、固有値が実数で、半正定値、固有値が非負

最小固有値が0で、その固有ベクトルが1

ラプラシアン行列や正規化ラプラシアンは、ハイパーグラフや、作用素としての拡張がある。

非線形多値作用素や劣モジュラー関数、

体積（グラフの頂点集合の部分集合の次数の総和）

枝境界（頂点部分集合の片方と、その補集合の他方の辺の集合）

カット関数（グラフのカット関数は、頂点部分集合の枝境界の辺の重みの総和を返す）

コンダクタンス、チーガー商（カット関数/min(体積, 補集合の体積)）

最小コンダクタンス（チーガー定数、グラフGのコンダクタンスで最小のもの）

無向グラフのチーガー不等式

コミュニティ検出アルゴリズムとの関係性

Personalized PageRank

ものぐさランダムウォークの遷移過程を使った、グラフの指標

熱方程式を、グラフ上の拡散方程式でモデルしている。そこにグラフラプラシアンが絡む。

面白そう。