Numerical Methods for Graph and Network Analysis

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

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.