CAREER: Networks and Statistical Inference: New Connections and Algorithms

网络对未来至关重要;这些网络可能会控制传感和通信、社会互动和电力传输的有效性。目前的网络研究主要是在一个问题一个问题的基础上进行的，这忽略了问题域的潜在相似性，随着技术挑战的激增，越来越站不住脚。这一提议迈出了网络算法更普遍科学的第一步。我们的方法的知识基础是网络和马尔可夫随机场（MRF）之间的新连接-一个经典的形式主义统计推断。我们开发了两大类网络问题的通用算法框架：（a）分布式组合优化;基于消息传递MRF估计算法，如置信传播。这同时为调度、网络形成、设施定位等提供了新的算法。(b)网络数据分析;基于用于MRF学习的正则化和秩最小化技术。对于任何特定的应用，我们的框架都会生成一个新的、有竞争力的第一切割解决方案，该解决方案可以很容易地将领域知识改进为最先进的解决方案。这项研究将显著影响我们如何控制大规模网络，并解释它们生成的高维数据。通过提供一种通用的算法语言，它将促进跨领域技术的轻松迁移。工业将通过UT的WNCG工业附属机构计划不断影响和吸收这项研究。我们将建立一个教育社交网络，这将使K-12和本科生接触网络研究，增强UT的教学资源，并生成真实世界的社交网络数据。

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.