Tuesday, February 28, 2012 - 4:15pm - 5:30pm
- Poster - Social network analysis reveals colony organization in an ant
Danielle Mersch (Université de Lausanne)
Ant colonies are known for their complex and efficient social organization that completely lacks hierarchical structure. However, little is known about how workers within a colony organize themselves. In this study, we tracked the position and orientation of all individually marked ants in six colonies for 41 days. We inferred interactions between ants by modeling each ant as a trapezoid and testing whether the head end on one ant was in the trapezoid of the other. For each day and each colony, we built a network by cumulating all interactions. To test whether the network had a community structure, we assigned each ant to a cluster with the infomap algorithm , and then derived the group membership for each ant. Workers were organized in three distinct but interconnected groups that persist over at least 10 days. Each group specialized in a different behavioral task: nursing, nest patrolling and rubbish collection, foraging. Spatial heatmaps further showed that each group occupied a specific area in the nest, and that workers of the same groups interacted preferentially in their group specific area, whereas workers of different groups interacted elsewhere in the nest. Analysis of the evolution of worker group membership showed that workers have a preferred behavioral trajectory, moving from nursing to nest patrolling, and from nest patrolling to foraging. Our results show that workers in ant colonies are organized in functional groups each of which specializes in a given task, which suggests that division of labor is embodied in the social organization of a colony. We further show that groups occupy different spatial positions suggesting that spatial structure is an important component in colony organization. Together these results emphasize that ant colonies rely on strong underlying organizational principles, and that the social structure is a relevant and defining characteristic of ant colonies.
 Rosvall M. & Bergstrom C.T. (2008) Maps of randoms walks on complex networks reveal community structure. PNAS 105: 1118-1123
- Poster - Event Detection in Social Streams
Karthik Subbian (University of Minnesota, Twin Cities)
Social networks generate a large amount of text content over
time because of continuous interaction between participants. The
mining of such social streams is more challenging than traditional
text streams, because of the presence of both text content and
implicit network structure within the stream. The problem of event
detection is also closely related to clustering, because the events
can only be inferred from aggregate trend changes in the stream. In
this paper, we will study the two related problems of clustering and
event detection in social streams. We will study both the supervised
and unsupervised case for the event detection problem. We present
experimental results illustrating the effectiveness of incorporating
network structure in event discovery over purely content-based
- Poster - Learning to agree: hypothesis testing for biased network data
John Pinney (Imperial College London)
Systems biology is often concerned with the representation of cellular interactions and their associated biological systems as networks. Substantial amounts of high quality interaction data are now available, obtained from large-scale (high-throughput) experiments or curated from multiple small-scale experiments published in the scientific literature.
Network analyses rely upon accurate data to draw robust and meaningful conclusions: one simple example is the relationship between the degree of a protein and its physical, functional or evolutionary properties. Given the targeted nature of the majority of the available interaction data, it is clearly feasible that biases in these networks may result in erroneous conclusions. Indeed, protein interaction data sets from different sources return seemingly statistically significant but mutually incompatible results for many hypothesis tests.
To compensate for this effect, we have devised a novel method to evaluate and correct for ascertainment biases arising from various sources. Application of this method to multiple protein interaction networks leads to an increase in agreement between data sources and hence more robust biological conclusions. We envisage this approach being of use in a wide range of network analyses where bias is known to be a confounding factor.
- Poster - GeneMANIA: Intelligent gene function prediction and interactive network visualization
Gary Bader (University of Toronto)
GeneMANIA (http://www.genemania.org) is a flexible tool providing researchers with a single point of access for generating hypotheses about gene function by querying large‐scale publicly available genomics and proteomics datasets. GeneMANIA finds other genes that are related to a set of input genes, using a very large set of functional association data. Association data include protein and genetic interactions, pathways, co-expression, co-localization and protein domain similarity. You can use GeneMANIA to find new members of a pathway or complex, find additional genes you may have missed in your screen or find new genes with a specific function, such as protein kinases. Your question is defined by the set of genes you input. If members of your gene list make up a protein complex, GeneMANIA will return more potential members of the protein complex. If you enter a gene list, GeneMANIA will return connections between your genes, within the selected datasets.
- Poster - Uncovering the Temporal Dynamics of Diffusion Networks
Manuel Gomez Rodriguez (Max-Planck-Institut für Intelligente Systeme)
Time plays an essential role in the diffusion of information,
influence and disease over networks. In many cases we only observe
when a node copies information, makes a decision or becomes infected
-- but the connectivity, transmission rates between nodes and
transmission sources are unknown. Inferring the underlying dynamics is
of outstanding interest since it enables forecasting, influencing and
retarding infections, broadly construed.
To this end, we model diffusion processes as discrete networks of
continuous temporal processes occurring at different rates. Given
cascade data -- observed infection times of nodes -- we infer the
edges of the global diffusion network and estimate the transmission
rates of each edge that best explain the observed data. The
optimization problem is convex. The model naturally (without
heuristics) imposes sparse solutions and requires no parameter tuning.
The problem decouples into a collection of independent smaller
problems, thus scaling easily to networks on the order of hundreds of
thousands of nodes. Experiments on real and synthetic data show that
our algorithm both recovers the edges of diffusion networks and
accurately estimates their transmission rates from cascade data.
- Semi-supervised Dictionary Learning for Network-wide Link Load Prediction
Pedro Forero (University of Minnesota, Twin Cities)
Being a primary indicator of network health, link traffic volumes are used in multiple network management and diagnostic tasks. Although link volumes are available using off-the-shelf tools, the corresponding measurement records typically contain errors and missing data. To overcome these challenges, the present paper develops a link traffic prediction algorithm that fills missing entries and removes noise from the observed entries in an online fashion. The algorithm not only exploits topological knowledge of the network, but also learns from the available historical link traffic data. During its operational phase, the novel algorithm relies on a sparse signal representation for the link counts over a data-driven dictionary. Prediction of link counts follows after solving an $\ell_1$-regularized least-squares problem. Prior to operation however, a dictionary is trained so that it captures all the necessary information from the historical data, allows for a sparse representation, and is aware of the network topology. This is accomplished through a novel semi-supervised dictionary learning scheme which works even when the training data has missing entries. Numerical tests on data from the Internet2 archive corroborate the proposed algorithms.
- Poster - Dynamic Network Kriging
Ketan Rajawat (University of Minnesota, Twin Cities)
We consider the problem of monitoring, tracking and predicting network-wide path performance metrics such as end-to-end delay and loss rates in IP networks. Classical prediction tools do not take full advantage of the inherent spatio-temporal correlations that performance metrics manifest in practice. Tapping into the spatio-temporal kriging theory, we put forth a dynamic network kriging approach with real-time network-wide prediction capabilities based on measurements acquired for a small subset of network paths. Going well beyond state-of-the-art methods, the proposed model captures not only spatio-temporal correlations but also unmodeled dynamics due to, e.g., congested routers. The framework also enables choosing optimal measurement locations in an online fashion.
- Poster - Machine learning approaches for inferring plant immune signaling networks
Yungil Kim (University of Minnesota, Twin Cities)
A major part of plant defense against pathogens consists of an inducible system, in which recognition mechanisms detect pathogens, multiple signaling pathways transduce information, and plant defense is activated. In the model plant, Arabidopsis thaliana, there are three major input signals that activate four critical pathways to mount a defense to a pathogen. These pathways interact in a sophisticated manner, forming a complex signaling network. Our collaborators in Fumiaki Katagiri’s lab (U. of MN, Plant Biology) collected quantitative measurements of both gene expression at multiple time points as well as plant resistance to two different bacterial pathogens in several well-defined genetic mutants with specific defects in these pathways. In total, these data cover all sixteen possible combinatorial perturbations (gene deletions) of the four pathways of interest with each of the three possible input signals (treatments) for both pathogen infections. Based on these data, we successfully built a predictive model of the plant immune system that accurately reflects systematic responses to genetic perturbation and dynamic expression of its components.
- Poster - Network topology complements sequence: insights into human disease
Vuk Janjic (Imperial College London)
Individual genes bear little significance when isolated from their networks of interaction; hence the importance
of networks in modelling biological behaviour of gene products. We devise sophisticated
network alignment algorithms and apply them to biological networks of different species. Our algorithms uncover
huge topologically and functionally conserved regions even across species as
diverse as baker’s yeast and humans. Also, we successfully use network topology to differentiate between cancer and non-cancer
genes: we apply our topological methods to predict novel regulators of melanogenesis from protein-protein interaction (PPI)
networks of human cells and our predictions are phenotypically validated. Also, we begun to apply topology to detect homology, as well
as to determine how “dominating” aging or disease proteins are in the PPI network. Thus, network biology is an
invaluable source of biological information that undeniably has a potential to impact therapeutics and health care.
- Poster - Methods for Scalable Analysis of Temporal Network Data with
Vertex and Edge Dynamics
Zack Almquist (University of California)
Network dynamics may be viewed as a process of change in the edge
structure of a network, in the vertex set on which edges are defined,
or in both simultaneously. Though early studies of such processes were
primarily descriptive, recent work on this topic has increasingly
turned to formal statistical models. While showing great promise, many
of these modern dynamic models are computationally intensive and scale
very poorly in the size of the network under study and/or the number
of time points considered. Likewise, currently employed models focus
on edge dynamics, with little support for endogenously changing vertex
sets. Here, we show how an existing approach based on logistic
network regression can be extended to serve as a highly scalable
framework for modeling large networks with dynamic vertex sets. We
place this approach within a general dynamic exponential family (ERGM)
context, clarifying the assumptions underlying the framework (and
providing a clear path for extensions), and show how model assessment
methods for cross-sectional networks can be extended to the dynamic
case. To illustrate this method and accompanying adequacy assessment
we apply dynamic logistic network regression on first a classic data
set involving interactions among windsurfers on a California beach,
and second on a large network of organizational collaboration
occurring during the 2005 Hurricane Katrina disaster. The
organizational collaboration network allows us to demonstrate that
network vital dynamics are a key component of network evolution, and
larger, system-level factors (e.g., geography) are critical for
accurate prediction of network structure. Implications of these
findings on the greater network literature and future of data
collection are also discussed.
- Poster - Optimal Bayesian Inference In Social Networks
Manisha Bhardwaj (University of Houston)
Understanding how information propagates in a social network has been an active area of research over the last few decades. Early mathematical models were developed to understand how consensus is reached in simple networks. With the advent of social media which can connect millions of users, there has been resurgent interest in the problem. For instance, Frongillo et al., have examined how individuals in a social network can optimally exchange information about a dynamically changing parameter.
It is frequently assumed that discussion improves the decisions of individuals. However, such exchanges can correlate the beliefs of different individuals in a social network, and negatively impact a collective decision. Indeed, even individual decisions may suffer after an exchange of information. Bahrami group  observed that discussion can have a positive impact on decision making only if the observers have approximately equal competence. Redundancies are likely to be present in social networks, specifically in large networks with many edges. In such situations, how should observers integrate incoming information to achieve the best possible estimate and reach the best decisions?
We study a simple graphical Bayesian model of interacting observers who try to estimate a value in the outside world with their own observations and their local neighborhood information. We study in detail feed forward and recurrent network and establish a general result on how the individuals can achieve optimal Bayesian inference in the presence of redundancies. Such redundancies impact the performance of even optimal observers. We also consider the propagation of individuals biases and priors in making decisions and show how certain network structures impact an individuals’ maximum-likelihood (ML) estimate.
 B. Bahrami, K. Olsen, P. E.Latham, A. Roepstorff, G. Rees, C.D.Frith, Optimally Inter- acting Minds. Science Vol 329, 2010
 R.M.Frongillo, G.S.Schoenebeck, O.Tamuz. Social Learning in a Changing World arXiv:1109.5482v1, cs.SI, 2011
- Poster - The effects of colony size on interaction networks and division of labor in ants
Nathalie Stroeymeyt (Université de Lausanne)
Group size is a fundamental determinant of the organization and functioning of many collective processes in humans, animals and in artificial systems. Human companies, animal societies and computer networks thus face similar challenges when they fluctuate in size, to maintain effective functioning and ensure ongoing performance of the system, i.e. to sustain system stability (homeostasis). In certain ant species, colonies undergo an annual cycle of fragmentation into several nests in early spring (fission), followed by coalescence into a single nest at the end of summer (fusion), a phenomenon known as “seasonal polydomy”. Using a cutting-edge system that allows the automated tracking of several hundreds of individuals simultaneously for extensive periods of time, we propose to investigate how abrupt variation in nest size caused by fission and fusion events affects social organization in the seasonally polydomous ant Camponotus kiusiuensis. We will focus especially on division of labor among workers and on the structure, functioning and resilience of interaction networks in the colony. We also aim to identify the behavioral strategies allowing the maintenance of homeostasis at both the individual and the collective levels. We present an overview of the project and the main expected challenges.
- Poster - Map of Jazz: Artists’ Collaborations Over Time
Carl Kingsford (University of Maryland)
We present an interactive Web-based tool for the exploration of the collaborations of jazz musicians. The website allows users to see who collaborated with a particular musician during any desired time range and allows users to interactively follow chains of collaborations. The display positions collaborators according an influence function that depends both the number of recorded collaborations and the time intervals between them. The user can dynamically change the timescale and range on which this influence is calculated.
- Poster - Triple-mutant interactions in yeast paralogs
reveal previously hidden common function
Benjamin VanderSluis (University of Minnesota, Twin Cities)
Duplicate genes have been shown to exhibit
fewer genetic interactions (digenic) than
expected. This may be due to pair level
buffering effects. Essentially, one copy of the
pair can substitute for the other as a backup
when the other is deleted. Any function that is
buffered in this way will not show any genetic
interactions unless we knock out the backup
as well. To this end we have constructed SGA
query strains which are missing not one but
two genes. Gene pairs selected are paralogs
(duplicate copies) primarily from the Whole
Genome Duplication even thought to have
taken place in yeast ~ 100 MYA.
- Poster- Spatial Stochastic Simulations for Diffusion-Controlled Reaction Network in Crowded Cytoplasm
Adwait Walimbe (University of Minnesota, Twin Cities)
Models based on mass action kinetics are widely used but, in a strict sense, limited to biochemical reactions in dilute solution, where reactants freely diffuse and react in an unobstructed space. Modeling diffusion-reaction kinetics in a crowded environment, such as the cytoplasm, requires fractal-like ordinary differential equation (ODE) models. In particular, generalized mass action systems have been proposed and successfully validated for this purpose. In this work, we establish two novel, particle-based methods to simulate biochemical diffusion-reaction systems within crowded environments. We distinguish two conceptually different situations.
- Poster - Stochastic 3-D Simulations for Diffusion-Controlled Reactions with Concentration-Dependent Kinetic Rates in Crowded Environments
Jialiang Wu (Georgia Institute of Technology)
Models based on mass action kinetics are widely used but, in a strict sense, limited to biochemical reactions in dilute solution, where reactants freely diffuse and react in an unobstructed space. Modeling diffusion-reaction kinetics in a crowded environment, such as the cytoplasm, requires fractal-like ordinary differential equation (ODE) models. In particular, generalized mass action systems have been proposed and successfully validated for this purpose. In this paper, we establish two novel, particle-based methods to simulate biochemical diffusion-reaction systems within crowded environments. We distinguish two conceptually different situations. In the first, the ODEs capture a microscopic “reaction-only” mechanism, while diffusion is modeled separately. In the second case, the ODEs model the combined effects of both reaction and diffusion. This distinction consequently leads to two simulation methods that both effectively simulate and quantify crowding effects, including reduced reaction volumes, reduced diffusion rates, and reduced accessibility between potentially reacting particles. The proposed methods account for fractal-like kinetics, where the reaction rate depends on the local concentrations of the molecules undergoing the reaction. Rooted in an agent based modeling framework, this aspect of the methods offers the capacity to address sophisticated intracellular spatial effects, such as macromolecular crowding.
- Poster - Systems-level insights from modular decomposition of the yeast genetic interaction network
Jeremy Bellay (University of Maryland)
Genetic interactions provide a powerful perspective into biological processes that is fundamentally different from other high-throughput genome-wide studies. Recently, Synthetic Genetic Array technology was used to produce the first genome scale map of digenic genetic interactions, which covered ~5.4 million genetic interactions or about ~30% of all possible gene pairs in yeast. This provides a first opportunity for a global, unbiased assessment of the structure of the genetic interaction network and the relationship between this structure and individual gene function. We developed a data mining approach based on association rule learning to exhaustively discover all block structures within the yeast genetic interaction network, producing a complete modular decomposition of the network. We find that genetic interaction hubs can be clearly differentiated into distinct classes of hubs based on their modular structure. Moreover, module membership provides a specific and unbiased assessment of the prevalence of multi-functionality among genes: we find that genes participate in far more functions or contexts than was previously appreciated. In addition, we find that genetic interactions contained within structured modules exhibit strikingly different functional properties relative to isolated interactions, providing insight into the evolution and functional divergence of duplicate genes. Finally, we used module membership to explore the evolution of module redundancy within the cell and find that while there is often age coherency within modules, modules that buffer each other often arise at different times indicating that much cellular redundancy is a product of subsequent diversification.
- Poster - Rules governing genetic interaction network topology are conserved in two distantly related yeast species
Elizabeth Koch (University of Minnesota, Twin Cities)
Physiological and evolutionary properties of genes have been shown to correlate with gene connectivity in the genetic interaction network of Saccharomyces cerevisiae. We extend this observation by showing that the same predictive relationships exist in Schizosaccharomyces pombe, an evolutionarily distant fission yeast. For each of these two yeast species, we build models that successfully predict genetic interaction degree from the gene properties, allowing the identification of expected highly connected genes. Consistency of rules in distant species allows a model trained on one of the yeast species and applied to the other to make predictions with accuracy as high as that of within-species predictions. We compare predicted genetic interaction degrees of S. pombe genes to the degrees of orthologous S. cerevisiae genes. Our approach demonstrates that knowledge of the widely-studied species S. cerevisiae can be used to direct the investigation of genetic interactions in S. pombe and even other distantly related species.