📂グラフ理論

ユークリッドグラフ

定義 ¹

簡単な定義

ユークリッド空間の有限部分集合 $V \subset \mathbb{R}^{p}$ とカットオフ$\delta \ge 0$ が与えられているとする。ユークリッドグラフは、$V$ を頂点^vertexとし、二点 $u,v \in V$ の距離が $\delta$ より小さい時、そしてその時に限りエッジ^edgeを結ぶグラフである。

難しい定義

ユークリッド空間の有限部分集合 $V \subset \mathbb{R}^{p}$ に対し、$E \subset V \times V$ で以下のように定義される関数 $w : E \to \mathbb{R}$ が与えられたグラフ $G := \left( V,E \right)$ をユークリッドグラフ^{euclidean Graph}とする。 $$ w (u,v) := \left\| u - v \right\|_{2} \qquad u,v \in V $$ ここで $w$ を重み^weightと呼ぶことができる。

---

• $\left\| \cdot \right\|_{2}$ はユークリッドノルムであり、ベクターの各成分を二乗してすべてを加算した後、ルート $\sqrt{\cdot}$ を取る関数である。

説明

紹介された難しい定義は、簡単な定義を含んでいる。単に重みがカットオフより小さいことを基準にすればいい。

ユークリッドグラフがどのように見えるかは、直接見る方がずっと早い。以下は、正方形 $[0,1]^2$ の内部で $20$ 点を均一分布に従ってランダムにサンプリングし、カットオフを $\delta = .2, .3, .5$ に変えながらグラフを描いた例である。カットオフが比較的小さい時は、近い点同士が結ばれ、比較的大きい時は、もう少し遠い点同士も結ばれて、グラフの構造が決まることがわかる。

データとランダムネットワーク

一般的にユークリッドネットワークはランダムネットワークである必要はないが、単に点間の距離を測ってグラフを作るという発想自体がそれほど面白くないため（点をグラフで表現する必要がほとんどないため）、必然的にデータに基づくユークリッドネットワークを考えることになる。任意に与えられた点ではなく、データとして与えられた点たちを、単に遠いか近いかではなく、ネットワーク的な性質に従って研究することができる。

データが適切でないために点がユークリッド空間に属していない場合でも、例えばカテゴリカルデータを含む場合であっても、とりあえずユークリッド空間にマッピングすることで、どうにかしてユークリッドネットワークを構築できる。簡単に言えば、適切な数字を割り当てることであり、洗練された言い方をすれば、エンベディングとも呼ばれる。

“$\mathbb{R}^{p}$ を使ってエンベディングしてネットワークを作成し分析すればいいのではないですか？”

しかし、データに対する深い理解がないまま「エンベディング」を乱用するのはあまりプロフェッショナルな態度ではない。無知に見えたくなければ、慎重に使用すること。

一般化

距離空間

ユークリッドグラフでのユークリッド空間は、一般的な距離空間 $\left( X , d \right)$ に置き換えても定義には全く問題がない。他のすべてが同じであり、重みは次のように調整すればいい。 $$ w (u,v) := d \left( u, v \right) \qquad u,v \in V $$

ムービングネットワーク

ユークリッドネットワーク $G$ の頂点が時間 $t$ に従ってその位置が動く $v = v(t)$ と表される場合、時間 $t$ に依存するユークリッドネットワークとして $G(t)$ のようにムービングネットワーク^{moving Network}と呼ぶことができる。

コード

説明で述べられた視覚化のためのJuliaコードは以下の通りです。

using Graphs, Random
using Plots, GraphRecipes

Random.seed!(0)
V = rand(2,20)
G2, _ = euclidean_graph(V, cutoff = 0.2)
graphplot(G2, x = V[1,:], y = V[2,:], curves = false, size = (400,400), title = "δ = 0.2")
png("G2.png")
G3, _ = euclidean_graph(V, cutoff = 0.3)
graphplot(G3, x = V[1,:], y = V[2,:], curves = false, size = (400,400), title = "δ = 0.3")
png("G3.png")
G5, _ = euclidean_graph(V, cutoff = 0.5)
graphplot(G5, x = V[1,:], y = V[2,:], curves = false, size = (400,400), title = "δ = 0.5")
png("G5.png")

環境

• OS: Windows
• julia: v1.7.0