Numerical Methods for Graph and Network Analysis

图和网络分析的数值方法

• 批准号: 1418889
• 负责人: Michele Benzi
• 金额: $ 18万
• 依托单位: Emory University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-07-15 至 2017-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1418889&HistoricalAwards=false
• 关键词: Numerical; Methods; Graph; Network; Analysis

Network science, the study of large, interconnected complex systems, has been the focus of much effort on the part of many scientists in recent years. The modeling and analysis of natural, engineered, and social networks, ranging from molecular and biological networks to the Internet, the World Wide Web, and also to online social media like Facebook and Twitter, has emerged as an important multidisciplinary field of study. Progress in this area is rapidly affecting many traditional fields of science and engineering as well as areas like public health, business, marketing, finance, and national security. The project concerns the development and analysis of computational methods for studying the structure of networks and of certain dynamical processes taking place on them. In particular, the project will develop mathematically sound approaches for maximally increasing the connectivity and robustness of networks when only a limited number of links can be added or modified. Network robustness is of paramount importance when designing infrastructure networks, since real world networks must be resilient to damage resulting from natural disasters or by man-made, malicious attacks. In addition, the project will develop efficient techniques for simulating the spread of information, viruses, rumors, etc. on networks, as well as the propagation of shocks. The techniques will be implemented on computers and tested on existing available data sets, and the software will be made available to other researchers. In the first part of the project we will design efficient algorithms for increasing network robustness and connectivity using as an objective function the total communicability of the network, which is a scalar quantity associated with the adjacency matrix of the graph. In particular, we will investigate different criteria for the addition of links in such a way as to (approximately) maximize the increase in total communicability. Edge rewiring and deletion will also be studied. The second part of the project deals with the numerical analysis of so-called Quantum Graphs. We will study numerical methods, including finite element discretizations and fast linear algebra, for solving PDEs posed on metric graphs (1D simplicial complexes), such as the diffusion and Schroedinger equations. In particular, we will study domain decomposition and iterative substructuring methods for solving the large linear systems arising when solving elliptic and parabolic problems on graphs. Exponential integrators based on Krylov subspace methods will also be investigated.

网络科学是研究大型、相互关联的复杂系统的科学，近年来一直是许多科学家努力的焦点。自然的、工程的和社交网络的建模和分析，从分子和生物网络到互联网、万维网，以及Facebook和Twitter等在线社交媒体，已经成为一个重要的多学科研究领域。这一领域的进展正在迅速影响许多传统的科学和工程领域，以及公共卫生、商业、市场营销、金融和国家安全等领域。该项目涉及研究网络结构和网络上发生的某些动态过程的计算方法的开发和分析。特别是，该项目将开发数学上合理的方法，以便在只能增加或修改有限数量的链接时最大限度地增加网络的连通性和鲁棒性。在设计基础设施网络时，网络鲁棒性至关重要，因为真实的世界网络必须能够抵御自然灾害或人为恶意攻击造成的破坏。此外，该项目将开发有效的技术，用于模拟网络上的信息、病毒、谣言等的传播以及冲击的传播。这些技术将在计算机上实施，并在现有的数据集上进行测试，该软件将提供给其他研究人员。 在该项目的第一部分，我们将设计有效的算法，以提高网络的鲁棒性和连通性作为目标函数的网络，这是一个标量与图的邻接矩阵。特别是，我们将研究不同的标准，以增加链接的方式（近似）最大限度地提高总的可通信性。边缘重新布线和删除也将进行研究。该项目的第二部分涉及所谓的量子图的数值分析。我们将研究数值方法，包括有限元离散化和快速线性代数，用于解决度量图（一维单纯形复形）上的偏微分方程，如扩散和薛定谔方程。特别是，我们将研究区域分解和迭代子结构方法来解决大型线性系统时，解决椭圆和抛物线问题的图。基于Krylov子空间方法的指数积分器也将被研究。