Mailing-List: contact giraph-dev-help@incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: giraph-dev@incubator.apache.org
Date: Fri, 18 May 2012 10:50:08 +0000 (UTC)
From: "Paolo Castagna (JIRA)" <jira@apache.org>
To: giraph-dev@incubator.apache.org
Message-ID: 
 <787411486.13532.1337338208156.JavaMail.tomcat@hel.zones.apache.org>
In-Reply-To: 
 <631269693.11007.1337288953530.JavaMail.tomcat@hel.zones.apache.org>
Subject: [jira] [Commented] (GIRAPH-191) Random Walk with Restart
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


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

Paolo Castagna commented on GIRAPH-191:
---------------------------------------

It would be good if we could also use this or provide a PageRank implementation which deals with dangling nodes/vertexes properly.

Dangling vertexes are vertexes with no edges.

SinglePageRankVertex has:

{code}
    if (getSuperstep() < MAX_SUPERSTEPS) {
      long edges = getNumOutEdges();
      sendMsgToAllEdges(
          new DoubleWritable(getVertexValue().get() / edges));
    } else {
      voteToHalt();
    }
{code}

This does not work when getNumOutEdges() returns 0.

Some suggest to divide the PageRank scores of dangling vertexes evenly among all other vertex (it's yet another sort of random jump to propagate PageRank scores to all nodes). This can be implemented in Giraph as a separate superstep using a SumAggregator.

Discussion on the giraph-user mailing list with further comments and references is here:

 - http://mail-archives.apache.org/mod_mbox/incubator-giraph-user/201205.mbox/%3C4FB509F4.4040407@googlemail.com%3E
                
> Random Walk with Restart
> ------------------------
>
>                 Key: GIRAPH-191
>                 URL: https://issues.apache.org/jira/browse/GIRAPH-191
>             Project: Giraph
>          Issue Type: New Feature
>            Reporter: Gianmarco De Francisci Morales
>         Attachments: GIRAPH-191.patch
>
>
> Implementing RWR on Giraph should be a very simple modification of the SimplePageRankVertex code.
> {code}
> if ( myID == sourceID )
>       DoubleWritable vertexValue = new DoubleWritable((0.15f + 0.85f * sum);
> else
>       DoubleWritable vertexValue = new DoubleWritable(0.85f * sum);
> {code}
> It would be nice to make it as configurable as possible by using parametric damping factors, preference vectors, strongly preferential, etc...
> More or less along these lines:
> http://law.dsi.unimi.it/software/docs/it/unimi/dsi/law/rank/PageRank.html

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira