Department of Electrical Engineering, Indian Institute of Technology Bombay
IITB Calendar

On statistical analysis of spectral graph algorithms for community detection in networks
Prof. Ambedkar Dukkipati, Department of Computer Science and Applications, Indian Institute of Science, Bangalore
Venue, Date and Time

GG Conference Room, Apr 25, 2017, 10:30 AM

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.
About the Speaker

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.