Efficient Distributed Algorithms on Random Graphs

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=\frac{c\ln n}{n^{\delta}}$ (for any constant $0 0$), that finds a Hamiltonian cycle with high probability in $\tilde{O}(n^{\delta})$ rounds.\footnote{The notation $\tilde{O}$ hides a $\text{polylog}(n)$ factor.} Our algorithm works in the (synchronous) CONGEST model (i.e., only $O(\log n)$-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.Computer Science, Department o