[FLINK-4896] PageRank algorithm for directed graphs

• Type: New Feature
• Status: Closed
• Priority: Major
• Resolution: Implemented
• Affects Version/s: 1.2.0
• Fix Version/s: 1.3.0
• Component/s: Library / Graph Processing
• Labels: algorithm
• Assignee: Greg Hogan
• Reporter: Greg Hogan
• Created: 24/Oct/16 20:12
• Updated: 03/Mar/17 00:24
• Resolved: 03/Mar/17 00:24

Description

Gelly includes PageRank implementations for scatter-gather and gather-sum-apply. Both ship with the warning "The implementation assumes that each page has at least one incoming and one outgoing link."

PageRank is a directed algorithm and sources and sinks are common in directed graphs.

Sinks drain the total score across the graph which affects convergence and the balance of the random hop (convergence is not currently a feature of Gelly's PageRanks as this a very recent feature from FLINK-3888).

Sources are handled nicely by the algorithm highlighted on Flink's features page under "Iterations and Delta Iterations" since score deltas are transmitted and a source's score never changes (is always equal to the random hop probability divided by the vertex count).
https://flink.apache.org/features.html

We should find an implementation featuring convergence and unrestricted processing of directed graphs and move other implementations to Gelly examples.

Issue Links

• links to: GitHub Pull Request #2733