Numerical Linear Algebra Tools for the Analysis of Complex Networks

用于分析复杂网络的数值线性代数工具

• 批准号: 1115692
• 负责人: Michele Benzi
• 金额: $ 30.3万
• 依托单位: Emory University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-08-01 至 2015-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1115692&HistoricalAwards=false
• 关键词: Numerical; Linear; Algebra; Tools; Analysis

This project concerns the development, analysis and applicationof numerical linear algebra tools for the quantitative study ofimportant properties of large-scale complex networks, such ascentrality, betweenness and communicability measures. Specifically,the investigator and his collaborators study efficient algorithmsfor the fast approximation of the entries of matrix functionssuch as the exponential and the resolvent of adjacency matricesand graph Laplacians, as well as their traces. While thesematrices are quite sparse, in the case of complex networksthey behave very differently from the matrices associated withregular lattices (grids), such as those arising from discretizationsof partial differential equations. Hence, there is a need todevelop new methods, both computational and analytical, to dealwith these very large-scale problems. The investigator bringstogether expertise in classical numerical analysis and approximationtheory, as well as methods from spectral graph theory and modernnetwork analysis, to enable efficient computations involving largegraphs. Potential applications include the analysis of social networks,the study of biological and neurological networks, applications in physicsand operations research, and so forth.Over the last decade or so, the emerging field of network sciencehas had a profound influence on such different domains as physics,chemistry, biology, operations research, engineering and the socialsciences. A deep understanding of network structure and dynamics isof great importance also for Homeland Security and for many businesses,including financial institutions and e-commerce. Detailed, quantitativemodels of massive and complex networks are now pervasive owing to the unprecedented availability of data on just about any conceivable topic. Extracting useful information from these massive data sets and networks requires fast and accurate algorithms. Such algorithms can be used, for instance, to rank the `importance' of elements of a network, i.e., to determine which nodes are essential for the proper functioning of a network. They are also used to determine bottlenecks in a network, and critical connections in a graph. The importance of these notions for crucial parts of the infrastructure of a country, such as power or transportation grids,cannot be overstated. The investigator and his collaborators develop fast computer techniques to solve these and related problems.

该项目涉及数字线性代数工具的开发、分析和应用，用于定量研究大规模复杂网络的重要性质，如中心性、介数和可通信性度量。具体来说，研究者和他的合作者研究有效的算法，用于快速近似矩阵函数的条目，如指数和邻接矩阵和图拉普拉斯算子的预解式，以及它们的迹。虽然这些矩阵是相当稀疏的，但在复杂网络的情况下，它们的行为与规则格（网格）相关的矩阵非常不同，例如那些由偏微分方程离散化产生的矩阵。因此，有必要开发新的方法，计算和分析，来处理这些非常大规模的问题。研究人员带来了经典数值分析和近似理论的专业知识，以及谱图理论和现代网络分析的方法，以实现涉及大型图的高效计算。网络科学的潜在应用包括社交网络的分析、生物网络和神经网络的研究、物理学和运筹学的应用等等，在过去的十多年里，网络科学这一新兴领域已经对物理学、化学、生物学、运筹学、工程学和社会科学等不同领域产生了深远的影响。深入了解网络结构和动态对国土安全部和许多企业（包括金融机构和电子商务）也非常重要。大规模复杂网络的详细、量化模型现在已经无处不在，因为几乎任何可以想象的主题都有前所未有的数据。从这些海量数据集和网络中提取有用的信息需要快速准确的算法。例如，这种算法可以用于对网络元素的"重要性"进行排名，即，以确定哪些节点对于网络的正常运行是必要的。它们还用于确定网络中的瓶颈和图中的关键连接。这些概念对于一个国家基础设施的关键部分，如电力或运输网络的重要性怎么强调都不过分。研究人员和他的合作者开发了快速的计算机技术来解决这些问题和相关问题。