Efficient eigenvalue counts for tree-like networks

is essential in several fields. The straightforward approach consists of calculating all the eigenvalues in O(n3) (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(n3). Although both methods provide the exact number of eigenvalues in [a,b], their application for large networks is computationally infeasible. Sometimes, an approximation of μ[a,b] is enough. In this case, Chebyshev’s method approximates μ[a,b] in O(|E|) (where |E| is the number of edges). This study presents two alternatives to compute μ[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|E|), where d is the number of iterations. The latter presented slightly lower accuracy but ran linearly (⁠O(n)).