April 28-May 02, 2014
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.
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.
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...
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.
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.
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.Read More...
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.
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.
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.
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...
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
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.
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...
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
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.
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
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.
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.
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.
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...
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.