RandNET: Randomness And Learning In Networks

WP1 – LIMITS ON GRAPHS AND NETWORKS

The study of random graphs goes back to the seminal work of Erdös and Rényi in 1960. Since then thousands of research papers and several textbooks have been published, resulting in a huge body of knowledge on fine properties of random graphs, threshold phenomena, random graph processes, random geometric graphs, percolation theory, and a variety of random graph models. In the last decades, a new paradigm has been emerging, namely to study limits of random graphs and other discrete structures, under suitable notions of convergence. Properties of discrete structures imply structural properties of the limiting objects and, conversely, knowledge of the limiting objects helps to understand and predict properties of discrete structures. This approach has become very fruitful and is currently a main topic of research. Typically, the limiting objects are continuous and random, and they may be equipped with metric, topological, and other properties. 

WP2 – Combinatorial parameters of random graphs and algorithms

Determining the limiting distributions of structural parameters is of paramount importance for understanding the limiting objects of discrete random structures. A significant part of the research on random graphs focuses on the analysis of graphs parameters, such as the distribution of vertex degrees, subgraphs counting, or extremal parameters such as chromatic number, diameter, maximum degree and size of largest components, as well as algorithms for computing or estimating them. By now there is a large body of results on the distribution of fundamental parameters. When a parameter is “additive”, a Gaussian limit law is expected. On the other hand, for extremal parameters non-Gaussian limit laws often occur, such as extreme value distribution or several stable laws. In this package we will mostly focus on random graphs from classes that have a proper combinatorial decomposition. Examples of such classes include many classes of trees, subcritical graph classes and minor-closed graph classes, like planar graphs. Concerning algorithms, a central topic in this area is the random generation of combinatorial objects. One of the main goals is to build efficient scalable samplers for graph models having a combinatorial decomposition.

WP3 – Combinatorial statistics and learning in networks 

With the explosion of available data in practically all areas of knowledge, statistical data analysis faces challenges of unprecedented dimension and social relevance. Processing and extracting information from enormous quantities of data poses new mathematical, statistical, and computational problems. In a rapidly growing number of applications, one needs to analyse and interpret data coming from massive networks. Instances of such explicit or implicit networks include as diverse examples as computer and communication networks, the internet, social networks, networks formed by protein interactions, networks underlying financial markets, etc. The statistical problems arising from such applications pose important novel mathematical challenges. These challenges include building novel probabilistic models, understanding the possibilities and limitations for statistical detection and inference, designing efficient algorithms for executing them, and understanding the inherent limitations of fast algorithms. In this project we aim at discovering the limits and possibilities of efficient learning and inference on large-scale networks. Inference on large graphs has been intensively studied in both Statistics and Computer Science.