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


Omer Angel - University of British Columbia

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.

Bob Bonneau - US Air Force Research Laboratory

Complex Information Systems

The talk will provide an overview of complex information systems including quantifying, managing, and designing heterogeneous networked systems. Methods of measuring and assessing the performance of networked, software, and hardware integrated systems such as cloud architectures will be discussed including techniques of sparse approximation in systems measurements, and algebraic and topological statistical metrics for performance. Strategies of quantifying risk over different geometric and statistical classes of distributed systems will be examined as well as methods of tracking and coding dynamic information flows.

Dr. Bonneau is a Division Chief of the Information, Decision and Complex Networks Division at the Air Force Office of Scientific Research, and has established programs in the information theory and mathematics of networking and computing in the Mathematics, Information, and Biological Sciences Division. He is also on the staff of the Assistant Secretary of Defense in Research and Engineering as a specialist in communications and information technology and a Lecturer at George Washington University in the Statistics Department. Previously, Dr. Bonneau was a Senior Research Scientist at the Air Force Research Laboratory, Information Directorate in networking, communications, sensing, and computing, and a Program Manager at the Defense Advanced Research Projects Agency (DARPA) in communications. He has held academic positions in communications and sensing research at Rensselaer Polytechnic Institute and Columbia University. Dr. Bonneau has a Ph.D. in electrical engineering from Columbia University, and a Masters and Bachelors in electrical engineering from Cornell University. Dr. Bonneau is a Senior Member of IEEE and has over 80 journal and conference papers, 1 book co-authorship, contributed to 2 book chapters, and holds 3 patents.

Victor Chepoi - Aix-Marseille Université
http://pageperso.lif.univ-mrs.fr/~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.

Read More...

Harish Chintakunta - North Carolina State University
http://www4.ncsu.edu/~hkchinta/index.html
Hamid Krim - North Carolina State University
http://www.ece.ncsu.edu/people/ahk

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.

Péter Csikvári - Massachusetts Institute of Technology
http://math.mit.edu/~csikvari/

Statistical Matching Theory

In this talk I will survey some results on statistical properties of matchings of very large and infinite graphs. The main goal of the talk is to describe a few applications of a new concept called matching measure. These applications include new results on the number of (perfect) matchings in large girth graphs as well as simple new proofs of certain statistical physical theorems. This is joint work with various subsets of Miklós Abért, Péter E. Frenkel, Tamás Hubai and Gábor Kun.

Tamal Dey - The Ohio State University
http://www.cse.ohio-state.edu/~tamaldey/

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.

Read More...

Joel Hass - University of California, Davis
math.ucdavis.edu/~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.

Patricia Hersh - North Carolina State University
http://www4.ncsu.edu/~plhersh/

Combinatorics and topology of generically injective maps

Keywords of the presentation: regular cell complex, poset map, phylogenetic trees, monomial maps

This talk will highlight some interesting maps of topological spaces giving rise to maps of face posets and how an interplay of combinatorics and topology may help reveal structure of both the image and the fibers of the map. Much of the talk will focus on joint work with Alex Engstrom and Bernd Sturmfels regarding images of monomial maps on probability spaces, namely maps given by d monomials in n variables where these variables are probabilities, so maps from an n-dimensional unit cube to a d-dimensional unit cube. We dub the images of such maps as 'toric cubes'. The motivating example is the edge product space of phylogenetic trees. For any monomial map, we provide a cell structure for the image which in fact is a regular CW decomposition of the image; this involves introducing a new family of maps which are generically injective. As time permits, we will briefly highlight other interesting examples of generically injective maps coming from total positivity theory and from electrical networks as well as some new combinatorial-topological tools for studying homeomorphism type and fibers of such maps.

Edmond Jonckheere - University of Southern California
http://ee.usc.edu/faculty_staff/faculty_directory/jonckheere.htm

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.

Read More...

Matthew Kahle - The Ohio State University
http://matthewkahle.org/

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 - Northeastern University
http://www.northeastern.edu/dima

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.

Read More...

Michael Mahoney - University of California, Berkeley
http://cs.stanford.edu/people/mmahoney/

Eigenvector Localization, Implicit Regularization, and Algorithmic Anti-differentiation for Large-scale Graphs and Networked Data

Although graphs and matrices are popular ways to model data drawn from many application domains, the size scale, sparsity properties, noise properties, and many other aspects of graphs and matrices arising in realistic machine learning and data analysis applications present fundamental challenges for traditional matrix and graph algorithms. Informally, this at root has to do with the observation that small-scale or local structure in many data sets is often better or more meaningful than large-scale or global structure, which is exactly the opposite of what many traditional asymptotic tools typically implicitly assume. For example, there might be meaningful small-scale clusters in social networks that are tree-like or expander-like at large size scales. Here, I will describe how eigenvector localization can be used to justify these sorts of claims, how localization can be engineered in a principled way into popular matrix and graph algorithms in order to characterize local properties in large data sets much more generally, and how seemingly-minor details in the approximate computation of localized (as well as non-localized) objectives can make a large difference in the usefulness of a given method in downstream applications. A common theme will be the critical role of what can be called implicit regularization---that is, regularization not in the usual sense of explicitly adding a regularization term and solving the modified objective exactly, but instead as an implicit side effect of heuristics that are often used to make approximation algorithms scale well---as well as the question of what is the objective function that an approximation algorithm implicitly solve exactly.

Yuriy Mileyko - University of Hawaii at Manoa

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 - Duke University
http://www.stat.duke.edu/~sayan/Home.html

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

Eran Nevo - Ben Gurion University of the Negev

Towards a Discrete Isoperimetric Inequality for Embedded Complexes

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.

Ron Rosenthal - ETH Zürich

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 - University of California, Davis
http://www.math.ucdavis.edu/~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 - Alcatel-Lucent Technologies Bell Laboratories
http://ect.bell-labs.com/who/iis/

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).

Read More...

Mei Yin - Brown University
http://www.math.brown.edu/~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.

Go