Collaborative Research: Geometric Analysis for Computer and Social Networks

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

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.