Mailing-List: contact giraph-user-help@incubator.apache.org; run by ezmlm
Precedence: bulk
Reply-To: giraph-user@incubator.apache.org
Received-SPF: pass (athena.apache.org: domain of castagna.lists@googlemail.com
 designates 209.85.212.177 as permitted sender)
Message-ID: <4FB5713B.2080504@googlemail.com>
Date: Thu, 17 May 2012 22:44:27 +0100
From: Paolo Castagna <castagna.lists@googlemail.com>
User-Agent: Thunderbird 2.0.0.24 (X11/20101027)
MIME-Version: 1.0
To: giraph-user@incubator.apache.org
Subject: Re: SimplePageRankVertex implementation, dangling nodes and sending
 messages to all nodes...
References: <4FB509F4.4040407@googlemail.com> <4FB52A7A.7030601@apache.org>
In-Reply-To: <4FB52A7A.7030601@apache.org>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

Hi Sebastian,
from SimplePageRankVertex.java, we have:

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

What happens if getNumOutEdges() returns 0 (i.e. it's a dangling node)?

Paolo

Sebastian Schelter wrote:
> The implementation implicitly deals with dangling nodes by computing the
> pageRank as
> 
> 0.15f / getNumVertices() + 0.85f * sumOfNeighborRanks
> 
> Conceptually, this is the same as connecting every vertex with every
> other vertex it is not yet connected to. This removes all dangling nodes
> from the graph as every vertex can reach every other vertex.
> 
> "Mining of Massive Datasets" [1] has a very well written explanation of
> this approach.
> 
> --sebastian
> 
> 
> [1] http://infolab.stanford.edu/~ullman/mmds.html
> 
> On 17.05.2012 16:23, Paolo Castagna wrote:
>> Hi,
>> I noticed that the SimplePageRankVertex implementation does not deal with
>> dangling nodes (dangling nodes are those nodes with no outgoing links).
>> And, probably that is one of the good reasons why there is a "Simple" in front. ;-)
>>
>>  "Dangling nodes exist in many forms. For example, a page of data, a page with a
>> postscript graph, [...], a page that has been fetched by a crawler but not yet
>> explored - these are all examples of possible dangling nodes. The more ambitious
>> the crawl, the bigger the proportion of dangling nodes because the set of
>> fetched but uncrawled pages grows quickly." (pag. 80) [1]
>>
>> Wikipedia's PageRank page says:
>>
>>  "If a page has no links to other pages, it becomes a sink and therefore
>> terminates the random surfing process. If the random surfer arrives at a sink
>> page, it picks another URL at random and continues surfing again. When
>> calculating PageRank, pages with no outbound links are assumed to link out to
>> all other pages in the collection. Their PageRank scores are therefore divided
>> evenly among all other pages. In other words, to be fair with pages that are not
>> sinks, these random transitions are added to all nodes in the Web, with a
>> residual probability usually set to d = 0.85, estimated from the frequency that
>> an average surfer uses his or her browser's bookmark feature." [2]
>>
>> Now, if I want to try to account for the dangling nodes I need to sum all
>> PageRank values for the dangling nodes and divide it evenly among all other
>> pages (which in practce means to send a message to all vertexes in Giraph...
>> which is not possible, as it would be crazy with large graphs).
>>
>> I imagine one can use a SumAggregator and alternate computing contribution from
>> dangling nodes and PageRank values (i.e. PageRank values are computed only every
>> 2 supersteps).
>>
>> What do you think?
>>
>> Paolo
>>
>>  [1] Amy N. Langville and Carl D. Meyer, "Google's PageRank and Beyond: The
>> Science of Search Engine Rankings" (2006)
>>  [2] http://en.wikipedia.org/wiki/PageRank
>