Reconstruction and Learning in Complex Networks

复杂网络中的重构和学习

• 批准号: 438574637
• 负责人: Professor Dr. Amin Coja-Oghlan
• 金额: --
• 依托单位: Informatik II - Lehrstuhl Effiziente Algorithmen und Komplexitätstheorie
• 依托单位国家: 德国
• 项目类别: Research Units
• 资助国家: 德国
• 项目状态: 未结题
• 来源: https://gepris.dfg.de/gepris/projekt/438574637?language=en
• 关键词: Reconstruction; Learning; 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.

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