Efficient Laplacian spectral density computations for networks with arbitrary degree distributions

Autor(es)

Guzman, Grover E. C. ^[1] ; Stadler, Peter F. ^{[2, 3]} ; Fujita, Andre ^[1]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Inst Math & Stat, Dept Comp Sci, Rua Matao 1010, BR-05508090 Sao Paulo, SP - Brazil

^[2] Univ Leipzig, Bioinformat Grp, Dept Comp Sci, Hartelstr 16-18, D-04107 Leipzig - Germany

^[3] Univ Leipzig, Interdisciplinary Ctr Bioinformat, Hartelstr 16-18, D-04107 Leipzig - Germany

• Tipo de documento: Artigo Científico
• Fonte: NETWORK SCIENCE; v. 9, n. 3, p. 312-327, SEP 2021.
• Citações Web of Science: 0

Resumo

The network Laplacian spectral density calculation is critical in many fields, including physics, chemistry, statistics, and mathematics. It is highly computationally intensive, limiting the analysis to small networks. Therefore, we present two efficient alternatives: one based on the network's edges and another on the degrees. The former gives the exact spectral density of locally tree-like networks but requires iterative edge-based message-passing equations. In contrast, the latter obtains an approximation of the spectral density using only the degree distribution. The computational complexities are O(vertical bar E vertical bar log (n)) and O(n), respectively, in contrast to O(n(3)) of the diagonalization method, where n is the number of vertices and vertical bar E vertical bar is the number of edges. (AU)

• 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