In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy

Reza Fathi

will defend his dissertation

Efficient Distributed Algorithms on Random Graphs

Abstract

This thesis 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 thesis, 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 shorter 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.

Date: Thursday, September 12, 2019
Time: 11:00 AM - 12:30 PM
Place: PGH 550
Advisor: Dr. Gopal Pandurangan

Faculty, students, and the general public are invited.