Implementing a triangle counting procedure in apace giraph

[Kaushik Patnaik <ka...@gmail.com>]

Hi

I am trying to implement a procedure which outputs both the number of
triangles in a graph and enumerates all the triangles for a vertex.

I am able to enumerate triangles for each node in three supersteps by the
following psuedo code

 - sending edge information (from -> to) as the message to the neighboring
nodes in each superstep
 - stopping at the third superstep and checking for symmetry of the message

However the above counts each triangle multiple times, and I have write the
message file to the disk to be queried again.

So my two questions are -

1) Is it possible to separate out messages based on the node they have come
from by using a hashmap
2) A better way to count the triangles withing giraph

Re: Implementing a triangle counting procedure in apace giraph

[Sebastian Schelter <ss...@apache.org>]

Search on google scholar for papers about triangle enumeration, there is a
huge body of work on that issue.
Am 18.11.2013 20:22 schrieb "Kaushik Patnaik" <ka...@gmail.com>:

> Hi
>
> I am trying to implement a procedure which outputs both the number of
> triangles in a graph and enumerates all the triangles for a vertex.
>
> I am able to enumerate triangles for each node in three supersteps by the
> following psuedo code
>
>  - sending edge information (from -> to) as the message to the neighboring
> nodes in each superstep
>  - stopping at the third superstep and checking for symmetry of the message
>
> However the above counts each triangle multiple times, and I have write
> the message file to the disk to be queried again.
>
> So my two questions are -
>
> 1) Is it possible to separate out messages based on the node they have
> come from by using a hashmap
> 2) A better way to count the triangles withing giraph
>