Using linear algebra to determine how information diffuses through a network given a start node I was looking at some old slides for a lecture and I encountered Network Diffusion, where two models were introduced Threshold and Cascade about how information diffuses in a network, but it never did clear up the good way of calculating how information diffuses through a network given a start node.
I've searched and searched and I can't seem to find anything(Possibly because I'm not searching for the right things) about how to actually do this, it seems like it is a very simple thing to do but my background of linear algebra is still fairly weak so I can't intuit my way to a solution.
As an example, given the network represented as a adjacency matrix:
$$\begin{pmatrix}
 0 & 1 & 0 & 0 & 0 \\
 1 & 0 & 0 & 1 & 0 \\
 0 & 0 & 0 & 1 & 1 \\
 0 & 1 & 1 & 0 & 0 \\
 0 & 0 & 1 & 0 & 0
\end{pmatrix}$$
I want to know how an 'infection' diffuses in the network given an initial starting point. Every node has a 100% chance of infecting its neighbours, so for example with Node 1 as a starting point:


*

*Node 1 infects Node 2

*Node 2 infects Node 4

*Node 4 infects Node 3

*Node 3 infects Node 5

*Done.


I can do this with an ad hoc algorithm, but I'd rather know the 'good way' of doing this.
Hope someone can help.
 A: As Ian pointed out, $A^k$ contains the number of walks from $i$ to $j$ of length $k$.
You start with a set of nodes $\{i_1, i_2, \dots i_k\}$ that are infected. You can represent this by a vector $v$, where $v_k = 1$ if node $k$ is infected, 0 otherwise.
If you want to check successively which nodes are infected in which step, you can do the following.


*

*Set $k = 0$ and $w_0 = v$.

*Compute $w_{k+1} = A^Tw_k$. This is the sum of the rows corresponding to the nodes infected in the previous step, i.e. $w_{k+1}$ will contain the number of connections from a node infected in the previous step to any other node.

*Mark down the positions of the nonzero elements of $w_k$ which has not appeared earlier. These are the nodes that were infected at this step, but not earlier.

*If all nodes have been infected, finish. Otherwise, go to step 2.


So, for your example, you get:
$$\begin{align}
w_0 = \left(
\begin{array}{c}
 1 \\
 0 \\
 0 \\
 0 \\
 0
\end{array}
\right), &
w_1 = \left(
\begin{array}{c}
 0 \\
 1 \\
 0 \\
 0 \\
 0
\end{array}
\right),
w_2 = \left(
\begin{array}{c}
 1 \\
 0 \\
 0 \\
 1 \\
 0
\end{array}
\right),
w_3 = \left(
\begin{array}{c}
 0 \\
 2 \\
 1 \\
 0 \\
 0
\end{array}
\right),
w_4 = \left(
\begin{array}{c}
 2 \\
 0 \\
 0 \\
 3 \\
 1
\end{array}
\right)
\end{align}$$
Of course, this is probably not very efficient. Doing matrix multiplications is not super cheap. It is probably faster to just scan the matrix: If you start with node $i$ being infected, just scan row $i$ to see which nodes will be infected in the second step, and so on, keeping a stack of the nodes that will be visited in the next step and keeping track of which nodes have already been visited.
If you want to only answer the question "Which nodes have been infected at step $k$ or earlier?" you can compute $v^T(I + A + A^2 + \cdots + A^k)$ and see which elements are non-zero. You can check out this answer on Stack Overflow for some tricks on computing this sum.
What you are basically asking for here is to find a "generalized neighborhood", given one or some nodes as starting point. This math.se answer might give some hints, if you are open to non-linear algebra answers.
