AbstractThe 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 ��(|E|log(n)) and ��(n), respectively, in contrast to ��(n3) of the diagonalization method, where n is the number of vertices and |E| is the number of edges.
%0 Journal Article
%1 Guzman2021-cm
%A Guzman, Grover E C
%A Stadler, Peter F
%A Fujita, André
%D 2021
%I Cambridge University Press (CUP)
%J Netw. Sci. (Camb. Univ. Press)
%K
%N 3
%P 312--327
%T Efficient Laplacian spectral density computations for networks with arbitrary degree distributions
%V 9
%X AbstractThe 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 ��(|E|log(n)) and ��(n), respectively, in contrast to ��(n3) of the diagonalization method, where n is the number of vertices and |E| is the number of edges.
@article{Guzman2021-cm,
abstract = {AbstractThe 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 ��(|E|log(n)) and ��(n), respectively, in contrast to ��(n3) of the diagonalization method, where n is the number of vertices and |E| is the number of edges.},
added-at = {2024-09-10T11:56:37.000+0200},
author = {Guzman, Grover E C and Stadler, Peter F and Fujita, Andr{\'e}},
biburl = {https://puma.scadsai.uni-leipzig.de/bibtex/2ca83beca5fd1077ce269e69dcd905372/scadsfct},
interhash = {7a53796c2b8650f8796457c4cd964e7d},
intrahash = {ca83beca5fd1077ce269e69dcd905372},
journal = {Netw. Sci. (Camb. Univ. Press)},
keywords = {},
language = {en},
month = sep,
number = 3,
pages = {312--327},
publisher = {Cambridge University Press (CUP)},
timestamp = {2024-09-10T15:15:57.000+0200},
title = {Efficient Laplacian spectral density computations for networks with arbitrary degree distributions},
volume = 9,
year = 2021
}
