权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

项目摘要

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.

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