Thanks, :)
but I am wondering if there is a message(none?) sent to the target vertex(the
rank change is less than tolerance) in below dynamic page rank implementation,
def sendMessage(edge: EdgeTriplet[(Double, Double), Double]) = {
if (edge.srcAttr._2 > tol) {
Iterator((edge.dstId, edge.srcAttr._2 * edge.attr))
} else {
Iterator.empty
}
}
so, in this case, there is a message, even is none, is still sent? or not?
Best,
Yifan
On 16 Sep 2014, at 11:48, Ankur Dave <[email protected]> wrote:
> At 2014-09-16 10:55:37 +0200, Yifan LI <[email protected]> wrote:
>> - from [1], and my understanding, the existing inactive feature in graphx
>> pregel api is “if there is no in-edges, from active vertex, to this vertex,
>> then we will say this one is inactive”, right?
>
> Well, that's true when messages are only sent forward along edges (from the
> source to the destination) and the activeDirection is EdgeDirection.Out. If
> both of these conditions are true, then a vertex without in-edges cannot
> receive a message, and therefore its vertex program will never run and a
> message will never be sent along its out-edges. PageRank is an application
> that satisfies both the conditions.
>
>> For instance, there is a graph in which every vertex has at least one
>> in-edges, then we run static Pagerank on it for 10 iterations. During this
>> calculation, is there any vertex would be set inactive?
>
> No: since every vertex always sends a message in static PageRank, if every
> vertex has an in-edge, it will always receive a message and will remain
> active.
>
> In fact, this is why I recently rewrote static PageRank not to use Pregel
> [3]. Assuming that most vertices do have in-edges, it's unnecessary to track
> active vertices, which can provide a big savings.
>
>> - for more “explicit active vertex tracking”, e.g. vote to halt, how to
>> achieve it in existing api?
>> (I am not sure I got the point of [2], that “vote” function has already been
>> introduced in graphx pregel api? )
>
> The current Pregel API effectively makes every vertex vote to halt in every
> superstep. Therefore only vertices that receive messages get awoken in the
> next superstep.
>
> Instead, [2] proposes to make every vertex run by default in every superstep
> unless it votes to halt *and* receives no messages. This allows a vertex to
> have more control over whether or not it will run, rather than leaving that
> entirely up to its neighbors.
>
> Ankur
>
>>> [1]
>>> http://spark.apache.org/docs/latest/api/scala/index.html#org.apache.spark.graphx.Pregel$
>>> [2] https://github.com/apache/spark/pull/1217
> [3] https://github.com/apache/spark/pull/2308
