[jira] [Created] (FLINK-4896) PageRank algorithm for directed graphs

[Shang Yuanchun (Jira)]

Greg Hogan created FLINK-4896:
---------------------------------

             Summary: PageRank algorithm for directed graphs
                 Key: FLINK-4896
                 URL: https://issues.apache.org/jira/browse/FLINK-4896
             Project: Flink
          Issue Type: New Feature
          Components: Gelly
    Affects Versions: 1.2.0
            Reporter: Greg Hogan
            Assignee: Greg Hogan


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.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)