Approximating the Spectrum of a Graph
| Autor: | David Cohen-Steiner, Christian Sohler, Gregory Valiant, Weihao Kong |
|---|---|
| Přispěvatelé: | Understanding the Shape of Data (DATASHAPE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria), Computer Science Department [Stanford], Stanford University, Computer Science Department [Dortmund], Technische Universität Dortmund [Dortmund] (TU), DataShape, European Project: 339025,EC:FP7:ERC,ERC-2013-ADG,GUDHI(2014) |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
FOS: Computer and information sciences sublinear algorithms Spectral graph theory random walks 0102 computer and information sciences Lambda Random walk [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG] 01 natural sciences Graph Spectral line 010104 statistics & probability 010201 computation theory & mathematics Computer Science - Data Structures and Algorithms Data Structures and Algorithms (cs.DS) method of moments Adjacency matrix 0101 mathematics Laplace operator Eigenvalues and eigenvectors Mathematics |
| Zdroj: | KDD 2018-Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining KDD 2018-Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Aug 2018, London, United Kingdom KDD |
| Popis: | International audience; The spectrum of a network or graph $G=(V,E)$ with adjacency matrix $A$, consists of the eigenvalues of the normalized Laplacian $L= I - D^{-1/2} A D^{-1/2}$. This set of eigenvalues encapsulates many aspects of the structure of the graph, including the extent to which the graph posses community structures at multiple scales. We study the problem of approximating the spectrum $\lambda = (\lambda_1,\dots,\lambda_{|V|})$, $0 \le \lambda_1,\le \dots, \le \lambda_{|V|}\le 2$ of $G$ in the regime where the graph is too large to explicitly calculate the spectrum. We present a sublinear time algorithm that, given the ability to query a random node in the graph and select a random neighbor of a given node, computes a succinct representation of an approximation $\widetilde \lambda = (\widetilde \lambda_1,\dots,\widetilde \lambda_{|V|})$, $0 \le \widetilde \lambda_1,\le \dots, \le \widetilde \lambda_{|V|}\le 2$ such that $\|\widetilde \lambda - \lambda\|_1 \le \epsilon |V|$. Our algorithm has query complexity and running time $exp(O(1/\epsilon))$, independent of the size of the graph, $|V|$. We demonstrate the practical viability of our algorithm on 15 different real-world graphs from the Stanford Large Network Dataset Collection, including social networks, academic collaboration graphs, and road networks. For the smallest of these graphs, we are able to validate the accuracy of our algorithm by explicitly calculating the true spectrum; for the larger graphs, such a calculation is computationally prohibitive. In addition we study the implications of our algorithm to property testing in the bounded degree graph model. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|