Efficient Distributed Algorithms on Random Graphs

Date

2019-12

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

This dissertation focuses on two prominent graph problems: finding Hamiltonian cycles and detecting communities in graphs. Both of them are NP-hard problems on general graphs but can admit efficient solutions in {\em random graphs}. In this dissertation, we present efficient distributed algorithms for the above two problems in random graphs. First, we present fast and efficient randomized distributed algorithms to find Hamiltonian cycles in random graphs. In particular, we design and analyze a randomized distributed algorithm for the classical G(n,p) random graph model, with number of nodes n and p=clnnnδ (for any constant 0<δ≤1 and for a suitably large constant c>0), that finds a Hamiltonian cycle with high probability in O~(nδ) rounds.\footnote{The notation O~ hides a polylog(n) factor.} Our algorithm works in the (synchronous) CONGEST model (i.e., only O(logn)-sized messages are communicated per edge per round) and its computational cost per node is sublinear (in n) per round and is fully-distributed (each node uses only o(n) memory and all nodes' computations are essentially balanced). Our algorithm improves over the previous best known result in terms of both the running time as well as the edge sparsity of the graphs where it can succeed; in particular, the denser the random graph, the smaller is the running time. Second, we present a distributed algorithm for community detection in the {\em stochastic block model} (also called {\em planted partition model}), a widely-studied and canonical random graph model for community detection and clustering. Designing effective algorithms for community detection is an important and challenging problem in {\em large-scale} graphs, studied extensively in the literature. Various solutions have been proposed, but many of them are centralized with expensive procedures (requiring full knowledge of the input graph) and have a large running time. Our algorithm called {\em CDRW(Community Detection by Random Walks)} is based on random walks, is localized and lightweight, and is easy to implement. A novel feature of the algorithm is that it uses the concept of {\em local mixing time} to identify the community around a given node. We also present experimental results for our CDRW algorithm that validate our theoretical analysis.

Description

Keywords

Distributed algorithms, Random Graphs, Hamiltonian Cycles, Community detection

Citation

Portions of this document appear in: Chatterjee, Soumyottam, Reza Fathi, Gopal Pandurangan, and Nguyen Dinh Pham. "Fast and efficient distributed computation of hamiltonian cycles in random graphs." In 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS), pp. 764-774. IEEE, 2018. And in: Fathi, Reza, Anisur Rahaman Molla, and Gopal Pandurangan. "Efficient Distributed Community Detection in the Stochastic Block Model." arXiv preprint arXiv:1904.07494 (2019).