Graph Spectra for Complex Networks

By Piet Van Mieghem. 2010

784 citations recorded by the source corpus.

This concise and self-contained introduction builds up the spectral theory of graphs from scratch, with linear algebra and the theory of polynomials developed in the later parts. The book focuses on properties and bounds for the eigenvalues of the adjacency, Laplacian and effective resistance matrices of a graph. The goal of the book is to collect spectral properties that may help to understand the behavior or main characteristics of real-world networks. The chapter on spectra of complex networks illustrates how the theory may be applied to deduce insights into real-world networks. The second edition contains new chapters on topics in linear algebra and on the effective resistance matrix, and treats the pseudoinverse of the Laplacian. The latter two matrices and the Laplacian describe linear processes, such as the flow of current, on a graph. The concepts of spectral sparsification and graph neural networks are included.

Subfields: Geometry and Topology, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/db48859397cfe3d28e32892d1f8df6709bce2704

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Geometry and Topology

In Statistical and Nonlinear Physics

Citations in the corpus

Effective graph resistance (2011, methodology): “As a result of the Interlacing Theorem [14,10] the pairwise effective resistance is a non-increasing function of the edge weights.”
The structure and dynamics of multilayer networks (2014, background): “Matrices and spectral properties It is well known that the spectral properties of the adjacency and Laplacian matrices of a network provide insights into its structure and dynamics [9,93,94].”
Diffusion dynamics on multiplex networks (2012, methodology): “Following a perturbative analysis of the spectra [16], our results allow us to get new physical insight about diffusion processes through the analytical determination of the asymptotic behavior of the eigenvalues of the Laplacian of the multiplex (supraLaplacian) when the diffusive coupling between ”
A Network Approach to Portfolio Selection (2016, background): “Based on Rayleigh’s inequality (Van Mieghem, 2011), the assumption 𝜆1 > 1 in Corollary 1 requires a positive mean correlation of returns, which is not a strong condition in practical terms.4 It is worth mentioning that centrality does not necessarily rank assets in the same way as the mean…”
The Mittag-Leffler function (2020, background): “) as in our book [40], is more a review, without detailed historical citations as in [16], but enriched with new results: art.”
Exact controllability of complex networks (2013, background): “We then have [54], det(−IN − A) = det(IN + A) = 0.”
Clustering and Community Detection in Directed Networks: A Survey (2013, background): “, λn) the diagonal matrix with the eigenvalues as entries [28, 29, 30].”
Non-Markovian Infection Spread Dramatically Alters the Susceptible-Infected-Susceptible Epidemic Threshold in Networks (2013, background): “Based on the general bound [9], maxðdav; ffiffiffiffiffiffiffiffiffi dmax p Þ 1 dmax, where dav and dmax are the average and maximum degree in a graph, respectively,”