Spectral Clustering and Block Models: A Review And A New Algorithm

Since its introduction in [15], spectral analysis of various matrices associated to groups has become one of the most widely used clustering techniques in statistics and machine learning. In the context of unlabeled graphs, a number of methods, all of which come under the broad heading of spectral clustering have been proposed. These methods based on spectral analysis of adjacency matrices or some derived matrix such as one of the Laplacians ([31], [28], [23], [29], [32]) have been studied in connection with their effectiveness in identifying members of blocks in exchangeable graph block models. In this paper after introducing the methods and models, we intend to review some of the literature.