Random Walks on Simplicial Complexes and the normalized Hodge 1-Laplacian
arXiv:1807.05044 · doi:10.1137/18M1201019
Abstract
Focusing on coupling between edges, we generalize the relationship between the normalized graph Laplacian and random walks on graphs by devising an appropriate normalization for the Hodge Laplacian -- the generalization of the graph Laplacian for simplicial complexes -- and relate this to a random walk on edges. Importantly, these random walks are intimately connected to the topology of the simplicial complex, just as random walks on graphs are related to the topology of the graph. This serves as a foundational step towards incorporating Laplacian-based analytics for higher-order interactions. We demonstrate how to use these dynamics for data analytics that extract information about the edge-space of a simplicial complex that complements and extends graph-based analysis. Specifically, we use our normalized Hodge Laplacian to derive spectral embeddings for examining trajectory data of ocean drifters near Madagascar and also develop a generalization of personalized PageRank for the edge-space of simplicial complexes to analyze a book co-purchasing dataset.
arXiv comment38 pages, 11 figures, 1 table (abstract above shortened); to appear in SIAM Review, June 2020
References in corpus (27)
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Modularity and community structure in networks
- Error and attack tolerance of complex networks
- Epidemic processes in complex networks
- Identification of influential spreaders in complex networks
- Network robustness and fragility: Percolation on random graphs
- Link communities reveal multiscale complexity in networks
- Higher-order organization of complex networks
- Simplicial models of social contagion
- A roadmap for the computation of persistent homology
- Random walks and diffusion on networks
- Line Graphs, Link Partitions and Overlapping Communities
- Simplicial Closure and higher-order link prediction
- Clique topology reveals intrinsic geometric structure in neural correlations
- Analysis of a continuous-time model of structural balance
- Generalized network structures: The configuration model and the canonical ensemble of simplicial complexes
- Emergent Hyperbolic Network Geometry
- Dualities in persistent (co)homology
- Topological data analysis of contagion maps for examining spreading processes on networks
- The many facets of community detection in complex networks
- Construction of and efficient sampling from the simplicial configuration model
- Simplicial complexes: spectrum, homology and random walks
- Block Models and Personalized PageRank
- Structure of complex networks: Quantifying edge-to-edge relations by failure-induced flow redistribution
- Isoperimetric Inequalities in Simplicial Complexes
- A unifying Perron-Frobenius theorem for nonnegative tensors via multi-homogeneous maps
Cited by in corpus (66)
- Networks beyond pairwise interactions: structure and dynamics
- The physics of higher-order interactions in complex systems
- Dynamics on higher-order networks: A review
- What are higher-order networks?
- Higher-order interactions in complex networks of phase oscillators promote abrupt synchronization switching
- Higher-order interactions shape collective dynamics differently in hypergraphs and simplicial complexes
- Multiorder Laplacian for synchronization in higher-order networks
- Higher-order motif analysis in hypergraphs
- Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
- Inference of hyperedges and overlapping communities in hypergraphs
- Simplicial contagion in temporal higher-order networks
- Unveiling the higher-order organization of multivariate time series
- Evolution of honesty in higher-order social networks
- Weighted simplicial complexes and their representation power of higher-order network data and topology
- Higher-order interactions improve optimal collective dynamics on networks
- Unified treatment of synchronization patterns in generalized networks with higher-order, multilayer, and temporal interactions
- Modelling Non-Linear Consensus Dynamics on Hypergraphs
- Consensus on simplicial complexes, or: The nonlinear simplicial Laplacian
- Percolation and Topological Properties of Temporal Higher-order Networks
- The topological Dirac equation of networks and simplicial complexes
- Hypergraphx: a library for higher-order network analysis
- Simplicial Convolutional Filters
- Deeper but smaller: Higher-order interactions increase linear stability but shrink basins
- Homological percolation transitions in growing simplicial complexes
- Dirac signal processing of higher-order topological signals
- Finite Impulse Response Filters for Simplicial Complexes
- Signal Processing on Cell Complexes
- Spectral Detection of Simplicial Communities via Hodge Laplacians
- A class of models for random hypergraphs
- Dirac synchronization is rhythmic and explosive
- Balanced Hodge Laplacians Optimize Consensus Dynamics over Simplicial Complexes
- Turing patterns on discrete topologies: from networks to higher-order structures
- Diffusion-driven instability of topological signals coupled by the Dirac operator
- Randomizing hypergraphs preserving degree correlation and local clustering
- Local Dirac Synchronization on Networks
- Topology and dynamics of higher-order multiplex networks
- Phase chimera states on non-local hyperrings
- Hyperlink communities in higher-order networks
- Collective dynamics on higher-order networks
- A framework to generate hypergraphs with community structure
- Multiplex measures for higher-order networks
- Global topological synchronization of weighted simplicial complexes
- Hodgelets: Localized Spectral Representations of Flows on Simplicial Complexes
- Tiered synchronization in coupled oscillator populations with interaction delays and higher-order interactions
- Random Simplicial Complexes: Models and Phenomena
- Higher-order Connection Laplacians for Directed Simplicial Complexes
- Opinion Dynamics with Multi-Body Interactions
- Beyond Euclid: An Illustrated Guide to Modern Machine Learning with Geometric, Topological, and Algebraic Structures
- Outlier Detection for Trajectories via Flow-embeddings
- Higher-order signal processing with the Dirac operator
- Theory of phase reduction from hypergraphs to simplicial complexes: a general route to higher-order Kuramoto models
- Dynamical fluctuations of random walks in higher-order networks
- Pinning control of chimera states in systems with higher-order interactions
- Signal Processing on Product Spaces
- Global Topological Dirac Synchronization
- Quantifying the structural stability of simplicial homology
- Dirac-Equation Signal Processing: Physics Boosts Topological Machine Learning
- Higher-order dissimilarity measures for hypergraph comparison
- Network stochastic resonance under higher-order interactions
- Time delay embeddings to characterize the timbre of musical instruments using Topological Data Analysis: a study on synthetic and real data
- The relevance of higher-order ties
- Topological Trajectory Classification and Landmark Inference on Simplicial Complexes
- Consensus dynamics on temporal hypergraphs
- Faster Inference of Cell Complexes from Flows via Matrix Factorization
- On the efficiency of pairwise Hamiltonian control to desynchronize the higher-order Kuramoto model
- Deterministic simplicial complexes