CAREER: Modern Numerical Matrix Methods for Network and Graph Computations

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

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.