Question

Python PageRank-Nibble

Parallel PageRank-Nibble is described in in Section 3.3 of [1]. At a high level, the algorithm works as follows:

• each node i in the graph gets two new quantities, p[i] and r[i].  p values will indicate the PageRank score, and r holds a "residual"
• add 1 unit of "mass" to r[seed]
• iteratively, for each node i with "enough residual" r[i]
  • transfer some proportion of the mass in residual r[i] to PageRank value p[i]
  • distribute some proportion of the remaining mass in residual r[i] equally to the residuals of i's neighbors

"Enough residual" and "some proportion" are parameters of the algorithm that impact the locality and precision of the algorithm. Once no nodes have enough residual to continue, the algorithm terminates and returns p[i] for each node. See Section 3.3 of [1] for a more in-depth description.

Figure 6 in [1] gives pseudocode for a couple of variants of the PR-nibble algorithm. Specifically, we want to implement optimized parallel PR-nibble. To avoid confusion, pseudocode for the exact variant of the algorithm that we want you to implement is shown below:

passed to EDGEMAP ► passed to VERTEXMAP 1: sparseSet p = {} 2: sparseSet r={} 3: sparseSet r' = {} 4: procedure UPDATENGH(s, d) 5: fetchAdd(&r'[d], ((1 – a)/(1+a))r[s]/d(s)) 6: procedure UPDATESELF(U) 7: p[u] = p[u] + (2a/(1+ a) r[u] 8: r'[u] = 0 9: procedure PR-NIBBLE(G, X, €, a) r= {(x, 1)} vertexSubset Frontier = {C} while (size(Frontier) > 0) do r = r VERTEX MAP(Frontier, UPDATESELF) 15: EDGEMAP(G, Frontier, UPDATENGH) 16: r=r 17: Frontier = {v | r[v] > d(ue} 18: return p ► seed vertex 13: 14: using filter

Note: This is a combination of Fig 5 and Fig 6 in [1], plus correction of a typo on Fig 5 line 13.

In the pseudocode above:

• d(v) is a function that returns the degree of vertex v.  epsilon and alpha are parameters.
• vertexMap(set Frontier, function fn) is a function that calls fn(x) on each node x of Frontier
• edgeMap(graph G, set F, function fn) is a function that calls

for each node x in F
   for each node neib adjacent to x in G
       fn(x, neib)

Note: The algorithm is called "parallel PR-nibble" because the vertexMap and edgeMap can be parallelized. This does not mean that they must be parallelized -- we highly recommend you implement a serial version of this algorithm first, and only add parallelization as an optimization once you have an implementation that passes the correctness checks.

Base code:

import os
import sys
import numpy as np
from time import time
from scipy.io import mmread


def parallel_pr_nibble(seeds, adj, alpha, epsilon):
    print(adj)
    pnib_scores = []
    for seed in seeds:
        # TODO
        pnib_score = 0
        pnib_scores.append(pnib_score)

    return pnib_scores


def main():
    adj = mmread('jhu.mtx').tocsr()
    t = time()
    pnib_seeds = list(range(50))
    pnib_scores = parallel_pr_nibble(pnib_seeds, adj, alpha=0.15, epsilon=1e-6)
    assert pnib_scores.shape[0] == adj.shape[0]
    assert pnib_scores.shape[1] == len(pnib_seeds)
    pnib_elapsed = time() - t
    print('parallel_pr_nibble: elapsed = %f' % pnib_elapsed, file=sys.stderr)
    os.makedirs('results', exist_ok=True)
    np.savetxt('results/pnib_score.txt', pnib_scores)
    open('results/pnib_elapsed', 'w').write(str(pnib_elapsed))


if __name__ == "__main__":
    main()

Answer 1

procedure UpdateNgh(s,d)

fetchAdd(&r'/[d], (1-Alpha)/(1+Alpha)) r[s]/d(s))

procedure UpdateSelf(v)

p[v]=p[v]+(2Alpha/(1+Alpha))r[v]

r'[v]=0

//Update functions for the optimized version of parallel PR-Nibble.//