Random walks on simplicial complexes and the normalized Hodge 1-Laplacian
From MaRDI portal
Publication:5113166
diffusion processesHodge decompositionHodge LaplaciannetworksPageRankrandom walkssimplicial complexesspectral embedding
Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Applications of graph theory (05C90) Combinatorial aspects of simplicial complexes (05E45) Simplicial sets and complexes in algebraic topology (55U10) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Social networks; opinion dynamics (91D30)
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.
Recommendations
- Random walks on simplicial complexes and harmonics
- Random walks and Laplacians on hypergraphs: when do they match?
- Signal Processing on Simplicial Complexes
- Spectral sparsification of simplicial complexes for clustering and label propagation
- High-ordered random walks and generalized Laplacians on hypergraphs
Cites work
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- P-persistent homology of finite topological spaces
- A Cheeger-type inequality on simplicial complexes
- A new status index derived from sociometric analysis
- A rough-and-ready cluster-based approach for extracting finite-time coherent sets from sparse and incomplete trajectory data
- A Unifying Perron--Frobenius Theorem for Nonnegative Tensors via Multihomogeneous Maps
- Algebraic Potential Theory on Graphs
- AN APPLICATION OF ALGEBRAIC TOPOLOGY TO NUMERICAL ANALYSIS: ON THE EXISTENCE OF A SOLUTION TO THE NETWORK PROBLEM
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Arboricity and Subgraph Listing Algorithms
- Axioms for Centrality
- Barcodes: The persistent topology of data
- Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
- Centralities in simplicial complexes. Applications to protein interaction networks
- Clique topology reveals intrinsic geometric structure in neural correlations
- Coboundary expanders
- Complex graphs and networks
- Complex networks: structure and dynamics
- Coverage in sensor networks via persistent homology
- Deeper Inside PageRank
- Diffusion maps
- Discrete calculus. Applied analysis on graphs for computational science
- Distributed Coverage Verification in Sensor Networks Without Location Information
- Dualities in persistent (co)homology
- Exploring complex networks
- Fastest Mixing Markov Chain on a Graph
- Harmonic functions and boundary value problems on a chain complex
- Hodge Laplacians on graphs
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 3957109 (Why is no real title available?)
- scientific article; zbMATH DE number 3780265 (Why is no real title available?)
- scientific article; zbMATH DE number 1168330 (Why is no real title available?)
- scientific article; zbMATH DE number 2103273 (Why is no real title available?)
- scientific article; zbMATH DE number 867649 (Why is no real title available?)
- scientific article; zbMATH DE number 3400923 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- Isoperimetric inequalities in simplicial complexes
- LSMR: An Iterative Algorithm for Sparse Least-Squares Problems
- LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
- Lx = b
- Main-memory triangle computations for very large (sparse (power-law)) graphs
- Networks. An introduction.
- PageRank beyond the web
- Random walks and diffusion on networks
- Random walks on simplicial complexes and harmonics
- Simplicial complexes: spectrum, homology and random walks
- Simplicial models and topological inference in biological systems
- Solving 1-Laplacians in nearly linear time: collapsing and expanding a topological ball
- Spectra of combinatorial Laplace operators on simplicial complexes
- Spectral properties of hypergraph Laplacian and approximation algorithms
- Spectral sparsification of simplicial complexes for clustering and label propagation
- Stability analysis of diagonally equipotent matrices
- Statistical mechanics of complex networks
- Statistical Methods in Markov Chains
- Statistical ranking and combinatorial Hodge theory
- Tensor analysis. Spectral theory and special tensors
- Testing contractibility in planar rips complexes
- The nonlinear statistics of high-contrast patches in natural images
- The Structure and Function of Complex Networks
- Topology and data
- Topology of random simplicial complexes: a survey
- Topology of viral evolution
- Why do simple algorithms for triangle enumeration work in the real world?
Cited in
(40)- Political structures and the topology of simplicial complexes
- Opinion dynamics with multi-body interactions
- Enforcing exact physics in scientific machine learning: a data-driven exterior calculus on graphs
- Random walks and Laplacians on hypergraphs: when do they match?
- Toward a spectral theory of cellular sheaves
- A general higher-order supracentrality framework based on motifs of temporal networks and multiplex networks
- Dynamical analysis of Hyper-SIR rumor spreading model
- Random walks on simplicial complexes and harmonics
- Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
- Random Simplicial Complexes: Models and Phenomena
- Flow-Based Community Detection in Hypergraphs
- Signal Processing on Simplicial Complexes
- Spectral sparsification of simplicial complexes for clustering and label propagation
- Hodge Laplacians on graphs
- Consensus on simplicial complexes: results on stability and synchronization
- What Are Higher-Order Networks?
- The structure and dynamics of networks with higher order interactions
- Quantifying the structural stability of simplicial homology
- Normalized Hodge Laplacian matrix and application to random walk on simplicial complexes
- Neuronal synchronization in time-varying higher-order networks
- Dynamics on networks with higher-order interactions
- Dirac signal processing of higher-order topological signals
- Balanced Hodge Laplacians optimize consensus dynamics over simplicial complexes
- Tiered synchronization in coupled oscillator populations with interaction delays and higher-order interactions
- Vital node identification in hypergraphs via gravity model
- Local Dirac synchronization on networks
- Ranking edges by their impact on the spectral complexity of information diffusion over networks
- Combinatorial and Hodge Laplacians: similarities and differences
- Cholesky-like preconditioner for Hodge Laplacians via heavy collapsible subcomplex
- Dynamic topology and percolation criticality in higher-order activity-vulnerability driven networks
- Theory of phase reduction from hypergraphs to simplicial complexes: a general route to higher-order Kuramoto models
- Proof of Lew's conjecture on the spectral gaps of simplicial complexes
- A graph discretization of vector Laplacian
- Multifractal detrended fluctuation and rank-based analyses of time series generated by unbiased random walks on complex networks
- A system model of three-body interactions in complex networks: consensus and conservation
- Turing patterns on discrete topologies: from networks to higher-order structures
- Synchronization of Dirac-Bianconi driven oscillators
- Multiscale Hodge scattering networks for data analysis
- Networks beyond pairwise interactions: structure and dynamics
- Boundary values, random walks, and ^p-cohomology in degree one
This page was built for publication: Random walks on simplicial complexes and the normalized Hodge 1-Laplacian
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113166)
