| Texto completo | |
| Autor(es): |
Guzman, Grover E. C.
;
Stadler, Peter F.
;
Fujita, Andre
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | PHYSICAL REVIEW E; v. 109, n. 3, p. 13-pg., 2024-03-07. |
| Resumo | |
Graphs have become widely used to represent and study social, biological, and technological systems. Statistical methods to analyze empirical graphs were proposed based on the graph's spectral density. However, their running time is cubic in the number of vertices, precluding direct application to large instances. Thus, efficient algorithms to calculate the spectral density become necessary. For sparse graphs, the cavity method can efficiently approximate the spectral density of locally treelike undirected and directed graphs. However, it does not apply to most empirical graphs because they have heterogeneous structures. Thus, we propose methods for undirected and directed graphs with heterogeneous structures using a new vertex's neighborhood definition and the cavity approach. Our methods' time and space complexities are O(|E|h3maxt) and O(|E|h2maxt), respectively, where |E| is the number of edges, hmax is the size of the largest local neighborhood of a vertex, and t is the number of iterations required for convergence. We demonstrate the practical efficacy by estimating the spectral density of simulated and real-world undirected and directed graphs. (AU) | |
| Processo FAPESP: | 19/22845-9 - Abordagens computacionais com o objetivo de explorar interações intra e inter espécies e seu papel em todos os domínios da vida |
| Beneficiário: | André Fujita |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |
| Processo FAPESP: | 18/21934-5 - Estatística de redes: teoria, métodos e aplicações |
| Beneficiário: | André Fujita |
| Modalidade de apoio: | Auxílio à Pesquisa - Temático |
| Processo FAPESP: | 20/08343-8 - Análise (espectral) de grafos/hipergrafos para comparar redes metabólicas do patógeno Trypanosoma sp. |
| Beneficiário: | André Fujita |
| Modalidade de apoio: | Auxílio à Pesquisa - Regular |