mahout-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Hudson (JIRA)" <j...@apache.org>
Subject [jira] [Commented] (MAHOUT-773) Implement Random Walk with Restarts
Date Wed, 14 Sep 2011 15:29:09 GMT

    [ https://issues.apache.org/jira/browse/MAHOUT-773?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13104569#comment-13104569
] 

Hudson commented on MAHOUT-773:
-------------------------------

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


> Implement Random Walk with Restarts
> -----------------------------------
>
>                 Key: MAHOUT-773
>                 URL: https://issues.apache.org/jira/browse/MAHOUT-773
>             Project: Mahout
>          Issue Type: New Feature
>          Components: Graph
>    Affects Versions: 0.5
>            Reporter: Sebastian Schelter
>            Assignee: Sebastian Schelter
>             Fix For: 0.6
>
>
> 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.

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

        

Mime
View raw message