Name
Abstract | ||
|---|---|---|
Evaluating an extremely useful graph property, the spectral radius (largest absolute eigenvalue of the graph adjacency matrix), for large graphs requires excessive computing resources. This problem becomes especially challenging, for instance with distributed or remote storage, when accessing the whole graph itself is expensive in terms of memory or bandwidth. One approach to tackle this challenge is to estimate the spectral radius of the graph while reading only a small portion of the graph. In this paper we present a sampling approach to estimate the spectral radius of large graphs. We define a score for vertices that i) is more of a combinatorial nature and is easier to compute and ii) has solid theoretical justifications hence, it closely approximate a vertex's contribution to the largest eigenvalue of the graph. Using this score, we model the sampling problem as a budgeted optimization problem and design a greedy algorithm to select a subgraph whose spectral radius approaches that of the whole graph. We provide analytical bound on computational complexity of our algorithm. We demonstrate effectiveness of our algorithm on various synthetic and real-world graphs and show that our algorithm also empirically outperforms known techniques. Furthermore, we compare the quality of our results to estimates obtained from well known upper and lower bounds known in the spectral graph theory literature. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1109/ICDCSW.2017.71 | 2017 IEEE 37th International Conference on Distributed Computing Systems Workshops (ICDCSW) |
Keywords | Field | DocType |
Spectral Analysis,Approximation Algorithms,Sampling | Adjacency matrix,Comparability graph,Spectral graph theory,Graph energy,Graph property,Computer science,Algorithm,Distance-hereditary graph,Pathwidth,Voltage graph | Conference |
ISSN | ISBN | Citations |
1545-0678 | 978-1-5386-3293-2 | 2 |
PageRank | References | Authors |
0.38 | 13 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samar Abbas | 1 | 2 | 0.71 |
| Juvaria Tariq | 2 | 5 | 1.80 |
| Arif Zaman | 3 | 8 | 2.83 |
| Imdadullah Khan | 4 | 34 | 5.80 |