Collaborative Research: Prediction, Optimization and Control for Information Propagation on Networks: A Differential Equation and Mass Transportation Based Approach

你有没有想过新闻传播的速度有多快，或者一个话题在网络社交网络上变得多么流行？要定量准确地回答这些问题实际上是非常具有挑战性的。用数学语言来说，困难在于这个过程发生在极其庞大的异质网络中，传播表现出普遍的随机性。例如，Twitter用户可以在任何时候转发一条帖子，或者直接忽略它。因此，了解和预测流行话题的传播是社交网络中最新兴的问题之一。这项研究也适用于智能手机/计算机恶意软件的爆发和传染病的流行病学，因为它们的传播有着相似的数学基础。因此，我们使用网络上信息传播的一般概念来描述这些问题的动态性。在网络上传播的“信息”可以是一个时髦的话题，一种新的计算机恶意软件，或者一种传染病；这些节点可以是社交网站的用户、互联网上的计算机或人类主机；网络中的链接可以是跟随者和追随者关系，计算机的网络连接，或者人与人之间的接近或身体接触。在这个项目中，我们的目标是为网络中信息传播的几个重要问题发展新的理论和有效的计算方法。我们提出了一种新的方法，将传播建模为连续时间离散空间随机过程，并提出了基于现代最优传输理论和图上的Fokker-Plank方程的新理论和算法来解决这些问题。我们特别关注了信息传播中三个密切相关的基本问题：影响预测、传播优化和传播控制。我们将基于新方法开发有效的数值方法来解决这些问题，并期望结果可以大大提高我们理解和控制信息传播的能力。本课题的重点是大规模异构网络中信息传播的理论分析与计算。该研究在现实世界中有着广泛的应用，包括社交网络、网络安全和传染病流行。本文主要研究了与网络信息传播相关的预测与决策的三个关键问题。1)影响预测：对于网络中给定的活动节点源集，预测其影响，即预计未来活动节点（接收信息的节点）的数量。2)最优源分布：选择最优的节点源集，实现最大的影响。3)网络控制：动态改变和操纵资源分布和网络拓扑结构，以达到信息在网络上传播的理想结果。由于网络的大规模和异构结构、传播的不确定性、对传播动态的不完全了解以及数据集中的噪声等因素，这些问题难以解决。为了克服这些困难，我们采取了一种不同于任何现有方法的新颖有效的方法。特别地，我们基于最近发展的图上的福克-普朗克方程建立了微分方程系统，以描述和计算网络激活状态的概率密度函数的时间演化并估计其影响。我们设计了基于图的随机优化方法，该方法与最优传输理论的最新进展密切相关，以有效地找到最优的源分布和传播控制策略。所提出的方法高效、准确，可以在大规模的现实网络中解决这些问题。

Have you ever been wondering how fast news spreads or a topic becomes trendy in online social networks? It is actually very challenging to answer such questions quantitatively and accurately. The difficulty, in mathematical language, is that the process takes place in extremely large heterogeneous networks, and the spreads exhibit pervasive randomness. For example, a Twitter user may retweet a post at literally any time, or just ignore it. Therefore, understanding and predicting the spread of trendy topics are among the most emerging problems in social networking. The study also has applications in smartphone/computer malware outbreak and epidemiology of infectious disease since the spreads share similar mathematical underpinning. Therefore, we use a general notion of information propagation on networks to describe the dynamic nature of those problems. The 'information' being propagated on networks can be a trendy topic, a new computer malware, or an infectious disease; the nodes can be users of social networking sites, computers on the internet, or human hosts; and links in the networks can be the followee and follower relationships, the network connections of computers, or the proximity or physical contact between people. In this project, we aim at developing new theory and efficient computational methods for several important problems about information propagation in networks. We advocate a new approach to model the propagation as continuous-time discrete-space stochastic processes, and propose to address these problems by novel theory and algorithms rooted in modern optimal transport theory and Fokker-Plank equations on graphs. In particular, we focus on three closely related problems which are fundamental in information propagation: influence prediction, propagation optimization, and propagation control. We will develop efficient numerical methods based on the novel approach to tackle these problems, and expect the results can greatly advance our ability to understand and control information propagation.The focus of this project is on theoretical analysis and computations of information propagation on large-scale heterogeneous networks. The research has extensive applications in the real-world including social networking, cyber security and epidemics of infectious diseases. We concentrate on the investigation of three key problems on prediction and decision-making related to information propagation on networks. 1) Influence prediction: for a given source set of active nodes in the network, predict the influence, i.e. expected number of activated nodes (nodes which receive the information) in the future. 2) Optimal source distribution: select an optimal source set of nodes to achieve maximal influence. 3) Network control: change and manipulate resource distribution and network topology dynamically to achieve the desirable outcomes for information propagation on networks. These problems are difficult to solve due to many factors, such as large scale and heterogeneous structure of networks, uncertainties in propagation, incomplete knowledge of propagation dynamics, and noise in datasets. To overcome these difficulties, we take a novel and effective approach which is different from any existing method. In particular, we establish systems of differential equations, based on recently developed Fokker-Planck equations on graphs, to describe and compute the time evolution of the probability density functions for the activation states of the network and estimate the influence. We design graph-based stochastic optimization methods, which are closely related to the recent advancements on optimal transport theory, to effectively find optimal source distribution and propagation control strategy. The proposed methods are efficient, accurate, and can tackle those problems on large-scale real-world networks.