Random Structures Spring 2014

Friday, 2:00PM-3.00PM, RLM 8.136

Organizers: Francois Baccelli and Ngoc Tran

This is a weekly working group at the Department of Mathematics at UT Austin. It is opened to anybody who is interested in topics around the theme of random structures, such as networks, spatial processes, random graphs, random combinatorial objects, with applications in operations research, machine learning and computer science.

DATE SPEAKER TITLE (click for abstract below)
February 7th Francois Baccelli Point-Shift Probabilities of a Point Process and Geometric Routing in Stochastic Networks
February 19th, 1.15PM, RLM 8.136 Daniel Valesin The Contact Process on Power Law Random Graphs
Friday March 21, RLM 8.136 Chris White An eigenvalue optimization problem for graph partitioning
Friday April 11, RLM 8.136 Francois Baccelli Random Connection Spatial Birth and Death Processes
Friday April 25th, RLM 8.136 Chris Hillar Maximum entropy distributions on graphs
Friday May 9th, RLM 8.136 Gordon (Guodong) Pang Fork-Join Networks with Non-Exchangeable Synchronization in Heavy Traffic

Title and Abstracts

Point-Shift Probabilities of a Point Process and Geometric Routing in Stochastic Networks

Francois Baccelli
Department of Mathematics, UT Austin
Department of Electrical and Computer Engineering, UT Austin

See http://www.ma.utexas.edu/seminar/abst.pdf for details

The Contact Process on Power Law Random Graphs

Daniel Valesin
Department of Mathematics, University of British Columbia

The contact process on a graph $G$ is an interacting particle system that models the spread of an infection in a population. Every infected node transmits the infection to each neighbour with rate $\lambda0$ and recovers from the infection with rate one. If $G$ is the d-dimensional integer lattice, the process exhibits a phase transition as $\lambda$ varies: if $\lambda$ is smaller than a certain threshold, then the infection disappears quickly, but if it is larger, then there is a chance for a massive epidemic. In this talk we consider the case when $G$ is a uniformly chosen random graph on $n$ vertices with a fixed heavy-tailed degree distribution. It is a result due to Chatterjee and Durrett (2009) that on such graphs, for any positive value of $\lambda$, the epidemic prevails for a long time. We study both the amount of time for the epidemic to halt and the typical density $\rho(\lambda)$ of infected vertices at times when the process is still active. We show thatthe small-$\lambda$ behaviour of $\rho(\lambda)$ depends sensitively on the exponent $a$ of the power law of the degree distribution of $G$: the decay of $\rho(\lambda)$ as $\lambda$ goes to zero exhibits three different phases if $a \in (2,2.5]$, $ a \in (2.5 , 3]$ or $a \in (3, \infty)$. Talk based on joint work with Thomas Mountford and Qiang Yao.

An eigenvalue optimization problem for graph partitioning

Chris White
Department of Mathematics, UT Austin

We will begin by reviewing extremal eigenvalue problems in the continuous setting; these problems arise frequently in shape optimization, where one is interested in determining optimal domains under various constraints. Motivated by this area, we then introduce a new graph partitioning objective where the optimality criterion is given by the sum of the Dirichlet eigenvalues of the partition components. We will discuss applications, as well as intriguing connections to other problems such as Nonnegative Matrix Factorization and Reaction Diffusion Equations. The ultimate goal of this talk will be to introduce a new framework (extremal eigenvalues) for analyzing problems on graphs. This is joint work with Braxton Osting and Edouard Oudet.

Maximum entropy distributions on graphs

Chris Hillar
Redwood Center for Theoretical Neuroscience, UC Berkeley

Inspired by the problem of sensory coding in neuroscience, we study the maximum entropy distribution on weighted graphs with a given expected degree sequence. This distribution is characterized by independent edge weights parameterized by vertex potentials at each node. Rather surprisingly, a single graph sample suffices to determine these parameters and thus the original distribution. We explain how we arrived at this result, first proved by Chatterjee, Diaconis, and Sly for the case of unweighted (binary) graphs, and how it relates to recent work of Sanyal, Sturmfels, and Vinzant on the entropic discriminant in algebraic geometry. Interestingly, our proofs require an intricate study of the inverses of diagonally dominant positive matrices and the combinatorics of bipartite graphs. (Joint work with Shaowei Lin and Andre Wibisono).

Random Connection Spatial Birth and Death Processes

Francois Baccelli
Department of Mathematics, UT Austin
Department of Electrical and Computer Engineering, UT Austin

This paper is focused on a class of spatial birth and death process of the Euclidean space where the birth rate is constant and the death rate of a given point is the shot noise created at its location by the other points of the current con guration for some response function f. An equivalent view point is that each pair of points of the con guration establishes a random connection at an exponential time determined by f, which results in the death of one of the two points. We concentrate on space-translation invariant processes of this type. Under some natural conditions on f, we construct the unique time-stationary regime of this class of point processes by a coupling argument. We then use the birth and death structure to establish a hierarchy of balance integral relations between the factorial moment measures. Finally, we use the theory of stochastic intensity to prove that the time-stationary point process exhibits a certain kind of repulsion between its points that we call f-repulsion.
Joint work with Fabien Mathieu and Ilkka Norros

Fork-Join Networks with Non-Exchangeable Synchronization in Heavy Traffic

Guodong Pang
College of Engineering, Penn State University

Fork-join networks consist of a set of service stations that serve job requests simultaneously and sequentially according to pre-designated deterministic precedence constraints. Such networks have many applications in manufacturing and telecommunications, patient flow analysis in healthcare and parallel computing. We are primarily motivated by patient flow analysis in hospitals, where as a prerequisite for a doctor examination, all the tests results for the same patient must be ready, and they cannot be mixed among patients. We call this type of constraint as non-exchangeable synchronization (NES), that is, each job can be synchronized only if all of its asks are completed. A main challenge to study fork-join networks with NES is the resequencing of tasks’ arrival orders at each service station after service completion. We tackle the resequencing issue when each service station has multiple servers under the FCFS discipline.

In this talk, we focus on a fundamental fork-join network model with a single class of jobs and NES in the many-server heavy-traffic regimes. Upon service completion, each parallel task will join a buffer associated with its service station and wait for synchronization. The goal is to understand the waiting buffer dynamics for synchronization as well as the service dynamics. We develop a new approach to show functional central limit theorems for the number of tasks in each waiting buffer for synchronization jointly with the number of tasks in each parallel service station and the number of synchronized jobs, under general assumptions on the arrival and service processes. All the limiting processes are functionals of two independent processes, the arrival limit process and the generalized Kiefer process driven by the service vector for the parallel tasks. We characterize the transient and stationary distributions of these limiting processes.