Graph connectivity in log steps using label propagation

DOI10.1142/S0129626421500213MaRDI QIDQ5087066zbMATH OpenOpenAlexFDO

Authors Paul Burkhardt

Publication date 8 July 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

parallel algorithmgraph connectivityMapReduceconnected componentsPRAM

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Describes a project that uses

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)