Graph connectivity in log steps using label propagation

DOI10.1142/S0129626421500213zbMATH Open1490.68295arXiv1808.06705OpenAlexW4206190346MaRDI QIDQ5087066FDOQ5087066

Authors: Paul Burkhardt 

Publication date: 8 July 2022

Published in: Parallel Processing Letters (Search for Journal in Brave)

Abstract: The fastest deterministic algorithms for connected components take logarithmic time and perform superlinear work on a Parallel Random Access Machine (PRAM). These algorithms maintain a spanning forest by merging and compressing trees, which requires pointer-chasing operations that increase memory access latency and are limited to shared-memory systems. Many of these PRAM algorithms are also very complicated to implement. Another popular method is "leader-contraction" where the challenge is to select a constant fraction of leaders that are adjacent to a constant fraction of non-leaders with high probability. Instead we investigate label propagation because it is deterministic and does not rely on pointer-chasing. Label propagation exchanges representative labels within a component using simple graph traversal, but it is inherently difficult to complete in a sublinear number of steps. We are able to solve the problems with label propagation for graph connectivity. We introduce a surprisingly simple framework for deterministic graph connectivity using label propagation that is easily adaptable to many computational models. It propagates directed edges and alternates edge direction to achieve linear edge count each step and sublinear convergence. We present new algorithms in PRAM, Stream, and MapReduce for a simple, undirected graph $G=(V,E)$ with $n=|V|$ vertices, $m=|E|$ edges. Our approach takes $O(m)$ work each step, but we can only prove logarithmic convergence on a path graph. It was conjectured by Liu and Tarjan (2019) to take $O(logn)$ steps or possibly $O(lo{g}^{2}n)$ steps. We leave the proof of convergence as an open problem.

Full work available at URL: https://arxiv.org/abs/1808.06705

Recommendations

• Connected components in \(O(\log^{3/2}n)\) parallel time for the CREW PRAM
• Finding Connected Components in O(log n log log n) Time on the EREW PRAM
• Fast Connected Components Algorithms for the EREW PRAM
• scientific article; zbMATH DE number 437524
• An efficient and fast parallel-connected component algorithm

zbMATH Keywords

parallel algorithmgraph connectivityMapReduceconnected componentsPRAM

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40) Parallel algorithms in computer science (68W10)

Cites Work

• Title not available (Why is that?)
• A Simpler Parallel Algorithm for Graph Connectivity
• Title not available (Why is that?)
• Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms
• Parallelism in random access machines
• Sequential Operations in Digital Picture Processing
• Title not available (Why is that?)
• Selection and sorting with limited storage
• New Connectivity and MSF Algorithms for Shuffle-Exchange Network and PRAM
• An O(logn) parallel connectivity algorithm
• Trading off space for passes in graph streaming problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Communication steps for parallel query processing
• A Survey of Graph Algorithms Under Extended Streaming Models of Computation
• Sorting, searching, and simulation in the MapReduce framework
• Fast Connected Components Algorithms for the EREW PRAM
• A fast, parallel spanning tree algorithm for symmetric multiprocessors (SMPs)
• Title not available (Why is that?)

Uses Software

• MapReduce
• SNAP
• DIMACS

This page was built for publication: Graph connectivity in log steps using label propagation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5087066)