Uploaded image for project: 'Giraph'
  1. Giraph
  2. GIRAPH-115

Port of the HCC algorithm for identifying all connected components of a graph

    XMLWordPrintableJSON

    Details

    • Type: New Feature
    • Status: Resolved
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 0.1.0
    • Fix Version/s: 0.1.0
    • Component/s: None
    • Labels:
      None

      Description

      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

        Attachments

          Activity

            People

            • Assignee:
              ssc Sebastian Schelter
              Reporter:
              ssc Sebastian Schelter
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: