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.