| Full text | |
| Author(s): |
Guzman, Grover E. C.
;
Fujita, Andre
Total Authors: 2
|
| Document type: | Journal article |
| Source: | JOURNAL OF COMPLEX NETWORKS; v. 11, n. 2, p. 15-pg., 2023-02-23. |
| Abstract | |
Graphs have become crucial for representing and examining biological, social and technological interactions. In this context, the graph spectrum is an exciting feature to be studied because it encodes the structural and dynamic characteristics of the graph. Hence, it becomes essential to efficiently compute the graph's spectral distribution (eigenvalue's density function). Recently, some authors proposed degree based methods to obtain the spectral density of locally tree-like networks in linear time. The bottleneck of their approach is that they assumed that the graph's assortativity is zero. However, most real-world networks, such as social and biological networks, present assortativity. Consequently, their spectral density approximations may be inaccurate. Here, we propose a method that considers assortativity. Our algorithm's time and space complexities are O(d(max)(2)), where d(max) is the largest degree of the graph. Finally, we show our method's efficacy in simulated and empirical networks. (AU) | |
| 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 |