Random walks on simplicial complexes and the normalized Hodge 1-Laplacian
From MaRDI portal
Publication:5113166
DOI10.1137/18M1201019zbMATH Open1441.05205arXiv1807.05044OpenAlexW3099736351MaRDI QIDQ5113166FDOQ5113166
Michael T. Schaub, Ali Jadbabaie, Austin R. Benson, Gabor Lippner, Paul Horn
Publication date: 3 June 2020
Published in: SIAM Review (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1807.05044
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
networkssimplicial complexesHodge decompositionrandom walksdiffusion processesspectral embeddingPageRankHodge Laplacian
Applications of graph theory (05C90) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Social networks; opinion dynamics (91D30) Data structures (68P05) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Simplicial sets and complexes in algebraic topology (55U10) Random walks on graphs (05C81) Combinatorial aspects of simplicial complexes (05E45)
Cites Work
- LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
- LSMR: An Iterative Algorithm for Sparse Least-Squares Problems
- Clique topology reveals intrinsic geometric structure in neural correlations
- Statistical mechanics of complex networks
- Diffusion maps
- Topology and data
- Title not available (Why is that?)
- Barcodes: The persistent topology of data
- Title not available (Why is that?)
- Complex networks: structure and dynamics
- Title not available (Why is that?)
- The Structure and Function of Complex Networks
- The nonlinear statistics of high-contrast patches in natural images
- A new status index derived from sociometric analysis
- Dualities in persistent (co)homology
- Exploring complex networks
- Networks
- Statistical ranking and combinatorial Hodge theory
- Title not available (Why is that?)
- Title not available (Why is that?)
- Coverage in sensor networks via persistent homology
- Deeper Inside PageRank
- COBOUNDARY EXPANDERS
- Complex graphs and networks
- Main-memory triangle computations for very large (sparse (power-law)) graphs
- Title not available (Why is that?)
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Isoperimetric inequalities in simplicial complexes
- A Cheeger-type inequality on simplicial complexes
- Algebraic Potential Theory on Graphs
- Title not available (Why is that?)
- Topology of viral evolution
- Statistical Methods in Markov Chains
- Arboricity and Subgraph Listing Algorithms
- Stability analysis of diagonally equipotent matrices
- Topology of random simplicial complexes: a survey
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
- Discrete Calculus
- Title not available (Why is that?)
- PageRank beyond the web
- Fastest Mixing Markov Chain on a Graph
- Harmonic functions and boundary value problems on a chain complex
- On Laplacians of random complexes
- Simplicial complexes: Spectrum, homology and random walks
- Spectra of combinatorial Laplace operators on simplicial complexes
- AN APPLICATION OF ALGEBRAIC TOPOLOGY TO NUMERICAL ANALYSIS: ON THE EXISTENCE OF A SOLUTION TO THE NETWORK PROBLEM
- Axioms for Centrality
- Distributed Coverage Verification in Sensor Networks Without Location Information
- Testing contractibility in planar rips complexes
- Tensor Analysis
- Why do simple algorithms for triangle enumeration work in the real world?
- A rough-and-ready cluster-based approach for extracting finite-time coherent sets from sparse and incomplete trajectory data
- Random walks and diffusion on networks
- Centralities in simplicial complexes. Applications to protein interaction networks
- Random walks on simplicial complexes and harmonics
- Spectral Properties of Hypergraph Laplacian and Approximation Algorithms
- Lx = b
- Hodge Laplacians on Graphs
- Simplicial Models and Topological Inference in Biological Systems
- A Unifying Perron--Frobenius Theorem for Nonnegative Tensors via Multihomogeneous Maps
- Spectral sparsification of simplicial complexes for clustering and label propagation
- $P$-persistent homology of finite topological spaces
- Solving 1-Laplacians in Nearly Linear Time: Collapsing and Expanding a Topological Ball
Cited In (28)
- Dirac signal processing of higher-order topological signals
- Local Dirac synchronization on networks
- Networks beyond pairwise interactions: structure and dynamics
- Quantifying the structural stability of simplicial homology
- Ranking edges by their impact on the spectral complexity of information diffusion over networks
- Combinatorial and Hodge Laplacians: similarities and differences
- Random Simplicial Complexes: Models and Phenomena
- Enforcing exact physics in scientific machine learning: a data-driven exterior calculus on graphs
- Toward a spectral theory of cellular sheaves
- Opinion dynamics with multi-body interactions
- What Are Higher-Order Networks?
- Boundary values, random walks, and \(\ell^p\)-cohomology in degree one
- Cholesky-like preconditioner for Hodge Laplacians via heavy collapsible subcomplex
- Hodge Laplacians on Graphs
- Consensus on simplicial complexes: Results on stability and synchronization
- Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
- Flow-Based Community Detection in Hypergraphs
- Political structures and the topology of simplicial complexes
- A general higher-order supracentrality framework based on motifs of temporal networks and multiplex networks
- The structure and dynamics of networks with higher order interactions
- Dynamical analysis of Hyper-SIR rumor spreading model
- Signal Processing on Simplicial Complexes
- 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
- 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
Uses Software
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)
