Characterization and comparison of large directed graphs through the spectra of the magnetic Laplacian
arXiv:2007.03466 · doi:10.1063/5.0006891
Abstract
In this paper we investigated the possibility to use the magnetic Laplacian to characterize directed graphs (a.k.a. networks). Many interesting results are obtained, including the finding that community structure is related to rotational symmetry in the spectral measurements for a type of stochastic block model. Due the hermiticity property of the magnetic Laplacian we show here how to scale our approach to larger networks containing hundreds of thousands of nodes using the Kernel Polynomial Method (KPM). We also propose to combine the KPM with the Wasserstein metric in order to measure distances between networks even when these networks are directed, large and have different sizes, a hard problem which cannot be tackled by previous methods presented in the literature. In addition, our python package is publicly available at \href{https://github.com/stdogpkg/emate}{github.com/stdogpkg/emate}. The codes can run in both CPU and GPU and can estimate the spectral density and related trace functions, such as entropy and Estrada index, even in directed or undirected networks with million of nodes.
arXiv commentAccepted for publication. This work represents the first part (with extension for large graphs) of the previous one that is available in arXiv:1812.02160
References in corpus (13)
- The Kernel Polynomial Method
- Entropy measures for complex networks: Toward an information theory of complex topologies
- Spectral entropies as information-theoretic tools for complex network comparison
- Hearing shapes of drums - mathematical and physical aspects of isospectrality
- Spectral properties of complex networks
- Magnetic eigenmaps for community detection in directed networks
- Thermodynamic characterization of networks using graph polynomials
- Nodal count of graph eigenfunctions via magnetic perturbation
- Magnetic interpretation of the nodal defect on graphs
- Isospectralization, or how to hear shape, style, and correspondence
- Self-organizing maps as a method for detecting phase transitions and phase identification
- Shape from sound: toward new tools for quantum gravity
- Thermodynamics of network model fitting with spectral entropies