Collaborative Research: Geometric Analysis of Computer and Social Networks

合作研究：计算机和社交网络的几何分析

• 批准号: 1418255
• 负责人: Xianfeng Gu
• 金额: $ 25万
• 依托单位: SUNY at Stony Brook
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1418255&HistoricalAwards=false
• 关键词: Collaborative; Research; Geometric; Analysis; Computer

This project is to develop theoretic foundations and practical algorithms for geometric analysis of massive, weighted graphs arising from computer networking applications. The main challenge of understanding large scale computer networking is the decentralized management and operations on the network. How the global behaviors (for example, congestion) emerge from decentralized, local operations (routing) is still a mystery. Differential geometry studies the connection of local structures (such as curvatures) and global properties (such as topology and geodesics). Geometric analysis theorems often naturally lead to distributed algorithms that achieve global objectives, which is ideal in networking applications.This project generalizes classical geometric analysis methods to massive graphs, the theoretic exploration focuses on the curvatures on graphs and the heat kernel estimates, relation between optimal transportation on graphs and curvatures, Ricci flow on graphs, and homology/cohomology/homotopy groups on directed graphs. The theoretic results will be applied for studying fundamental problems in computer networks, including: 1) Geodesics and network congestion: which aims to understand the connection of network congestion (e.g., on the Internet) with network curvature, and try to apply Ricci flow to alleviate network congestion by modifying local curvature; 2) Graph embedding and efficient routing: which investigates how to find an embedding of the network in geometric space in order to support greedy routing; and 3) Resource allocation in wireless networks: which applies optimal transport theory to the problem of capacitated base station allocation. The research results will be useful for applications in a broad range of fields, from pure mathematics research to theoretic physics, from telecommunication in engineering to brain imaging in medicine.

该项目旨在为计算机网络应用中产生的大规模加权图的几何分析开发理论基础和实用算法。理解大规模计算机网络的主要挑战是网络上的分散管理和操作。全局行为（例如拥塞）如何从分散的局部操作（路由）中产生仍然是一个谜。微分几何研究局部结构（如曲率）和全局性质（如拓扑和测地线）之间的联系。 本项目将经典的几何分析方法推广到海量图上，理论探索主要集中在图的曲率与热核估计、图的最优运输与曲率的关系、图的Ricci流、有向图的同调/上同调/同伦群等方面。理论结果将应用于研究计算机网络中的基本问题，包括：1）测地线和网络拥塞：旨在了解网络拥塞的联系（例如，在互联网上）与网络曲率，并尝试应用Ricci流，以减轻网络拥塞，通过修改局部曲率; 2）图嵌入和高效路由：研究如何找到一个嵌入的网络在几何空间中，以支持贪婪路由;和3）无线网络中的资源分配：这适用于最优传输理论的容量限制的基站分配问题。研究结果将有助于在广泛的领域中的应用，从纯数学研究到理论物理，从工程中的电信到医学中的脑成像。