Analysis and generation of data with topology from combinatorial representations
Join Zoom Meeting
https://nus-sg.zoom.us/j/86120340641?pwd=dHR1RTZuNnY5YTJGYUxLbnVwRytsdz09
Meeting ID: 861 2034 0641
Password: 499555
Abstract:
Combinatorial representations of data as simplicial complexes and more generally, as hypergraphs have found application in a variety of domains ranging from social media to geometric shape analysis and biology not only as natural models for data with polyadic relations but also as canonical representations for analysing and computing global topological properties of data. These global topological properties manifest themselves in the simplicial representation of data as connected components, cycles, voids and their higher dimensional analogues.
There are three complementary aspects of understanding data with topological properties. The first aspect involves analysing the data qualitatively by visualising its hypergraph representation. The second aspect involves analysing the data quantitatively by computing its global topological properties. The third and last aspect involves generating synthetic hypergraphs with a prescribed topological property to facilitate simulation-based studies. Motivated by these qualitative, quantitative and data-generation aspects of analysing data with topological properties, this thesis makes the following three contributions.
First, we propose a family of algorithms for visualising hypergraphs inspired by the seminal work by Fruchterman and Reingold's on force-based graph drawing. We propose and discuss some criteria for good hypergraph drawing.
Second, we propose to use the notion of epsilon-net for computing a sparse simplicial representation known in the literature as lazy witness complex. The objective of the sparse representation is to approximately compute global topological properties of data since exact computation is computationally expensive due to the combinatorial nature of simplicial complexes. We derive a new bound on the approximation quality of the lazy witness representation as a result of using epsilon-net in the computation.
Finally, we propose algorithms for the construction and random generation of hypergraphs that conforms to a prescribed degree and dimension sequences as local topological constraint. Our construction algorithm facilitates the construction of an initial conforming hypergraph, as needed by the existing Markov chain Monte Carlo algorithm. Our random generation algorithm has the property that all conforming hypergraphs are generated with a positive probability. In addition, the random generation algorithm leads to an importance sampling estimator for estimating hypergraph properties. As an application, we study the effectiveness of the proposed estimator in estimating average clustering coefficients of the graph of conforming hypergraphs.