Paper Info
Title
Spectral Analysis of Random Graphs with Skewed Degree Distributions
Abstract
We extend spectral methods to random graphs with skewed degree distributions through a degree based normalization closely connected to the normalized Laplacian. The normalization is based on intuition drawn from perturbation theory of random matrices, and has the effect of boosting the expectation of the random adjacency matrix without increasing the variances of its entries, leading to better perturbation bounds. The primary implication of this result lies in the realm of spectral analysis of random graphs with skewed degree distributions, such as the ubiquitous "power law graphs". Recently Mihail and Papadimitriou [22] argued that for randomly generated graphs satisfying a power law degree distribution, spectral analysis of the adjacency matrix will simply produce the neighborhoods of the high degree nodes as its eigenvectors, and thus miss any embedded structure. We present a generalization of their model, incorporating latent structure, and prove that after applying our transformation, spectral analysis succeeds in recovering the latent structure with high probability.
Year
DOI
Venue
2004
10.1109/FOCS.2004.61
FOCS
Keywords
Field
DocType
random graph,spectral analysis,spectral method,random matrix,embedded structure,random adjacency matrix,random graphs,high degree node,power law degree distribution,latent structure,skewed degree distribution,skewed degree distributions,power law,perturbation theory,adjacency matrix,satisfiability,random matrices,degree distribution,eigenvectors,graph theory,random processes
Graph theory,Adjacency matrix,Discrete mathematics,Combinatorics,Normalization (statistics),Random graph,Stochastic process,Degree distribution,Eigenvalues and eigenvectors,Mathematics,Random matrix
Conference
ISSN
ISBN
Citations 
0272-5428
0-7695-2228-9
25
PageRank 
References 
Authors
1.38
18
3
Name
Order
Citations
PageRank
Anirban Dasgupta12535136.99
John E. Hopcroft2874.10
Frank McSherry34289288.94