Mathematical foundations of network models and their applications.- Research School.

Basic Information

• Dates : December 9-13th, 2024
• Organisers :
  • Louigi Addario-Berry, McGill University;
  • Siva Athreya, International Centre for Theoretical Sciences-TIFR;
  • Shankar Bhamidi . University of North Carolina
  • Serte Donderwinkel, University of Groningen
  • Soumik Pal, University of Washington
• Venue :Chennai Mathematical Institute H1, SIPCOT IT Park, Siruseri, Kelambakkam, 603103



About the meeting

• Topics:
  • Network dynamics and processes on networks
    Stochastic processes that evolve over time on networks arise in multiple disciplines including physics, systems biology, computer science, sociology and epidemiology. Examples are the spread of information, misinformation, and opinions on social networks; epidemics and spread of pathogens on contact networks; the ranking of individuals in a network via random walks on it; or the evolution of synchronization in collections of interacting neurons. Secondly, a host of real world networks are dynamic in their topology (e.g. the evolution of Twitter or the web graph; disconnections in networks in agent based epidemic models due to non pharmaceutical interventions). Analyzing models of growing and changing random graphs for the above applications has been an active research area in recent years. Despite significant interest from scientists in application areas, the mathematical analysis of such phenomena is still in its infancy. This in part owing to the emergence of complex macroscopic phenomena even from simple microscopic interaction rules. Thus making studying processes on networks evolving in time one of the key challenges in the field.
  • Limits of network models
    Graph limit theory uses tools from analysis to study the structure of large graphs. Some of the most successful graph limit theories to date include the theory of graphons (for dense graphs), Benjamini–Schramm limits (for graphs with bounded average degree), and Gromov–Haudorff–Prokhorov scaling limits (for sparse random graphs with fractal structure). A primary motivation for deriving such limit theories is to understand the behavior of functionals that are continuous with respect to the associated convergence, thus enabling an understanding of asymptotics for the models of interest. On the one hand, the full domain of applicability of the existing theories is not understood. On the other hand, for important families of graphs and networks and for some natural properties, the correct limit theories are still unclear. Notable examples include graphs with diverging but sublinear degrees, directed graph models which play an important role in understanding the web graph and motif counts in large networks and their applications in neuroscience. Also under- standing processes and scaling limits on graph models such as random walks which are used in recommender systems such as PageRank, as well as more general Markov chains incorporating non-backtracking propensities are of interest in the field.
  • Statistical learning and networks
    This is a vast and rapidly burgeoning field which requires the confluence of researchers at the interface of prob- ability, statistics, and network theory. We shall concentrate on two specific challenges. The first falls within the community detection problem in a network. More specifically, suppose we are given information on a large group of people and the social relationships between them. One would then like to identify groups within the network that have higher within group connectivity as opposed to inter-group connectivity. There are techniques such as modularity and clustering methods to identify such groups but rigorous methods with precise computational efficiency remain a challenge. The second topic is identifying important features of the network that enable efficient estimation of the intial seed (source) for a wide array of propagation dynamics on networks. Such a question has applications in various areas including epidemiology. For example, origin of a rumour/gossip on social networks and source of a pathogen on contact networks.
  • Optimization on large networks
    Network-based techniques now play a key role in various pipelines in machine learning, including, for example, graph representation learning. Many widely-used applications of networks try to optimize the weights on the edges (and/or vertices) to minimize a given loss function. This is the case, for example, for neural networks, although many other problems ranging from extremal graph theory to the find maximum likelihood estimates for exponential random graph models can be cast in this framework. The minimizer is rarely explicit, and hence, in practice, it is useful to consider dynamic optimization techniques such as gradient descent or stochastic gradient descent to approximate the minimizer. Since graphs are discrete, one may take a graphon limit (see (2) above) and then consider a dynamically evolving family of graphons (see (1) above) that converges “fastest” to the minimizer. Although this approach is used in practice, the theory is still in its infancy. A very recent line of work investigated the limits of gradient descents and stochastic gradient descents in this limiting regime. The theory is strongly influenced by Wasserstein gradient flows from Monge–Kantorovich optimal transport. In that theory common diffusions, such as Brownian motion or Fokker–Planck, and Markov chains that approximate such diffusions, can be described as Wasserstein gradient flows of entropy-like functions. These descriptions, in turn, can give bounds on rates of convergence and geometric inequalities. Establishing such convergence bounds for gradient descent or stochastic gradient descents on graphons will give workable algorithms to compute the optimizer networks.
• Description of the workshop:

  This meeting preceeds the week long BIRS-CMI meeting from Dec 16-20 on “Mathematical Foundations of Network Models and their Applications “.

  The goal of this supporting week, which will take place form December 9-13, is to provide research problem background and training for graduate students, postdocs and others working in or interested in deepening their understanding of this area of probability. Individuals who are selected for the program will additionally be invited to attend the lectures in BIRS-CMI workshop the following week

  To maximize the benefit of the activity for junior participants, this workshop will have a pedagogical component. Specifically, the week will feature a couple of lectures by each of 7 established researchers that discuss the foundations of the field, while exposing connections to current research on the topics covered in the main workshop.  Each researcher will then aim to outline a research project that will be worked on by a group of 5 students/postdocs as a team. The following leading experts across the four focus areas of the workshop

  • Kavita Ramanan, Brown University.
  • Bhaswar Bhattacharya, University of Pennsylvania
  • Souvik Dhara, Prudue University
  • Minmin Wang, University of Sussex
  • Gabor Lugosi Barcelona School of Economics
  • Vivek Borkar Indian Institute of Technolog, Mumbai, India
  • Frank den Hollander, Leiden University
  have agreed to be part of this effort

  The afternoons will start with a one-hour-long block of contributed talks so that senior students and postdocs can present their work to each other. After that, the participants will work on problem sets in small groups.

• Registration form and application for travel and local hospitality: We hope to have limited support for the workshop to support local hospitality and travel within India for Ph.d. students and postdocs. If you are student or postdoc and are interested in participating then please fill the google form before September 15th, 2024 12pm, IST.