# Spectral Clustering of Graphs with General Degrees in the Extended Planted Partition Model

@inproceedings{Chaudhuri2012SpectralCO, title={Spectral Clustering of Graphs with General Degrees in the Extended Planted Partition Model}, author={Kamalika Chaudhuri and Fan Chung Graham and Alexander Tsiatas}, booktitle={COLT}, year={2012} }

In this paper, we examine a spectral clustering algorithm for similarity graphs drawn from a simple random graph model, where nodes are allowed to have varying degrees, and we provide theoretical bounds on its performance. The random graph model we study is the Extended Planted Partition (EPP) model, a variant of the classical planted partition model. The standard approach to spectral clustering of graphs is to compute the bottom k singular vectors or eigenvectors of a suitable graph Laplacian… Expand

#### Topics from this paper

#### 193 Citations

Improved Graph Clustering

- Mathematics, Computer Science
- IEEE Transactions on Information Theory
- 2014

This paper presents a new algorithm-a convexified version of maximum likelihood-for graph clustering, and shows that, in the classic stochastic block model setting, it outperforms existing methods by polynomial factors when the cluster size is allowed to have general scalings. Expand

Diffusion and clustering on large graphs

- Mathematics
- 2012

This dissertation studies two important algorithmic problems on networks: graph diffusion and clustering. These problems are closely related: bottlenecks that diffusive processes find difficult to… Expand

Title Concentration and regularization of random graphs Permalink

- 2016

This paper studies how close random graphs are typically to their expectations. We interpret this question through the concentration of the adjacency and Laplacian matrices in the spectral norm. We… Expand

Understanding Regularized Spectral Clustering via Graph Conductance

- Computer Science, Mathematics
- NeurIPS
- 2018

The results show that unbalanced partitions from spectral clustering can be understood as overfitting to noise in the periphery of a sparse and stochastic graph and demonstrate how regularization can improve the computational speed of spectral clusters. Expand

Challenges in random graph models with degree heterogeneity: existence, enumeration and asymptotics of the spectral radius

- Mathematics
- 2016

In order to understand how the network structure impacts the underlying dynamics, we seek an assortment of methods for efficiently constructing graphs of interest that resemble their empirically… Expand

Concentration and regularization of random graphs

- Mathematics, Computer Science
- Random Struct. Algorithms
- 2017

This paper studies how close random graphs are typically to their expectations through the concentration of the adjacency and Laplacian matrices in the spectral norm, and builds a new decomposition of random graphs based on Grothendieck-Pietsch factorization. Expand

Sparse random graphs: regularization and concentration of the Laplacian

- Mathematics, Computer Science
- ArXiv
- 2015

It is proved that this regularization indeed forces Laplacian to concentrate even in sparse graphs, establishing the validity of one of the simplest and fastest approaches to community detection -- regularized spectral clustering, under the stochastic block model. Expand

Asymptotics of the spectral radius for directed Chung-Lu random graphs with community structure

- Computer Science, Mathematics
- ArXiv
- 2017

The spectral radius of the adjacency matrix can impact both algorithmic efficiency as well as the stability of solutions to an underlying dynamical process and this work provides novel concentration results for the spectral radius for the directed Chung-Lu random graph model. Expand

Searching for a Single Community in a Graph

- Computer Science, Mathematics
- ACM Trans. Model. Perform. Evaluation Comput. Syst.
- 2018

This article develops a variant of the method of moments that identifies nodes in the target more reliably, and with lower computation, than generic community detection methods that do not use side information and partition the entire graph. Expand

Regularized spectral methods for clustering signed networks

- Mathematics, Computer Science
- ArXiv
- 2020

This work builds on the results in [CDGT 2019] on two fronts for the normalized versions of SPONGE and the Signed Laplacian, and introduces regularized versions of both methods to handle sparse graphs in the regime where the graph is moderately dense. Expand

#### References

SHOWING 1-10 OF 31 REFERENCES

Finding Planted Partitions in Random Graphs with General Degree Distributions

- Mathematics, Computer Science
- SIAM J. Discret. Math.
- 2009

There is a polynomial time algorithm for recovering (a large part of) the planted partition in this model even in the sparse case, where the average degree is constant, and this model is characterized by a prescribed expected degree sequence. Expand

Spectral analysis of random graphs with skewed degree distributions

- Mathematics, Computer Science
- 45th Annual IEEE Symposium on Foundations of Computer Science
- 2004

This work extends spectral methods to random graphs with skewed degree distributions through a degree based normalization closely connected to the normalized Laplacian, and proves that after applying the transformation, spectral analysis succeeds in recovering the latent structure with high probability. Expand

Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges

- Mathematics
- 2010

Consider any random graph model where potential edges appear independently, with possibly different probabilities, and assume that the minimum expected degree is !(lnn). We prove that the adjacency… Expand

Algorithms for graph partitioning on the planted partition model

- Computer Science
- Random Struct. Algorithms
- 2001

The NP-hard graph bisection problem is to partition the nodes of an undirected graph into two equal-sized groups so as to minimize the number of edges that cross the partition. The more general graph… Expand

Spectral graph theory

- Zeta and 𝐿-functions in Number Theory and Combinatorics
- 2019

With every graph (or digraph) one can associate several different matrices. We have already seen the vertex-edge incidence matrix, the Laplacian and the adjacency matrix of a graph. Here we shall… Expand

Spectral partitioning of random graphs

- Computer Science
- Proceedings 2001 IEEE International Conference on Cluster Computing
- 2001

This paper shows that a simple spectral algorithm can solve all three problems above in the average case, as well as a more general problem of partitioning graphs based on edge density. Expand

Finding Planted Partitions in Nearly Linear Time using Arrested Spectral Clustering

- Mathematics, Computer Science
- ICML
- 2010

Lower bounds are provided that imply that the "large enough" constraint cannot be improved much, even using a computationally unbounded algorithm. Expand

Spectral clustering and the high-dimensional stochastic blockmodel

- Mathematics
- 2011

Networks or graphs can easily represent a diverse set of data sources that are characterized by interacting units or actors. Social ne tworks, representing people who communicate with each other, are… Expand

On the Spectra of General Random Graphs

- Mathematics, Computer Science
- Electron. J. Comb.
- 2011

A Chernoff inequality for matrices is used to show that the eigenvalues of the adjacency matrix and the normalized Laplacian of such a random graph can be approximated by those of the weighted expectation graph, with error bounds dependent upon the minimum and maximum expected degrees. Expand

Complex Graphs and Networks

- Mathematics
- 2006

Graph theory in the information age Old and new concentration inequalities A generative model--the preferential attachment scheme Duplication models for biological networks Random graphs with given… Expand