Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userConstruction of Simplicial Complexes with Prescribed Degree-Size Sequences
434
0
0.0
(
0
)
Added by
Tzu-Chi Yen
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Authors
Tzu-Chi Yen
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We propose algorithms for construction and random generation of hypergraphs without loops and with prescribed degree and dimension sequences. The objective is to provide a starting point for as well as an alternative to Markov chain Monte Carlo approaches. Our algorithms leverage the transposition of properties and algorithms devised for matrices constituted of zeros and ones with prescribed row- and column-sums to hypergraphs. The construction algorithm extends the applicability of Markov chain Monte Carlo approaches when the initial hypergraph is not provided. The random generation algorithm allows the development of a self-normalised importance sampling estimator for hypergraph properties such as the average clustering coefficient.We prove the correctness of the proposed algorithms. We also prove that the random generation algorithm generates any hypergraph following the prescribed degree and dimension sequences with a non-zero probability. We empirically and comparatively evaluate the effectiveness and efficiency of the random generation algorithm. Experiments show that the random generation algorithm provides stable and accurate estimates of average clustering coefficient, and also demonstrates a better effective sample size in comparison with the Markov chain Monte Carlo approaches.
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.
In this paper, we study linear filters to process signals defined on simplicial complexes, i.e., signals defined on nodes, edges, triangles, etc. of a simplicial complex, thereby generalizing filtering operations for graph signals. We propose a finite impulse response filter based on the Hodge Laplacian, and demonstrate how this filter can be designed to amplify or attenuate certain spectral components of simplicial signals. Specifically, we discuss how, unlike in the case of node signals, the Fourier transform in the context of edge signals can be understood in terms of two orthogonal subspaces corresponding to the gradient-flow signals and curl-flow signals arising from the Hodge decomposition. By assigning different filter coefficients to the associated terms of the Hodge Laplacian, we develop a subspace-varying filter which enables more nuanced control over these signal types. Numerical experiments are conducted to show the potential of simplicial filters for sub-component extraction, denoising and model approximation.
ErdH{o}s determined the maximum size of a nonhamiltonian graph of order $n$ and minimum degree at least $k$ in 1962. Recently, Ning and Peng generalized. ErdH{o}s work and gave the maximum size $h(n,c,k)$ of graphs with prescribed order $n$, circumference $c$ and minimum degree at least $k.$ But for some triples $n,c,k,$ the maximum size is not attained by a graph of minimum degree $k.$ For example, $h(15,14,3)=77$ is attained by a unique graph of minimum degree $7,$ not $3.$ In this paper we obtain more precise information by determining the maximum size of a graph with prescribed order, circumference and minimum degree. Consequently we solve the corresponding problem for longest paths. All these results on the size of graphs have cliq
In the spirit of topological entropy we introduce new complexity functions for general dynamical systems (namely groups and semigroups acting on closed manifolds) but with an emphasis on the dynamics induced on simplicial complexes. For expansive systems remarkable properties are observed. Known examples are revisited and new examples are presented.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
