CAREER: Modern Numerical Matrix Methods for Network and Graph Computations

职业：网络和图计算的现代数值矩阵方法

• 批准号: 1149756
• 负责人: David Gleich
• 金额: $ 49.96万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-05-01 至 2019-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1149756&HistoricalAwards=false
• 关键词: CAREER; Modern; Numerical; Matrix; Methods; CAREER; Modern; Numerical; Matrix; Methods

Connected data is a hallmark of the Internet age. We now have an unprecedented ability to collect information i) on social relationships from websites like Facebook; ii) on connections between ideas from hyperlinked repositories such as Wikipedia; iii) on links between scientific fields from online cross-referenced citation databases; iv) on interactions between proteins in biology; and v) even on the connections in the human brain. Network computations, such as finding the most important people, ideas, papers, or the most important connections, help refine these raw collections of information into meaningful summaries. Consequently, making these computations fast and efficient will help produce scientific insights from the growing plethora of data available.A highly successful paradigm for stating network computations is as the solution of a matrix problem. For instance, such an approach was the heart of Google's celebrated PageRank algorithm for finding the most important pages on the web. Modern connected data, however, is so large that it has eclipsed the ability of even the best algorithms from the 20th century to cope. Interesting network computations have become more complicated as well. The investigator will study a new class of algorithms to compute nonlinear functions of matrices, such as the matrix exponential. The matrix exponential has many uses; for example, it underlies many new computations designed to identify the most important relationships in neural networks. Standard techniques for the matrix exponential involve examining all of the connections at each step (and there could be hundreds or thousands of steps), only to highlight a few pieces of information. A more recent paradigm, called local computations, only utilizes the connections from a few entities (in the matrix, they only look at a few rows or columns) at a time. The goal of this research is to design new algorithms for the matrix exponential and other functions of matrices in the local computations paradigm. These new algorithms will be able to operate on the world's largest networks quickly (ideally in seconds or minutes), and help application specialists study their data in new ways. Three driving applications will be ranking and voting, link prediction, and brain networks. The investigation will also include the study of higher-order connections in networks that give rise to three or four dimensional matrices -- commonly called tensors. All of the software developed for this research will be made available in a software package for local computations of matrix functions. The investigator will present tutorials on this software package to ensure that researchers across many disciplines can utilize the outcome of this research. To ensure that this research reaches students across many disciplines, the investigator will develop a graduate course on the use of matrix methods for network computations. Finally, given the growing importance of network data, the investigator will develop a module for high school students to show how solving systems of equations, part of the core high school curriculum, can be used to analyze information networks.

连接的数据是互联网时代的标志。 现在，我们具有前所未有的能力来收集信息i）来自Facebook等网站的社会关系； ii）关于超链接存储库（例如Wikipedia）的思想之间的联系； iii）关于来自在线交叉引用数据库的科学领域之间的联系； iv）关于生物学中蛋白质之间的相互作用； v）即使在人脑的联系上也是如此。 网络计算，例如查找最重要的人，想法，论文或最重要的联系，有助于将这些原始信息集中在有意义的摘要中。 因此，快速有效地进行这些计算将有助于从不断增长的数据可用数据中产生科学见解。一种非常成功的用于说明网络计算的范式是矩阵问题的解决方案。 例如，这种方法是Google著名的Pagerank算法的核心，用于在网络上找到最重要的页面。 但是，现代连接的数据是如此之大，以至于它甚至使20世纪最佳算法的能力黯然失色。有趣的网络计算也变得更加复杂。研究者将研究一类新的算法来计算矩阵的非线性函数，例如矩阵指数。矩阵指数有很多用途；例如，它是许多旨在识别神经网络中最重要关系的新计算的基础。矩阵指数的标准技术涉及检查每个步骤的所有连接（并且可能有数百或数千个步骤），只是突出显示一些信息。 一个更新的范式称为本地计算，仅利用来自少数实体的连接（在矩阵中，它们仅查看几行或列）一次。这项研究的目的是为局部计算范式中的矩阵指数和其他功能设计新算法。 这些新算法将能够在世界上最大的网络上（理想情况下在几秒钟或分钟内）运行，并帮助应用程序专家以新的方式研究其数据。三个驾驶应用程序将进行排名和投票，链接预测和大脑网络。 该研究还将包括对网络中高阶连接的研究，这些连接产生了三个或四个维矩阵（通常称为张量）。 为本研究开发的所有软件将在软件包中提供，用于矩阵函数的本地计算。 研究人员将在此软件包上介绍教程，以确保许多学科的研究人员可以利用这项研究的结果。为了确保这项研究能够覆盖许多学科的学生，研究人员将开发有关使用矩阵方法进行网络计算的研究生课程。最后，鉴于网络数据的重要性越来越重要，研究人员将为高中生开发一个模块，以展示如何使用方程组（核心高中课程的一部分）来分析信息网络。