無向グラフの Laplacian では以下の定理が成り立ちます。
- 定理（無向グラフ ver.）
- Laplacian の固有値 0 の重複度は、グラフの連結成分の数に等しい。
これの有向グラフ ver. を探し求めて三千里、ようやく同様の定理を見つけました。
用語の定義などは後述するとして、先に定理を述べておきます。
- 定理（有向グラフ ver.）
- Laplacian の固有値 0 の重複度は、グラフの Reach の数に等しい。
以下では、Laplacian や Reach などの定義をまとめます。
In-degree Laplacian
$G=(V,E)$ を有向グラフとします。
$V$ と $E$ はそれぞれノード集合とエッジ集合で、ノードは $1,2,\ldots,n$ と表されているとします。
$G$ の入次数行列 $D$ とは、対角成分にノード $i$ の入次数 $d_i$ を並べた対角行列のことをいいます。
D := \mathrm{diag}(d_1, d_2, \ldots, d_n).
$G$ の隣接行列 $A$ とは、その第 $(i,j)$ 成分 $a_{ij}$ について、ノード $i$ からノード $j$ へのエッジが存在するとき $a_{ij}=1$、存在しないとき $a_{ij}=0$ を代入して得られる $n\times n$ 行列のことをいいます。
$G$ の入次数行列 $D$ と隣接行列 $A$ に対して、$L:=D-A$ を In-degree Laplacian といいます1。
Python による実装
import networkx as nx
import numpy as np
def indegree_laplacian (G: nx.DiGraph):
D = np.diag([ d for _, d in G.in_degree() ])
A = nx.adjacency_matrix(G).toarray()
return D - A
上記の定理（有向グラフ ver.）の Laplacian は、この In-degree Laplacian のことです。
一般に、In-degree Laplacian は非対称行列なので、固有値に複素数が出てくることがあります。
Reach
ノード $i$ からノード $j$ への経路が存在するとき、これを $i\rightsquigarrow j$ で表すことにします。
ノード $i$ の Reachable set $R(i)$ とは、$i$ を出発して到達可能なノード全体（$i$ 自身も含む）の集合のことです。
R(i) := \{i\} \cup \{ j \in V \mid i \rightsquigarrow j \}.
特に、（包含関係において）極大な Reachable set を $G$ の Reach といいます。
Python による実装
import networkx as nx
def reachableset (G: nx.DiGraph, i):
Ri = {i} # Reachable set
I = {i}
while True:
J = { j for i in I
for j in G.successors(i)
if j not in Ri }
if len(J) == 0:
return Ri
else:
Ri |= J
I = J.copy()
def reaches (G: nx.DiGraph):
V = set(G.nodes())
Rs = [] # Reaches
while len(V) > 0:
i = V.pop()
Ri = reachableset(G, i)
V = V - Ri
Rs_rm = [ R for R in Rs if R <= Ri ]
[ Rs.remove(R) for R in Rs_rm ]
Rs.append(Ri)
return Rs
Reach の条件は、弱連結より少し強く、片方向連結2より少し弱い条件と言えます。
片方向連結成分と同様に、2 つの異なる Reach で同じノードを共有することがあります。
簡単な例で確認
次のような 5 個のノードからなる有向グラフ $G$ を考えます。
$G$ には 2 個の Reach $\{1,2,3\}$、$\{2,3,4,5\}$ があります。
$G$ の入次数行列 $D$ と隣接行列 $A$ はそれぞれ次の通りです。
D := \begin{pmatrix}
0 & & & & \\
& 2 & & & \\
& & 2 & & \\
& & & 0 & \\
& & & & 1
\end{pmatrix}, \quad
A := \begin{pmatrix}
0 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0\\
0 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 1\\
0 & 0 & 0 & 0 & 0
\end{pmatrix}.
したがって、$G$ の In-degree Laplacian $L$ は以下のようになります。
L := D - A = \begin{pmatrix}
0 & -1 & 0 & 0 & 0\\
0 & 2 & -1 & 0 & 0\\
0 & -1 & 2 & 0 & 0\\
0 & 0 & -1 & 0 & -1\\
0 & 0 & 0 & 0 & 1
\end{pmatrix}
これの固有多項式は $-\lambda^2(\lambda-1)^2(\lambda-3)$ なので3、固有値 0 の重複度が 2 と求まります。
Reach の数が 2 個だったので、確かに、定理（有向グラフ ver.）が成り立っています。
ちなみに、$G$ の強連結成分等の数は次のようになっています。
| 連結性 | 成分の数 |
|---|---|
| 強連結 | 4 |
| 弱連結 | 1 |
| 片方向連結 | 3 |
| Reach | 2 |
参考
- J. J. P. Veerman and R. Lyons. (2020) A primer on laplacian dynamics in directed graphs. arXiv, abs/2002.02605.