What is an edge hop? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-11-21T14:49:45Z https://cs.stackexchange.com/feeds/question/38375 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/38375 2 What is an edge hop? Kelmikra https://cs.stackexchange.com/users/24518 2015-02-15T01:14:42Z 2015-02-15T02:37:39Z <p>I've tried googling it, but found nothing. Here is the context it's in:</p> <p>From <em>Bayesian Reasoning and Machine Learning</em>:</p> <p>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.</p> https://cs.stackexchange.com/questions/38375/-/38378#38378 4 Answer by Yuval Filmus for What is an edge hop? Yuval Filmus https://cs.stackexchange.com/users/683 2015-02-15T02:37:39Z 2015-02-15T02:37:39Z <p>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.</p>