Models and Algorithms for Higher Order Network Inference
Abstract
This project proposes to develop methods for analyzing large-scale networks that are capable of making inferences based on higher order structure. A broad range of methods across network science that are currently in use today reply on very strong "first order" assumptions about network structure. Methods such as PageRank assume that importance is defined as a local recursion: a node is important if the nodes that point to the node are important. Models of competition assume that comparisons follow from a total ordering of inherent utilities. The study of mixing patterns in general -- and degree assortativity in particular -- focus on the local correlations between pairs of connected nodes. The proposed research aims to move all these research topics (ranking, competition, assortativity) beyond first order methods. For ranking, we propose to study the general concept of higher order recursive definitions on networks, motivated by two recent applied papers that lack the context of a general theory. For competition, we aim to generalize nascent methods for non-transitive comparisons with extended methods that have sound foundations in the field of discrete choice theory. For assortativity, we propose to study the role of higher-order degree correlations in spreading processes, the friendship paradox, and the majority illusion. The proposal builds on recently published advances by the PI to model higher order structure, specifically the concept of monophily (which modifies previous understandings on homophily) and a generalization of the stochastic block model called the overdispersed stochastic block model. While the traditionally study of homophily (`love of same ) describes a bias in attribute preferences for similar others, this recent work observes that attribute preferences can exhibit variation beyond what can be explained by homophily. We call this excess variation monophily (for `love of one ) to describe the presence of individuals with extreme preferences for a particular attribute possibly unrelated to their own attribute. Monophily can result in a counter-intuitive ``two-hop (friend-of-friend) correlation between attributes of nodes, which has required re-thinking the local ``one-hop nature of network modeling and inference. The proposal aims to extend these insights into diverse subfields of network science. The methods proposed in this work have the potentially to greatly advance the foundations of networks science and the applied practice of graph mining and cyberanalytics. The PI (Johan Ugander) will be responsible for overseeing all aspects of this project at Stanford, including research, publication, and software development. All publications will be accompanied by open source software implementations of the key contributions.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 14, 2019
- Source ID
- W911NF1910031
Entities
People
- Johan Ugander
Organizations
- Army Contracting Command
- Stanford University
- United States Army