Spectral Analysis of Random Graphs with Skewed Degree Distributions
- 23 December 2004
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 602-610
- https://doi.org/10.1109/focs.2004.61
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.Keywords
This publication has 23 references indexed in Scilit:
- On clusterings-good, bad and spectralPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Co-clustering documents and words using bipartite spectral graph partitioningPublished by Association for Computing Machinery (ACM) ,2001
- Bipartite graph partitioning and data clusteringPublished by Association for Computing Machinery (ACM) ,2001
- Spectral partitioning of random graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2001
- Latent Semantic Indexing: A Probabilistic AnalysisJournal of Computer and System Sciences, 2000
- Authoritative sources in a hyperlinked environmentJournal of the ACM, 1999
- Exploring the similarity spaceACM SIGIR Forum, 1998
- Randomized AlgorithmsPublished by Cambridge University Press (CUP) ,1995
- Indexing by latent semantic analysisJournal of the American Society for Information Science, 1990
- The eigenvalues of random symmetric matricesCombinatorica, 1981