Reconstruction and Learning in Complex Networks

已知的许多重要结果都是处理网络上算法和过程的前向分析，即预测网络上过程的可能演变。这种正向分析的第一个例子是Erdos和Renyi在1960年发表的一篇论文中对随机图的巨分量的研究，这篇论文开始了对随机图的系统研究。其他例子包括对谣言传播过程或流行病的研究。但是对于重建问题所知甚少：给定流程的快照，我们能否推断流程启动时的初始配置或流程的其他关键参数？然而，这些问题在计算机科学和其他学科（如流行病学）的交汇处发挥着根本性的作用。此外，更好地理解这种重构问题可以用于学习任务的概率构建，如组测试和集合数据问题。因此，本项目的目的是推动对这些重建和学习问题的严格研究，包括信息论和算法方面。项目的第二阶段将重点关注以下四个项目：RLCN-2.1：通过概率方法学习和重建。这里的目标是通过适当的概率结构，特别是密集的图形模型和受称为近似消息传递的新范式启发的算法方法来解决重建和学习问题。RLCN-2.2：空间混合、频谱独立性和采样算法。目标是抓住最近的工具，如光谱方法，以便为随机图形模型开发新的采样算法。RLCN-2.3：网络动力学的亚稳态。相反，这里的目的是研究有效采样的障碍，如束缚动态过程的约束或障碍。RLCN-2.4：零例患者和接触者追踪。零号病人问题要求从快照中重建流行病的来源。在最近的实证研究中出现了一个有趣的问题，即是否可以使用零病人方法来减轻流行病的传播。

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.