Spectral graph methods for detecting communities in networks have been very successful for two reasons: (i) good practical solutions and easy implementations, and (ii) theoretical guarantees. A statistical treatment for analysis of spectral algorithms involves, assuming that the data or network is generated from a random model, with a planted partition and then derive bounds on the error obtained by a particular spectral algorithm. A spectral algorithm is said to be strongly consistent if the error obtained is o(1) with high probability and weakly consistent if error obtained is o(n), where n is the number of nodes in a network. In this talk, I will give a quick introduction to these methods by mentioning underlying spectral graph theory results. Then, I will give a detailed account of establishing consistency results and required tools of the trade: Davis-Kahan theorems and some concentration inequalities. Towards the end of the talk, I will provide a brief overview of our recent results on hypergraph partitioning problems.
Prof. Ambedkar Dullipati did his B.Tech. from IIT Madras and M.E. and Ph.D. in Indian Institute of Science, Bangalore. After a postdoctoral stint at EURANDOM in The Netherlands, he joined the Department of Computer Science and Automation at the Indian Institute of Science. His research interests are in information theory, algorithmic algebra and symbolic computation, and statistics and machine learning.