Uploaded image for project: 'Flink'
  1. Flink
  2. FLINK-4896

PageRank algorithm for directed graphs

    Details

    • Type: New Feature
    • Status: Closed
    • Priority: Major
    • Resolution: Implemented
    • Affects Version/s: 1.2.0
    • Fix Version/s: 1.3.0
    • Component/s: Gelly
    • Labels:

      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.

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                greghogan Greg Hogan
                Reporter:
                greghogan Greg Hogan
              • Votes:
                0 Vote for this issue
                Watchers:
                2 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved: