Campuses:

Poster Session

Tuesday, April 29, 2014 - 4:05pm - 6:00pm
Lind 400
  • One Graph to Rule Them All
    Francesco Vaccarino (Politecnico di Torino)
    Let P be a finite poset. We will show that for any P-persistent
    object X in the category of finite topological spaces there is a P-
    weighted graph, whose weighted clique complex has the same P-persistent
    homology as X

    (Joint work with G.Petri (ISI Found - IMA long term visitors), A.Patania
    (ISI found and Politecnico di Torino) and M.Scolamiero (KTH))
  • Persistent Homology with Clique Filtration for Digraphs
    Irene Donato (ISI Foundation)
    Extracting synthetic and meaningful features from a
    network is extremely hard due to the intricate influence
    patterns, displayed at all the scales, and often also to
    its huge size. A novel topological way to approach this
    problem is to adapt persistent homology theory to
    networks. This can be naturally done for non-directed
    graph using clique complex construction.
    Our aim is to extend the persistent homology approach
    to directed graphs. For these graphs the main problem is
    the identification of clique complexes due to the presence
    of double links and loops. In our work we have developed
    a mapping that allows to build an undirected graph in a
    consistent way i.e., such that the information about the
    directivity of the original graph is preserved. While this
    procedure implies a proliferation of the nodes it provides
    the basic object, the undirected graph, on which the
    clique complexes identification is possible and the
    machinery of persistent homology can be applied. While
    this construction is fairly general we have discussed its
    applicability to a specific kind of directed graphs i.e.,
    those describing Markov processes.

    Joint work with G. Petri, F. Vaccarino and R. Lima
  • The Persistent Homology of the Vietoris-Rips Complex of the Circle is

    Nontrivial in Every Odd Dimension
    Henry Adams (University of Minnesota, Twin Cities)
    Consider the Vietoris-Rips complex of the circle of unit circumference equipped with the geodesic metric. Its persistent homology diagram contains an interval of positive length in every odd dimension. In particular, the persistence diagram for (2k+1)-dimensional homology consists of the open interval with birth time k/(2k+1) and death time (k+1)/(2k+3), and over this interval the Vietoris-Rips complex is homotopy equivalent to the (2k+1)-dimensional sphere.

    Joint work-in-progress with Michal Adamaszek,Christopher Peterson, and Corrine Previte.
  • Injectivity and Cubical Clustering
    Dan Guralnik (University of Pennsylvania)
    This is joint work with Jared Culbertson (AFRL) and Peter Stiller (Texas A&M). Extending the work of Carlsson--Memoli, we aim to construct a method for non-nested hierarchical clustering that is based on Isbell's theory of injective spaces. Every metric space isometrically embeds in a unique (up to isometry) injective envelope that highlights canonical features of the original metric space. Inspired by the work of Bandelt--Dress on split decompositions, we seek to exploit the structure of the injective envelope to determine a non-nested clustering program which replaces tree-based dendrograms with cubical complexes. Towards this end, we present results on the injectivity of cubical complexes and discuss some of the limitations of related work.
  • Non Total-Unimodularity Neutralized Simplicial Complexes
    Bala Krishnamoorthy (Washington State University)
    Given a simplicial complex K with weights on its simplices and a chain on it, the Optimal Homologous Chain Problem(OHCP) is to find a chain with minimal weight that is homologous to the given chain. The OHCP is NP-complete, but if the boundary matrix of K is totally unimodular (TU), it becomes solvable in polynomial time when modeled as a linear program (LP). We define a condition on K called non total-unimodularity neutralized (NTUN), which ensures that even when the boundary matrix is not TU, the OHCP LP must contain an integral optimal vertex for every input chain. This is joint work with Gavin Smith. A preprint is available at http://www.arXiv.org/abs/1304.4985.
  • Minimal Crystallizations of 3-Manifolds
    Biplab Basak (Indian Institute of Science)
    We have introduced the weight of a group which has a presentation with number of relations is at most the number of generators. We have shown that the number of vertices in any crystallization of a connected closed 3-manifold $M$ is at least the weight of the fundamental group of $M$. This lower bound is sharp for the 3-manifolds $mathbb{R P}^3$, $L(3,1)$, $L(5,2)$, $S^1times S^1 times S^1$, $S^{hspace{.2mm}2} times S^1$, $S^{hspace{.2mm}2}
    mbox{$times hspace{-5mm}_{-}$} , S^{hspace{.1mm}1}$ and $S^{hspace{.2mm}3}/Q_8$, where $Q_8$ is the quaternion group.
    Moreover, there is a unique such facet minimal crystallization in each of these seven cases. We have also constructed crystallizations of $L(kq-1,q)$ with $4(q+k-1)$ facets for $q, k geq 2$ and $L(kq+1,q)$ with $4(q+k)$ facets for $q, kgeq 1$. By a recent result of Swartz, our crystallizations of $L(kq+1, q)$ are facet minimal when $kq+1$ are even. Our construction of a crystallization of a 3-manifold $M$ is based on a presentation of the fundamental group of $M$.
  • Hierarchical Quasi-Clustering Methods for Asymmetric Networks
    Santiago Segarra (University of Pennsylvania)
    We introduce hierarchical quasi-clustering methods, a generalization of hierarchical clustering for asymmetric networks where the output structure preserves the asymmetry of the input data. We show that this output structure is equivalent to a finite quasi-ultrametric space and study admissibility with respect to two desirable properties. We prove that a modified version of single linkage is the only admissible quasi-clustering method. Moreover, we show stability of the proposed method and we establish invariance properties fulfilled by it. Algorithms are further developed and the value of quasi-clustering analysis is illustrated with a study of internal migration within United States.
  • Towards a Discrete Isoperimetric Inequality for Embedded Complexes
    Eran Nevo (Ben Gurion University of the Negev)
    Descartes showed that a planar graph with n vertices, n at least 3, has at most 3n-6 edges; this follows easily from Euler's formula. We seek an analog in higher dimensions. Kalai and Sarkaria conjectured that for d-dimensional simplicial complexes embeddable in the 2d-sphere, the ratio between the number of d-faces and (d-1)-faces is bounded by a constant depending on d.
    We present a new approach towards this problem, by suggesting a rigidity theory for balanced complexes, analogous to the classical framework rigidity.
    Based on a joint work with Gil Kalai and Isabella Novik, arXiv:1312.0209.
  • The Ordered Switching Method; Uniform Sampling for Random Directed

    Acyclic Networks
    Corrie Jacobien Carstens (RMIT University)
    Random graph models are commonly used as a null-hypothesis in the study of
    real-world networks. The random graphs generated by such models are used to
    deduce the significance of properties of real networks. As such, it is
    important that they sample uniformly from a set of networks that resemble
    the real network under study. For instance, it is common to sample from a
    specific network class, such as the class of simple undirected networks. It
    is also common to fix the degree sequence of the random networks, since the
    degree distribution has a big impact on other network properties.

    Directed acyclic networks are an important class of networks, they appear
    in biology, computer science, engineering, pure mathematics and statistics.
    The defining property of a directed acyclic network is that its vertices
    can be ordered such that all edges are directed from new to old. Such
    an ordering on the vertices is called a topological ordering.

    Existing random graph models introduce unnatural features when used to
    randomize this class of networks, such as directed cycles and multiple
    edges. We propose the ordered switching method to overcome the shortcomings
    of existing models. As its name suggests, it is a type of switching method.
    We prove that this method samples uniformly from all directed acyclic
    networks with fixed in-degree and out-degree sequence and fixed topological
    ordering.

    Since directed acyclic networks are an important class of networks and
    random graph models are widely used to find significant properties of real
    networks, there are many applications for this new random network model.
  • Ricci Curvature of the Internet Topology
    Jie Gao (State University of New York, Stony Brook (SUNY))
    Analysis of Internet topologies at both the router and AS level has shown that the Internet topology has negative curvature, measured by Gromov’s “thin triangle condition”. Negative curvature property is tightly related to structural properties of the network, such as core congestion and route reliability. In this work we analyze the discrete Ricci curvature, defined and studied by Ollivier, Lin & Yau, etc, of the Internet topologies. Ricci curvature measures whether local distances diverge or converge and is a local measure that can be quickly computed. It is a more refined measure which allows us to understand the network structure at various resolutions. We show by various Internet data sets a few universal observations — 1) the network uses negatively curved edges to connect clusters of nodes, within which edges are mostly positively curved; 2) negative Ricci curvature is closely correlated to network congestion; 3) geodesics through negatively curved edges are more stable, under node/link perturbations. We also show that the configuration model using power law degree distribution generates networks of similar curvature distribution while G(n, p) model does not.

    This is joint work with Chien Chun Ni and Xianfeng David Gu from Stony Brook University.
  • A-infinity Persistence
    Aniceto Murillo (University of Málaga)
    We introduce A-infinity persistence of a given homology filtration of topological spaces. This is a family
    homological invariants which provide information not readily available by the persistent Betti numbers of the given filtration. This may help to detect noise, not just in the simplicial structure of the filtration
    but in further geometrical properties in which the higher diagonals of the A-infinity structure are translated. For instance, persistence of the second diagonal translates into persistence of indecomposability of cup products. In the same way, persistence of the third diagonal translates into persistence of indecomposability of Massey products.

    Joint work with Francisco Belchi
  • Intrinsic Volumes of Random Cubes
    Michael Werman (Hebrew University)Matthew Wright (University of Minnesota, Twin Cities)
    The intrinsic volumes generalize both Euler characteristic and Lebesgue
    volume, quantifying the size of a set in various ways. A random cubical
    complex is a union of (possibly high-dimensional) unit cubes selected from
    a lattice according to some probability model. We analyze the intrinsic
    volumes of various types of random cubical complexes, obtaining polynomial
    formulae for the expected value and variance of these intrinsic volumes. We
    then prove an interleaving theorem about the roots of the expected
    intrinsic volumes -- that is, the values of the probability parameter at
    which an expected value is zero. Furthermore, we present a central limit
    theorem, showing that the distribution of each intrinsic volume tends
    toward a normal distribution as the size of the lattice increases towards
    infinity. This work is motivated by the study of noise in digital images
    and has applications in image processing.
  • Topological Data Analysis Through Directed Filtrations
    Greg Bell (University of North Carolina, Greensboro)
    Given a finite point set X, one constructs the Cech complex at scale r by
    taking the nerve of the subset covered by r-balls centered at the points of
    X.

    Given a direction vector u and a scale 0 ellipsoids with major axis parallel to u and length r. The normal
    directions to u have length cr. We then compute the homology of the complex
    obtained as the nerve of this cover. This additional structure defines a
    generalized persistence module, yields a correspondence between rotations
    and interleavings of persistence modules and suggests an approach to detect
    directed homological features.

    This is joint work with Athanasios Gentimis at NC State.
  • Higher-dimensional Discrete Cheeger Inequalities
    Anna Gundert (Universität zu Köln)
    For graphs, expansion is a useful concept that has found applications in various areas. The success of this concept has inspired the search for a corresponding notion in higher-dimensions.
    Expansion for graphs can be expressed combinatorially or via the spectrum of the Laplacian. The close connection of these two notions is expressed, e.g., by the discrete Cheeger inequality.
    We describe several possible notions of expansion for simplicial complexes of higher dimension as well as results exploring connections between these properties.
  • Complex Contagion on Noisy Geometric Networks
    Dane Taylor (Statistical and Applied Mathematical Sciences Institute (SAMSI))
    The study of contagion on networks is central to our understanding of collective social processes and epidemiology. However, for networks arising from an underlying manifold such as the Earth’s surface, it remains unclear the extent to which the dynamics will reflect this inherent structure, especially when long-range, “noisy” edges are present. We study the Watts threshold model (WTM) for complex contagion on noisy geometric networks – a generalization of small world networks in which nodes are embedded on a manifold. To study the extent to which contagion adheres to the manifold versus the network, which can greatly disagree on notions such as node-to-node distance, we present WTM-maps that embed the network nodes as a point cloud for which we study the topology, dimensionality, and geometry.