You are viewing a plain text version of this content. The canonical link for it is here.

Posted to dev@giraph.apache.org by "Avery Ching (Assigned) (JIRA)" <ji...@apache.org> on 2011/12/26 06:20:30 UTC

[jira] [Assigned] (GIRAPH-115) Port of the HCC algorithm for identifying all connected components of a graph

     [ https://issues.apache.org/jira/browse/GIRAPH-115?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Avery Ching reassigned GIRAPH-115:
----------------------------------

    Assignee: Sebastian Schelter
    
> Port of the HCC algorithm for identifying all connected components of a graph
> -----------------------------------------------------------------------------
>
>                 Key: GIRAPH-115
>                 URL: https://issues.apache.org/jira/browse/GIRAPH-115
>             Project: Giraph
>          Issue Type: New Feature
>    Affects Versions: 0.70.0
>            Reporter: Sebastian Schelter
>            Assignee: Sebastian Schelter
>
> Port of the HCC algorithm that identifies connected components and assigns a componented id (the smallest vertex id in the component) to each vertex.
> The idea behind the algorithm is very simple: propagate the smallest vertex id along the edges to all vertices of a connected component until convergence. The number of supersteps necessary is equal to the length of the maximum diameter of all components + 1
> The original Hadoop-based variant of this algorithm was proposed by Kang, Charalampos, Tsourakakis and Faloutsos in "PEGASUS: Mining Peta-Scale Graphs", 2010
> http://www.cs.cmu.edu/~ukang/papers/PegasusKAIS.pdf

--
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