Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRandom Walks on Simplicial Complexes and the normalized Hodge 1-Laplacian
115
0
0.0
(
0
)
Added by
Michael Schaub
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic 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.
rate research
Read More
We study the realizability of simplicial complexes with a given pair of integer sequences, representing the node degree distribution and facet size distribution, respectively. While the $s$-uniform variant of the problem is $mathsf{NP}$-complete when $s geq 3$, we identify two populations of input sequences, most of which can be solved in polynomial time using a recursive algorithm that we contribute. Combining with a sampler for the simplicial configuration model [Young $textit{et al.}$, Phys. Rev. E $textbf{96}$, 032312 (2017)], we facilitate efficient sampling of simplicial ensembles from arbitrary degree and size distributions. We find that, contrary to expectations based on dyadic networks, increasing nodes degrees reduces the number of loops in simplicial complexes. Our work unveils a fundamental constraint on the degree-size sequences and sheds light on further analysis of higher-order phenomena based on local structures.
We provide a random simplicial complex by applying standard constructions to a Poisson point process in Euclidean space. It is gigantic in the sense that - up to homotopy equivalence - it almost surely contains infinitely many copies of every compact topological manifold, both in isolation and in percolation.
The cutoff phenomenon was recently confirmed for random walks on Ramanujan graphs by the first author and Peres. In this work, we obtain analogs in higher dimensions, for random walk operators on any Ramanujan complex associated with a simple group $G$ over a local field $F$. We show that if $T$ is any $k$-regular $G$-equivariant operator on the Bruhat-Tits building with a simple combinatorial property (collision-free), the associated random walk on the $n$-vertex Ramanujan complex has cutoff at time $log_k n$. The high dimensional case, unlike that of graphs, requires tools from non-commutative harmonic analysis and the infinite-dimensional representation theory of $G$. Via these, we show that operators $T$ as above on Ramanujan complexes give rise to Ramanujan digraphs with a special property ($r$-normal), implying cutoff. Applications include geodesic flow operators, geometric implications, and a confirmation of the Riemann Hypothesis for the associated zeta functions over every group $G$, previously known for groups of type $widetilde A_n$ and $widetilde C_2$.
We review a collection of models of random simplicial complexes together with some of the most exciting phenomena related to them. We do not attempt to cover all existing models, but try to focus on those for which many important results have been recently established rigorously in mathematics, especially in the context of algebraic topology. In application to real-world systems, the reviewed models are typically used as null models, so that we take a statistical stance, emphasizing, where applicable, the entropic properties of the reviewed models. We also review a collection of phenomena and features observed in these models, and split the presented results into two classes: phase transitions and distributional limits. We conclude with an outline of interesting future research directions.
Random abstract simplicial complex representation provides a mathematical description of wireless networks and their topology. In order to reduce the energy consumption in this type of network, we intend to reduce the number of network nodes without modifying neither the connectivity nor the coverage of the network. In this paper, we present a reduction algorithm that lower the number of points of an abstract simplicial complex in an optimal order while maintaining its topology. Then, we study the complexity of such an algorithm for a network simulated by a binomial point process and represented by a Vietoris-Rips complex.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
