In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy
will defend his dissertation proposal
Decentralized Algorithms for Community Detection
Designing effective algorithms for community detection is an important and challenging problem in large-scale graphs, studied extensively in the literature. Various solutions have been proposed, but since the edge density of a graph and the distribution of community structures can vary a lot, not a single solution works well on all graphs. We present two decentralized algorithms for detecting community structures in graphs. Our first algorithm CDRW (Community Detection by Random Walks) is based on the recently proposed local mixing paradigm (IPDPS 2018) to detect community structure on sparse (bounded-degree) graphs. This algorithm uses random walks and is easy to implement in a decentralized manner. Our second algorithm called CDST (Community Detection by Sparsification-Triangulation) exploits the small-world property (in particular, large clustering coefficient) of real-world graphs and uses a simple and local operation known as triangulation repeatedly to reorient edges so that the resultant graph gets decomposed to communities. This algorithm is fully decentralized and works significantly better for real-world graphs compared to our first algorithm and finds communities with higher modularity value compared to several existing methods. However, the second algorithm, unlike the first, doesn't work well in the sparse planted partition model which have high expansion, but low clustering coefficient. Our work is a step towards designing community detection algorithms that are effective vis-a-vis the underlying graph structure.
Date: Friday, November 30, 2018
Time: 10:00 AM
Place: PGH 501D
Advisors: Dr. Gopal Pandurangan
Faculty, students, and the general public are invited.