まめいろん

きのおもむくままに

記事一覧
26 September 2021

スペクトルグラフ理論

(加筆中)

我々はいま何らかの対象を理解したいとする．第一に大切なのは，対象そのものをじっくり観察することである．第二に大切なのは，「対象を理解する」ことの本質を知ることである．後者については，これまで多くの考察がなされている．例えばアルトゥル・ショウペンハウエルは，真理獲得のプロセスについて次のように述べている．

何か一つのことを知り，一つの真理をものにするといっても，それを他のさまざまの知識や真理と結合し比較する必要があり，この手続きを経て初めて，自分自身の知識が完全な意味で獲得され，その知識を自由に駆使することができるからである．1

もう少し具体的で，われわれの社会になくてはならない科学に関する視点から，アンリ・ポアンカレは次のように述べている．

科学はわたしたちの目の前で，日々，有効に働いている．これは科学が実在の何かを教えてくれているのでなければ起こりえないことだ．ただし，科学の手が届くのは，単純な教条主義者が思っているように物そのものではなく，物と物の関係だけである．これらの関係以外に，私たちが知ることのできる実在はない．2

もう少し言いたい．もう少し深く議論するため問題を分割したい． 実在と概念，概念と概念の関係の二つの理解があると． 前者は物理，後者は数学．

例えば物理学的視点では，次のような考察がある．

**

数学的視点では，次のような考察もある．

元来，数学は有機的統一体であり，それは真理という鳥の大群をとらえるために張りめぐらされた大きな鳥網のようなものである．それは 1 つにつながっていることによって目的を達するのである．鳥が衝突して，それを捕らえるのは網の一部分にすぎないが，鳥を直接捕えなかった他の部分は決して無用であったのではなく，それなくしては鳥は逃げ去ってしまったであろう．3

つまり対象を理解することとは，対象と他の様々な事柄との関係を築くことである．

ここでは特に数学的な視点で考察したい．こうした対象間の「関係」は，代数的な視点でみると究極的には，集合論の二項関係である．ただし現実の複雑性を集合論だけで理解するのは難しい．そこでより高次の枠組みとしてグラフ理論がある．グラフ理論は視覚的に対象間の関係を認識しやすい．そして回路網，交通網，社会網，通信網，ニューラルネットワークなどのさまざまなネットワークに応用されている．

グラフの性質をより深く知るためのものとして，スペクトルグラフ理論がある．スペクトルグラフ理論はグラフ理論に線形代数を適用したもので，例えばエッジの情報を隣接行列やグラフラプラシアンなどの行列形式にすることで，固有値解析などでグラフの性質を議論することができる．代数的扱いやすさ以外にも，われわれの認識を実空間から周波数空間に拡げるという意味で興味深い．例えば電磁気学や流体力学におけるフーリエ解析がそれに近い．電磁気学や流体方程式では偏微分方程式を線形化し，固有値解析を行うことで系内を伝搬する波や系の安定性を議論する．スペクトルグラフ理論においても，グラフの固有値や固有ベクトルから，ネットワーク（系）の性質を議論する．グラフの固有値はフーリエ解析の周波数に対応する何かであり，グラフの連結性や，コミュニティと密接な関係がある．

スペクトルグラフ理論を通じてネットワークを理解する様子を下図に示す．最も大きな部分で，われわれが実在をネットワークとして「直感」する領域と，学問の力でわれわれが繋がりを「直観」できる領域がある．ここで「ネットワークを理解する」ことの意味に立ち戻る．ネットワークとは実在と実在の繋がりである．実在と実在の間の繋がりはわれわれの認識によって確立される．より遠くにある実在間の繋がりや，より深い関係を知るには，より深い認識が必要である．深い認識とは，より抽象的概念の結びつきであったり，より多くの概念間の繋がりによって成り立っている．つまり，実在間の関係は，実在→概念→(概念間の結びつき)→概念→実在によって理解される．

下図に戻って具体的にいうと，われわれはまずネットワークを構成する要素や要素間の繋がりを観察する．本質以外のものを削ぎ落とし，要素を点，要素間の繋がりを辺で表現する（実在と直感的に関連付けられる表現）．そしてそこから隣接行列や接続行列などの線形代数に適用可能な形式に変換する．変換した形式からグラフラプラシアンの固有値や固有ベクトルといったより抽象的なネットワークの特徴を得て，それを連結度や彩色数などの具体的指標（実在と直感的に関連付けられる表現）と関連付けて理解する．

繋がりには代数的繋がりと，アルゴリズム的繋がりがある．（ヒューリスティック近似アルゴリズムなどの弱い繋がりは応用上重要ではあるが取りあげない．）

relations

Fig.1: Relation

$\mathcal{A}$: Adjacency matrix $\in \mathbb{R}^{| V| \times| V| }$

$\mathcal{B}$: Incidence matrix $\in \mathbb{R}^{| E| \times| V| }$

$\mathcal{C}$: カットセット行列

$\mathcal{D}$: Degree matrix $\in \mathbb{R}^{| V| \times| V| }$

$\mathcal{L}$: (Graph) Laplacian

$\mathcal{L}^D$: Distance Laplacian

$\chi$: 彩色数

$\phi$: コンダクタンス

$\kappa_v, \kappa_e$: vertex/edge connectivity

[r1] $\mathcal{L}=\mathcal{B}\mathcal{B}^T$, 有向グラフのみに成り立つ関係．

[r2] $\mathcal{L}=\mathcal{D}-\mathcal{A}$

[r3] $\chi\le \lfloor \mu_{\max} \rfloor+1$ : Wilf の定理4

[r4] $\displaystyle \frac{\lambda_2}{2}\le \phi\le \sqrt{2\lambda_2}$: Cheeger inequality5

[r5] $\lambda_2\le\kappa_v\le\kappa_e$ Fiedler6

[r6] $(1-\epsilon){\boldsymbol x}^T\mathcal{L}{\boldsymbol x}\le{\boldsymbol x}^T\mathcal{L}’{\boldsymbol x}\le (1+\epsilon){\boldsymbol x}^T\mathcal{L}{\boldsymbol x}$: グラフ疎化7． 例えば ${\boldsymbol x}={\boldsymbol \nu}_i$ として固有値 $\lambda_i$ を保存しつつ疎化を行う．

[r7] Dijkstra

[r8] アルゴリズム．参考文献8 の Table 1 によくまとまった記載がある．また参考文献 9 (4.5 (c),(d) 参照) ではメンガーの定理との繋がりから最大フロー問題との関係まで非常に丁寧かつ明快に解説されている．

[r9] $\mathcal{L}^D=\mathcal{D}^D-\mathcal{A}^D$．半正定値対称であり，加法の定義なども考えられている10．

参考文献

  1. アルトゥル・ショウペンハウエル，「読書について」，岩波文庫 ↩

  2. アンリ・ポアンカレ，「科学と仮説」，ちくま学芸文庫，p.10 ↩

  3. 遠山 啓，「代数的構造」，ちくま学芸文庫，p.41 ↩

  4. H.S. Wilf “Eigenvalues of a graph and its chromatic number,” Journal of the London Mathematical Society, (42), pp. 330-332, 1967 ↩

  5. x, “,” ↩

  6. Fiedler, Miroslav. “Algebraic connectivity of graphs.” Czechoslovak Mathematical Journal 23.2 (1973): 298-305. http://eudml.org/doc/12723. ↩

  7. J. Batron, D.A. Spielman and N. Srivastava “Twice-Ramanujan sparsifiers,” SIAM Review, 56(2), pp. 315-334, 2014 ↩

  8. A.H. Esfahanian, “Connectivity Algorithms,” https://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf ↩

  9. 滝根哲哉，伊藤大雄，西尾章治郎「ネットワーク設計理論」岩波文庫，第 1 版，2001 ↩

  10. Aouchiche, 2013 ↩

tags: 理解，関係，グラフ，スペクトルグラフ理論