Parallel Personalized PageRank algorithm implementation.

This implementation uses the standalone GraphFrame interface and runs personalized PageRank in parallel for a fixed number of iterations. This can be run by setting maxIter. The source vertex Ids are set in sourceIds. A simple local implementation of this algorithm is as follows.

var oldPR = Array.fill(n)( 1.0 )
val PR = (0 until n).map(i => if sourceIds.contains(i) alpha else 0.0)
for( iter <- 0 until maxIter ) {
  swap(oldPR, PR)
  for( i <- 0 until n ) {
    PR[i] = (1 - alpha) * inNbrs[i].map(j => oldPR[j] / outDeg[j]).sum
    if (sourceIds.contains(i)) PR[i] += alpha
  }
}

alpha is the random reset probability (typically 0.15), inNbrs[i] is the set of neighbors which link to i and outDeg[j] is the out degree of vertex j.

Note that this is not the "normalized" PageRank and as a consequence pages that have no inlinks will have a PageRank of alpha. In particular, the pageranks may have some values greater than 1.

The resulting vertices DataFrame contains one additional column:

• pageranks (VectorType): the pageranks of this vertex from all input source vertices

The resulting edges DataFrame contains one additional column:

• weight (DoubleType): the normalized weight of this edge after running PageRank