有向带权网络的结构信息理论及其应用

This project focuses on the study of the theory and applications of structural information on directed weighted networks.. Structural information of networks is a new concept that was proposed by the applicant and his cooperator in 2016. The idea of definition is to explore the structure of a network by using a randomly walking particle, and measure the complexity of this network by the minimum average length of the codes that encoding the random walk under the stationary distribution based on a hierarchical structure. A theory of structural information on undirected weighted networks has been built up, and achieved good applications in the areas of biology and network security. This project is devoted to generalizing this theory to directed weighted networks. First, give the definition of structural entropy on directed weighted networks, which will be quite different from that on undirected weighted ones. Second, prove the upper and lower bounds theorem for 1- and 2-dimensional structural entropy, and give the corresponding combinatorial characterizations. Last, based on this theory, design a clustering algorithm which will be the first one in the sense of network flows on directed weighted networks, and apply it to the flow clustering problem on financial transaction networks in financial network analysis.

本项目主要研究有向带权网络中的结构信息理论及其应用。. 网络结构信息是申请人及其合作者于2016年正式提出的一个新概念，定义思想是用稳定分布下的随机游走的粒子来探索网络的结构，通过给稳定分布下的随机游走做编码，用层次结构下的最小平均编码长度来度量该网络的复杂性。基于这一思想建立起了无向带权网络的结构信息理论，并在生物学和网络安全领域获得了较好的应用。本项目致力于将这一理论推广至有向带权网络。首先，给出有向带权网络上结构熵的定义，而这一定义与无向网络中的定义将是很不一样的。其次，证明一维、二维结构熵的上下界定理，并给出相应的组合刻画。最后，基此设计出第一个有向网络上的基于网络流意义下的聚类算法，将其应用于金融网络分析中资金交易网络的流聚类问题。

本项目是项目负责人在自己团队创立的结构信息论的基础上，将该理论在有向带权网络上的扩展研究。项目主要研究有向带权网络的结构信息理论及其应用，具体内容包括：（1）有向带权网络结构熵的数学定义；（2）一、二维结构熵的上下界以及结构熵刻画的组合性质；（3）结构熵优化算法；（4）有向图结构信息理论在金融网络中的应用。项目成果包括：（1）给出了有向带权网络结构熵的数学定义；（2）证明了简单有向图一、二维结构熵上下界均可取到 \Theta(1)，此时组合性质上呈现出“黑洞”现象，即图上随机游走稳态分布中几乎所有的概率都集中在一个大小可忽略的顶点子集上。（3）针对不同的应用场景，设计了基于结构熵极小化的全局和局部聚类算法；（4）分别在非法集资和洗钱实际案例中验证了我们算法的有效性。这些成果表明，有向图结构熵与无向图相比，具有显著差异，前者在挖掘资金流汇聚的社团结构中具有独特的优势。我们与公安部第一研究所以及北京银行合作，开发了以结构熵优化算法为基础的风险管理工具，用于非法集资风险监控。