Towards a Theory for Network Clustering

Monday, March 24, 2014
ETC 2.136

Community detection in networks is a key exploratory tool with applications ranging from identifying protein complexes in protein-protein interaction networks to scaling network computation by divide and conquer-type algorithms. Many clustering algorithms make heuristic choices which work well in practice, but their theoretical underpinnings are not well understood. For example, it is commonly believed that normalizing the network adjacency matrix improves the performance of Spectral Clustering. In the first part of this talk I will show that under a broad parameter regime, this is indeed true.

In the second part of the talk, I will focus on another heuristic which determines the number of communities in a network from the knee of the eigen-spectrum of the adjacency matrix. I will present a hypothesis testing framework that formalizes this heuristic and can be used for automatically determining the number of clusters in a network. Our analyses are in the context of a Stochastic Blockmodel, which is a widely used model for generating labeled networks.


Postdoctoral Scholar
University of California, Berkeley

Purnamrita Sarkar is a postdoctoral scholar at University of California, Berkeley. She works with Prof. Michael Jordan and Prof. Peter Bickel on models, theory and algorithms for large networks.

She received her PhD from the Machine Learning Department at Carnegie Mellon University. Her doctoral advisor was Prof. Andrew W. Moore. Her thesis research has been aimed at analyzing theoretical properties of different proximity measures arising from random walks, and using them for designing fast algorithms. Here is a link to her thesis.

Before joining Carnegie Mellon, she was an undergraduate at the Computer Science and Engineering Department in Indian Institute of Technology, Kharagpur, where she spent four years. During her undergrad years shealso worked with Prof. Charles Isbell as a summer intern in Georgia Tech. She grew up in Calcutta, and her native language is Bengali.