Topological Data Analysis: Visualization and Generation of hypergraphs; and topological approximation.
COM1 Level 2
SR2, COM1-02-04
Abstract:
Combinatorial structures such as hypergraphs and simplicial complexes have found application in different domains ranging from social media to geometric shape analysis and biology; not only as a natural model for data with polyadic structure but also as the canonical representation for analyzing and computing global features of metric data. For data with Euclidean geometry, these global features have geometric interpretation in terms of the connected components, loops, voids and their high dimensional analogues. The importance of these global features of metric data has recently drawn significant attention due to the advent of a recently developed research domain of `Topological Data Analysis' and its application in image analysis, machine learning, shape analysis, computational neuroscience, computational geometry, dynamical systems, and many more. This thesis makes three contributions to the area of `Topological Data Analysis'.
First, We propose and evaluate a family of algorithms for visualizing 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 and devise several metrics to empirically and comparatively evaluate our algorithms on both synthetic and real-world datasets.
Second, We propose and evaluate an algorithm for generating k-uniform random hypergraphs with a prescribed degree sequence. We derive some analytical properties of the generated hypergraphs. Our work generalizes the configuration model for graphs to k-uniform hypergraphs.
Finally, we adopt the notion of epsilon-net of a metric space to capture bounds on the loss of topological features induced by the simplicial representation of lazy witness complex. We derive several properties of epsilon-net of point cloud and graph data to show that epsilon-nets, as a sample, is a good approximation to the data. Furthermore, epsilon-nets, as landmarks for constructing simplicial representation of lazy witness complex, gives a 3log(3)-approximation to the topological features of point cloud and graph data. We propose algorithms for constructing epsilon-nets of point clouds and graphs. We empirically validate the efficiency and effectiveness of our algorithms on several real-world point cloud and graph datasets.