この記事では、電力網のネットワーク、交通網のネットワーク、人間関係のネットワーク、神経ネットワーク、遺伝子ネットワークのようなネットワークシステムの性質を解析する際に重要なグラフラプラシアンについて解説します(枝に向きのないネットワークだけ解説します)。
グラフ、隣接行列、次数行列
下図のように節点と枝から構成されるネットワークを数学的に表現するには、グラフという概念が役立ちます。
グラフとは、節点の集合 と枝の集合 の組 のことです。例えば上のネットワークだと節点集合が で枝集合が です。このように なら が成り立つグラフを正確には無向グラフといいます(この記事では、無向グラフだけを説明します)。節点は頂点、枝は辺とも呼ばれます。
上のグラフはそれぞれの枝が同等の重要度を持っているとすると、次のような行列で表現できます。
より数学的には、 グラフ の枝と重み(重要度)との対応関係を表す関数 をグラフ 上の重み関数といいます( は正の実数の集合)。ただし、 なら を満たします。この重み付きグラフを と書きます。このような重み付きグラフ を行列によって表現した対称行列 を隣接行列といい、次のように定義されます。
通常のグラフ はすべての に対して となる重み付きグラフのことです。
重み付きグラフ が与えられたとき、節点 の次数を で定義します。ただし、 はそのグラフの節点の数です。次のように各節点の次数を対角上に並べた対角行列を重み付きグラフ の次数行列と呼びます。\begin{align}
D={\rm diag}( d_1, d_2,\ldots, d_n)
\end{align}
例えば上のグラフが与えられたとすると、次数行列は です。
グラフラプラシアン、接続行列
重み付きグラフ が与えられたとします。このとき、隣接行列 と次数行列 を用いて定義される次の行列 を重み付きグラフ のグラフラプラシアンといいます。\begin{align}
L:=D-A
\end{align} グラフラプラシアンの定義からグラフラプラシアン は固有値 0 を少なくとも一つもち、1をすべての成分に並べたベクトル は固有値 0 に対応する固有ベクトルとなります。なぜなら、 となるからです。
グラフラプラシアンは接続行列と呼ばれる行列によっても特徴付けられます。接続行列を定義するために、重み付き無向グラフ の枝に一意な番号と任意に向きを付けます。例えば、はじめに与えた例のグラフの枝に次のように番号と向きをつけてみましょう。
この枝に番号と向きの付いたグラフは次の行列と対応付けることができます。
グラフラプラシアンという名前の由来
グラフラプラシアンという名前はベクトル解析で登場するラプラシアンという作用素に由来します。ここでは重みのない無向グラフ 、つまり任意の に対して となる無向グラフのグラフラプラシアンがどのようにラプラシアンに関係しているかを説明します。
まず、グラフラプラシアン のベクトル への作用は次のようになることに注意します。
次に、以下のような向きと重みのない格子グラフを考えます。
(L\phi)(x,y) = 4\phi (x,y) -\phi(x+1,y) -\phi(x-1,y)-\phi(x,y+1)-\phi(x,y-1)
\end{align}となると考えられます。
\phi(x+h,y) &= \phi(x,y) + h\frac{\partial \phi}{\partial x}(x,y) + \frac{h^2}{2!}\frac{\partial^2 \phi}{\partial x^2}(x,y)+\cdots \\ \phi(x,y+h) &= \phi(x,y) + h\frac{\partial \phi}{\partial y}(x,y) + \frac{h^2}{2!}\frac{\partial^2 \phi}{\partial y^2}(x,y)+\cdots
\end{align}となるので、\begin{align}
\frac{\partial^2 \phi}{\partial x^2}(x,y) &\approx \frac{\phi(x+h,y)+\phi(x-h,y)-2\phi(x,y)}{h^2} \\ \frac{\partial^2 \phi}{\partial y^2}(x,y) &\approx \frac{\phi(x,y+h)+\phi(x,y-h)-2\phi(x,y)}{h^2}
\end{align}となります。よって、\begin{align}
\frac{\partial^2 \phi}{\partial x^2}(x,y)+ \frac{\partial^2 \phi}{\partial y^2}(x,y) \approx \frac{\phi(x+h,y)+\phi(x-h,y)+\phi(x,y+h)+\phi(x,y-h)-4\phi(x,y)}{h^2}
\end{align}となりますが、 上のラプラシアン は なので、\begin{align}
(\Delta \phi)(x,y) \approx \frac{\phi(x+h,y)+\phi(x-h,y)+\phi(x,y+h)+\phi(x,y-h)-4\phi(x,y)}{h^2}
\end{align}となります。したがって、グラフラプラシアン はラプラシアン の(-1)倍の離散化とみなせます。
グラフラプラシアンの名前の由来のもう少し深いところ
上で説明したように、グラフ理論のグラフラプラシアンとベクトル解析のラプラシアンには密接な関係があります。ここでは先ほどと同様に重みのない無向グラフを対象として、もう少し深いつながりを見たいと思います。
ベクトル解析のラプラシアン は\begin{align} \Delta = {\rm div} ({\rm grad}) \end{align}のことです。ここで、 は勾配(gradient)の作用素、 は発散(divergence)の作用素を表します。つまり、ラプラシアンは勾配と発散の合成によって表現されます。
このことと同様なことがグラフラプラシアンでも言えて、接続行列の転置が勾配に対応し、接続行列が発散に対応します。つまり、\begin{align} L = BB^T \end{align} が成り立ちます。この関係式は上で既に証明しています(今は重みなしで考えているので であることに注意)。つまり、上で証明したグラフラプラシアンと接続行列の関係式は、ベクトル解析のラプラシアンが勾配と発散によって関係づけられていることから自然な関係式なのだということが分かります。
まず、接続行列の転置 が勾配 に対応することを示します。 を に作用させると、第k成分は\begin{align} (B^T\phi)_k = \sum_{i=1}^n B_{ik} \psi_i \end{align} となります。接続行列 の行は節点、列は枝に対応していたので、 で節点iから節点jに行く向きが付いてると の第k列の第i成分は1、第j成分は-1になります。よって、\begin{align} (B^T\phi)_k = \phi_i-\phi_j \end{align}となり、節点集合上に定義された関数の差、つまり、勾配として を見ることができます。さらに、 自身は枝上に定義された関数として解釈できます。したがって、ベクトル解析の勾配はスカラー場(関数)をベクトル場(関数)にしましたが、グラフ上の勾配(接続行列の転置)は節点集合上の関数を枝集合上の関数にすると解釈できます。
次に、接続行列 が発散 に対応することを示します。 として を作用させると、\begin{align} (B\psi)_i = \sum_{k=1}^m B_{ik}\psi_k \end{align} となりますが、接続行列の定義から、これは\begin{align} (B\psi)_i = \sum_{節点iから出る枝k} \psi_k -\sum_{節点iに入る枝k}\psi_k \end{align}を意味しています。例えば、以下のような感じです。
これは、ベクトル解析の発散のイメージそのものです。ベクトル解析の発散のイメージについては、
あたりを参考にしてください。
以上をまとめると、以下の対応関係が得られます。
先ほどまで、勾配、発散、ラプラシアンはユークリッド空間上の関数に作用させていましたが、リーマン多様体上の関数に対しても勾配、発散、ラプラシアンが定義でき、上のような対応関係が得られます。リーマン多様体については、以下を参考にしてください。
参考文献
記事を書くにあたって参考にした文献です。
(1) 重み付きグラフとグラフラプラシアンの定義のところを参考にしました。グラフ理論の初歩的な内容の解説と、初歩的なグラフ理論の制御工学の問題への応用が分かりやすく説明してあります。
マルチエージェントシステムの制御 (システム制御工学シリーズ)
- 作者: 東 俊一,永原 正章,石井 秀明,林 直樹,桜間 一徳,畑中 健志
- 出版社/メーカー: コロナ社
- 発売日: 2015/08/28
- メディア: 単行本(ソフトカバー)
- この商品を含むブログを見る
(2) ベクトル解析の勾配、発散、ラプラシアンがグラフ理論の接続行列の転置、接続行列、グラフラプラシアンにそれぞれ対応しているという解説を参考にしました。この本は電気回路のネットワークの性質をグラフ理論の概念を使って色々解析しています。面白いです。
(3) リーマン多様体上の関数への勾配、発散、ラプラシアンの作用素が詳しく説明されています。