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

University Of Texas At Austin, Austin TX

Investigators

Abstract

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.