Mahout
  1. Mahout
  2. MAHOUT-773

Implement Random Walk with Restarts

    Details

    • Type: New Feature New Feature
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: 0.5
    • Fix Version/s: 0.6
    • Component/s: Graph
    • Labels:
      None

      Description

      I'll create an implementation of Random Walk with Restarts as described in Kang, Tsourakakis, Faloutsos, "PEGASUS: A Peta-Scale Graph Mining System - Implementation and Observations" http://www.cs.cmu.edu/~christos/PUBLICATIONS/icdm09-pegasus.pdf

      The algorithm is a random walk similar to PageRank with the difference that you start at and teleport to a certain node. The probabilities it computes can be seen as a measure of proximity between the start node and a reached node. To my knowledge RWR can be e.g used for link predicition in social networks.

      I will try to create an implementation that is able to do several walks in parallel and I will assume that a steadystate probability vector fits in memory.

      I don't plan to use the implementation details from the paper but I'll model the algorithm as an iterative multiplication between the adjacency matrix of the graph and the matrix created from the steadystate probability vectors for the vertices we compute the random walks for.

        Activity

        Hide
        Hudson added a comment -

        Integrated in Mahout-Quality #1037 (See https://builds.apache.org/job/Mahout-Quality/1037/)
        MAHOUT-773 Implement Random Walk with Restarts

        ssc : http://svn.apache.org/viewcvs.cgi/?root=Apache-SVN&view=rev&rev=1170491
        Files :

        • /mahout/trunk/core/src/main/java/org/apache/mahout/common/AbstractJob.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/AugmentGraphWithDegreesJob.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/DegreeDistributionJob.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/EnumerateTrianglesJob.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/GraphUtils.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/JoinableUndirectedEdge.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/LocalClusteringCoefficientJob.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/SimplifyGraphJob.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/UndirectedEdgeWithDegrees.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/VertexOrMarker.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/VertexWithDegree.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/package-info.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/linkanalysis/PageRankJob.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/linkanalysis/RandomWalk.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/linkanalysis/RandomWalkWithRestartJob.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/linkanalysis/SortableIndex.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/linkanalysis/VectorElementWritable.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/model/Edge.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/model/Triangle.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/model/UndirectedEdge.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/model/UndirectedEdgeWithDegrees.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/model/Vertex.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/model/VertexWithDegree.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/model/package-info.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/package-info.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/preprocessing
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/preprocessing/AdjacencyMatrixJob.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/preprocessing/GraphUtils.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/preprocessing/SimplifyGraphJob.java
        • /mahout/trunk/core/src/main/java/org/apache/mahout/graph/triangles
        • /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/TransposeJob.java
        • /mahout/trunk/core/src/test/java/org/apache/mahout/graph/GraphTestCase.java
        • /mahout/trunk/core/src/test/java/org/apache/mahout/graph/common/AugmentGraphWithDegreesJobTest.java
        • /mahout/trunk/core/src/test/java/org/apache/mahout/graph/common/EnumerateTrianglesJobTest.java
        • /mahout/trunk/core/src/test/java/org/apache/mahout/graph/common/SimplifyGraphJobTest.java
        • /mahout/trunk/core/src/test/java/org/apache/mahout/graph/linkanalysis/PageRankJobTest.java
        • /mahout/trunk/core/src/test/java/org/apache/mahout/graph/linkanalysis/RandomWalkWithRestartJobTest.java
        • /mahout/trunk/core/src/test/java/org/apache/mahout/graph/preprocessing
        • /mahout/trunk/core/src/test/java/org/apache/mahout/graph/preprocessing/AdjacencyMatrixJobTest.java
        • /mahout/trunk/core/src/test/java/org/apache/mahout/graph/preprocessing/SimplifyGraphJobTest.java
        • /mahout/trunk/core/src/test/java/org/apache/mahout/graph/triangles
        Show
        Hudson added a comment - Integrated in Mahout-Quality #1037 (See https://builds.apache.org/job/Mahout-Quality/1037/ ) MAHOUT-773 Implement Random Walk with Restarts ssc : http://svn.apache.org/viewcvs.cgi/?root=Apache-SVN&view=rev&rev=1170491 Files : /mahout/trunk/core/src/main/java/org/apache/mahout/common/AbstractJob.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/AugmentGraphWithDegreesJob.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/DegreeDistributionJob.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/EnumerateTrianglesJob.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/GraphUtils.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/JoinableUndirectedEdge.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/LocalClusteringCoefficientJob.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/SimplifyGraphJob.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/UndirectedEdgeWithDegrees.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/VertexOrMarker.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/VertexWithDegree.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/common/package-info.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/linkanalysis/PageRankJob.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/linkanalysis/RandomWalk.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/linkanalysis/RandomWalkWithRestartJob.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/linkanalysis/SortableIndex.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/linkanalysis/VectorElementWritable.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/model/Edge.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/model/Triangle.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/model/UndirectedEdge.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/model/UndirectedEdgeWithDegrees.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/model/Vertex.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/model/VertexWithDegree.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/model/package-info.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/package-info.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/preprocessing /mahout/trunk/core/src/main/java/org/apache/mahout/graph/preprocessing/AdjacencyMatrixJob.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/preprocessing/GraphUtils.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/preprocessing/SimplifyGraphJob.java /mahout/trunk/core/src/main/java/org/apache/mahout/graph/triangles /mahout/trunk/core/src/main/java/org/apache/mahout/math/hadoop/TransposeJob.java /mahout/trunk/core/src/test/java/org/apache/mahout/graph/GraphTestCase.java /mahout/trunk/core/src/test/java/org/apache/mahout/graph/common/AugmentGraphWithDegreesJobTest.java /mahout/trunk/core/src/test/java/org/apache/mahout/graph/common/EnumerateTrianglesJobTest.java /mahout/trunk/core/src/test/java/org/apache/mahout/graph/common/SimplifyGraphJobTest.java /mahout/trunk/core/src/test/java/org/apache/mahout/graph/linkanalysis/PageRankJobTest.java /mahout/trunk/core/src/test/java/org/apache/mahout/graph/linkanalysis/RandomWalkWithRestartJobTest.java /mahout/trunk/core/src/test/java/org/apache/mahout/graph/preprocessing /mahout/trunk/core/src/test/java/org/apache/mahout/graph/preprocessing/AdjacencyMatrixJobTest.java /mahout/trunk/core/src/test/java/org/apache/mahout/graph/preprocessing/SimplifyGraphJobTest.java /mahout/trunk/core/src/test/java/org/apache/mahout/graph/triangles
        Hide
        Sebastian Schelter added a comment -

        Committed a standard implementation that computes probabilities for a single source node only. Included a lot of refactoring as we're on the way of maturing the graph package. We have an extra job to create and stochastify the adjacency matrix for a graph now for example.

        Show
        Sebastian Schelter added a comment - Committed a standard implementation that computes probabilities for a single source node only. Included a lot of refactoring as we're on the way of maturing the graph package. We have an extra job to create and stochastify the adjacency matrix for a graph now for example.

          People

          • Assignee:
            Sebastian Schelter
            Reporter:
            Sebastian Schelter
          • Votes:
            0 Vote for this issue
            Watchers:
            0 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development