AF: Small: Geometric Methods for Network Science

分析流行病的传播，评估基于互联网的基础设施的脆弱性，对在线社交网络中的观点动态进行建模，了解大脑中的相互联系，以及基因之间的相互作用--所有这些任务，在抽象的背景下，都难以理解由相互关联的节点组成的大规模复杂网络。这些网络之所以复杂，不仅是因为它们的规模-社交网络和物联网跨越数十亿个节点，甚至大脑的粗略信息地图也涉及数百万个体素和路径-还因为它们涉及复杂、嘈杂和时变的行为-人们对社交网络中的链接或大脑中连接的结构知之甚少，几乎所有真实的网络都受到非线性动力学的影响。图论的抽象，其中任何节点都可以链接，导致算法成为这些大型且杂乱的网络图上的计算瓶颈。该项目主张在几何空间中嵌入复杂网络为应用几何方法进行快速、可扩展和近似的复杂网络分析提供了一个框架。该项目有三个研究主题：(1)可扩展网络分析中的几何嵌入的理论研究：从理论上更好地理解为什么某些图(从经验上)看起来很好地嵌入在低维空间中，发现导致大失真的自然图的性质，并设计高效且可扩展的算法来构造低失真嵌入。(2)不确定图的概率嵌入：为了评估几何嵌入的空间丰富性如何捕捉几乎所有实用图模型中固有的链接不确定性，以及(3)在二维平面中嵌入图形以用于信息制图：在二维平面中嵌入复杂的图形以揭示重要的结构主题。这些主旨是相辅相成的，因为网络分析总是需要初始的定量部分-通过通过整个网络的嵌入而实现的高效算法来估计各种网络统计数据--然后是定性的呈现-在视觉环境中显示这些网络聚合和子结构，以创建信息制图。该项目的结果将显著扩大几何算法在网络科学和一般现代数据集中的适用性。该项目涉及理论计算机科学和数学的许多主题，包括离散和计算几何、非欧几里德几何、概率论、图形绘制和信息地图学。

Analyzing the spread of an epidemic, evaluating the vulnerability of Internet-based infrastructures, modeling dynamics of opinion in online social networks, understanding interconnections in the brain, and interactions between genes -- all these tasks are, in an abstract setting, struggling to understand large-scale, complex networks of interlinked nodes. These networks are complex not only because of their scale---social networks and the Internet-of-Things span billions of nodes and even coarse information maps of the brain involve many millions of voxels and pathways---but also because they entail complex, noisy, and time-varying behavior---the structure of links in social networks or connections in brain is poorly understood, and virtually all real networks are subject to non-linear dynamics. The abstraction of graph theory, in which any nodes can be linked, leads to algorithms that become computational bottlenecks on the graphs for these large and messy networks. This project advocates that embedding complex networks in a geometric space gives a framework to apply the use of geometric methods for fast, scalable and approximate analysis of complex networks.The project has three research thrusts: (1) theoretical investigation of geometric embeddings for 'scalable network analysis:' to better understand theoretically why certain graphs appear (empirically) to embed nicely in low-dimensional spaces, discover natural graph properties that cause large distortions, and design efficient and scalable algorithms for constructing low-distortion embeddings.(2) probabilistic embeddings for 'uncertain graphs:' to evaluate how the spatial richness of geometric embeddings capture the link uncertainties inherent in virtually all practical graph models, and(3) embedding of graphs in two-dimensional plane for 'information cartography:' to embed complex graphs in the two-dimensional plane to reveal important structural themes.These thrusts complement each other, since network analysis invariably requires both an initial quantitative part---estimating various network statistics by highly efficient algorithms that are enabled by the embedding of the entire network---followed by a qualitative presentation---displaying those network aggregates and substructrures in a visual context to create an informational cartogram.The results of this project will significantly broaden the applicability of geometric algorithms to network science, and to modern data sets in general. The project touches upon many topics in theoretical computer science and mathematics including discrete and computational geometry, non-Euclidean geometry, probability theory, graph drawing, and information cartography.