[SPARK-18845] PageRank has incorrect initialization value that leads to slow convergence

• Type: Bug
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 1.2.2, 1.3.1, 1.4.1, 1.5.2, 1.6.3, 2.0.2
• Fix Version/s: 2.2.0
• Component/s: GraphX
• Assignee: Andrew Ray
• Reporter: Andrew Ray
• Created: 13/Dec/16 21:19
• Updated: 16/Dec/16 07:40
• Resolved: 16/Dec/16 07:39

Description

All variants of PageRank in GraphX have incorrect initialization value that leads to slow convergence. In the current implementations ranks are seeded with the reset probability when it should be 1. This appears to have been introduced a long time ago in https://github.com/apache/spark/commit/15a564598fe63003652b1e24527c432080b5976c#diff-b2bf3f97dcd2f19d61c921836159cda9L90

This also hides the fact that source vertices (vertices with no incoming edges) are not updated. This is because source vertices generally* have pagerank equal to the reset probability. Therefore both need to be fixed at once.

PR will be added shortly

*when there are no sinks – but that's a separate bug

Issue Links

• blocks: SPARK-18847 PageRank gives incorrect results for graphs with sinks
• blocks: SPARK-18848 PageRank gives incorrect results for graphs with sinks
• links to: [Github] Pull Request #16271 (aray)