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)网络控制：动态地改变和操纵资源分布和网络拓扑，以达到信息在网络上传播的预期效果。由于网络规模大、结构异构性强、传播过程中存在不确定性、传播动力学知识不完全以及数据集中存在噪声等因素，这些问题难以解决。为了克服这些困难，我们采取了一种不同于任何现有方法的新颖和有效的方法。特别是，我们根据最近发展起来的图上的Fokker-Planck方程建立了微分方程组，用来描述和计算网络活化态的概率密度函数的时间演化，并估计其影响。我们设计了基于图的随机优化方法，与最优运输理论的最新进展密切相关，以有效地寻找最优源分配和传播控制策略。所提出的方法是高效、准确的，可以在大规模真实网络上解决这些问题。

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 on 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.