Efficient Laplacian spectral density computations for networks with arbitrary degree distributions
Bibliographic Data
| ID | 6161384 |
|---|---|
| Authors | Grover Enrique Castro Guzmán (0000-0002-2900-3235), Peter F Stadler (0000-0002-5016-5191), André Fujita (0000-0002-7756-7051) |
| Year | 2021 |
| Volume | 9 |
| Issue | 3 |
| Pages | 312-327 |
| Publication date | 2021-09-01 |
| Peer Reviewed | Yes |
| Open Access | Yes |
| Type | ARTICLE |
| Venue | Network Science (JOURNAL) |
| Journal identifiers | ISSN: 2050-1250 • E-ISSN: 2050-1242 |
| Publisher | Cambridge University Press (PUBLISHER • US) |
| DOI | 10.1017/nws.2021.10 |
| OpenAlex | W3203442390 |
| Language | EN |
| References cited | 45 |
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(| E |log( n )) and O( n ), respectively, in contrast to O( n 3 ) of the diagonalization method, where n is the number of vertices and | E | is the number of edges
Algorithm · Combinatorics · Complex network · Computation · Contrast (vision · Degree (music · Degree distribution · Discrete mathematics · Iterative method · Laplace operator · Laplacian matrix · Limiting · Mathematical analysis · Physics · Statistical physics · Complex Network Analysis Techniques · Computer Science · Graph theory and applications · Mathematics · Synthesis and Properties of Aromatic Compounds · Applied Mathematics
| Citation velocity | historical |
|---|---|
| Highly cited | No |