Consistency of Spectral Clustering for the Stochastic Block Model with a Growing Number of Blocks

• Activity Number: 382
• Type: Invited
• Date/Time: Tuesday, August 3, 2010 : 2:00 PM to 3:50 PM
• Sponsor: Section on Statistical Learning and Data Mining
• Author(s): Karl Greiner Rohe*+ and Sourav Chatterjee and Bin Yu
• Companies: University of California, Berkeley and University of California, Berkeley and University of California, Berkeley
• Keywords: Spectral Clustering ; High Dimensional Learning ; Stochastic Blockmodel ; Network Analysis ; Clustering

Abstract

In recent years several fields have found new applications of social network analysis. One primary activity in analyzing a network is to find communities or clusters of nodes which behave similarly. The Stochastic Blockmodel can aid in this effort. Leskovec et al. (2008) observed that in several massive networks, clusters sizes do not become large. As a result, any asymptotic proof of consistency for clustering should allow the number of groups to grow as the number of nodes grows. This gives the problem a flavor of high dimensional learning. We give conditions for the consistency of spectral clustering in the Stochastic Blockmodel where the number of blocks or clusters grows with the number of nodes.

J. Leskovec, K. Lang, A. Dasgupta, and M. Mahoney. Statistical properties of community structure in large social and information networks. 2008.