Spectral techniques applied to sparse random graphs

By Uriel Feige, Eran Ofek. 2005

278 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology, Algorithms & Complexity, Network Science & Complex Systems

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 Discrete Mathematics and Combinatorics

In Geometry and Topology

In Algorithms & Complexity

In Network Science & Complex Systems

Citations in the corpus

Recovery guarantee of weighted low-rank approximation via alternating minimization (2016, background): “We ﬁrst note that when the m observed entries are sampled uniformly at random from an n by n matrix, the corresponding binary weight matrix will have a spectral gap γ = O ( ) (see, e.g., [Feige and Ofek, 2005]).”
Community Structure in Large Networks: Natural Cluster Sizes and the Absence of Large Well-Defined Clusters (2008, background): “[63] U. Feige and E. Ofek.”
Concentration of the adjacency matrix and of the Laplacian in random graphs with independent edges (2009, methodology): “A more recent way of bounding eigenvalues and eigenvectors is in some sense based on bounding “discrepancies” [33, 29].”
Spectral Gaps of Random Graphs and Applications (2012, methodology): “This follows from the standard Kahn–Szemerérdi argument, and it is essentially proven in both Feige and Ofek [18] and the original Friedman, Kahn, and Szemerérdi paper [22].”
Principal Component Analysis and Higher Correlations for Distributed Data (2013, methodology): “We combine this with Lemma 4 in Appendix A of [4], based on [15], to conclude that for all vectors x, ‖PAx‖2 = (1 ± ε)‖Ax‖2 with probability 1− exp(−d) (for a different constant in the exp() function).”
Community detection thresholds and the weak Ramanujan property (2013, methodology): “Categories and Subject Descriptors F.2 [Theory of Computation]: Analysis of Algorithms and Problem Complexity Keywords spectral clustering, community detection, phase transition, spectral separation”
Improved Approximation Algorithms for Large Matrices via Random Projections (2006, background): “Lemma 10 ([32], see also [8] for a restated proof) Let 0 < 0, T = {x : x ∈ 0 kZ , ‖x‖2 ≤ 1} and C ∈ Rk×k.”
ALGEBRAIC CONNECTIVITY OF ERDÖS-RÉNYI GRAPHS NEAR THE CONNECTIVITY THRESHOLD (2014, background): “There is a large literature on Erdös-Rényi graphs [1, 6, 18, 23] and, in particular, their spectral properties [19, 28, 29].”
Extremal eigenvalues of critical Erdős–Rényi graphs (2021, result): “The behaviour of the extremal eigenvalues is more subtle, and has been investigated in several recent works [2, 3, 7, 6, 9, 12, 8, 13, 14, 19, 11].”
Size biased couplings and the spectral gap for random regular graphs (2015, methodology): “However, it is more flexible in some ways than the trace method: it has been adapted to establish bounds on the spectral gap for several other random graph models (see, for instance, [15, 19, 20, 25, 29, 40, 42]), and it can be applied when d grows with n, as observed in [15].”
Faster least squares approximation (2007, background): “The lemma is due to Arora, Hazan, and Kale [3], although it is a modification of a lemma due to Feige and Ofek [10].”
Matrix completion from a few entries (2009, background): “The next two remarks are proved in [15], [16], and relate the original problem to the discretized one.”
Consistency of spectral clustering in stochastic block models (2013, methodology): “…T W y from the light pairs can be written as where the last inequality follows from the fact that d ≥ np max and By a standard volume argument we have | T | ≤ e n log(7 /δ ) (see Claim 2.9 of Feige & Ofek (2005) for the idea of proof; the constant 7 is obtained by a slightly more reﬁned argument).”
Universal Matrix Completion (2014, methodology): “However, (Feige & Ofek, 2005) Corollary 4.4.”
Spectral radii of sparse random matrices (2017, background): “As mentioned above, [13, 10] require the stronger condition d log n.”