CAREER: Modern Numerical Matrix Methods for Network and Graph Computations

互联数据是互联网时代的一个标志。我们现在拥有前所未有的能力来收集信息：1)从Facebook等网站收集社会关系；2)从维基百科等超链接储存库收集想法之间的联系；3)从在线交叉引用数据库中收集科学领域之间的链接；4)生物学中蛋白质之间的相互作用；5)甚至是人脑中的联系。网络计算，例如寻找最重要的人、想法、论文或最重要的联系，有助于将这些原始信息集合提炼成有意义的摘要。因此，使这些计算快速高效将有助于从日益增长的可用数据中产生科学见解。陈述网络计算的一个非常成功的范例是作为矩阵问题的解决方案。例如，这种方法是谷歌著名的PageRank算法的核心，该算法用于查找网络上最重要的页面。然而，现代互联数据是如此之大，以至于它已经超过了20世纪最好的算法的处理能力。有趣的网络计算也变得更加复杂。研究人员将研究一类新的计算矩阵非线性函数的算法，如矩阵指数。矩阵指数有许多用途；例如，它是许多新计算的基础，这些计算旨在识别神经网络中最重要的关系。矩阵指数的标准技术包括检查每一步的所有联系(可能有数百步或数千步)，只是为了突出几条信息。一种更新的范例，称为局部计算，一次只利用几个实体(在矩阵中，它们只查看几行或几列)的连接。这项研究的目的是设计新的算法，在局部计算范式下计算矩阵的指数和其他函数。这些新算法将能够在世界上最大的网络上快速运行(理想情况下只需几秒钟或几分钟)，并帮助应用专家以新的方式研究他们的数据。三个驱动应用程序将是排名和投票、链接预测和大脑网络。这项研究还将包括对产生三维或四维矩阵--通常称为张量--的网络中的高阶连接的研究。为这项研究开发的所有软件都将在一个软件包中提供，用于矩阵函数的本地计算。研究人员将提供有关该软件包的教程，以确保跨多个学科的研究人员可以利用这项研究的成果。为了确保这项研究覆盖多个学科的学生，调查人员将开发一门关于使用矩阵方法进行网络计算的研究生课程。最后，鉴于网络数据的重要性与日俱增，研究人员将为高中生开发一个模块，展示如何使用高中核心课程--方程求解系统--来分析信息网络。

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.