title: How to calculate a personalized PageRank over millions of nodes?
body: <p>I have a sparse graph containing about a million nodes and 10 million edges. I want to calculate a <em>personalized</em> PageRank for each node, where by personalized PageRank at node n I mean:</p>
  
  <pre><code># x_0 is a column vector of all zeros, except a 1 in the position corresponding to node n
  # adjacency_matrix is a matrix with a 1 in position (i, j) if there is an edge from node i to node j
  
  x_1 = 0.5 * x_0 + 0.5 * adjacency_matrix * x_0
  x_2 = 0.5 * x_0 + 0.5 * adjacency_matrix * x_1
  x_3 = 0.5 * x_0 + 0.5 * adjacency_matrix * x_2
  
  # x_3 now holds the personalized PageRank scores
  
  # i'm basically approximating the personalized PageRank by running this for only 3 iterations
  </code></pre>
  
  <p>I tried coding this up using NumPy, but it was taking too long to run. (about 1 second to calculate the personalized PageRank for each node) </p>
  
  <p>I also tried changing x_0 to be matrix (by combining the column vectors of several different nodes), but this also didn't help much, and actually made the computation take much longer. (possibly because the matrix gets dense fairly quickly, and so it no longer fits in RAM? I'm not sure)</p>
  
  <p>Is there another suggested way to calculate this, preferably in Python? I also thought about going the non-matrix approach to PageRank calculation, by doing a kind of simulated random walk for three iterations (i.e., I start each node with a score of 1, then propagate this score to its neighbors, etc.), but I'm not sure if this would be any faster. Would it be, and if so, why?</p>