%0 Journal Article %1 guzman2022efficient %A Guzman, Grover E C %A Stadler, Peter F %A Fujita, André %D 2022 %J Journal of Complex Networks %K topic_mathfoundation imported %N 5 %P cnac040 %R 10.1093/comnet/cnac040 %T Efficient eigenvalue counts for tree-like networks %U https://doi.org/10.1093/comnet/cnac040 %V 10 %X Estimating the number of eigenvalues \textbackslashmu\_\a,b\\textbackslash of a network’s adjacency matrix in a given interval \textbackslasha,b\textbackslash is essential in several fields. The straightforward approach consists of calculating all the eigenvalues in \textbackslashO(nˆ3)\textbackslash (where \textbackslashn\textbackslash is the number of nodes in the network) and then counting the ones that belong to the interval \textbackslasha,b\textbackslash. Another approach is to use Sylvester’s law of inertia, which also requires \textbackslashO(nˆ3)\textbackslash. Although both methods provide the exact number of eigenvalues in \textbackslasha,b\textbackslash, their application for large networks is computationally infeasible. Sometimes, an approximation of \textbackslashmu\_\a,b\\textbackslash is enough. In this case, Chebyshev’s method approximates \textbackslashmu\_\a,b\\textbackslash in \textbackslashO(\textbarE\textbar)\textbackslash (where \textbackslash\textbarE\textbar\textbackslash is the number of edges). This study presents two alternatives to compute \textbackslashmu\_\a,b\\textbackslash for locally tree-like networks: edge- and degree-based algorithms. The former presented a better accuracy than Chebyshev’s method. It runs in \textbackslashO(d\textbarE\textbar)\textbackslash, where \textbackslashd\textbackslash is the number of iterations. The latter presented slightly lower accuracy but ran linearly (\textbackslashO(n)\textbackslash).

@article{guzman2022efficient, abstract = {Estimating the number of eigenvalues {\textbackslash}mu\_\{[a,b]\}{\textbackslash} of a network’s adjacency matrix in a given interval {\textbackslash}[a,b]{\textbackslash} is essential in several fields. The straightforward approach consists of calculating all the eigenvalues in {\textbackslash}O(n{\textasciicircum}3){\textbackslash} (where {\textbackslash}n{\textbackslash} is the number of nodes in the network) and then counting the ones that belong to the interval {\textbackslash}[a,b]{\textbackslash}. Another approach is to use Sylvester’s law of inertia, which also requires {\textbackslash}O(n{\textasciicircum}3){\textbackslash}. Although both methods provide the exact number of eigenvalues in {\textbackslash}[a,b]{\textbackslash}, their application for large networks is computationally infeasible. Sometimes, an approximation of {\textbackslash}mu\_\{[a,b]\}{\textbackslash} is enough. In this case, Chebyshev’s method approximates {\textbackslash}mu\_\{[a,b]\}{\textbackslash} in {\textbackslash}O({\textbar}E{\textbar}){\textbackslash} (where {\textbackslash}{\textbar}E{\textbar}{\textbackslash} is the number of edges). This study presents two alternatives to compute {\textbackslash}mu\_\{[a,b]\}{\textbackslash} for locally tree-like networks: edge- and degree-based algorithms. The former presented a better accuracy than Chebyshev’s method. It runs in {\textbackslash}O(d{\textbar}E{\textbar}){\textbackslash}, where {\textbackslash}d{\textbackslash} is the number of iterations. The latter presented slightly lower accuracy but ran linearly ({\textbackslash}O(n){\textbackslash}).}, added-at = {2024-10-02T13:52:45.000+0200}, author = {Guzman, Grover E C and Stadler, Peter F and Fujita, André}, biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/2549d229399517a1b05f7206baaff8458/scadsfct}, doi = {10.1093/comnet/cnac040}, interhash = {3b61caed43a0aedf159aac4fb43875f1}, intrahash = {549d229399517a1b05f7206baaff8458}, issn = {2051-1329}, journal = {Journal of Complex Networks}, keywords = {topic_mathfoundation imported}, month = aug, note = {\_eprint: https://academic.oup.com/comnet/article-pdf/10/5/cnac040/45499049/cnac040.pdf}, number = 5, pages = {cnac040}, timestamp = {2024-11-22T15:49:19.000+0100}, title = {Efficient eigenvalue counts for tree-like networks}, url = {https://doi.org/10.1093/comnet/cnac040}, volume = 10, year = 2022 }