| Full text | |
| Author(s): |
Guzman, Grover E. C.
;
Stadler, Peter F.
;
Fujita, Andre
Total Authors: 3
|
| Document type: | Journal article |
| Source: | JOURNAL OF COMPLEX NETWORKS; v. 10, n. 5, p. 15-pg., 2022-08-23. |
| Abstract | |
Estimating the number of eigenvalues mu([a,b]) of a network's adjacency matrix in a given interval [a,b] is essential in several fields. The straightforward approach consists of calculating all the eigenvalues in O(n(3)) (where n is the number of nodes in the network) and then counting the ones that belong to the interval [a,b]. Another approach is to use Sylvester's law of inertia, which also requires O(n(3)). Although both methods provide the exact number of eigenvalues in [a,b], their application for large networks is computationally infeasible. Sometimes, an approximation of mu([a,b]) is enough. In this case, Chebyshev's method approximates mu([a,b]) in O(vertical bar E vertical bar) (where vertical bar E vertical bar is the number of edges). This study presents two alternatives to compute mu([a,b]) for locally tree-like networks: edge- and degree-based algorithms. The former presented a better accuracy than Chebyshev's method. It runs in O(d vertical bar E vertical bar), where d is the number of iterations. The latter presented slightly lower accuracy but ran linearly (O(n)). (AU) | |
| FAPESP's process: | 20/08343-8 - Graph/Hypergraph (spectral) analysis to compare metabolic networks of pathogenic Trypanosoma sp. |
| Grantee: | André Fujita |
| Support Opportunities: | Regular Research Grants |
| FAPESP's process: | 19/22845-9 - Computational approaches with the objective to explore intra and cross-species interactions and their role in all domains of life |
| Grantee: | André Fujita |
| Support Opportunities: | Regular Research Grants |
| FAPESP's process: | 18/21934-5 - Network statistics: theory, methods, and applications |
| Grantee: | André Fujita |
| Support Opportunities: | Research Projects - Thematic Grants |