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.