Spectral partitioning of random graphs

By Frank McSherry. Proceedings IEEE International Conference on Cluster Computing, 2001

680 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/085e729f762c2f6271b89bbfa14c4330bf9c2f0d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Geometry and Topology

Citations in the corpus

Learning Mixed Membership Community Models in Social Tagging Networks through Tensor Methods (2015, methodology): “For any rank-matrixA, we have ‖(Pr̂oj−I)A‖ ≤ 2‖Â−A‖ Proof: This is directly from (McSherry, 2001, Lemma 12).”
A decentralized algorithm for spectral analysis (2004, background): “In addition, several recent results have also shown how to use spectral techniques for clustering [13, 18, 17], characterization [8, 15, 1], and recommendation/prediction [2].”
Hierarchical Clustering (2017, methodology): “ goal is also simply to identify the kclusters and not any hierarchy upon them. The following theorem is derived from McSherry (2001) (Observation 11 and a simpliﬁcation of Theorem 12). Theorem 5.10 (McSherry (2001)). Let sbe the size of the smallest cluster (of the kclusters) and δbe the conﬁdence ”
Correlation Clustering (2002, background): “In fact, this problem nearly matches a special case of the plantedpartition problem of McSherry [18].”
A tutorial on spectral clustering (2007, methodology): “Random walks and Ncut A formal equivalence between Ncut and transition probabilities of the random walk has been observed in Meila and Shi (2001).”
Exact Recovery in the Stochastic Block Model (2014, background): “More specifically, the stochastic block model has been at the center of the attention in a large body of literature [14]–[16], [19], [24], [26], [29], [30], [32], [33], [35], [38], [39], as a testbed for algorithms (see [10] for a survey) as well as a scalable model for large data sets (see [22] and”
A discriminative framework for clustering via similarity functions (2008, result): “This is similarly the case with work on planted partitions in graphs [4, 28 , 16].”
Spectral redemption in clustering sparse networks (2013, background): “Both statistical inference and spectral methods have been shown to work well in networks that are sufficiently dense, or when the graph is regular [4–8].”
A Proof of the Block Model Threshold Conjecture (2013, methodology): “…in the average case analysis of the minimum-bisection problem led to intensive research on algorithms for recovering the partition [6,3,10,16,8,21] (although not all of these works used the same model as us; for example, [6] considered random regular graphs with a ﬁxed minimum bisection size).”
Regularized Spectral Clustering under the Degree-Corrected Stochastic Blockmodel (2013, background): “Several previous authors have studied the estimation properties of spectral clustering under various statistical network models (McSherry [3], Dasgupta et al.”
Finding and Leveraging Structure in Learning Problems (2012, background): “McSherry [McSherry, 2001] studies the “cluster-structured” random graph model in which the probability of adding an edge can vary depending on the clusters the edge connects.”
Manufacturing Consent (2015, neutral): “We consider three types of graphs for creating the underlying network of nodes- complete graph, random graphs and planted multi-section [41] graphs.”
Spectral Graph Theory (2012, background): “10 Perturbation Theory and Random Graphs McSherry [74] observes that the spectral partitioning heuristics and the related spectral heuristics for graph coloring can be understood through matrix perturbation theory.”
A Method of Moments for Mixture Models and Hidden Markov Models (2012, background): “Some previous spectral approaches for related learning problems only use second-order moments, but these approaches can only estimate a subspace containing the parameter vectors and not the parameters themselves (McSherry, 2001).”
Modularity-maximizing graph communities via mathematical programming (2007, methodology): “This family extends the basic idea of planted partitionings as suggested by McSherry [41] and Girvan and Newman [8], to generate a variable number of communities, with parametrized degree distributions (parameter γ), community distributions (parameter β), average node degree (k), and mixing paramete”