📂그래프이론

유클리드 그래프

정의 ¹

쉬운 정의

유클리드 공간의 유한 부분집합 $V \subset \mathbb{R}^{p}$ 와 컷오프^cutoff $\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$ 로 바꿔가며 그래프를 그려본 것이다. 컷오프가 상대적으로 작을 땐 가까운 점들끼리 이어지고, 상대적으로 클 땐 조금 더 먼 점들끼리 이어져서 그래프가 결정되는 것을 확인할 수 있다.

데이터와 랜덤 네트워크

일반적으로 유클리드 네트워크가 랜덤 네트워크일 필요는 없지만, 단순히 점들 사이의 거리를 재서 그래프를 만든다는 발상 자체는 그다지 흥미롭지 않기 때문에(굳이 점들을 그래프로 표현할 이유가 없으므로) 필연적으로 데이터^data에 기반한 유클리드 네트워크를 고려하게 된다. 작위적으로 주어진 점들이 아닌 데이터로써의 점들이 주어졌을 때, 이들을 단순히 멀고 가깝고가 아닌 네트워크적인 성질에 따라 연구할 수 있다.

데이터가 좋지 않아서 점들이 유클리드 공간에 속하지 않은 경우, 예로써 범주형 데이터를 포함한다고 하더라도 급한대로 유클리드 공간으로 보내면 어쨌거나 유클리드 네트워크는 구축할 수 있다. 이를 쉽게 말하면 그냥 적당한 숫자를 매기는 것이고, 유식해보이는 말로는 임베딩^embedding이라 하기도 한다.

“그거 그냥 $\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)$ 와 같이 표현된다면, 무빙 네트워크 $G(t)$ 와 같이 시간 $t$ 에 종속된 유클리드 네트워크를 무빙 네트워크^{moving Network}라 부를 수 있다.

코드

다음은 설명에서의 시각화를 위한 줄리아 코드다.

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