Entropic Spectral Learning for Large-Scale Graphs
arXiv:1804.06802
Abstract
Graph spectra have been successfully used to classify network types, compute the similarity between graphs, and determine the number of communities in a network. For large graphs, where an eigen-decomposition is infeasible, iterative moment matched approximations to the spectra and kernel smoothing are typically used. We show that the underlying moment information is lost when using kernel smoothing. We further propose a spectral density approximation based on the method of Maximum Entropy, for which we develop a new algorithm. This method matches moments exactly and is everywhere positive. We demonstrate its effectiveness and superiority over existing approaches in learning graph spectra, via experiments on both synthetic networks, such as the Erdős-Rényi and Barabási-Albert random graphs, and real-world networks, such as the social networks for Orkut, YouTube, and Amazon from the SNAP dataset.
arXiv comment13 pages, 12 figures
References in corpus (12)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- Modularity and community structure in networks
- Community detection in graphs
- Uncovering the overlapping community structure of complex networks in nature and society
- Finding community structure in networks using the eigenvectors of matrices
- The Dynamics of Viral Marketing
- Spectra of "Real-World" Graphs: Beyond the Semi-Circle Law
- Detecting communities in large networks
- Calculation of Densities of States and Spectral Functions by Chebyshev Recursion and Maximum Entropy
- Maximum entropy and the problem of moments: A stable algorithm
- Application of the Maximum relative Entropy method to the physics of ferromagnetic materials