Random walks on simplicial complexes and the normalized Hodge 1-Laplacian
From MaRDI portal
Publication:5113166
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)
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
- 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?)
- A Cheeger-type inequality on simplicial complexes
- A Unifying Perron--Frobenius Theorem for Nonnegative Tensors via Multihomogeneous Maps
- 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
- AN APPLICATION OF ALGEBRAIC TOPOLOGY TO NUMERICAL ANALYSIS: ON THE EXISTENCE OF A SOLUTION TO THE NETWORK PROBLEM
- Algebraic Potential Theory on Graphs
- 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
- 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 Methods in Markov Chains
- Statistical mechanics of complex networks
- Statistical ranking and combinatorial Hodge theory
- Tensor analysis. Spectral theory and special tensors
- Testing contractibility in planar rips complexes
- The Structure and Function of Complex Networks
- The nonlinear statistics of high-contrast patches in natural images
- 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?
- P-persistent homology of finite topological spaces
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
Cited in
(40)- Networks beyond pairwise interactions: structure and dynamics
- Dirac signal processing of higher-order topological signals
- Local Dirac synchronization on networks
- Quantifying the structural stability of simplicial homology
- 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
- Spectral sparsification of simplicial complexes for clustering and label propagation
- 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
- Random walks and Laplacians on hypergraphs: when do they match?
- Opinion dynamics with multi-body interactions
- Boundary values, random walks, and ^p-cohomology in degree one
- Random walks on simplicial complexes and harmonics
- What Are Higher-Order Networks?
- Synchronization of Dirac-Bianconi driven oscillators
- Dynamic topology and percolation criticality in higher-order activity-vulnerability driven networks
- Cholesky-like preconditioner for Hodge Laplacians via heavy collapsible subcomplex
- Proof of Lew's conjecture on the spectral gaps of simplicial complexes
- Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method
- Theory of phase reduction from hypergraphs to simplicial complexes: a general route to higher-order Kuramoto models
- A graph discretization of vector Laplacian
- 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
- Multiscale Hodge scattering networks for data analysis
- The structure and dynamics of networks with higher order interactions
- Consensus on simplicial complexes: results on stability and synchronization
- Dynamical analysis of Hyper-SIR rumor spreading model
- Hodge Laplacians on graphs
- 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
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)
