初級Mathマニアの寝言

数学は色々なところで応用可能であり、多くの人が数学の抽象的な概念の意味や意義を鮮明に知ることができれば今まで以上に面白い物や仕組みが生まれるかもしれません。このブログは数学を専門にしない人のために抽象的な概念の意味や意義を分かりやすく説明することを目的としています。数学を使って何かしたい人のお役に立てたら幸いです。

グラフラプラシアン

この記事では、電力網のネットワーク、交通網のネットワーク、人間関係のネットワーク、神経ネットワーク、遺伝子ネットワークのようなネットワークシステムの性質を解析する際に重要なグラフラプラシアンについて解説します(枝に向きのないネットワークだけ解説します)。

グラフ、隣接行列、次数行列

下図のように節点と枝から構成されるネットワークを数学的に表現するには、グラフという概念が役立ちます。

f:id:ogyahogya:20180119164435p:plain

グラフとは、節点の集合  V と枝の集合  E\subset V\times V の組  (V, E) のことです。例えば上のネットワークだと節点集合が \{1, 2, 3, 4, 5, 6\} で枝集合が  \{(1,2), (1,3), (1,5), (2,1),(2,3), (3,1), (3,2), (3,6), (4,5), (4,6), (5,1), (5,4), (6,3),(6,4)\} です。このように  (i,j)\in E なら  (j,i)\in E が成り立つグラフを正確には無向グラフといいます(この記事では、無向グラフだけを説明します)。節点は頂点、枝は辺とも呼ばれます。

上のグラフはそれぞれの枝が同等の重要度を持っているとすると、次のような行列で表現できます。

f:id:ogyahogya:20180123123124p:plain
つまり、上のグラフは枝  (1,2) が存在するので行列の  (1,2) 成分と  (2,1) 成分のところを1として、枝  (1,4) は存在しないので行列の  (1,4) 成分と  (4,1) 成分を0としています。他の成分も同様に定義すると、上のような対称行列が得られます。逆に上の対称行列から上のグラフが構成できます。もしグラフのそれぞれの枝で重要度が異なる(重み付きグラフという)なら、重要度に応じて1以外の正の実数を行列の成分に定義することで重み付きグラフを対称行列によって表現できます。

より数学的には、 グラフ  G=(V,E) の枝と重み(重要度)との対応関係を表す関数  w:E\rightarrow {\bf R}_+ をグラフ G 上の重み関数といいます(  {\bf R}_+ は正の実数の集合)。ただし、 (i,j)\in E なら  w ( (i,j) )=w( (j,i) ) を満たします。この重み付きグラフを  (G,w) と書きます。このような重み付きグラフ  (G,w)を行列によって表現した対称行列  A=(a_{ij})隣接行列といい、次のように定義されます。

f:id:ogyahogya:20180123162009p:plain

通常のグラフ  G はすべての  (i,j)\in E に対して  w( (i,j) )=1 となる重み付きグラフのことです。

重み付きグラフ  (G,w) が与えられたとき、節点  i\in V次数 d_i:= \sum_{j=1}^n a_{ij} で定義します。ただし、 n はそのグラフの節点の数です。次のように各節点の次数を対角上に並べた対角行列を重み付きグラフ  (G,w)次数行列と呼びます。\begin{align}
D={\rm diag}( d_1, d_2,\ldots, d_n)
\end{align}

例えば上のグラフが与えられたとすると、次数行列は  D={\rm diag} (3, 2, 3, 2, 2, 2) です。

グラフラプラシアン、接続行列

重み付きグラフ  (G,w) が与えられたとします。このとき、隣接行列  A と次数行列  D を用いて定義される次の行列  L\in {\bf R}^{n\times n} を重み付きグラフ  (G,w)グラフラプラシアンといいます。\begin{align}
L:=D-A
\end{align} グラフラプラシアンの定義からグラフラプラシアン  L\in {\bf R}^{n\times n} は固有値 0 を少なくとも一つもち、1をすべての成分に並べたベクトル  {\bf 1}\in {\bf R}^n は固有値 0 に対応する固有ベクトルとなります。なぜなら、 L{\bf 1} = 0 となるからです。

グラフラプラシアンは接続行列と呼ばれる行列によっても特徴付けられます。接続行列を定義するために、重み付き無向グラフ  (G,w)枝に一意な番号と任意に向きを付けます。例えば、はじめに与えた例のグラフの枝に次のように番号と向きをつけてみましょう。

f:id:ogyahogya:20180124100158p:plain

 この枝に番号と向きの付いたグラフは次の行列と対応付けることができます。

f:id:ogyahogya:20180124104614p:plain
つまり、枝が節点から出るときに 1 を、枝が節点に入るときに -1 を、どちらでもないときに 0 を割り当てるというルールで枝に番号と向きの付いたグラフを行列表現できます。このような行列を接続行列といい、正確には次のように定義されます。
f:id:ogyahogya:20180124114512p:plain
重み付き無向グラフの接続行列を定義したとき、各枝には番号が付いています。したがって、枝の上に定義されていた重み関数  w:E\rightarrow {\bf R}_+ から各枝に付いている番号の上の関数  w_e w_e = w( (i,j) ) = w( (j,i) ) (  e= (i,j) = (j,i) ) というように定義されます
 
重み付き無向グラフ  (G,w) のグラフラプラシアン  L\in {\bf R}^{n\times n} と接続行列  B\in {\bf R}^{n\times m} は、枝の番号の上に定義された関数  w_e を用いて次の関係で結ばれます。
f:id:ogyahogya:20180124122305p:plain
この等式は枝に任意に向きを付けた接続行列から、グラフラプラシアンという枝の向きに独立な行列を構築できることを意味しています。また、この等式から重み付き無向グラフ  (G,w)グラフラプラシアンは固有値 0 を少なくとも一つ持つ半正定値対称行列であることが即座に分かります。この等式の証明は以下の通りです。

f:id:ogyahogya:20180124164228p:plain

f:id:ogyahogya:20180124164354p:plain

f:id:ogyahogya:20180124164514p:plain

 グラフラプラシアンという名前の由来

グラフラプラシアンという名前はベクトル解析で登場するラプラシアンという作用素に由来します。ここでは重みのない無向グラフ  (G,w) 、つまり任意の  (i,j)\in E に対して  w( (i,j) ) =1 となる無向グラフのグラフラプラシアンがどのようにラプラシアンに関係しているかを説明します。

まず、グラフラプラシアン  L\in {\bf R}^{n\times n} のベクトル  \psi\in {\bf R}^n への作用は次のようになることに注意します。

f:id:ogyahogya:20180125133359p:plain

次に、以下のような向きと重みのない格子グラフを考えます。

この格子グラフの節点を格子座標  (x,y) で表し、節点の集合を  V とすると、上図のようにグラフの境界から離れた節点の次数は4なので、グラフラプラシアン  L の節点集合上の関数  \phi: V\rightarrow {\bf R} への作用は、グラフラプラシアンのベクトルへの作用のアナロジーで、\begin{align}
(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}となると考えられます。
さらに今度は同じ記号を使ってユークリッド空間  {\bf R}^2 上のテイラー展開可能な関数 \phi: {\bf R}^2\rightarrow {\bf R} を考えます。このとき、  h を非常に小さいとして、 \phi(x+h,y) \phi(x,y+h) を点  (x,y)\in {\bf R}^2 の周りでテイラー展開すると、\begin{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}となりますが、 {\bf R}^2 上のラプラシアン  \Delta \Delta= \frac{\partial^2}{\partial x^2} + \frac{\partial^2}{\partial y^2} なので、\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}となります。したがって、グラフラプラシアン  L はラプラシアン  \Delta の(-1)倍の離散化とみなせます

グラフラプラシアンの名前の由来のもう少し深いところ

上で説明したように、グラフ理論のグラフラプラシアンとベクトル解析のラプラシアンには密接な関係があります。ここでは先ほどと同様に重みのない無向グラフを対象として、もう少し深いつながりを見たいと思います。

ベクトル解析のラプラシアン  \Delta は\begin{align} \Delta = {\rm div} ({\rm grad}) \end{align}のことです。ここで、 {\rm grad} は勾配(gradient)の作用素、 {\rm div} は発散(divergence)の作用素を表します。つまり、ラプラシアンは勾配と発散の合成によって表現されます。

このことと同様なことがグラフラプラシアンでも言えて、接続行列の転置が勾配に対応し、接続行列が発散に対応します。つまり、\begin{align} L = BB^T \end{align} が成り立ちます。この関係式は上で既に証明しています(今は重みなしで考えているので  w_1=w_2=\cdots =w_m=1 であることに注意)。つまり、上で証明したグラフラプラシアンと接続行列の関係式は、ベクトル解析のラプラシアンが勾配と発散によって関係づけられていることから自然な関係式なのだということが分かります。

まず、接続行列の転置  B^T\in {\bf R}^{m\times n} が勾配  {\rm grad} に対応することを示します。  B^T \phi = (\phi_1,\phi_2,\ldots, \phi_n)\in {\bf R}^n に作用させると、第k成分は\begin{align} (B^T\phi)_k = \sum_{i=1}^n B_{ik} \psi_i \end{align} となります。接続行列  B の行は節点、列は枝に対応していたので、 k=(i,j)\in E で節点iから節点jに行く向きが付いてると  B の第k列の第i成分は1、第j成分は-1になります。よって、\begin{align} (B^T\phi)_k = \phi_i-\phi_j \end{align}となり、節点集合上に定義された関数の差、つまり、勾配として  (B^T\phi)_k を見ることができます。さらに、 B^T\phi 自身は枝上に定義された関数として解釈できます。したがって、ベクトル解析の勾配はスカラー場(関数)をベクトル場(関数)にしましたが、グラフ上の勾配(接続行列の転置)は節点集合上の関数を枝集合上の関数にすると解釈できます

次に、接続行列  B\in {\bf R}^{n\times m} が発散  {\rm div} に対応することを示します。 \psi = (\psi_1,\psi_2,\ldots, \psi_m)\in {\bf R}^m として  B を作用させると、\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}を意味しています。例えば、以下のような感じです。

f:id:ogyahogya:20180126111510p:plain

これは、ベクトル解析の発散のイメージそのものです。ベクトル解析の発散のイメージについては、

EMANの物理学・電磁気学・ガウスの定理の証明

あたりを参考にしてください。

以上をまとめると、以下の対応関係が得られます。

f:id:ogyahogya:20180125165128p:plain

先ほどまで、勾配、発散、ラプラシアンはユークリッド空間上の関数に作用させていましたが、リーマン多様体上の関数に対しても勾配、発散、ラプラシアンが定義でき、上のような対応関係が得られます。リーマン多様体については、以下を参考にしてください。

ogyahogya.hatenablog.co

参考文献

記事を書くにあたって参考にした文献です。

(1) 重み付きグラフとグラフラプラシアンの定義のところを参考にしました。グラフ理論の初歩的な内容の解説と、初歩的なグラフ理論の制御工学の問題への応用が分かりやすく説明してあります。

マルチエージェントシステムの制御 (システム制御工学シリーズ)

マルチエージェントシステムの制御 (システム制御工学シリーズ)

  • 作者: 東 俊一,永原 正章,石井 秀明,林 直樹,桜間 一徳,畑中 健志
  • 出版社/メーカー: コロナ社
  • 発売日: 2015/08/28
  • メディア: 単行本(ソフトカバー)
  • この商品を含むブログを見る
 

 (2) ベクトル解析の勾配、発散、ラプラシアンがグラフ理論の接続行列の転置、接続行列、グラフラプラシアンにそれぞれ対応しているという解説を参考にしました。この本は電気回路のネットワークの性質をグラフ理論の概念を使って色々解析しています。面白いです。

線形代数とネットワーク

線形代数とネットワーク

 

 (3) リーマン多様体上の関数への勾配、発散、ラプラシアンの作用素が詳しく説明されています。

ラプラシアンの幾何と有限要素法 (朝倉数学大系)

ラプラシアンの幾何と有限要素法 (朝倉数学大系)