NETWORK SCIENCE
WORKSHOP

Organized by Professor R. Ravi, Carnegie Bosch Professor at the
Tepper School of Business

MONDAY, OCTOBER 19, 2009
9:00 AM - 5:00 PM
152 POSNER HALL
TEPPER SCHOOL OF BUSINESS

Welcome and Introduction - Ms. Sylvia Vogt, President of CBI and Professor R. Ravi, Carnegie Bosch Professor

The purpose of the workshop is to forge new connections across the various disciplines that use network models and brainstorm new topics for interdisciplinary research in this area. The common theme underlying the talks is to explore the ways in which network models and optimization have played an important role in understanding social, economic, information and scientific phenomena.

speaker abstracts

bren meeder
Understanding Information Flow with the Twitter Social Network
(PDF) (Video)

Questions about information flow and disease spread are central in current network research. One focus in this area is to find models that accurately predict how a message or disease is transferred within some community. Another area of interest is to look at combinatorial optimizations over these models. For example, we might want to know to which k people should a message be initially told to so as to maximize the number of people who hear the message through word-of-mouth spread. Our work focuses on crawling the Twitter online social network in an effort to better understand how information spreads. By observing user actions such as "retweeting," "@-replying," and the posting of shortened URLs, we are able to witness and measure message propagation. This talk focuses on our analysis of how well previously proposed models such as the probabilistic cascade and inear-threshold models capture information spread in the Twitter network. Top

alan frieze
Random Graph Models of Networks
(PDF) (Video)

Real world networks appear to grow randomly and so it is natural to model them as random graphs. The classical models of Erdos and Renyi show some inconsistencies with observations. Attempts have been made to construct models which better fit observation. I will survey some of these models. Top

Stephen Fienberg
Statistical Approaches to Network Modeling and Analysis
(PDF) (Video)

Each field that intersects with the study of networks has a different style and approach to the problem and to empirical work. In this talk I will briefly characterize some of these and explain what makes the statistical perspective unique, using some of my recent research work as illustrations. I will also briefly illustrate some of the challenges that the statistical perspective poses for ongoing research on networks. Top

Russell Schwartz
Fast Phylogenetic Inference from Genetic Variation Data
(PDF) (Video)

This talk will describe work on the inference of evolutionary trees from genetic data cataloging variations among individuals within a species. The problem of intraspecies phylogenetics has a long history in the computational biology literature, but has gained new significance in recent years as technological advances have made it possible to gather vastly larger datasets than had previously been feasible. It is commonly posed as a problem of minimum cost Steiner tree inference, in which we seek to explain ancestry among a set of observed individuals with as few mutations as possible. We will examine new methods we have developed for the Steiner tree problem, which use integer linear programming formulations to solve for harder problem instances and larger numbers of genetic regions than was possible with prior methods. These methods have made it possible to perform phylogenetic inferences of local genetic regions on a genome-wide scale. We will conclude by surveying some applications that are enabled by this new ability to perform phylogenetic inference on genomic scales, including work in analyzing the history of human populations and statistically identifying genetic regions correlated with disease states. Top

David Krackhardt
Organizational Science from a Network Perspective
(Video)

Organizations are complex social systems of interdependencies. The network paradigm has opened many doors to understanding organizations; it has allowed us to both ask and answer questions that were heretofore impossible (or at least ignored). In this overview, I will offer a structure for characterizing organizational analysis that highlights these paradigmatic advantages. I will demonstrate these features with empirical examples that draw on graph theoretic primitives and compound relations to integrate organizational networks, task designs, and overall performance in the firm. Top

Kathleen Carley
Dynamic Network Analysis: Management and Intervention
(PDF) (Video)

Social networks exist in a dynamic and evolving ecology of networks connecting the who, what, how, why, and where. By considering this ecology, it is possible to not only identify key communication nodes and assess change, but to identify emergent leaders and factors influencing performance such as congruence. These ideas are illustrated with examples from various management, law enforcement, and political elite structures. Top

Eric Xing
Time Varying Networks: Reverse Engineering and Analyzing Rewiring Social and Genetic Interactions
(Video)

A plausible representation of the relational information among entities in dynamic systems such as a social community or a living cell is a stochastic network that is topologically rewiring and semantically evolving over time. While there is a rich literature in modeling static or temporally invariant networks, until recently, little has been done toward modeling the dynamic processes underlying rewiring networks, and on recovering such networks when they are not observable. In this talk, I will present a new formalism for modeling network evolution over time based on temporal exponential random graphs, and several new algorithms for estimating the structure of time-evolving probabilistic graphical models underlying nonstationary time-series of nodal attributes. I will show some promising results on recovering the latent sequence of evolving social networks in the US Senate based on it voting history, and the gene network of more than 4000 genes during the life cycle of Drosophila melanogaster from microarray time course, at a time resolution only limited by sample frequency. I will also sketch some theoretical results on the asymptotic sparsistency of the proposed methods, which differ significantly from traditional sparsistency analysis of static structure estimation based on iid samples because of the temporal relatedness of samples. If time permits, I will also report a hierarchical Bayesian model for estimating and visualizing the trajectories of latent mixed-membership nodal states in the recovered evolving networks. Top

Ziv Bar-Joseph
Cross Species Analysis of Molecular Interaction Networks
(PDF) (Video)

Recent advances in genomics are enabling researchers to accumulate large datasets in multiple species. These include sequence data as well as functional information such as the level of gene expression and various types of interactions. However, while the sequence and function of genes are highly conserved between close species, expression and interaction data appears to be much less conserved. In this talk I will present methods that utilize graphical models for integrating sequence and functional data from multiple species. We used these methods to study two biological systems: cell cycle and immune response. As we show, using these methods we can improve on the sets of genes recovered for each species independently. More importantly, these methods allow us to recover the core set of genes for specific biological systems indicating that integrating network data across species can overcome problems associated with the analysis of genomics data. Top