NeTS: Small: Inverse Problems from Cascades: Structure, Causation and Opinions

NeTS：小：级联反问题：结构、因果关系和观点

• 批准号: 1320175
• 负责人: Sanjay Shakkottai
• 金额: $ 49.97万
• 依托单位: University of Texas at Austin
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1320175&HistoricalAwards=false
• 关键词: NeTS; Small; Inverse; Problems; Cascades

Cascades, also known as epidemic processes, are network phenomena where the activation of one node increases the likelihood of activation of its neighbors; this results in an event starting at one node eventually affecting a much larger part of the network via successive spread. Cascade processes serve as flexible yet coherent models for several phenomena: spread of viruses and malware in mobile phones, diseases in human society, opinions and actions in online social networks. This project focuses on using cascades as an inference and learning tool; the aim is to ascertain important network structure and properties, from partial and very noisy observations of cascade progressions on it. This runs counter to the vast majority of work on cascades, which is focused on the "forward" problem (of predicting how a cascade will spread given network properties). The project will develop an analytical and algorithmic framework that achieves the following three aims: 1. Inferring Graph Structure: What graph best explains observed cascades? From noisy samples of multiple cascade progressions, the project will formulate graph-learning as non-parametric statistical inference, and propose an algorithmic approach that leverages recent break-throughs in regularized convex optimization and iterative (forward-backward) methods. Conversely, the project will develop lower-bounds on sample complexity using statistical minimax theory. Applications abound - for instance, learning the true Twitter interest graph from observation of cascades over the follower network. 2. Detecting and Identifying the Causative Network: Is it possible to detect if a cascade is progressing; if so which network is it evolving on? Interactions occur over multiple possible networks in many different domains (mobile forensics, epidemiology, online social networks), pointing to the broad applicability of this thrust. 3. Learning Node Opinions: Users often need to be active participate for cascades to progress (e.g., retweet on social media). By correlating user decisions with user actions, is it possible to learn individual user opinions? For validation the project will test the algorithms both on both synthetic data and real data. Public data sets to be leveraged include Texas hospital records along with online blog and search records (Spinn3r, Twitter, Google Flu Trends, infochimps).Cascade processes are widely prevalent in modern networks. The project's algorithms and understanding of inverse problems will further the state of the art in diverse fields including biological and human disease networks, societal networks of self-interested agents, and mobile and malware networks. In addition, this project will continue and broaden the PI's emphasis on recruiting and mentoring students from under-represented communities. The industrial affiliates program of the Wireless Networking and Communications Group at The University of Texas at Austin will facilitate technology transfer to industry.

级联，也称为流行过程，是一种网络现象，其中一个节点的激活会增加其邻居激活的可能性；这会导致从一个节点开始的事件最终通过连续传播影响网络的更大部分。级联过程可以作为多种现象的灵活而连贯的模型：手机中病毒和恶意软件的传播、人类社会中的疾病、在线社交网络中的观点和行为。该项目的重点是使用级联作为推理和学习工具；目的是通过对级联进程的部分和非常嘈杂的观察来确定重要的网络结构和属性。这与级联的绝大多数工作背道而驰，级联的工作重点是“前向”问题（预测级联将如何在给定的网络属性中传播）。该项目将开发一个分析和算法框架，以实现以下三个目标： 1. 推断图结构：哪种图最能解释观察到的级联？该项目将根据多个级联级数的噪声样本，将图学习表述为非参数统计推断，并提出一种算法方法，利用正则化凸优化和迭代（前向-后向）方法的最新突破。相反，该项目将使用统计极小极大理论开发样本复杂性的下限。应用程序比比皆是 - 例如，通过观察关注者网络上的级联来学习真实的 Twitter 兴趣图。 2. 检测和识别致病网络：是否可以检测级联是否正在进展；如果是的话，它是在哪个网络上发展的？交互发生在许多不同领域（移动取证、流行病学、在线社交网络）的多个可能的网络上，表明了这一推论的广泛适用性。 3. 学习节点意见：用户通常需要积极参与级联才能取得进展（例如，在社交媒体上转发）。通过将用户决策与用户行为相关联，是否可以了解单个用户的意见？ 为了进行验证，该项目将在合成数据和真实数据上测试算法。要利用的公共数据集包括德克萨斯州医院记录以及在线博客和搜索记录（Spinn3r、Twitter、Google Flu Trends、infochimps）。级联过程在现代网络中广泛流行。该项目的算法和对逆问题的理解将进一步推动不同领域的最新技术，包括生物和人类疾病网络、自利代理的社会网络以及移动和恶意软件网络。此外，该项目将继续并扩大 PI 对招募和指导来自代表性不足社区的学生的重视。德克萨斯大学奥斯汀分校无线网络和通信小组的工业附属计划将促进技术向工业的转移。