Randomness and Learning in Networks
ABOUT THE PROJECT
Large Networks is one of the key notions in contemporary science and technology. The availability of massive amounts of data and interaction between individuals of large populations of any kind, whether biological, social or computer units, places network analysis at the forefront of current scientific challenges. The mathematical foundations of large networks have now become the focus of research in the later decades from diverse perspectives.
The project RandNET brings together leading researchers worldwide from the areas of combinatorics, probability theory, computer science and statistics with the aim of blending approaches from these areas in the rigorous mathematical foundations for analysing random networks. The whole project is driven by real applications in data science and learning on large networks. This is planned through an alliance between academic and industrial partners. A second goal of the project is to establish a wide platform of knowledge dissemination on the topic of randomness and learning in networks for use of specialists from all scientific disciplines.
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.
The satisfaction of the main goals of RandNET requires complementary expertise in combinatorics, graph theory, probability theory, statistics and computer science. The composition of the consortium has been designed so that these areas of expertise are widely covered and interdisciplinarity is enhanced.
Pompeu Fabra University