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

合作研究：网络信息传播的预测、优化和控制：基于微分方程和大众运输的方法

• 批准号: 1620345
• 负责人: Haomin Zhou
• 金额: $ 16.48万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2020-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1620345&HistoricalAwards=false
• 关键词: Collaborative; Research; Prediction; Optimization; Control

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.

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