Abstract: The attempt to construct a theory of gravity which is consistent with quantum physics has led physicists to believe that space and time itself possesses a sort of atomic structure at very small length scales, analogous to the atoms of ordinary matter. Such a structure can be modeled by a collection of 'spacetime atoms' which are connected by causal links. I will describe gravity in terms of such a causal network, called a Causal Set, and show how one can construct a dynamical law for the network's growth in terms of two fundamental physical principles. The resulting dynamical law produces causal networks with an intriguing similarity to the universe in which we live.

Abstract: In the first months of 2011, Internet communications were disrupted in several North African countries in response to civilian protests and threats of civil war. In this work we analyze episodes of these disruptions in two countries: Egypt and Libya. Our analysis relies on multiple sources of large-scale data already available to academic researchers: BGP interdomain routing control plane data; unsolicited data plane traffic to unassigned address space; active macroscopic traceroute measurements; RIR delegation files; and MaxMind's geolocation database. We used the latter two data sets to determine which IP address ranges were allocated to entities within each country, and then mapped these IP addresses of interest to BGP-announced address ranges (prefixes) and origin ASes using publicly available BGP data repositories in the U.S. and Europe. We then analyzed observable activity related to these sets of prefixes and ASes throughout the censorship episodes. Using both control plane and data plane data sets in combination allowed us to narrow down which forms of Internet access disruption were implemented in a given region over time. Among other insights, we detected what we believe were Libya's attempts to test firewall-based blocking before they executed more aggressive BGP-based disconnection. Our methodology could be used, and automated, to detect outages or similar macroscopically disruptive events in other geographic or topological regions.

Abstract: In this talk we argue for an algorithmic approach to understanding the collective dynamics of human behavior. We consider the distributed game of pairing up individuals connected over a network of social contacts. Our experimental set-up is simple. Individuals are represented by nodes of a network with edges representing potential matches. They are connected over a virtual network and interact with their neighbors through a computer interface. They are given only local information about the network, and can only communicate with their immediate neighbors. They have the shared goal of maximizing the total number of matches in the network. We have conducted over 200 experiments with human subjects on a pool of over 50 networks with up to 24 nodes each. From a first set of experiments we identify a behavioral principle called ``prudence'' and develop an algorithmic model to analyze its properties mathematically and by simulations, and finally validate the model with additional human subject experiments for various network sizes and topologies. We show that the human subjects largely abide by prudence and their collective behavior is closely tracked by the predictions of the mathematical model. Hence, we argue that 1) observational data collected from experiments on human subjects interacting using a simple computer interface can be useful to uncover basic behavioral properties such as prudence, that may not be apparent from the more classic approach of off-line surveys; and 2) algorithmic modeling and the mathematical analysis of algorithms can be a useful tool to systematically predict aggregate social behavior and the dynamics of coordination over social networks. Possible extensions of this work to hybrid computer-human networks, preferential goals, and incentive mechanisms will be discussed.

Abstract: Planning, scheduling, and resource allocation are examples of real-world situations in which humans must solve complex combinatorial problems. It is often the case that no global entity is present, and a network of inter-personal influences is the conduit for the solution. In these cases, humans must solve combinatorial problems in a distributed fashion. We call these coordination problems. We know from computer science research that distributed algorithms sometimes use considerable information about the past to reduce the time to coordination. Furthermore, we know that a history of inter-personal interactions can create strong behavioral biases in humans, potentially influencing their behavior. We want to know whether humans use this historical information in solving coordination problems, and if they do so to their advantage. Using graph 2-coloring as a simple representative of coordination problems, we perform human subject experiments and agent-based simulations designed to elucidate the role of historical information in human coordination tasks. We report on the game dynamics and average completion times for these experiments.

Abstract: Many phenomena in social science and in biology are represented naturally as graphs or networks. Typically, the relevant networks are only known incompletely, so a fundamental research question is how to infer missing information in a network, given all available known information. In this talk I will present a general method for learning from known nodes and edges in a graph to predict labels for other nodes and edges. The new method induces latent features to represent implicit properties of nodes, and combines the latent features with any available explicit features to make accurate predictions. The method is an extension and combination of matrix factorization and a log-linear model. For link prediction, the new method achieves state of the art accuracy over a wider range of datasets, from biology and from social science, than any previous method. (Joint work with Aditya Menon.)

Abstract: At its highest level the Internet can be viewed as a collection of Autonomous Systems (AS). Except for a few special cases, each AS is a fully connected set of addresses. ASes announce their address sets to their neighbors, which in turn pass these on to a subset of their neighbors. These selective announcement policies reflect the hierarchical structure of the Internet and prescribes the possible set of Internet routes. For many years CAIDA has released an AS Core graph which reflects this structure in an easy to understand visualization. This talk is an introduction to this visualization, the data sources used in its construction, where to get that data, how to use them, and some general insights that can been inferred from the graph.

Abstract: Many social, biological and technological systems can be conveniently represented as bipartite networks, consisting of two disjoint sets of elements along with edges connecting only elements from different sets. Many of such systems are characterized by high values of bipartite clustering coefficient. We also find that pairs of elements in these bipartite systems tend to have many common neighbors. We present a natural interpretation of these observations. We suggest that elements of the above bipartite systems exist in underlying metric spaces, such that the observed high clustering is a topological reflection of the triangle inequality, the key property of metric space. We propose a simple stochastic mechanism of formation of bipartite networks embedded in metric spaces. We prove that this mechanism is able to reproduce the observed topological properties of bipartite networks. We also discuss the possibility of constructive embedding of real bipartite systems into metric spaces. In my talk I will overview the concept of hidden metric spaces with respect to both unipartite and bipartite networks. I will also discuss existing methods used to infer hidden metric spaces in real networks and possible applications for bipartite networks.

Abstract: CANCELLED

Abstract: The abstract is under embargo....

Abstract: A growing literature suggests that network design affects our ability to solve collective problems. Recent experimental studies in the social and computer sciences claim that higher network connectivity helps groups overcome coordination problems. However, this is not always the case; we demonstrate that networks can have both constraining edges that inhibit coordination and redundant edges that facilitate it. Though constraining edges increase communication, they also shrink the solution space of the coordination problem, stifling collective action. By contrast, redundant edges that do not impose additional constraints aid coordination, as described in previous work. We explain why the negative effect of constraint trumps the positive effect of communication by analyzing coordination games as a special case of widely studied constraint satisfaction problems. The results show that the complexity of the coordination problem must be a central concern when designing efficient networks.

Abstract: The Internet consists of thousands of autonomous systems (ASes) that voluntarily form bilateral interconnection agreements to provide end-to-end reachability. Despite much recent interest in the economic aspects of the Internet, such as network interconnection (peering) and pricing, there is a persistent disconnect between economic models and actual operational practices on the Internet, because currently available analytical tools cannot capture all the complexities of the Internet ecosystem. We have developed an agent-based (as opposed to analytical) model of Internet interconnection that captures interactions between interdomain traffic flow, routing, pricing/cost structures, and interconnection strategies of different network types. We parameterize our model using recent trends seen in the Internet ecosystem -- geographical expansion and traffic growth by large content providers, and less restrictive peering between ISPs. We study the resulting evolutionary transition from a hierarchical to a "flat" Internet, and the effects on global traffic flow, topology, and profitability of various network types. I will also describe some of our ongoing work on interconnection strategy selection by autonomous networks, and how these strategies affect the properties of the resulting equilibrium.

Abstract: From a chemical viewpoint life is an autocatalytic self-propagating set of chemical reactions. Organisms ingest raw materials which are converted into value-added products or used as energy sources for growth, maintenance, and reproduction. The extraction of value from raw materials is accomplished by interconnected networks of thousands of biochemical reactions. Molecular machines, termed enzymes, selectively catalyze a variety of biochemical reactions and are conditionally expressed to guide the distribution of energy and materials to suit current demands. Over the past decade, there has been substantial effort to reconstruct genome-scale networks of the cellular metabolism, and extract biological knowledge from the systems level view afforded by these networks. A limitation of current models is that they do not account for capital equipment costs and thus may generate biologically impracticable solutions; i. e. there are typically no reactions in these models that explicitly account for expression of mRNA transcripts or enzymes. This lack of accounting for mRNA and protein expression results in a free-ride problem where the model will over-predict flux through a reaction because there are no costs associated with producing the associated catalyst. Incoporation of the macromolecular machinery synthesis and assembly processes into the models will remove the free-ride problem and allow for the direct integration of high-throughput biological data. As a proof-of-concept, we have developed a mass-balanced genome-scale integrated model of metabolism and macromolecular expression for the hyperthermophile Thermotoga maritima. T. maritima is an industrially-interesting microbe due to its ability to produce hydrogen from a variety of organic wastes. Direct integration of transcriptome data as constraints in the model resulted in predicted hydrogen production rates consistent with experiments.

Abstract: Distributed consensus algorithms compute a function of data held at different locations in a network by passing messages between agents in the network. Applications for this simple operation include load balancing in power networks, coordination in robotic networks, and calibration in sensor networks. In this talk I will give an overview of this problem and discuss work on asynchronous "gossip"-style algorithms for computing averages in networks and provide asymptotic results for large networks as well as guarantees for smaller networks under different assumptions on the network's capabilities. Joint work with Alex Dimakis, Tuncer Can Aysal, Ercan Yildiz, Anna Scaglione, and Tara Javidi

Abstract: Abstract not available. Contact speaker for further information.

Abstract: Networks portray a multitude of interactions through which people meet, ideas are spread and infectious diseases propagate within a society. Identifying the most efficient 'spreaders' a network is an important step towards optimizing the use of available resources and ensuring the more efficient spread of information. Here we show that, in contrast to common belief, there are plausible circumstances where the best spreaders do not correspond to the most highly connected or the most central people. Instead, we find that the most efficient spreaders are those located within the core of the network as identified by the k-shell decomposition analysis and that when multiple spreaders are considered simultaneously the distance between them becomes the crucial parameter that determines the extent of the spreading. Furthermore, we show that infections persist in the high-k shells of the network in the case where recovered individuals do not develop immunity. Our analysis should provide a route for an optimal design of efficient dissemination strategies.

doi: 10.1038/nphys1746

Abstract: Liberal theory predicts that increased trade interdependence reduces the probability of conflict between states. In both theoretical and empirical terms, however, the existing literature has addressed these ideas primarily at the dyadic level. We argue that liberal theory, as well as the research designs for testing its implications, could benefit greatly from taking into account the networked structure of international trade. Specifically, if trade has a pacifying effect on dyadic relations, then this effect should be observable not only based on dyadic trade levels, but also based on the relative positions of states within the international network of trading states. We define trading communities as groups of states that are more trade-dependent on each other than they are on states, and use the concept of modularity to measure these communities. We hypothesize that, regardless of the extent to which they directly trade with each other, states that belong to the same trading community will be less likely to go to war. We find significant support for this hypothesis and, more generally, for the notion that the fundamental arguments of liberal theory can be extended to extra-dyadic relations.

Abstract: Networks, be they metabolic, neuronal, or genetic, are emerging as the biological unit of function. Studies in our laboratory on the network nature of gene interactions in Drosophila have revealed that a surprisingly wide range of genes is capable of affecting a phenotype, and that the relationships among genes interacting in a network is more plastic than previously thought. The findings also show that there are numerous, degenerate ways to achieve the same output from these networks. These are all features that had previously been well established in studies of nervous system function, suggesting a common underlying principle. The presence of such pronounced degeneracy raises the interesting possibility of an altogether new kind of mechanistic explanation: that the relationships among classes of components in the network are more important than any specific components in producing a given output. In other words, conservation of function can occur without conservation of the specific elements. Understanding this property is of central importance in any attempt to identify an underlying principle for biological networks.

Abstract: We establish a connection between the scale-free topology of complex networks, and the hyperbolic geometry of hidden metric spaces underlying these networks. Given a hyperbolic space, networks topologies with scale-free degree distributions and strong clustering naturally emerge on top of the space as topological reflections of its hyperbolic geometry. Conversely, for any scale-free network with strong clustering, there is an effective hyperbolic space underlying the network. The underlying hyperbolic geometry enables greedy routing with optimal efficiency. Greedy routing does not require any global information about network topology to navigate the network. At each hop, greedy routing selects as the next hop the current hop's neighbor closest to the destination in the underlying hyperbolic space. We show that in complex networks mapped to their hyperbolic spaces, greedy routing always succeeds reaching the destination, following the topologically shortest paths. Furthermore, we show that even without re-mapping the network or changing any node coordinates, this navigation efficiency is remarkably robust with respect to rapid network dynamics, and catastrophic levels of network damage. We map the real Internet AS-level topology to its hyperbolic space, and find that greedy routing using this map exhibits similar efficiency. These results effectively deliver a solution for Internet routing with theoretically best possible scaling properties. Not only routing table sizes and lengths of routing paths are as small as possible, but also routing communication overhead is reduced to zero.