Shortcutting Label Propagation for Distributed Connected Components

Feb 6, 2018

Connected Components is a fundamental graph mining problem that has been studied for the PRAM, MapReduce and BSP models. We present a simple CC algorithm for BSP that does not mutate the graph, converges in O(log n) supersteps and scales to graphs of trillions of edges.

  • The 11th ACM International Conference on Web Search and Data Mining (WSDM 2018)
  • Conference/Workshop Paper