Directed Network Laplacians and Random Graph Models
arXiv:2107.03026 · doi:10.1098/rsos.211144
Abstract
We consider spectral methods that uncover hidden structures in directed networks. We establish and exploit connections between node reordering via (a) minimizing an objective function and (b) maximizing the likelihood of a random graph model. We focus on two existing spectral approaches that build and analyse Laplacian-style matrices via the minimization of frustration and trophic incoherence. These algorithms aim to reveal directed periodic and linear hierarchies, respectively. We show that reordering nodes using the two algorithms, or mapping them onto a specified lattice, is associated with new classes of directed random graph models. Using this random graph setting, we are able to compare the two algorithms on a given network and quantify which structure is more likely to be present. We illustrate the approach on synthetic and real networks, and discuss practical implementation issues.
References in corpus (7)
- Finding community structure in networks using the eigenvectors of matrices
- Higher-order organization of complex networks
- Nonoptimal Component Placement, but Short Processing Paths, due to Long-Distance Projections in Neural Systems
- Clustering and Community Detection in Directed Networks: A Survey
- Magnetic eigenmaps for community detection in directed networks
- Magnetic Eigenmaps for the Visualization of Directed Networks
- Graph Hierarchy: A novel approach to understanding hierarchical structures in complex networks