On consistency of spectral graph algorithms for community detection in networks ---- Ambedkar Dukkipati

In the last few decades, we have witnessed a massive explosion of network or relational data: from social to biological networks. One of the most important problems in network analysis is community detection in networks. Communities or clusters of highly connected actors form an essential feature in the structure of several real-world networks. 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.

While we think of networks that capture two-way interactions (edge size 2), there are other complex networks that can have multi-way interactions which are called hypergraphs. I will provide a brief account of our results on the consistency of hypergraph partitioning using spectral graph methods by giving details on required tools of the trade: Davis-Kahan theorems and some concentration inequalities. I will also provide a necessary background in the beginning of the talk by giving a quick introduction to spectral graph theory results that lead to an approximate method for graph partitioning.