CAREER: Networks and Statistical Inference: New Connections and Algorithms

职业：网络和统计推断：新连接和算法

• 批准号: 0954059
• 负责人: Sujay Sanghavi
• 金额: $ 42.5万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2010
• 资助国家: 美国
• 起止时间: 2010-02-01 至 2017-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0954059&HistoricalAwards=false
• 关键词: CAREER; Networks; Statistical; Inference; New

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.

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