Event
ANC Colloquium: Venkat Anantharam: "Studying large networks via local weak limit theory"
Friday, March 10, 2017
11:00 a.m.
1146 AV Williams Building
Kimberly Edwards
kedwards@umd.edu
Studying large networks via local weak limit theory
Venkat Anantharam
EECS Department
University of California, Berkeley
Roundtable at 3:00 pm in 1146 AVW.
Abstract
Large networks, such as social networks, communication networks, and networks describing biological processes are ubiquitous in modern applications. Further, many modern data sources arising in these applications are are best viewed as indexed by the underlying networks, rather than as time series. The local weak limit theory for sparse graphs, also known as the objective method, due to Benjamini, Schramm, Aldous, Steele, Lyons and others, provides a framework in which to make sense of what one might mean by a stationary process indexed by graphs when the graph is sparse, i.e. the number of edges is on the same scale as the number of vertices.
The theory of time series is the engine driving an enormous range of applications in areas such as control theory, communications, information theory and signal processing. It is to be expected that a theory of stationary stochastic processes indexed by combinatorial structures, in particular graphs, would eventually have a similarly wide ranging impact. The aim of this talk is to propound this vision.
For instance, consider the problem of load balancing where the number of resources and the number of demands is large. The local weak limit theory provides a way to write down a recursive distributional equation that characterizes the distribution of the balanced load experienced by a typical resource. We will illustrate how this works for load balancing on sparse graphs (joint work with Justin Salez, already published) and for load balancing on sparse hypergraphs (joint work with Payam Delgosha).
As another example, consider a sparse graph whose edges carry marks, viewed as data samples associated to the edge. For example the vertices might be individuals and an edge mark might describe the degree of affinity between the corresponding pair of individuals. We pose the problem of representing the information content of such a marked graph in the most efficient way possible. Further, we would like to do this in a universal sense, i.e., in effect, without making any statistical assumptions about the data sample being compressed. It turns out that one can do this, and what is more, the compression can be done in the most efficient way possible (joint work with Payam Delgosha). Namely, one can make sense of a notion of entropy associated to the local weak limit (due to Bordenave and Caputo) which is on a linear scale in the number of nodes, and one can compress down to this entropy in a universal sense.
All the necessary background from the theory of local weak limits that is needed will be developed during the talk. This machinery provides a way to study many problems of interest in large networks beyond just the problems that will be the focus of this talk. It is therefore valuable to familiarize oneself with this theory if one is interested in understanding the behavior of large networks, such as wired and wireless networks, transportation networks, and social networks.
Biography
Venkat Anantharam is on the faculty of the EECS Department at the University of California, Berkeley. He received the Philips India Medal and the President of India Gold Medal from IIT Madras in 1980 and an NSF Presidential Young Investigator award in 1988. He is a corecipient of the 1998 Prize Paper Award of the IEEE Information Theory Society, and a corecipient of the 2000 Stephen O. Rice Prize Paper Award of the IEEE Communications Theory Society. He received the Distinguished Alumnus Award from IIT Madras in 2008. He is a Fellow of the IEEE.
