Efficient eigenvalue counts for tree-like networks

• DOI: 10.1093/comnet/cnac040
• Publication Date: 2022-08-23T07:08:09Z
• Authors: Grover E C Guzman; Peter F Stadler; André Fujita
• Keywords: Adjacency matrix; Tree (set theory); Degree (music); Matrix (chemical analysis)

Abstract Estimating the number of eigenvalues $\mu_{[a,b]}$ a network’s adjacency matrix in given interval $[a,b]$ is essential several fields. The straightforward approach consists calculating all $O(n^3)$ (where $n$ nodes network) and then counting ones that belong to $[a,b]$. Another use Sylvester’s law inertia, which also requires $O(n^3)$. Although both methods provide exact $[a,b]$, their application for large networks computationally infeasible. Sometimes, an approximation enough. In this case, Chebyshev’s method approximates $O(|E|)$ $|E|$ edges). This study presents two alternatives compute locally tree-like networks: edge- degree-based algorithms. former presented better accuracy than method. It runs $O(d|E|)$, where $d$ iterations. latter slightly lower but ran linearly ($O(n)$).