📂Graph Theory

Euclidean Graph

Definitions ¹

Simple Definition

Let us assume that we have a finite subset $V \subset \mathbb{R}^{p}$ of the Euclidean space and a cutoff $\delta \ge 0$. A Euclidean Graph is defined as a graph that connects an edge between two points $u,v \in V$ only when the distance between them is less than $\delta$, with $V$ as vertices.

Complex Definition

For a finite subset $V \subset \mathbb{R}^{p}$ of the Euclidean space, a Euclidean Graph is defined as the graph $G := \left( V,E \right)$ given by the function $w : E \to \mathbb{R}$ defined as follows in $E \subset V \times V$: $$ w (u,v) := \left\| u - v \right\|_{2} \qquad u,v \in V $$ Here, $w$ can be referred to as the weight.

---

• $\left\| \cdot \right\|_{2}$ is the Euclidean norm, a function that squares each component of a vector, sums them all up, and then takes the root $\sqrt{\cdot}$.

Explanation

The complex definition encapsulates the simple definition. One simply needs to consider the weight being less than the cutoff as the criterion.

To get a clearer idea of what a Euclidean graph looks like is much faster by seeing it directly. Below are examples of graphs drawn by randomly sampling $20$ points inside a square $[0,1]^2$ according to a uniform distribution and changing the cutoff to $\delta = .2, .3, .5$. When the cutoff is relatively small, closer points are connected, and when it’s relatively large, even points that are a bit further away are connected, determining the structure of the graph.

Data and Random Networks

Generally, Euclidean networks do not have to be random networks, but since the idea of creating a graph by measuring the distances between points is not that interesting (because there’s hardly any reason to represent points as a graph), one inevitably considers Euclidean networks based on data. When points are not arbitrarily given but are given as data, they can be studied based on network properties, not merely by how close or far they are.

Even if the data is not suitable, meaning it doesn’t belong in Euclidean space, including categorical data, Euclidean networks can still be constructed by hastily mapping it to Euclidean space anyway. In simple terms, it’s just assigning appropriate numbers, and in more sophisticated terms, it’s also called embedding.

“Why not just use $\mathbb{R}^{p}$ for embedding to create and analyze the network?”

However, recklessly using ’embedding’ without a deep understanding of the data is not exactly a professional attitude. Better think carefully before using it if you don’t want to appear ignorant.

Generalization

Metric Space

The Euclidean space in the Euclidean Graph can be replaced with a general metric space $\left( X , d \right)$ without any issues with the definition. Everything else remains the same, and the weight is simply adjusted as follows: $$ w (u,v) := d \left( u, v \right) \qquad u,v \in V $$

Moving Networks

If the vertices $G$ of the Euclidean network move over time $t$ as expressed by $v = v(t)$, then the time-dependent Euclidean network like $G(t)$ can be referred to as a Moving Network.

Code

Below is the Julia code for visualization described in the explanation.

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")

Environment

• OS: Windows
• julia: v1.7.0