Pandurangan, Gopal2019-12-17December 22019-12December 2Portions 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).https://hdl.handle.net/10657/5606This 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 < \delta \leq 1$ and for a suitably large constant $c > 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.application/pdfengThe author of this work is the copyright owner. UH Libraries and the Texas Digital Library have their permission to store and provide access to this work. UH Libraries has secured permission to reproduce any and all previously published materials contained in the work. Further transmission, reproduction, or presentation of this work is prohibited except with permission of the author(s).Distributed algorithmsRandom GraphsHamiltonian CyclesCommunity detection2019-12-17Thesisborn digital