复杂网络信息系统的遍历理论

This project aims at developing a rigorous mathematical theory of complex networked information systems which presents a general mathematical method to comprehend the connection between network structure and function. First, we extend the fundamental concept--routing strategy, and establish a space-time average theorem that shows the essential unity between the local revolution in micro and global behavior in macro. The theory can be used in a variety of application domains such as Google's Pagerank and the Intelligent Passport System. Second, We describe a general mechanism that explains the classical localization phenomenon observed in many complex networked system of the real world. This mechanism relies on the ergodic decomposition of any routing strategy. The theory can also be used to investigate the question of modularity in complex networks. Third, we give a systematic look at what is the efficiency of complex networked information systems in mathematical and statistical fashion. Furthermore, we establish a variational principle that can be used to choose the optimal routing strategy for a given objective function. The method has practical applications in a wide range of areas where networks are used to model complex systems.

复杂网络信息系统是信息数理学领域的核心研究内容，是以云计算和物联网为代表的新计算模式的科学基础。但迄今已知结果多止于对复杂现象本身的观测和描述，而对其产生机制尚缺乏深入而系统的理论研究。本项目以复杂网络的信息行为作为研究对象，以遍历论和动力系统为基本研究工具，在基础层面建立网络结构与功能的深刻联系，对于系统的效率与优化问题给予形式化的统一处理。这有助于发现各类动态随机复杂现象的共同本质。具体研究内容包括：建立网络信息系统的时空平均理论。揭示系统微观局部演化与宏观整体行为的内在统一性。构建网络信息系统的结构化数学描述体系，以及系统效率的变分理论。并发展一套严格的数学算法来选择恰当的路由策略以实现网络系统目标功能的最优化。本项目对于从理论上理解和认识复杂网络信息系统的内在规律性具有根本性的重要意义，同时，也能为优化网络构造模型以及软件系统的研制和开发提供理论指导。

复杂网络信息系统的核心问题在于理解网络拓扑结构与随机动态功能的关系。而以往的理论研究多局限于刻画网络结构本身，对于复杂现象产生的机制缺乏严格而系统的数学探讨。因为经典图论与随机图论不再适用于复杂网络的研究，所以本项目设法在严格意义下建立复杂网络信息系统的数学理论，并发展一套适合研究网络动态随机复杂性以及演化规律的一般方法。因此，要在基础层面建立网络结构与功能的深刻联系，对于网络功能的效率与优化问题给予形式化的统一处理。主要研究内容包括：构建网络信息系统的结构化数学描述体系，效率问题的形式化数学结构、功能最优化的实现算法与程序等。. 研究发现，每个复杂网络信息系统都自然地对应一个紧致度量空间上的拓扑动力系统，该示性动力系统的不变测度可以完全刻画网络结构与功能的全部统计特征。因此，对于复杂网络的研究就可以转化为对这个动力系统的遍历性研究。在此基础上，建立复杂网络信息系统的时空平均理论以及结构化数学描述体系。在此体系下，复杂网络的各种特定功能，在微观上都可由相应的路由策略来实现。这样，网络功能的最大化对应着路由策略的最优化。于是将系统功能的效率抽象化，最终建立系统效率的结构化变分理论。并通过建立路由策略的遍历分解理论，而发展一套严格的数学算法来选择恰当的路由策略以实现网络目标功能的最优化。以此为工具，系统地看待复杂网络的各类问题。对于一些经典问题，如节点中心性、网络拥塞、信息流动与扩散、导航以及小世界等现象，提供全新的理解和诠释。 . 本项目所建立的数学工具为严格而系统地研究复杂网络的动态随机行为以及系统功能的效率及优化问题提供了坚实的理论基础。为彻底解决复杂网络中结构与功能的根本问题，初步提供了普适的理论框架和系统的处理方法。研究结果深化了我们对复杂网络结构与功能的理解，有助于发现那些决定着复杂网络信息行为的最深刻的基本规律。与此同时，在那些网络被用作描述复杂系统的主要模型的实际领域中，这些方法都有着广阔的应用前景。