CAREER: Networks and Statistical Inference: New Connections and Algorithms

网络对未来至关重要；这些网络可能会管理感知和通信、社会互动和电力传输的有效性。目前的网络研究主要是在一个接一个问题的基础上进行的；这忽略了问题领域的潜在相似性，随着技术挑战的激增，这一点越来越站不住脚。这项提议向网络算法的更普遍的科学迈出了第一步。我们方法的智力基础是网络和马尔可夫随机场(MRF)之间的新联系--马尔可夫随机场是统计推理的经典形式。我们为两类广泛的网络问题开发了通用的算法框架：(A)分布式组合优化；基于消息传递的MRF估计启发式，如信念传播。这同时为调度、网络形成、设施选址等提供了新的算法。(B)网络数据分析；基于用于在MRF中学习的正则化和秩最小化技术。对于任何特定的应用，我们的框架都会生成一个新的、具有竞争力的初创解决方案，该领域知识很容易提升为最新的解决方案。这项研究将对我们如何控制大规模网络以及解释它们生成的高维数据产生重大影响。通过提供一种通用的算法语言，它将促进技术跨领域的轻松移植。工业界将通过德克萨斯大学的WNCG工业附属公司计划，继续影响和吸收这项研究。我们将建立一个教育社交网络，让K-12和本科生接触网络研究，加强德克萨斯大学的教学资源，并生成真实的社交网络数据。

Networks are crucial to the future; these networks may govern the effectiveness of sensing and communication, social interactions, and power transmission. Current network research primarily proceeds on a disconnected problem-by-problem basis; this ignores the underlying similarities of problem domains, and is increasingly untenable as technology challenges proliferate. This proposal takes first steps towards a more universal science for network algorithms. The intellectual foundations of our approach are new connections between networks and Markov Random Fields (MRFs) - a classic formalism for statistical inference. We develop general-purpose algorithmic frameworks for two broad classes of network problems: (a) distributed combinatorial optimization; based on message-passing MRF estimation heuristics, like Belief Propagation. This simultaneously provides new algorithms for scheduling, network formation, facility location etc.(b) network data analysis; based on regularization and rank-minimization techniques used for learning in MRFs. This enables new methods for tomography, social network clustering, localization etc.For any particular application, our framework generates a new and competitive first-cut solution, which domain knowledge easily improves into a state-of-the-art solution.This research will significantly impact both how we control large-scale networks, and interpret the high-dimensional data they generate. By providing a common algorithmic language, it will facilitate the easy migration of techniques across fields. Industry will continuously influence and absorb this research, via the WNCG industrial affiliates program at UT. We will build a social network for education, which will expose K-12 and undergraduates to network research, enhance pedagogical resources at UT, and generate real-world social network data.