---- > [!definition] Definition. ([[geodesic distance in networks]]) > A **geodesic path** in a [[network]] is a shortest [[parameterized curve]] between a pair of nodes, i.e., the walk that traverses the fewest number of edges. The **geodesic distance** between two nodes is defined to be $d(i,j)=d_{ij}:=\min \{ r \in \mathbb{N} : [A^{r}]_{ij} > 0\},$ > provided the set $\{ r \in \mathbb{N} : A^{r} >0 \}$ is [[bounded set|bounded]] (that is, provided there exists a path at all). $[A^{r}]_{ij}$ denotes the $ij^{th}$ entry of $r^{th}$ power of the [[network]]'s [[adjacency matrix]]. > \ > The set might not be bounded if the [[network]] has [[component of a graph|disconnected components]]. In this case $d_{ij}$ is undefined, or by convention sometimes said to be $\infty$. > \ > If the [[network]] is connected, then $d(i,j)$ is a [[metric]] on it. > [!justification] > The **geodesic distance** definition follows directly from [[number of walks of given length on a network]]: it is the smallest number $r$ for which there exists a path of length $r$ from node $j$ to $i$. > [!justification] > We need to show that $d$ is a [[metric]]. > > Positive-definiteness is immediate: fixing vertices $i$ and $j$ in the ([[connected]]) [[network|graph]], we by definition have $d(i,j) \geq 0$ because $d(i,j)$ is equal to the number of entries in a nonempty sequence minus one. Moreover, $d(i,j)=0$ if and only if the path from $i$ to $j$ has one entry, namely the entry $i=j$. > Symmetry is also immediate, for the length of any path $(v_{1},\dots,v_{n})$ from $v_{1}$ to $v_{n}$ is of course equal to the length of a path $(v_{n}, \dots, v_{1})$ from $v_{n}$ to $v_{1}$. This includes the path with infimum-length which realize the geodesics. > Let $i,j,k \in \mathcal{V}$. Letting $P_{ik}$ denote the set of all paths from $i$ to $k$ and $\ell$ a function that returns the length of a finite sequence $s$, it is by construction that $d(i,k)=\inf_{p \in P_{ik}} \{ \ell (p) \} \leq \ell(s) \text{ for any } s \in P_{ik}. (*)$ Since lengths are integers, there exists a geodesic path $g_{ij}=(v_{1}^{(i)},\dots, v_{n}^{(j)})$ realizing the infimum length $d(i,j)$ of paths from $i$ to $j$, and likewise a geodesic path $g_{jk}=(w_{1}^{(j)},\dots,w_{m}^{(j)})$ realizing the infimum length $d(j,k)$ of paths from $j$ to $k$. Now, $s_{}:=(v_{1}^{(i)},\dots,v_{n}^{(j)},w_{1}^{(j)},\dots,w_{m}^{(k)})$ is a path from $i$ to $k$ with length $\ell(s)=d(i,j)+d(j,k)$. By $(*)$ we then have $d(i,k) \leq \ell(s) = d(i,j) +d(j,k)$ and so the [[triangle inequality]] holds. ^c086f3 > [!basicexample] > ![[CleanShot 2023-09-19 at 22.32.09.jpg]] ---- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```