Numerical Linear Algebra Tools for the Analysis of Complex Networks

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

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.