HOME    »    SCIENTIFIC RESOURCES    »    Volumes
Abstracts and Talk Materials
Topology and Geometry of Networks and Discrete Metric Spaces
April 28-May 2, 2014

Omer Angel

Random Walks and Boundaries of Planar Graphs

The Poisson and Martin Boundaries of a planar graph will be discussed, and shown to be equivalent to the geometric boundary when the planar embedding is sufficiently nice. Based on joint work with Barlow, Gurel-Gurevich and Nachmias.

Victor Chepoi

Cop and Robber Game and Hyperbolicity

Keywords of the presentation: cop and robber game, dismantlable graphs, Gromov hyperbolicity

In the talk, after an introduction of the cop and robber game and Gromov hyperbolicity, we will outline the proof that all cop-win graphs G in the game in which the robber and the cop move at different speeds s and s' with s'0, this establishes a new --game-theoretical-- characterization of Gromov hyperbolicity. Using these results, we describe a simple constant-factor approximation of hyperbolicity of a graph on n vertices running in O(n^2log n) time. Joint work with J. Chalopin, P. Papasoglu, and T. Pecatte.


Harish Chintakunta
Hamid Krim

Preserving, Tracking and Exploiting Topological Features

The persistent/zig-zag persistent intervals provide a meaningful topological summary of a given filtration/sequence of spaces. However, there often arises the need to compute sparse generators for these intervals which serve to "track" the features corresponding to the intervals. We will address this problem on two aspects: 1) simplification of the data in order to reduce the computational complexity while preserving the desired topological features , and 2) computing a specific summand decomposition of the given persistent/zig-zag module where the summands result in the desired generators. Further, given a choice of a set of filtrations, we will present meaningful ways to choose the right filtration where the resulting bar-code reflects some underlying geometric features.

Tamal K. Dey

Computing Topological Persistence for Simplicial Maps with Application to Data Sparsification

Keywords of the presentation: Persistence, (co)homology, simplicial map, Rips filtration, sparsification

Recent data sparsification strategies in topological data analysis such as Graph Induced Complex and sparsified Rips complex give rise to a sequence of simplicial complexes connected by simplicial maps rather than inclusions. As a result, the need for computing topological persistence under such maps arises. We propose a practical algorithm for computing such persistence in Z2-homology.

A simplicial map can be decomposed into a set of elementary inclusions and vertex collapses--two atomic operations that can be supported efficiently with the notion of simplex annotations for computing persistent homology. A consistent annotation through these atomic operations implies the maintenance of a consistent cohomology basis, hence a homology basis by duality. While the idea of maintaining a cohomology basis through an inclusion is not new, maintaining them through a vertex collapse is new, which constitutes an important atomic operation for simulating simplicial maps. Annotations support the vertex collapse in addition to the usual inclusion quite naturally. We exhibit an application of this new tool in which we approximate the persistence diagram of a filtration of Rips complexes where vertex collapses are used to tame the blow-up in size.


Joel Hass

Maps Between Discrete Surfaces and Applications to Biology

Keywords of the presentation: Energy of surface deformations

There are a variety of ways to measure the stretching that occurs when one surface is deformed onto another. Various energies can be defined to quantify such distortions, and the magnitude of these energies can be used to compare the difference between two shapes.

We will discuss some applications of these ideas to mathematics and to biology. In topology, these ideas lead to new results on the space of triangulations of a surface. In biology, we will discuss computations used to compare brain cortices and proteins.

Edmond Jonckheere

Ollivier-Ricci Curvature in Wireless Networks and Adiabatic Quantum Computer Architecture

Keywords of the presentation: Ollivier-Ricci curvature, wireless networks, capacity region, tree-width, quantum adiabatic computations

Ollivier-Ricci curvature appeared in the context of Riemannian geometry as a coarse notion of the ordinary Ricci curvature. It then migrated to graphs, where its interpretation as a transportation cost (formalized under the first Wasserstein distance) clearly makes it relevant to networking problems. The first occurrence of the Ollivier-Ricci curvature is in the context of wireless networking under a protocol inspired, but different in many respects, from the Back-Pressure and referred to as Heat-Diffusion. Equipped with a concept of heat diffusion on a directed, interference network, it will be shown that the Heat-Diffusion protocol has the unique property of throughput optimality in addition to Pareto optimality relative to average queue length and routing cost. As major result, it will be shown that average queue length and routing cost both increase as the Ollivier-Ricci curvature decreases (becomes more negative). In addition, as the Ollivier-Ricci curvature decreases (becomes more negative), the capacity region shrinks. In a sense, the Ollivier-Ricci curvature plays the same role as the Gromov curvature of wireline networks. It should be noted, however, that the protocol for wireless and wireline networks are different and hence call for different curvature concept to deal with the "congestion" problem. This already gives the hint that the two curvatures cannot be related to each other. This fact is best confirmed by the tree-width problem, instrumental in mapping--and solving--a QUBO problem on a quantum adiabatic architecture. Simulation results on a variety of graphs show a simple linear interpolation relation between tree-width and Ollivier-Ricci curvature, while Gromov curvature, related to tree-length, can be demonstrated to be incomparable with tree-width.


Matthew Kahle

Simplicial Complexes with Large Homological Systoles

(This is work in progress with Dominic Dotterrer and Larry Guth.)

In a graph, the girth is the length of the smallest cycle. How large the girth can be for a graph on n vertices and m edges is a very well studied problem in combinatorics. More generally, in a d-dimensional simplicial complex, we define the d-systole to be the smallest nonempty collection of closed d-dimensional faces whose union has no boundary, and we measure the size of a systole in terms of volume, i.e. the number of faces. It is natural to ask what is the largest possible d-systole for a simplicial complex on n vertices with m top-dimensional faces.

We show the existence of simplicial complexes with large systoles using random simplicial complexes with modifications, and we also require some new results on estimating the number of triangulated surfaces on a given number of vertices. On the other hand, we show that the systoles can not be much larger than this, so these results are essentially optimal. In the higher-dimensional setting, there are surprising contrasts with the classical graph theoretic picture, and in particular the systoles can be quite large.

Dima Krioukov

Lorentzian Geometry of Complex Networks

Keywords of the presentation: Lorentzian geometry, de Sitter spaces, complex networks

Random geometric graphs in Lorentzian spaces of constant positive curvature---de Sitter spaces---are shown to model well the structure and dynamics of some complex networks, such as the Internet, social and biological networks. Random geometric graphs on Lorentzian manifolds are known as causal sets in quantum gravity where they represent discretizations of the global causal structure of spacetime. If the expansion of a universe is accelerating, its spacetime is asymptotically de Sitter spacetime. Several connections between random de Sitter graphs, and Apollonian circle packings, Farey trees, divisibility network of natural numbers, and the Riemann hypothesis are also discussed.


Yuriy Mileyko

Internet and its Dimension

Keywords of the presentation: Internet, dimension, ASN graph, persistent homology

The large-scale structure of the Internet (or, rather of the graph of the Autonomous System Nodes) has been attracting a lot of attention by the researchers for decades. One family of attractive models for this graph stipulates that it "looks like" is if sampled from a hyperbolic plane. We discuss possible tests for the dimension of samples from manifolds, and apply them to the ANS graph.

Sayan Mukherjee

Cheeger Inequalities and Random Walks on Simplicial Complexes

We state some results on Cheeger Inequalities for the combinatorial Laplacian and random walks on simplicial complexes.

Specifically, for the combinatorial Laplacian we prove that a Cheeger type inequality holds on the highest dimension, or for the boundary operator with Dirichlet boundary conditions. We also show that coboundary expanders do not satisfy natural Buser or Cheeger inequalities. We provide some statements about middle dimensions.

We also introduce random walks with absorbing states on simplicial complexes. Given a simplicial complex of dimension d, a random walk with an absorbing state is defined which relates to the spectrum of the k-dimensional Laplacian. We also examine an application of random walks on simplicial complexes to a semi-supervised learning problem. Specifically, we consider a label propagation algorithm on oriented edges, which applies to a generalization of the partially labelled classification problem on graphs.

Joint work with: John Steenbergen, Caroline Klivans, Anil Hirani, and Mark Schubel

Ron Rosenthal

Random Walks on Simplicial Complexes

Keywords of the presentation: Random walks, simplicial complexes, spectrum, homology

There are well known connections between the random walk on a graph, and its topological and spectral properties. In this talk we will define a new stochastic process on higher dimensional simplicial complexes, which reflects their homological and spectral properties in a parallel way. This leads to high dimensional analogues (not all of which hold!) of classical theorems of Kesten, Alon-Boppana, and others. Based on a joint work with Ori Parzanchevski.

Naoki Saito

Graph Laplacian Eigenvectors and Their Use for Building Wavelet Packets on Graphs

Keywords of the presentation: graph Laplacian eigenvectors, eigenfunction localization, wavelet packets and basis dictionaries on graphs

I will start describing some basics of the graph Laplacian eigenvectors of a given graph and their properties. In particular, I will describe the peculiar phase transition/localization phenomena of such eigenvectors observed on a certain type of graphs (e.g., dendritic trees of neurons). Then, I will describe how to construct wavelet packets on a given graph including the Haar-Walsh basis dictionary using the graph Laplacian eigenvectors. As an application of such basis dictionaries, I will discuss efficient approximation of functions given on graphs. This is a joint work with Jeff Irion, Yuji Nakatsukasa, and Ernest Woei.

Iraj Saniee

Large-scale Curvature of Real-life Networks and Its Implications for Computations

Keywords of the presentation: real-life networks, large-scale curvature, delta-hyperbolic graphs, shortest path distance approximation, hyperbolic core

We provide evidence that networks representing social interactions, as measured and archived by electronic communication systems, such as friendship, collaboration, co-authorship, web, peer-to-peer and other kindred networks, exhibit strong hyperbolicity in the sense of Gromov (4-point delta being much smaller than the graph diameter). We outline how one may exploit hyperbolicity to reduce computations on such graphs massively. As an example, we show that all-pair distances on a (mobile call) graph with E=100s of millions of edges may be approximated in O(E) time (i.e., in tens of minutes) with small average error (well below 10% additive error), far smaller than anticipated by theory. We speculate that this result is likely due to the uncharacteristically small hyperbolic cores of these networks (i.e., the set of nodes whose betweenness centrality scales like k*N^2 with k~0.5 as N = the node size of the graph goes to infinity).


Mei Yin

Phase Transitions in the Edge-triangle Exponential Random Graph Model

Keywords of the presentation: edge-triangle exponential random graphs, graph limits, asymptotic quantization, jump discontinuity

The edge-triangle exponential random graph model has been a topic of continued research interest. We review recent developments in the study of this classic model and concentrate on the phenomenon of phase transitions. We first describe the asymptotic feature of the model along general straight lines. We show that as we continuously vary the slopes of these lines, a typical graph exhibits quantized behavior, jumping from one complete multipartite structure to another, and the jumps happen precisely at the normal lines of a polyhedral set with infinitely many facets. We then turn to exponential models where certain constraints are imposed and capture another interesting type of jump discontinuity. Based on recent joint work with Alessandro Rinaldo and Sukhada Fadnavis and current joint work in progress with Richard Kenyon.