patternMinor
What is an edge hop?
Viewed 0 times
edgehopwhat
Problem
I've tried googling it, but found nothing. Here is the context it's in:
From Bayesian Reasoning and Machine Learning:
Adjacency matrices may seem wasteful since many of the entries are zero. However, they have a useful property that more than redeems them. For an N x N adjacency matrix A, powers of the adjacency matrix $[A^k]_i$$_j$ specify how many paths there are from node i to node j in k edge hops. If we include 1's on the diagonal of A then $[A^{N-1}]_i$$_j$ is non-zero when there is a path connecting i to j in the graph. If A corresponds to a DAG the non-zero entries of the jth row of $[A^{N-1}]_i$$_j$ correspond to the descendants of node j.
From Bayesian Reasoning and Machine Learning:
Adjacency matrices may seem wasteful since many of the entries are zero. However, they have a useful property that more than redeems them. For an N x N adjacency matrix A, powers of the adjacency matrix $[A^k]_i$$_j$ specify how many paths there are from node i to node j in k edge hops. If we include 1's on the diagonal of A then $[A^{N-1}]_i$$_j$ is non-zero when there is a path connecting i to j in the graph. If A corresponds to a DAG the non-zero entries of the jth row of $[A^{N-1}]_i$$_j$ correspond to the descendants of node j.
Solution
An "edge hop" is the "act" of crossing an edge. It's a figurative term. The entry $[A^k]_{ij}$ counts how many paths there are from $i$ to $j$ of length $k$. A path of length $k$ entails traversing $k$ edges, hence the $k$ edge hops.
Context
StackExchange Computer Science Q#38375, answer score: 7
Revisions (0)
No revisions yet.