Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Efficient Laplacian spectral density computations for networks with arbitrary degree distributions

Full text
Author(s):
Guzman, Grover E. C. [1] ; Stadler, Peter F. [2, 3] ; Fujita, Andre [1]
Total Authors: 3
Affiliation:
[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
Total Affiliations: 3
Document type: Journal article
Source: NETWORK SCIENCE; v. 9, n. 3, p. 312-327, SEP 2021.
Web of Science Citations: 0
Abstract

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)

FAPESP's process: 18/21934-5 - Network statistics: theory, methods, and applications
Grantee:André Fujita
Support Opportunities: Research Projects - Thematic Grants