Abstract: Detecting network communities---groups of objects that correspond to functional modules---is crucial for the understanding of social, technological, and biological systems. In this talk we present a new paradigm for uncovering the modular structure of complex networks, based on a `deconvolution' of a network into any combination of overlapping, non-overlapping and hierarchically organized communities. We unify two fundamental organizing principles of complex networks from a range of disciplines: modular communities and the commonly observed core-periphery structure. We show that dense network cores form as a convolution of many overlapping communities. We discover that communities in social, information, and foodweb networks have a single central dominant core, while communities in protein-protein interaction as well as product co-purchasing networks have small overlaps and form many local cores. Our discoveries have implications for the controllability of complex systems and the emergence of densely connected cores in networks.

Abstract: The causal set approach to quantum gravity is based on the idea that the deep structure of spacetime is described by a locally finite partial order: a causal set. I will talk about recent work aimed at defining a theory of quantum fields on causal sets, and how it relates to field theory on continuous spacetime manifolds. I hope to leave plenty of time to discuss the role of causal set ideas in the broader context of complex networks. For example, the "retarded propagator" of a scalar field on a causal set appears to be closely related to a certain network centrality measure.

Abstract: Clustering is, along with the small-world and scale-free properties, the most ubiquitous topological property of real complex networks. Yet, unlike the small-world effect and the heterogeneity of nodes' degrees, clustering is not an emergent property spontaneously generated by paradigmatic connectivity principles such as preferential attachment and, therefore, calls for specific mechanisms for explaining its emergence, thus giving important insights into the nature of network formation and network evolution. Besides, clustering has subtle and, sometimes, apparently contradictory effects on many processes taking place on networks. This evidences the need for a profound understanding of the global organization of clustering in complex networks.

Here we accomplish this task by proposing a network decomposition based on edge multiplicity, defined as the number of triangles attached going through an edge, that we name m-core decomposition. We have developed a visualization tool that, coupled to this decomposition, allows us to observe the large-scale organization of triangles in a network at a single glance, thus making it possible to compare networks with the same local properties but generated with different mechanisms leading to different hierarchical and modular architectures. In this way, we have been able to show that real networks are close to maximally random once the degree distribution and clustering coefficient are fixed. In turn, this result supports the idea that network formation and evolution is the result of a self-organized process operating with local information.

Abstract: Traditional techniques and systems for analyzing graphs are of little use for modern graph data. This is due to (1) the giant scale and dynamic nature of graph data (e.g., social networks); and (2) new applications that interactively query these graphs, thus having stringent latency requirements. We need both new techniques, and new systems that enable efficient implementation of these techniques. In this talk, I will focus on shortest path queries that are a fundamental primitive for several applications including social search, context-aware search, social auctions and social network privacy. I will present ASAP, a system that on graphs with millions of nodes and edges, can answer queries in tens of microseconds, roughly a factor 10,000x faster than the state of the art. ASAP easily maps on to distributed graph processing frameworks and can gracefully handle dynamic graphs.

The observations made during design of ASAP have led to advances in several other domains. By formalizing the techniques used in ASAP, we (1) significantly improve upon the decade-old theory results on computing approximately shortest paths; and (2) get simplified proofs of several theory results that used substantially more complex techniques. By applying the former to the problem of routing in networks with limited memory, we also get a distributed routing protocol that uses little router memory and routes along paths that are shorter than what was previously thought possible.

Abstract: There is no best community detection algorithm for all kinds of networks, it should be chosen according to the network at the hand. In this talk, I will present the difference between modularity-based and flow-based community detection algorithms. In particular, I will explain the infoMap, an information-theoretic approach for community detection in directed networks. Then I will present, how to find communities at multiscales using Markov dynamics.

Abstract: This framework is based on the causal set approach to discrete quantum gravity. We first construct a causal growth process (CGP). We "quantize" the CGP by forming Hilbert spaces of sets of finite paths. A quantum dynamics is generated by a sequence of probability operators on these Hilbert spaces which then gives a quantum sequential growth process. We also obtain a quantum measure space using suitable subsets of the path space. We define a covariant bidifference operator on the Hilbert space of causal sets. Employing this operator we define a discrete curvature operator and discrete Einstein equations. We comment on the relationship of this to classical general relativity.

Abstract: The properties of dynamical systems taking place on networks, such as opinion dynamics, synchronisation, consensus or random walks, are strongly related to the structure of the network. In particular every consensus dynamics provides a centrality measure of the nodes and edges in the network, and---through time scale separation---a way to cluster the nodes into communities, i.e. sets of densely connected nodes. This dynamical approach to large networks analysis highlights unexpected links between various notions such as PageRank, MinCut, modularity and spectral clustering.

We illustrate our methods on large social, biological (proteins) and technological (power networks, Internet, images) networks, where finding central nodes and communities are key data mining tools to understand or visualize those networks.

Abstract: Persons who engage in non-suicidal self-injury (NSSI), often conceal their practices which limits the examination and understanding of those who engage in NSSI. The goal of this research is to utilize public online social networks (namely, in LiveJournal, a major blogging network) to observe the NSSI population's communication in a naturally occurring setting. Specifically, LiveJournal users can publicly declare their interests. We collected the self-declared interests of 22,000 users who are members of or participate in 43 NSSI-related communities. We extracted a bimodal socio-semantic network of users and interests based on their similarity. The semantic subnetwork of interests contains NSSI terms (such as "self-injury" and "razors"), references to music performers (such as "Nine Inch Nails"), and general daily life and creativity related terms (such as "poetry" and "boys"). Assuming users are genuine in their declarations, the words reveal distinct patterns of interest and may serve as signal keys to NSSI. (This talk discusses joint work with Dan Stefanescu, Lance Swenson, and Gary Fireman.)

Abstract: I discuss "simple" dynamical systems on networks and examine how network structure affects dynamics of processes running on top of networks. I consider results based on "locally tree-like" and/or mean-field and pair approximations and examine when they seem to work well, what can cause them to fail, and when they seem to produce accurate results even though their hypotheses are violated fantastically. I'll also present a new model for multi-stage complex contagions--in which fanatics produce greater influence than mere followers--and examine dynamics on networks with heterogeneous correlations. (This talk discusses joint work with James Gleeson, Sergey Melnik, Peter Mucha, and Jonathan Ward.)

Abstract: Mobile phone use is increasingly common, especially in developing countries. Telecommunications traffic between areas served by individual mobile phone antennae in Cote d'Ivoire, provided by France Telecom-Orange's subsidiary as part of the D4D Challenge, thus provides a finely resolved measure of interactions within the geographically distributed population. We extract a community structure from this communication network, and observe that it is geographically localized. Fitting the intensity of interactions between nodes to a gravity model, we find that it decays with distance, (partially) explaining the geographic locality of the network communities. We develop a novel method for using the weighted network to compare this community structure with geographical divisions of the population originating in ethnic, language, or religious differences. The same methodology also supports analysis of the association between such cultural factors and political differences, accounting for spatial (and possibly other) autocorrelations. This is a preliminary description of work being done with Orest Bucicovschi, Rex Douglass, Megha Ram, David Rideout, and Dongjin Song.

Abstract: Recent research has explored the increasingly important role of social media by examining the dynamics of individual and group behavior, characterizing patterns of information diffusion, and developing different methods for identifying influential participants. In this talk I will present a novel measure of influence for social media participants that is based on the information-theoretic notion of transfer entropy, or information transfer. This theoretically grounded measure is based on dynamic information, captures fine-grain notions of influence, and admits a natural, predictive interpretation. Networks inferred by transfer entropy can differ significantly from static friendship networks because most friendship links are not useful for predicting future dynamics. In addition, transfer entropy allows to differentiate between weak influence over large groups and strong influence over small groups.

Abstract: Finding communities in networks is crucial to understand their structure and function, as well as to identify the role of the nodes and uncover hidden relationships between nodes. In this talk I will present the main concepts of community detection and highlight the many open problems that still keep the scientific community from having a shared set of reliable tools for the clustering analysis of real networks. In particular I will address the complexity of real community detection, due to the presence of overlapping communities and hierarchical structure, I will discuss the limits of null models at the basis of existing techniques and assess the delicate issue of testing the performance of methods.

Abstract: The combination of two inexorable trends---increasing parallelism and increasing big data analytics---means modern data centers urgently need efficient high-capacity networks interconnecting thousands of servers. But we have lacked a fundamental understanding of what network topologies achieve high throughput. This talk shows how surprisingly, today's carefully-structured designs such as fat-trees are far from optimal. Our Jellyfish architecture uses a completely random network to achieve substantially higher throughput than deployed designs, and allows easy incremental expansion. This leads to numerous important theoretical and practical questions in network design, such as optimality and the design of heterogeneous networks. Joint work with Ankit Singla, Chi-Yao Hong, Alexandra Kolla, and Lucian Popa.

Abstract: Detecting community structure in networks is of high interest in many scientific fields. Nodes within the same community are expected to share attributes, common properties or functional relationships and, therefore, the characterization of those communities can improve our understanding of complex systems. In this talk, I will present the main concepts of community detection and our recent work in the field. In particular, I will introduce Surprise, our recently proposed measure to evaluate the quality of the partition of a network into communities. Our results demonstrate that the use of Newman and Girvan's modularity (the most popular measure proposed to this end) is incorrect. On the contrary, the strategy of maximizing Surprise recovers the expected communities in all networks tested. Moreover, the extremely small error made by this approach, suggests that Surprise maximization could be an optimal way to detect the real community structure of complex networks.

Abstract: The Internet is a complex and dynamic interconnection of about 40,000 Autonomous Systems (ASes). A link in this context represents a business agreement between two ASes to exchange traffic under various policy and capacity constraints. Some links represent transit relations, in which one AS acts as the provider of the other AS (the customer), offering the latter access to the entire Internet. Other links represent settlement-free peering (or simply 'peering') relations, in which the two ASes exchange their local and customer-originating traffic for free. The conventional wisdom is that transit providers should be selective in choosing their settlement-free peers because they prefer to offer revenue generating transit service to others. Surprisingly, however, real-world data shows that about 70% of the transit providers use an "Open" peering strategy, meaning that they are willing to peer for free with any other network. What causes this large scale adoption of Open peering, especially among transit providers? What are the economic consequences of this peering paradigm for the population of transit providers? We approach these questions through agent-based modeling, capturing the dynamics of peering strategy adoption, internetwork formation and interdomain traffic flow. We explain why transit providers gravitate towards Open peering even though that move is often detrimental to their economic fitness. We also identify classes of transit providers that would do better (or worse) under the Open peering regime, as well as those that remain selective. Finally, we examine the impact of certain Open peering variants that are often discussed among transit providers as potential ways to avoid the economic drawback of Open peering.

Abstract: Preferential attachment is a powerful mechanism explaining the emergence of scaling in growing networks. If new connections are established preferentially to more popular nodes in a network, then the network is scale-free. Here we show that not only popularity but also similarity is a strong force shaping the network structure and dynamics. We develop a framework where new connections, instead of preferring popular nodes, optimize certain trade-offs between popularity and similarity. The framework admits a geometric interpretation, in which preferential attachment emerges from local optimization processes. The optimization framework accurately describes large-scale evolution of technological (Internet), social (web of trust), and biological (E.coli metabolic) networks, predicting the probability of new links in them with a remarkable precision. The developed framework can thus be used for predicting new links in evolving networks, and provides a different perspective on preferential attachment as an emergent phenomenon. arXiv:1106.0286

Abstract: Botnets are the most common vehicle of cyber-criminal activity. They are used for spamming, phishing, denial of service attacks, brute-force cracking, stealing private information, and cyber warfare. Botnets carry out network scans for several reasons, including searching for vulnerable machines to infect and recruit into the botnet, probing networks for enumeration or penetration, etc. We present the measurement and analysis of a horizontal scan of the entire IPv4 address space conducted by the Sality botnet in February of last year. This 12-day scan originated from approximately 3 million distinct IP addresses, and used a heavily coordinated and unusually covert scanning strategy to try to discover and compromise VoIP-related (SIP server) infrastructure. We observed this event through the UCSD Network Telescope, a /8 darknet continuously receiving large amounts of unsolicited traffic, and we correlate this traffic data with other public sources of data to validate our inferences. Sality is one of the largest botnets ever identified by researchers, its behavior represents ominous advances in the evolution of modern malware: the use of more sophisticated stealth scanning strategies by millions of coordinated bots, targeting critical voice communications infrastructure.

Abstract: If the Internet was designed with the goal to have a robust, fault-tolerant, and distributed computer network, Crowdsourcing, Internet's latest spawn, aims to be serves as a robust, fault-tolerant, and distributed collective problem solving platform. To put this idea to test, government agencies held the 2009 DARPA Network Challenge, the 2011 DARPA Shredder Challenge, and 2012 Department of State's Tag Challenge. In the DARPA Network Challenge competing teams were asked to locate 10 red weather balloons in the continental US under 8 hours. In the Shredder Challenge, DARPA asked participants to reconstruct 5 puzzles of the hardest computational nature under 5 weeks. In the Tag Challenge, team had to locate 5 jewel thieves in cities across Europe and the US under 12 hours. Using a recursive incentive mechanism that both spread information about the task and incentivized individuals to act, our team was able to win the Network and Tag Challenges, and make significant progress in the Shedder Challenge while suffering constant attacks. This talk outlines the theoretical and empirical properties of this mechanism, but places emphasis on the observed adversary capability and intent. The multiplicity of aggression episodes serves to illustrate the different factors that make Crowdsourcing vulnerable.

Abstract: Network measures of structurally cohesive groups and pairs of individuals within and linked to (stru-)cohesive groups have a powerful record of causal predictions in social networks generally: e.g., attachment to school and community and formation of new corporate partnerships. Here these concepts are applied to forager societies studied ethnographically and coded for ethnographic variables in Binford's "Frames of Reference" and the "Kinsources" network datasets, each of which contain numerous measures of social cooperation. A main hypothesis tested is that network and stru-cohesion measures outperform existing rules of kin selection, genetic, and game theoretical approaches to the evolution of cooperation in human groups but rather an interaction between culture and sexual selection. I show how group attachment cohesion with benefits of cooperation need not depend on genetic models of cooperation or group selection. Rather the pan-human biparental and role-based structure of human kinship, in all of its variants, provides low-order or egalitarian cohesive structure. This leads to a novel conception of human evolution, '''contra''' Richard Dawkins. Hierarchical cohesive structure (of order 5 and higher), however, has been shown to lead to bullying and the nongenetic emergence of selfishness as network-dependent phenomena.

Abstract: In this talk, I will discuss our work on two problems in optimization and evolution of networks. The first part of the talk is about emergence of functional modularity in multitasking networks. Biological networks are known to possess functionally specialized modules, which perform tasks almost independently of each other. I will show that phenotypic adaptation (non-evolutionary learning) can lead to the formation of functional modules in an initially homogeneous system that performs multi-tasks. Also, I will discuss that the degree of independence between the tasks dictates the degree of functional specialization emerging in the network. The second part of the presentation is about degree-based graph construction and sampling. Network representation and modeling has been one of the most comprehensive ways to study various complex systems. In many cases, the graph representing the system has to be built from its degree sequence. I will introduce problems related to the construction of all the possible graphs with a given degree sequence and will present our solution for these problems. By using this result, I will show how to provide an efficient, polynomial time algorithm that generates graph samples with a given degree sequence. Unlike other existing algorithms, this method always produces statistically independent samples and provides weight associated with each sample. The weights allow graph observables to be measured uniformly over the graph ensemble.

Abstract: We consider critical phenomena on heterogeneous small-world networks having a scale-free character but also arbitrary short loops. After deriving the self-consistent equation for the order parameter and the critical surface, we prove that the critical behavior on complex networks is in fact infinitely robust with respect to the presence of arbitrary short loops.

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.