A fast algorithm to approximate the spectral density of locally tree-like networks with assortativity

• DOI: 10.1093/comnet/cnad005
• Publication Date: 2023-03-07T19:27:26Z
• Authors: Grover E C Guzman; André Fujita
• Keywords: Assortativity; Spectral Radius; Degree distribution

Abstract Graphs have become crucial for representing and examining biological, social technological interactions. In this context, the graph spectrum is an exciting feature to be studied because it encodes structural dynamic characteristics of graph. Hence, becomes essential efficiently compute graph’s spectral distribution (eigenvalue’s density function). Recently, some authors proposed degree-based methods obtain locally tree-like networks in linear time. The bottleneck their approach that they assumed assortativity zero. However, most real-world networks, such as biological present assortativity. Consequently, approximations may inaccurate. Here, we propose a method considers Our algorithm’s time space complexities are $\mathscr{O}(d_{\max}^{2})$, where $d_{\max}$ largest degree Finally, show our method’s efficacy simulated empirical networks.