Reconstruction and Learning in Complex Networks

点击翻译按钮获取中文摘要

Numerous important results are known that deal with the forward analysis of algorithms and processes on networks, i.e., predict the likely evolution of a process on a network. The first example of such a forward analysis is the study of the giant component of a random graph, conducted by Erdos and Renyi in 1960 in the paper that started the systematic investigation of random graphs. Other examples include the study of rumor spreading processes or epidemics. But much less is known about the reconstruction problem: given a snapshot of the process, can we infer the initial configuration from which the process started or other key parameters of the process? Yet these questions play a fundamental role at the junction of computer science and other disciplines, such as epidemiology. Furthermore, a better understanding of such reconstruction problems can be harnessed toward probabilistic constructions for learning tasks such as the group testing and the pooled data problems. Hence, the aim of this project is to advance the rigorous study of such reconstruction and learning problems, encompassing both information-theoretic and algorithmic aspects. The second phase of the project is going to focus on the following four items: RLCN-2.1: learning and reconstruction via the probabilistic method. Here the goal is to tackle reconstruction and learning problems by means of suitable probabilistic constructions, particularly dense graphical models, and algorithmic methods inspired by the a new paradigm called Approximate Message Passing. RLCN-2.2: spatial mixing, spectral independence and sampling algorithms. The objective is to seize upon recent tools such as spectral methods in order to develop new sampling algorithms for random graphical models. RLCN-2.3: metastability of dynamics on networks. Conversely, here the aim is to investigate obstacles to efficient sampling, such as constrictions or barriers that trap dynamical processes. RLCN-2.4: patient zero and contact tracing. The patient zero problem asks to reconstruct the source of an epidemic from a snapshot. An intriguing question that emerged in recent empirical studies is whether patient zero methods can be used to mitigate epidemic spreads.