Juliaでグラフラプラシアンの固有値を求めて描画する

内容

• 有向グラフの隣接行列 $A$から、次数行列 $D$ を計算する
• 最大の次数 $\Delta$ のとき、中心 $(\Delta, 0)$ 半径 $\Delta$ の円を描画する
• グラフラプラシアン $L = D - A$の固有値をJuliaで求めて二次元プロットする

例題

• 隣接行列 $A = \begin{pmatrix}
  0 & 0 & 0 & 1 & 0 \newline
  1 & 0 & 1 & 0 & 0 \newline
  0 & 0 & 0 & 0 & 1 \newline
  0 & 1 & 0 & 0 & 0 \newline
  1 & 0 & 0 & 0 & 0
  \end{pmatrix}
  $

• 出力

コード

# -*- coding: utf-8 -*-
# graph laplacian and visualization of eigen values

using PyPlot
using PyCall
@pyimport matplotlib.patches as patch

# adjacency matrix
A = [0 0 0 1 0;
     1 0 1 0 0;
     0 0 0 0 1;
     0 1 0 0 0;
     1 0 0 0 0]

# degrees, maximum degree and laplacian L
D = diagm(squeeze(sum(A, 2), 2))
Δ = maximum(D)
L = D - A

# eigen values
evs = eigvals(L)
for cv in evs
    println(real(cv), ",", imag(cv))
end

# plot
figure(figsize=(5, 5))

# circle
c = patch.Circle([Δ, 0.0], Δ, fc="red", zorder=0, alpha=0.3)
ax = gca()
grid(true)
ax[:add_patch](c)
for cv in evs
    plot(real(cv), imag(cv), "rx")
end
xlim(-0.1, 2*Δ+0.1)
ylim(-Δ-0.1, Δ+0.1)
tight_layout()
show()