Invited Speakers

Austin Benson, Cornell - Choosing to grow a graph
We provide a framework for modeling social network growth through the lens of discrete choice and random utility theory, in which each new edge is viewed as a choice made by a node to connect to another node, based on (generic) features of the other nodes available to make a connection. This perspective on network formation unifies existing models such as preferential attachment, triadic closure, and node fitness, which are all special cases. When sequential information about the arrival of edges in a graph are available, our framework provides a flexible means for conceptualizing, estimating, and comparing models. Moreover, mixtures of existing models can be estimated by adapting known expectation-maximization algorithms, and the significance of node features can be evaluated in a statistically rigorous manner. We demonstrate the flexibility of our framework through examples that show how to separate the effects of preferential attachment and triadic closure and also find evidence for an increased role of degree when accounting for age in a large citation network.

Sinead Williamson, UT Austin - Random clique covers for graphs with local density and global sparsity
Large real-world graphs tend to be sparse, but they often contain densely connected subgraphs and exhibit high clustering coefficients. While recent random graph models can capture this sparsity, they ignore the local density, or vice versa. We develop a Bayesian nonparametric graph model based on distributions over edge clique covers, and show that this model can capture power law degree distribution, global sparsity and local density. This distribution can be used directly as a prior on observed graphs, or as part of a hierarchical Bayesian model for inferring latent graph structures. This is joint work with Mauricio Tec

Tamara Broderick, MIT - Edge-exchangeable graphs and sparsity
Many popular network models rely on the assumption of (vertex) exchangeability, in which the distribution of the graph is invariant to relabelings of the vertices. However, the Aldous-Hoover theorem guarantees that these graphs are dense or empty with probability one, whereas many real-world graphs are sparse. We present an alternative notion of exchangeability for random graphs, which we call edge exchangeability, in which the distribution of a graph sequence is invariant to the order of the edges. We demonstrate that a wide range of edge-exchangeable models, unlike any models that are traditionally vertex-exchangeable, can exhibit sparsity. To develop characterization theorems for edge-exchangeable graphs analogous to the powerful Aldous-Hoover theorem for vertex-exchangeable graphs, we turn to a seemingly different combinatorial problem: clustering. Clustering involves placing entities into mutually exclusive categories. A "feature allocation" relaxes the requirement of mutual exclusivity and allows entities to belong simultaneously to multiple categories. In the case of clustering the class of probability distributions over exchangeable partitions of a dataset has been characterized (via "exchangeable partition probability functions” and the "Kingman paintbox"). These characterizations support an elegant nonparametric Bayesian framework for clustering in which the number of clusters is not assumed to be known a priori. We show how these characterizations can be extended to feature allocations and, from there, to edge-exchangeable graphs.

Elizabeth Hobson, Santa Fe Institute - The evolution of decision-making, social cognition, and complex sociality
In many social species across both humans and other animals, individuals both create their social worlds through interaction decisions and are then subject to and constrained by these social constructs, which can affect an individual’s future actions. Understanding how much individuals know about their social worlds is critical in understanding these potential feedbacks. However, it is difficult to determine how much information individuals have about the social structures and networks of relationships in which they live. I present new network-based methods that make detecting the presence and use of social information more tractable and serve as social assays to detect novel structure in social interactions. My work with a highly social species of parrot shows that individuals quickly gain and strategically use social information in conflicts, particularly information about relative rank in dominance hierarchies. I apply a similar approach to historical aggression data from 85 species to measure new axes of conflict and assay the social strategies used by groups. These measures, and a taxonomically broad approach, provide new opportunities to investigate the effect of social information on individual behavior within conflict, and has the potential to provide rigorous evidence for the evolutionary patterns underlying social cognition.