CODEWITHSUNDEEP
algorithmgraphpagerank
Nitish Upreti
Nitish Upreti

Reputation: 6550

How to check for Page Rank convergence?

I am writing a small code (sequential) to calculate Page Rank for a modest dataset (although not completely trivial).

The algo goes like this :

while ( not converged ) {
   // Do a bunch of things to calculate PR
}

I am clear on the algorithm apart from the 'convergence' criteria. What is the best way to check if the algorithm has converged? Should I :

Check I keep a copy of all individual node's PR from an iteration and check all node's PR in the next iteration to be the same value?

This seems highly inefficient to me. Is this a right way to do it?

Upvotes: 4

Views: 7573

Answers (1)

jksnw
jksnw

Reputation: 658

For each node take the difference in score between the current iteration and the last one, if this error falls below a certain threshold the graph has converged.

The paper for TextRank describes the quite well:

Starting from arbitrary values assigned to each node in the graph, the computation iterates until convergence below a given threshold is achieved.

Convergence is achieved when the error rate for any vertex in the graph falls below a given threshold. The error rate of a vertex is defined as the difference between the “real” score of the vertex S(Vi) and the score computed at iteration k, S^K(Vi) . Since the real score is not known apriori, this error rate is approximated with the difference between the scores computed at two successive iterations: S^(k+1)(Vi)+S^(k)(Vi).

Upvotes: 5

Related Questions