[
https://issues.apache.org/jira/browse/FLINK-2570?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14711790#comment-14711790
]
ASF GitHub Bot commented on FLINK-2570:
---------------------------------------
Github user andralungu commented on the pull request:
https://github.com/apache/flink/pull/1054#issuecomment-134702560
Hi @vasia,
I clarified the type of input expected. The graph should be undirected.
Without the distinct, you get duplicate edges there(and an erroneous number of
triangles). The second bullet point is again not an issue because the graph is
undirected.
The result should be fine. For the SNAP data sets, I got a number equal to
theirs on a cluster.
Concerning the runtime, you are right, It's just true for some cases
(generally faster by a factor of two) but it highly depends on the data set.
So, once this gets merged, I'll go ahead and propose the vertex centric version
as well. That way, the user can choose.
Hope I clarified everything!
Let me know if you still have questions :)
> Add a Triangle Count Library Method
> -----------------------------------
>
> Key: FLINK-2570
> URL: https://issues.apache.org/jira/browse/FLINK-2570
> Project: Flink
> Issue Type: Task
> Components: Gelly
> Affects Versions: 0.10
> Reporter: Andra Lungu
> Assignee: Andra Lungu
> Priority: Minor
>
> The Gather-Sum-Apply-Scatter version of this algorithm receives an undirected
> graph as input and outputs the total number of triangles formed by the
> graph's edges.
> The implementation consists of three phases:
> 1). Select neighbours with id greater than the current vertex id.
> Gather: no-op
> Sum: create a set out of these neighbours
> Apply: attach the computed values to the vertices
> 2). Propagate each received value to neighbours with higher id (again using
> GSA)
> 3). Compute the number of Triangles by verifying if the final vertex contains
> the sender's id in its list.
--
This message was sent by Atlassian JIRA
(v6.3.4#6332)
