AF: Small: Geometric Methods for Network Science

AF：小：网络科学的几何方法

• 批准号: 1525817
• 负责人: Subhash Suri
• 金额: $ 49.99万
• 依托单位: University of California-Santa Barbara
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-07-01 至 2020-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1525817&HistoricalAwards=false
• 关键词: AF; Small; Geometric; Methods; Network

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.

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