Carter Butts, UC Irvine, Mathematical Sociology

Title Bounding Complex Network Models with Bernoulli Graphs

Abstract

Complex network models (i.e., stochastic models for networks incorporating heterogeneity and/or dependence among edges) are increasingly widely used in the study of social and other networks, but few techniques other than simulation have been available for studying their behavior. Random graphs with independent edges (i.e., the Bernoulli graphs), on the other hand, are well-studied, and a large literature exists regarding their properties. Here, I demonstrate a method for leveraging this knowledge by constructing families of Bernoulli graphs that bound the behavior of general exponential-family random graphs in a well-defined sense. By studying the behavior of these Bernoulli graph bounds, one can thus constrain the properties of a given random graph. Several applications of this method to the study of complex network models are discussed, including degeneracy identification and robustness testing.

Bio

Carter is an associate professor in the Department of Sociology and the Institute for Mathematical Behavioral Sciences at the University of California, Irvine. Professor Butts joined the UCI faculty in 2002, after receiving his Ph.D. from the Department of Social and Decision Sciences at Carnegie Mellon University. His work focuses on the structure of spatially embedded large-scale interpersonal networks; models for informant accuracy, network inference, and graph comparison; graphical representations of life history data; and models for human behavior in strategic situations.

Jonathan Chang, Facebook

Title Facebook: Challenges for 2011

Abstract

This past year Facebook launched several new products such as Questions and Places, and revamped several products such as Groups and Photos. Each of these products offer rich, structured data to supplement the existing friendship and content graphs. With these new data come new opportunities for machine learning and data analysis --- underpinning the success of these products is our ability to answer questions such as "Does this user provide high-quality answers to questions?" and "Are these places socially interesting to users?" In this talk, I will describe these new data and some approaches to answering these questions. I will also talk about many open problems surrounding these products which may lead to further improvements.

Bio

Jonathan received his B.S. from the California Institute of Technology and did his graduate work at Princeton University. He is currently a Data Scientist at Facebook.

Aaron Clauset, University of Colorado Boulder, Computer Science, Complex Systems (accepted)

Title The Trouble with Community Detection

Abstract

Modular structures in complex networks can be extremely important for understanding the functional, dynamical, and evolutionary properties of networks, and are widely believed to be ubiquitous in complex social, biological and technological networks. Most of the empirical evidence in support of this modular hypothesis, however, is indirect and derived from "community" or module detection algorithms. In general, these techniques do not yield unambiguous results and their objective performance in scientific contexts is not well characterized. In this talk, I'll discuss some of the problems with the existing popular community detection frameworks and show that even in simple contexts they can produce highly counter-intuitive results. A consequence is that probably none of the existing claims of modular structure in, for example, biological networks should be trusted and there remains a great deal of work to be done to test the modular-organization hypothesis in such contexts. I'll conclude with some forward-looking thoughts about the general problem of identifying network modules from connectivity data alone, and the likelihood of circumventing these problems using, for instance, notions of functionality.

Bio

Aaron is an Assistant Professor of Computer Science at the University of Colorado at Boulder and a fellow in the Colorado Initiative in Molecular Biotechnology. He was previously an Omidyar Fellow at the Santa Fe Institute. Currently, he is working on large-scale organizational patterns of complex social, biological and technological networks; and the mathematical processes that shape the dynamics of violent human conflicts, such as modern terrorism and warfare among other things.

Lise Getoor, University of Maryland, Computer Science

Title Collective Graph Identification

Abstract

The importance of network analysis is growing across many domains, and is fundamental in understanding online social interactions, biological processes, communication, ecological, financial, and transportation networks, and many more. In most of these domains, the networks of interest are not directly observed, but must be inferred from noisy and incomplete data, data that was often generated for purposes other than scientific analysis. In this talk, I will describe graph identification, the process of inferring the hidden network from noisy observational data. In particular, I will describe a collective approach to graph identification, which interleaves the necessary steps in the reconstruction of the network.
Joint work with Galileo Namata.

Bio

Lise is an associate professor in the Computer Science Department at the University of Maryland, College Park. She received her PhD from Stanford University in 2001. Her current work includes research on link mining, statistical relational learning and representing uncertainty in structured and semi-structured data. She has most recently has significantly contributed to social network analysis and visual analytics.

Sayan Mukherjee, Duke University, Statistics

Title Geometry based graph and network models

Abstract

We will discuss two graph or network models based on geometric
ideas. The first model was motivated by problems in computational
molecular biology. The objective is to infer conditional dependece
structure between gene products or molecular pathways that are
predictive or explain variation in disease phenotypes. This
objective will be related to inference of a geometric
quantity, the gradient of a regression function. An application
to cancer progression will be used to illustrate the ideas.
The second model involves the inference of higher-order
dependence structure in graphical models. Ideas from
computational geometry/topology and spatial point processes
are integrated to achieve this, the inference is formulated in
a Bayesian paradigm.

Bio

Sayan is an assistant professor in the department of statistical science and is a member of the Institute for Genome Sciences & Policy (IGSP). He received a PhD from the Massachusetts Institute of Technology in 2001. Professor Mukherjee is involved in the development and analysis of probabilistic models and algorithms for inference of structure in high-dimensional data. Probabilistic models of genomic data to both predict complex phenotypes as well as elucidate biological function.