The fundamental advantages of temporal networks

Most networked systems of scientific interest are characterized by temporal links, meaning the network's structure changes over time. Link temporality has been shown to hinder many dynamical processes, from information spreading to accessibility, by disrupting network paths. Considering the ubiquity of temporal networks in nature, we ask: Are there any advantages of the networks' temporality? We use an analytical framework to show that temporal networks can, compared to their static counterparts, reach controllability faster, demand orders of magnitude less control energy, and have control trajectories, that are considerably more compact than those characterizing static networks. Thus, temporality ensures a degree of flexibility that would be unattainable in static networks, enhancing our ability to control them.

Small but slow world: how network topology and burstiness slow down spreading

While communication networks show the small-world property of short paths, the spreading dynamics in them turns out slow. Here, the time evolution of information propagation is followed through communication networks by using empirical data on contact sequences and the susceptible-infected model. Introducing null models where event sequences are appropriately shuffled, we are able to distinguish between the contributions of different impeding effects. The slowing down of spreading is found to be caused mainly by weight-topology correlations and the bursty activity patterns of individuals.

Cancer metastasis networks and the prediction of progression patterns

Background:

Metastasis patterns in cancer vary both spatially and temporally. Network modelling may allow the incorporation of the temporal dimension in the analysis of these patterns.

Methods:

We used Medicare claims of 2 265 167 elderly patients aged ⩾65 years to study the large-scale clinical pattern of metastases. We introduce the concept of a cancer metastasis network, in which nodes represent the primary cancer site and the sites of subsequent metastases, connected by links that measure the strength of co-occurrence.

Results:

These cancer metastasis networks capture both temporal and subtle relational information, the dynamics of which differ between cancer types. Using these networks as entities on which the metastatic disease of individual patients may evolve, we show that they may be used, for certain cancer types, to make retrograde predictions of a primary cancer type given a sequence of metastases, as well as anterograde predictions of future sites of metastasis.

Conclusion:

Improvements over traditional techniques show that such a network-based modelling approach may be suitable for studying metastasis patterns.

The product space conditions the development of nations

Economies grow by upgrading the products they produce and export. The technology, capital, institutions, and skills needed to make newer products are more easily adapted from some products than from others. Here, we study this network of relatedness between products, or "product space," finding that more-sophisticated products are located in a densely connected core whereas less-sophisticated products occupy a less-connected periphery. Empirically, countries move through the product space by developing goods close to those they currently produce. Most countries can reach the core only by traversing empirically infrequent distances, which may help explain why poor countries have trouble developing more competitive exports and fail to converge to the income levels of rich countries.

Structure and tie strengths in mobile communication networks

Electronic databases, from phone to e-mails logs, currently provide detailed records of human communication patterns, offering novel avenues to map and explore the structure of social and communication networks. Here we examine the communication patterns of millions of mobile phone users, allowing us to simultaneously study the local and the global structure of a society-wide communication network. We observe a coupling between interaction strengths and the network's local structure, with the counterintuitive consequence that social networks are robust to the removal of the strong ties but fall apart after a phase transition if the weak ties are removed. We show that this coupling significantly slows the diffusion process, resulting in dynamic trapping of information in communities and find that, when it comes to information diffusion, weak and strong ties are both simultaneously ineffective.

Dynamics of information access on the web

While current studies on complex networks focus on systems that change relatively slowly in time, the structure of the most visited regions of the web is altered at the time scale from hours to days. Here we investigate the dynamics of visitation of a major news portal, representing the prototype for such a rapidly evolving network. The nodes of the network can be classified into stable nodes, which form the time-independent skeleton of the portal, and news documents. The visitations of the two node classes are markedly different, the skeleton acquiring visits at a constant rate, while a news document's visitation peaks after a few hours. We find that the visitation pattern of a news document decays as a power law, in contrast with the exponential prediction provided by simple models of site visitation. This is rooted in the inhomogeneous nature of the browsing pattern characterizing individual users: the time interval between consecutive visits by the same user to the site follows a power-law distribution, in contrast to the exponential expected for Poisson processes. We show that the exponent characterizing the individual user's browsing patterns determines the power-law decay in a document's visitation. Finally, our results document the fleeting quality of news and events: while fifteen minutes of fame is still an exaggeration in the online media, we find that access to most news items significantly decays after 36 hours of posting.

Topological units of environmental signal processing in the transcriptional regulatory network of Escherichia coli

Recent evidence indicates that potential interactions within metabolic, protein-protein interaction, and transcriptional regulatory networks are used differentially according to the environmental conditions in which a cell exists. However, the topological units underlying such differential utilization are not understood. Here we use the transcriptional regulatory network of Escherichia coli to identify such units, called origons, representing regulatory subnetworks that originate at a distinct class of sensor transcription factors. Using microarray data, we find that specific environmental signals affect mRNA expression levels significantly only within the origons responsible for their detection and processing. We also show that small regulatory interaction patterns, called subgraphs and motifs, occupy distinct positions in and between origons, offering insights into their dynamical role in information processing. The identified features are likely to represent a general framework for environmental signal processing in prokaryotes.

The topological relationship between the large-scale attributes and local interaction patterns of complex networks

Recent evidence indicates that the abundance of recurring elementary interaction patterns in complex networks, often called subgraphs or motifs, carry significant information about their function and overall organization. Yet, the underlying reasons for the variable quantity of different subgraph types, their propensity to form clusters, and their relationship with the networks' global organization remain poorly understood. Here we show that a network's large-scale topological organization and its local subgraph structure mutually define and predict each other, as confirmed by direct measurements in five well studied cellular networks. We also demonstrate the inherent existence of two distinct classes of subgraphs, and show that, in contrast to the low-density type II subgraphs, the highly abundant type I subgraphs cannot exist in isolation but must naturally aggregate into subgraph clusters. The identified topological framework may have important implications for our understanding of the origin and function of subgraphs in all complex networks.

Separating internal and external dynamics of complex systems

The observable behavior of a complex system reflects the mechanisms governing the internal interactions between the system's components and the effect of external perturbations. Here we show that by capturing the simultaneous activity of several of the system's components we can separate the internal dynamics from the external fluctuations. The method allows us to systematically determine the origin of fluctuations in various real systems, finding that while the Internet and the computer chip have robust internal dynamics, highway and Web traffic are driven by external demand. As multichannel measurements are becoming the norm in most fields, the method could help uncover the collective dynamics of a wide array of complex systems.

Global organization of metabolic fluxes in the bacterium Escherichia coli

Cellular metabolism, the integrated interconversion of thousands of metabolic substrates through enzyme-catalysed biochemical reactions, is the most investigated complex intracellular web of molecular interactions. Although the topological organization of individual reactions into metabolic networks is well understood, the principles that govern their global functional use under different growth conditions raise many unanswered questions. By implementing a flux balance analysis of the metabolism of Escherichia coli strain MG1655, here we show that network use is highly uneven. Whereas most metabolic reactions have low fluxes, the overall activity of the metabolism is dominated by several reactions with very high fluxes. E. coli responds to changes in growth conditions by reorganizing the rates of selected fluxes predominantly within this high-flux backbone. This behaviour probably represents a universal feature of metabolic activity in all cells, with potential implications for metabolic engineering.

Fluctuations in network dynamics

Most complex networks serve as conduits for various dynamical processes, ranging from mass transfer by chemical reactions in the cell to packet transfer on the Internet. We collected data on the time dependent activity of five natural and technological networks, finding that for each the coupling of the flux fluctuations with the total flux on individual nodes obeys a unique scaling law. We show that the observed scaling can explain the competition between the system's internal collective dynamics and changes in the external environment, allowing us to predict the relevant scaling exponents.

Evolutionary conservation of motif constituents in the yeast protein interaction network

Understanding why some cellular components are conserved across species but others evolve rapidly is a key question of modern biology. Here we show that in Saccharomyces cerevisiae, proteins organized in cohesive patterns of interactions are conserved to a substantially higher degree than those that do not participate in such motifs. We find that the conservation of proteins in distinct topological motifs correlates with the interconnectedness and function of that motif and also depends on the structure of the overall interactome topology. These findings indicate that motifs may represent evolutionary conserved topological units of cellular networks molded in accordance with the specific biological function in which they participate.

Emerging behavior in electronic bidding

We characterize the statistical properties of a large number of agents on two major online auction sites. The measurements indicate that the total number of bids placed in a single category and the number of distinct auctions frequented by a given agent follow power-law distributions, implying that a few agents are responsible for a significant fraction of the total bidding activity on the online market. We find that these agents exert an unproportional influence on the final price of the auctioned items. This domination of online auctions by an unusually active minority may be a generic feature of all online mercantile processes.

Hierarchical organization of modularity in metabolic networks

Spatially or chemically isolated functional modules composed of several cellular components and carrying discrete functions are considered fundamental building blocks of cellular organization, but their presence in highly integrated biochemical networks lacks quantitative support. Here, we show that the metabolic networks of 43 distinct organisms are organized into many small, highly connected topologic modules that combine in a hierarchical manner into larger, less cohesive units, with their number and degree of clustering following a power law. Within Escherichia coli, the uncovered hierarchical modularity closely overlaps with known metabolic functions. The identified network architecture may be generic to system-level cellular organization.

Percolation in directed scale-free networks

Many complex networks in nature have directed links, a property that affects the network's navigability and large-scale topology. Here we study the percolation properties of such directed scale-free networks with correlated in and out degree distributions. We derive a phase diagram that indicates the existence of three regimes, determined by the values of the degree exponents. In the first regime we regain the known directed percolation mean field exponents. In contrast, the second and third regimes are characterized by anomalous exponents, which we calculate analytically. In the third regime the network is resilient to random dilution, i.e., the percolation threshold is p(c)-->1.

Monte Carlo simulation of sinusoidally modulated superlattice growth

The fabrication of ZnSe/ZnTe superlattices grown by the process of rotating the substrate in the presence of an inhomogeneous flux distribution instead of the successively closing and opening of source shutters is studied via Monte Carlo simulations. It is found that the concentration of each compound is sinusoidally modulated along the growth direction, caused by the uneven arrival of Se and Te atoms at a given point of the sample, and by the variation of the Te/Se ratio at that point due to the rotation of the substrate. In this way we obtain a ZnSe(1-x)Tex alloy in which the composition x varies sinusoidally along the growth direction. The period of the modulation is directly controlled by the rate of the substrate rotation. The amplitude of the compositional modulation is monotonic for small angular velocities of the substrate rotation, but is itself modulated for large angular velocities. The average amplitude of the modulation pattern decreases as the angular velocity of substrate rotation increases and the measurement position approaches the center of rotation. The simulation results are in good agreement with previously published experimental measurements on superlattices fabricated in this manner.

Granular drag on a discrete object: shape effects on jamming

We study the drag force on discrete objects with circular cross section moving slowly through a spherical granular medium. Variations in the geometry of the dragged object change the drag force only by a small fraction relative to shape effects in fluid drag. The drag force depends quadratically on the object's diameter as expected. We do observe, however, a deviation above the expected linear depth dependence, and the magnitude of the deviation is apparently controlled by geometrical factors.

Modeling relaxation and jamming in granular media

We introduce a stochastic microscopic model to investigate the jamming and reorganization of grains induced by an object moving through a granular medium. The model reproduces the experimentally observed periodic sawtooth fluctuations in the jamming force and predicts the period and the power spectrum in terms of the controllable physical parameters. It also predicts that the avalanche sizes, defined as the number of displaced grains during a single advance of the object, follow a power law P(s) approximately s(-tau), where the exponent is independent of the physical parameters.

Comparable system-level organization of Archaea and Eukaryotes

A central and long-standing issue in evolutionary theory is the origin of the biological variation upon which natural selection acts. Some hypotheses suggest that evolutionary change represents an adaptation to the surrounding environment within the constraints of an organism's innate characteristics. Elucidation of the origin and evolutionary relationship of species has been complemented by nucleotide sequence and gene content analyses, with profound implications for recognizing life's major domains. Understanding of evolutionary relationships may be further expanded by comparing systemic higher-level organization among species. Here we employ multivariate analyses to evaluate the biochemical reaction pathways characterizing 43 species. Comparison of the information transfer pathways of Archaea and Eukaryotes indicates a close relationship between these domains. In addition, whereas eukaryotic metabolic enzymes are primarily of bacterial origin, the pathway-level organization of archaeal and eukaryotic metabolic networks is more closely related. Our analyses therefore suggest that during the symbiotic evolution of eukaryotes, incorporation of bacterial metabolic enzymes into the proto-archaeal proteome was constrained by the host's pre-existing metabolic architecture.

Parasitic computing

Reliable communication on the Internet is guaranteed by a standard set of protocols, used by all computers. Here we show that these protocols can be exploited to compute with the communication infrastructure, transforming the Internet into a distributed computer in which servers unwittingly perform computation on behalf of a remote node. In this model, which we call 'parasitic computing', one machine forces target computers to solve a piece of a complex computational problem merely by engaging them in standard communication. Consequently, the target computers are unaware that they have performed computation for the benefit of a commanding node. As experimental evidence of the principle of parasitic computing, we harness the power of several web servers across the globe, which-unknown to them-work together to solve an NP complete problem.

Spectra of "real-world" graphs: beyond the semicircle law

Many natural and social systems develop complex networks that are usually modeled as random graphs. The eigenvalue spectrum of these graphs provides information about their structural properties. While the semicircle law is known to describe the spectral densities of uncorrelated random graphs, much less is known about the spectra of real-world graphs, describing such complex systems as the Internet, metabolic pathways, networks of power stations, scientific collaborations, or movie actors, which are inherently correlated and usually very sparse. An important limitation in addressing the spectra of these systems is that the numerical determination of the spectra for systems with more than a few thousand nodes is prohibitively time and memory consuming. Making use of recent advances in algorithms for spectral characterization, here we develop methods to determine the eigenvalues of networks comparable in size to real systems, obtaining several surprising results on the spectra of adjacency matrices corresponding to models of real-world graphs. We find that when the number of links grows as the number of nodes, the spectral density of uncorrelated random matrices does not converge to the semicircle law. Furthermore, the spectra of real-world graphs have specific features, depending on the details of the corresponding models. In particular, scale-free graphs develop a trianglelike spectral density with a power-law tail, while small-world graphs have a complex spectral density consisting of several sharp peaks. These and further results indicate that the spectra of correlated graphs represent a practical tool for graph classification and can provide useful insight into the relevant structural properties of real networks.

Weighted evolving networks

Many biological, ecological, and economic systems are best described by weighted networks, as the nodes interact with each other with varying strength. However, most evolving network models studied so far are binary, the link strength being either 0 or 1. In this paper we introduce and investigate the scaling properties of a class of models which assign weights to the links as the network evolves. The combined numerical and analytical approach indicates that asymptotically the total weight distribution converges to the scaling behavior of the connectivity distribution, but this convergence is hampered by strong logarithmic corrections.

Bose-Einstein condensation in complex networks

The evolution of many complex systems, including the World Wide Web, business, and citation networks, is encoded in the dynamic web describing the interactions between the system's constituents. Despite their irreversible and nonequilibrium nature these networks follow Bose statistics and can undergo Bose-Einstein condensation. Addressing the dynamical properties of these nonequilibrium systems within the framework of equilibrium quantum gases predicts that the "first-mover-advantage," "fit-get-rich," and "winner-takes-all" phenomena observed in competitive systems are thermodynamically distinct phases of the underlying evolving networks.

The large-scale organization of metabolic networks

In a cell or microorganism, the processes that generate mass, energy, information transfer and cell-fate specification are seamlessly integrated through a complex network of cellular constituents and reactions. However, despite the key role of these networks in sustaining cellular functions, their large-scale structure is essentially unknown. Here we present a systematic comparative mathematical analysis of the metabolic networks of 43 organisms representing all three domains of life. We show that, despite significant variation in their individual constituents and pathways, these metabolic networks have the same topological scaling properties and show striking similarities to the inherent organization of complex non-biological systems. This may indicate that metabolic organization is not only identical for all living organisms, but also complies with the design principles of robust and error-tolerant scale-free networks, and may represent a common blueprint for the large-scale organization of interactions among all cellular constituents.

Physics of the rhythmic applause

We report on a series of measurements aimed to characterize the development and the dynamics of the rhythmic applause in concert halls. Our results demonstrate that while this process shares many characteristics of other systems that are known to synchronize, it also has features that are unexpected and unaccounted for in many other systems. In particular, we find that the mechanism lying at the heart of the synchronization process is the period doubling of the clapping rhythm. The characteristic interplay between synchronized and unsynchronized regimes during the applause is the result of a frustration in the system. All results are understandable in the framework of the Kuramoto model.

Liquid-induced transitions in granular media

We investigate the effect of interstitial liquid on the physical properties of granular media by measuring the angle of repose as a function of the liquid content. The resultant adhesive forces lead to three distinct regimes in the observed behavior as the liquid content is increased: a granular regime in which the grains move individually, a correlated regime in which the grains move in correlated clusters, and a plastic regime in which the grains flow coherently. We discuss these regimes in terms of two proposed theories describing the effects of liquid on the physical properties of granular media.

Irregularities and power law distributions in the breathing pattern in preterm and term infants

Unlike older children, young infants are prone to develop unstable respiratory patterns, suggesting important differences in their control of breathing. We examined the irregular breathing pattern in infants by measuring the time interval between breaths ("interbreath interval"; IBI) assessed from abdominal movement during 2 h of sleep in 25 preterm infants at a postconceptional age of 40.5 +/- 5.2 (SD) wk and in 14 term healthy infants at a postnatal age of 8.2 +/- 4 wk. In 10 infants we performed longitudinal measurements on two occasions. We developed a threshold algorithm for the detection of a breath so that an IBI included an apneic period and potentially some periods of insufficient tidal breathing excursions (hypopneas). The probability density distribution (P) of IBIs follows a power law, P(IBI) approximately IBI-alpha, with the exponent alpha providing a statistical measurement of the relative risk of insufficient breathing. With maturation, alpha increased from 2.62 +/- 0.4 at 41. 2 +/- 3.6 wk to 3.22 +/- 0.4 at 47.3 +/- 6.4 wk postconceptional age, indicating a decrease in long hypopneas (for paired data P = 0.002). The statistical properties of IBI were well reproduced in a model of the respiratory oscillator on the basis of two hypotheses: 1) tonic neural inputs to the respiratory oscillator are noisy; and 2) the noise explores a critical region where IBI diverges with decreasing tonic inputs. Accordingly, maturation of infant respiratory control can be explained by the tonic inputs moving away from this critical region. We conclude that breathing irregularities in infants can be characterized by alpha, which provides a link between clinically accessible data and the neurophysiology of the respiratory oscillator.

Lung tissue viscoelasticity: a mathematical framework and its molecular basis

Recent studies indicated that lung tissue stress relaxation is well represented by a simple empirical equation involving a power law, t-beta (where t is time). Likewise, tissue impedance is well described by a model having a frequency-independent (constant) phase with impedance proportional to omega-alpha (where omega is angular frequency and alpha is a constant). These models provide superior descriptions over conventional spring-dashpot systems. Here we offer a mathematical framework and explore its mechanistic basis for using the power law relaxation function and constant-phase impedance. We show that replacing ordinary time derivatives with fractional time derivatives in the constitutive equation of conventional spring-dashpot systems naturally leads to power law relaxation function, the Fourier transform of which is the constant-phase impedance with alpha = 1 - beta. We further establish that fractional derivatives have a mechanistic basis with respect to the viscoelasticity of certain polymer systems. This mechanistic basis arises from molecular theories that take into account the complexity and statistical nature of the system at the molecular level. Moreover, because tissues are composed of long flexible biopolymers, we argue that these molecular theories may also apply for soft tissues. In our approach a key parameter is the exponent beta, which is shown to be directly related to dynamic processes at the tissue fiber and matrix level. By exploring statistical properties of various polymer systems, we offer a molecular basis for several salient features of the dynamic passive mechanical properties of soft tissues.

Avalanches and power-law behaviour in lung inflation

When lungs are emptied during exhalation, peripheral airways close up. For people with lung disease, they may not reopen for a significant portion of inhalation, impairing gas exchange. A knowledge of the mechanisms that govern reinflation of collapsed regions of lungs is therefore central to the development of ventilation strategies for combating respiratory problems. Here we report measurements of the terminal airway resistance, Rt, during the opening of isolated dog lungs. When inflated by a constant flow, Rt decreases in discrete jumps. We find that the probability distribution of the sizes of the jumps and of the time intervals between them exhibit power-law behaviour over two decades. We develop a model of the inflation process in which 'avalanches' of airway openings are seen--with power-law distributions of both the size of avalanches and the time intervals between them--which agree quantitatively with those seen experimentally, and are reminiscent of the power-law behaviour observed for self-organized critical systems. Thus power-law distributions, arising from avalanches associated with threshold phenomena propagating down a branching tree structure, appear to govern the recruitment of terminal airspaces.