A friend (who works on social networking analysis) asked this over at twitter:

What is the n-th power of the adjacency matrix equal to, in terms of paths, NOT walks?

EDIT: Complimentary question: "Is there any algorithm counting paths between pairs of nodes, given the adjacency list or matrix?"

(If there's a way to transfer the question to math.SE as a more appropriate forum, please help me do so).

loop-erased random walkson a graph, where one does a random walk and erases a loop (cycle) as soon as it is created. This gives a model for a random path that is closely connected to random spanning trees. See en.wikipedia.org/wiki/Loop-erased_random_walk. However, this model has little connection with powers of the adjacency matrix. $\endgroup$