Self-similarity of complex networks

From a single network to a network of networks

Network science has attracted much attention in recent years due to its interdisciplinary applications. We witnessed the revolution of network science in 1998 and 1999 started with small-world and scale-free networks having now thousands of high-profile publications, and it seems that since 2010 studies of ‘network of networks’ (NON), sometimes called multilayer networks or multiplex, have attracted more and more attention. The analytic framework for NON yields a novel percolation law for n interdependent networks that shows that percolation theory of single networks studied extensively in physics and mathematics in the last 50 years is a specific limit of the rich and very different general case of n coupled networks. Since then, properties and dynamics of interdependent and interconnected networks have been studied extensively, and scientists are finding many interesting results and discovering many surprising phenomena. Because most natural and engineered systems are composed of multiple subsystems and layers of connectivity, it is important to consider these features in order to improve our understanding of such complex systems. Now the study of NON has become one of the important directions in network science. In this paper, we review recent studies on the new emerging area—NON. Due to the fast growth of this field, there are many definitions of different types of NON, such as interdependent networks, interconnected networks, multilayered networks, multiplex networks and many others. There exist many datasets that can be represented as NON, such as network of different transportation networks including flight networks, railway networks and road networks, network of ecological networks including species interacting networks and food webs, network of biological networks including gene regulation network, metabolic network and protein–protein interacting network, network of social networks and so on. Among them, many interdependent networks including critical infrastructures are embedded in space, introducing spatial constraints. Thus, we also review the progress on study of spatially embedded networks. As a result of spatial constraints, such interdependent networks exhibit extreme vulnerabilities compared with their non-embedded counterparts. Such studies help us to understand, realize and hopefully mitigate the increasing risk in NON.

Geometrical invariability of transformation between a time series and a complex network

We present a dynamically equivalent transformation between time series and complex networks based on coarse geometry theory. In terms of quasi-isometric maps, we characterize how the underlying geometrical characters of complex systems are preserved during transformations. Fractal dimensions are shown to be the same for time series (or complex network) and its transformed counterpart. Results from the Rössler system, fractional Brownian motion, synthetic networks, and real networks support our findings. This work gives theoretical evidences for an equivalent transformation between time series and networks.

Extracting the globally and locally adaptive backbone of complex networks

A complex network is a useful tool for representing and analyzing complex systems, such as the world-wide web and transportation systems. However, the growing size of complex networks is becoming an obstacle to the understanding of the topological structure and their characteristics. In this study, a globally and locally adaptive network backbone (GLANB) extraction method is proposed. The GLANB method uses the involvement of links in shortest paths and a statistical hypothesis to evaluate the statistical importance of the links; then it extracts the backbone, based on the statistical importance, from the network by filtering the less important links and preserving the more important links; the result is an extracted subnetwork with fewer links and nodes. The GLANB determines the importance of the links by synthetically considering the topological structure, the weights of the links and the degrees of the nodes. The links that have a small weight but are important from the view of topological structure are not belittled. The GLANB method can be applied to all types of networks regardless of whether they are weighted or unweighted and regardless of whether they are directed or undirected. The experiments on four real networks show that the link importance distribution given by the GLANB method has a bimodal shape, which gives a robust classification of the links; moreover, the GLANB method tends to put the nodes that are identified as the core of the network by the k-shell algorithm into the backbone. This method can help us to understand the structure of the networks better, to determine what links are important for transferring information, and to express the network by a backbone easily.

Catalytic reaction dynamics in inhomogeneous networks

Biochemical reactions in a cell can be modeled by a catalytic reaction network (CRN). It has been reported that catalytic chain reactions occur intermittently in the CRN with a homogeneous random-graph topology and its avalanche-size distribution obeys a power law with the exponent 4/3 [A. Awazu and K. Kaneko, Phys. Rev. E 80, 010902(R) (2009)]. This fact indicates that the catalytic reaction dynamics in homogeneous CRNs exhibits self-organized criticality (SOC). Structures of actual CRNs are, however, known to be highly inhomogeneous. We study the influence of various types of inhomogeneities found in real-world metabolic networks on the universality class of SOC. Our numerical results clarify that SOC keeps its universality class even for networks possessing structural inhomogeneities such as the scale-free property, community structures, and degree correlations. In contrast, if the CRN has inhomogeneous catalytic functionality, the universality class of SOC depends on how widely distributed the number of reaction paths catalyzed by a single chemical species is.

Overlapping-box-covering method for the fractal dimension of complex networks

The fractality and self-similarity of complex networks have been widely investigated by evaluating the fractal dimension, the crux of which is how to locate the optimal solution or how to tile the network with the fewest boxes. The results yielded by the box-covering method with separated boxes possess great randomness or large errors. In this paper, we adopt the overlapping box to tile the entire network, called the overlapping-box-covering method. In such a case, for verifying its validity, we propose an overlapping-box-covering algorithm; we first apply it to three deterministic networks, then to four real-world fractal networks. It produces optimums or more accurate fractal dimension for the former; the quantities of boxes finally obtained for the latter are fewer and more deterministic, with the redundant box reaching up to 33.3%. The experimental results show that the overlapping-box-covering method is available and that the overlapping box outperforms the previous case, rendering the errors smaller. Moreover, we conclude that the overlapping box is an important determinant to acquire the fewest boxes for complex networks.

Resolving structural variability in network models and the brain

Large-scale white matter pathways crisscrossing the cortex create a complex pattern of connectivity that underlies human cognitive function. Generative mechanisms for this architecture have been difficult to identify in part because little is known in general about mechanistic drivers of structured networks. Here we contrast network properties derived from diffusion spectrum imaging data of the human brain with 13 synthetic network models chosen to probe the roles of physical network embedding and temporal network growth. We characterize both the empirical and synthetic networks using familiar graph metrics, but presented here in a more complete statistical form, as scatter plots and distributions, to reveal the full range of variability of each measure across scales in the network. We focus specifically on the degree distribution, degree assortativity, hierarchy, topological Rentian scaling, and topological fractal scaling—in addition to several summary statistics, including the mean clustering coefficient, the shortest path-length, and the network diameter. The models are investigated in a progressive, branching sequence, aimed at capturing different elements thought to be important in the brain, and range from simple random and regular networks, to models that incorporate specific growth rules and constraints. We find that synthetic models that constrain the network nodes to be physically embedded in anatomical brain regions tend to produce distributions that are most similar to the corresponding measurements for the brain. We also find that network models hardcoded to display one network property (e.g., assortativity) do not in general simultaneously display a second (e.g., hierarchy). This relative independence of network properties suggests that multiple neurobiological mechanisms might be at play in the development of human brain network architecture. Together, the network models that we develop and employ provide a potentially useful starting point for the statistical inference of brain network structure from neuroimaging data.

White matter tracts crisscrossing the human cortex are linked in a complex pattern that constrains human thought and behavior. Why the human brain displays the complex pattern that it does is a fascinating open question. Progress in uncovering generative mechanisms for this architecture requires greater knowledge about mechanistic drivers of anatomical networks. Here we contrast network properties derived from images of the human brain with 13 synthetic network models investigated in a progressive, branching sequence, chosen to probe the roles of physical embedding and temporal growth. We characterize both the empirical and synthetic networks using network diagnostics presented here in statistical form, as scatter plots and distributions, to reveal the full range of variability of each measure. We find that synthetic models that constrain the network nodes to be physically embedded in anatomical brain regions tend to produce distributions that are most similar to the corresponding measurements for the brain. We also find that network models hardcoded to display one network property do not in general simultaneously display a second, suggesting that multiple neurobiological mechanisms drive human brain network development. The network models that we develop and employ enable statistical inference of brain network structure from neuroimaging data.

Emergence of criticality in the transportation passenger flow: scaling and renormalization in the Seoul bus system

Social systems have recently attracted much attention, with attempts to understand social behavior with the aid of statistical mechanics applied to complex systems. Collective properties of such systems emerge from couplings between components, for example, individual persons, transportation nodes such as airports or subway stations, and administrative districts. Among various collective properties, criticality is known as a characteristic property of a complex system, which helps the systems to respond flexibly to external perturbations. This work considers the criticality of the urban transportation system entailed in the massive smart card data on the Seoul transportation network. Analyzing the passenger flow on the Seoul bus system during one week, we find explicit power-law correlations in the system, that is, power-law behavior of the strength correlation function of bus stops and verify scale invariance of the strength fluctuations. Such criticality is probed by means of the scaling and renormalization analysis of the modified gravity model applied to the system. Here a group of nearby (bare) bus stops are transformed into a (renormalized) "block stop" and the scaling relations of the network density turn out to be closely related to the fractal dimensions of the system, revealing the underlying structure. Specifically, the resulting renormalized values of the gravity exponent and of the Hill coefficient give a good description of the Seoul bus system: The former measures the characteristic dimensionality of the network whereas the latter reflects the coupling between distinct transportation modes. It is thus demonstrated that such ideas of physics as scaling and renormalization can be applied successfully to social phenomena exemplified by the passenger flow.

Robustness of a partially interdependent network formed of clustered networks

Clustering, or transitivity, a behavior observed in real-world networks, affects network structure and function. This property has been studied extensively, but most of this research has been limited to clustering in single networks. The effect of clustering on the robustness of coupled networks, on the other hand, has received much less attention. Only the case of a pair of fully coupled networks with clustering has recently received study. Here we generalize the study of clustering of a fully coupled pair of networks and apply it to a partially interdependent network of networks with clustering within the network components. We show, both analytically and numerically, how clustering within networks affects the percolation properties of interdependent networks, including the percolation threshold, the size of the giant component, and the critical coupling point at which the first-order phase transition changes to a second-order phase transition as the coupling between the networks is reduced. We study two types of clustering, one proposed by Newman [Phys. Rev. Lett. 103, 058701 (2009)] in which the average degree is kept constant while the clustering is changed, and the other by Hackett et al. [Phys. Rev. E 83, 056107 (2011)] in which the degree distribution is kept constant. The first type of clustering is studied both analytically and numerically, and the second is studied numerically.

Topological properties and fractal analysis of a recurrence network constructed from fractional Brownian motions

Many studies have shown that we can gain additional information on time series by investigating their accompanying complex networks. In this work, we investigate the fundamental topological and fractal properties of recurrence networks constructed from fractional Brownian motions (FBMs). First, our results indicate that the constructed recurrence networks have exponential degree distributions; the average degree exponent 〈λ〉 increases first and then decreases with the increase of Hurst index H of the associated FBMs; the relationship between H and 〈λ〉 can be represented by a cubic polynomial function. We next focus on the motif rank distribution of recurrence networks, so that we can better understand networks at the local structure level. We find the interesting superfamily phenomenon, i.e., the recurrence networks with the same motif rank pattern being grouped into two superfamilies. Last, we numerically analyze the fractal and multifractal properties of recurrence networks. We find that the average fractal dimension 〈dB〉 of recurrence networks decreases with the Hurst index H of the associated FBMs, and their dependence approximately satisfies the linear formula 〈dB〉≈2-H, which means that the fractal dimension of the associated recurrence network is close to that of the graph of the FBM. Moreover, our numerical results of multifractal analysis show that the multifractality exists in these recurrence networks, and the multifractality of these networks becomes stronger at first and then weaker when the Hurst index of the associated time series becomes larger from 0.4 to 0.95. In particular, the recurrence network with the Hurst index H=0.5 possesses the strongest multifractality. In addition, the dependence relationships of the average information dimension 〈D(1)〉 and the average correlation dimension 〈D(2)〉 on the Hurst index H can also be fitted well with linear functions. Our results strongly suggest that the recurrence network inherits the basic characteristic and the fractal nature of the associated FBM series.

Identification of core T cell network based on immunome interactome

Background

Data-driven studies on the dynamics of reconstructed protein-protein interaction (PPI) networks facilitate investigation and identification of proteins important for particular processes or diseases and reduces time and costs of experimental verification. Modeling the dynamics of very large PPI networks is computationally costly.

Results

To circumvent this problem, we created a link-weighted human immunome interactome and performed filtering. We reconstructed the immunome interactome and weighed the links using jackknife gene expression correlation of integrated, time course gene expression data. Statistical significance of the links was computed using the Global Statistical Significance (GloSS) filtering algorithm. P-values from GloSS were computed for the integrated, time course gene expression data. We filtered the immunome interactome to identify core components of the T cell PPI network (TPPIN). The interconnectedness of the major pathways for T cell survival and response, including the T cell receptor, MAPK and JAK-STAT pathways, are maintained in the TPPIN network. The obtained TPPIN network is supported both by Gene Ontology term enrichment analysis along with study of essential genes enrichment.

Conclusions

By integrating gene expression data to the immunome interactome and using a weighted network filtering method, we identified the T cell PPI immune response network. This network reveals the most central and crucial network in T cells. The approach is general and applicable to any dataset that contains sufficient information.

Output-input ratio in thermally fluctuating biomolecular machines

Biological molecular machines are proteins that operate under isothermal conditions and hence are referred to as free energy transducers. They can be formally considered as enzymes that simultaneously catalyze two chemical reactions: the free energy-donating (input) reaction and the free energy-accepting (output) one. Most if not all biologically active proteins display a slow stochastic dynamics of transitions between a variety of conformational substates composing their native state. This makes the description of the enzymatic reaction kinetics in terms of conventional rate constants insufficient. In the steady state, upon taking advantage of the assumption that each reaction proceeds through a single pair (the gate) of transition conformational substates of the enzyme-substrates complex, the degree of coupling between the output and the input reaction fluxes has been expressed in terms of the mean first-passage times on a conformational transition network between the distinguished substates. The theory is confronted with the results of random-walk simulations on the five-dimensional hypercube. The formal proof is given that, for single input and output gates, the output-input degree of coupling cannot exceed unity. As some experiments suggest such exceeding, looking for the conditions for increasing the degree of coupling value over unity challenges the theory. Performed simulations of random walks on several model networks involving more extended gates indicate that the case of the degree of coupling value higher than 1 is realized in a natural way on critical branching trees extended by long-range shortcuts. Such networks are scale-free and display the property of the small world. For short-range shortcuts, the networks are scale-free and fractal, representing a reasonable model for biomolecular machines displaying tight coupling, i.e., the degree of coupling equal exactly to unity. A hypothesis is stated that the protein conformational transition networks, as just as higher-level biological networks, the protein interaction network, and the metabolic network, have evolved in the process of self-organized criticality.

COARSE-GRAINED MODELING OF PROTEIN UNFOLDING DYNAMICS

We present a new dynamic elastic network model (DENM) that describes the unfolding process of a force-loaded protein. The protein interaction network and its potentials are constructed based on information of its native-state structure obtained from the Protein Data Bank, with network nodes positioned at the C_α coordinates of the protein backbone. Specifically, to mimic the unfolding process, i.e., to simulate the process of overcoming the local energy barrier on the free energy landscape with force loading, the noncovalent protein network bonds (i.e., hydrogen bonds, salt bridges, hydrophobic contacts, etc.) are broken one-by-one with a certain probability, while the strong covalent bonds along the backbone (i.e., peptide bonds, disulfide bonds, etc.) are kept intact. The jumping event from local energy minima (bonds breaking rate) are chosen according to Kramer's theory and the Bell model. Moreover, we exploit the self-similar structure of proteins at different scales to design an effective coarse-graining procedure for DENM with optimal parameter selection. The robustness of DENM is validated by coarse-grained molecular dynamics (MD) simulation against atomistic MD simulation of force-extension processes of the Fibrinogen and Titin Immunoglobulin proteins. We observe that the native structure of the proteins determines the total unfolding dynamics (including large deviations) and not just the fluctuations around the native state.

Percolation of a general network of networks

Percolation theory is an approach to study the vulnerability of a system. We develop an analytical framework and analyze the percolation properties of a network composed of interdependent networks (NetONet). Typically, percolation of a single network shows that the damage in the network due to a failure is a continuous function of the size of the failure, i.e., the fraction of failed nodes. In sharp contrast, in NetONet, due to the cascading failures, the percolation transition may be discontinuous and even a single node failure may lead to an abrupt collapse of the system. We demonstrate our general framework for a NetONet composed of n classic Erdős-Rényi (ER) networks, where each network depends on the same number m of other networks, i.e., for a random regular network (RR) formed of interdependent ER networks. The dependency between nodes of different networks is taken as one-to-one correspondence, i.e., a node in one network can depend only on one node in the other network (no-feedback condition). In contrast to a treelike NetONet in which the size of the largest connected cluster (mutual component) depends on n, the loops in the RR NetONet cause the largest connected cluster to depend only on m and the topology of each network but not on n. We also analyzed the extremely vulnerable feedback condition of coupling, where the coupling between nodes of different networks is not one-to-one correspondence. In the case of NetONet formed of ER networks, percolation only exhibits two phases, a second order phase transition and collapse, and no first order percolation transition regime is found in the case of the no-feedback condition. In the case of NetONet composed of RR networks, there exists a first order phase transition when the coupling strength q (fraction of interdependency links) is large and a second order phase transition when q is small. Our insight on the resilience of coupled networks might help in designing robust interdependent systems.

Fractal-Based Analysis for the Energy Consumption Efficiency of Biological Networks

Using a simulation model, we investigated the energy consumption efficiency of biological networks in terms of the fractal dimension of network morphology, the flow rate inside, and the resources needed for network construction. In themodel, we constructedmany types of tree networks and simulated the fluidic flow inside the networks. As a result, we clarified the precision of a preexisting equation and the efficiency of energy consumption for the networks.

Box-covering algorithm for fractal dimension of weighted networks

Box-covering algorithm is a widely used method to measure the fractal dimension of complex networks. Existing researches mainly deal with the fractal dimension of unweighted networks. Here, the classical box covering algorithm is modified to deal with the fractal dimension of weighted networks. Box size length is obtained by accumulating the distance between two nodes connected directly and graph-coloring algorithm is based on the node strength. The proposed method is applied to calculate the fractal dimensions of the “Sierpinski” weighted fractal networks, the E.coli network, the Scientific collaboration network, the C.elegans network and the USAir97 network. Our results show that the proposed method is efficient when dealing with the fractal dimension problem of complex networks. We find that the fractal property is influenced by the edge-weight in weighted networks. The possible variation of fractal dimension due to changes in edge-weights of weighted networks is also discussed.

Quantum Google in a complex network

We investigate the behaviour of the recently proposed Quantum PageRank algorithm, in large complex networks. We find that the algorithm is able to univocally reveal the underlying topology of the network and to identify and order the most relevant nodes. Furthermore, it is capable to clearly highlight the structure of secondary hubs and to resolve the degeneracy in importance of the low lying part of the list of rankings. The quantum algorithm displays an increased stability with respect to a variation of the damping parameter, present in the Google algorithm, and a more clearly pronounced power-law behaviour in the distribution of importance, as compared to the classical algorithm. We test the performance and confirm the listed features by applying it to real world examples from the WWW. Finally, we raise and partially address whether the increased sensitivity of the quantum algorithm persists under coordinated attacks in scale-free and random networks.

Exponential random graph models for networks with community structure

Although the community structure organization is an important characteristic of real-world networks, most of the traditional network models fail to reproduce the feature. Therefore, the models are useless as benchmark graphs for testing community detection algorithms. They are also inadequate to predict various properties of real networks. With this paper we intend to fill the gap. We develop an exponential random graph approach to networks with community structure. To this end we mainly built upon the idea of blockmodels. We consider both the classical blockmodel and its degree-corrected counterpart and study many of their properties analytically. We show that in the degree-corrected blockmodel, node degrees display an interesting scaling property, which is reminiscent of what is observed in real-world fractal networks. A short description of Monte Carlo simulations of the models is also given in the hope of being useful to others working in the field.

Anomalous biased diffusion in networks

We study diffusion with a bias toward a target node in networks. This problem is relevant to efficient routing strategies in emerging communication networks like optical networks. Bias is represented by a probability p of the packet or particle to travel at every hop toward a site that is along the shortest path to the target node. We investigate the scaling of the mean first passage time (MFPT) with the size of the network. We find by using theoretical analysis and computer simulations that for random regular (RR) and Erdős-Rényi networks, there exists a threshold probability, p(th), such that for p<p(th) the MFPT scales anomalously as N(α), where N is the number of nodes, and α depends on p. For p>p(th), the MFPT scales logarithmically with N. The threshold value p(th) of the bias parameter for which the regime transition occurs is found to depend only on the mean degree of the nodes. An exact solution for every value of p is given for the scaling of the MFPT in RR networks. The regime transition is also observed for the second moment of the probability distribution function, the standard deviation. For the case of scale-free (SF) networks, we present analytical bounds and simulations results showing that the MFPT scales at most as lnN to a positive power for any finite bias, which means that in SF networks even a very small bias is considerably more efficient in comparison to unbiased walk.

IMDB network revisited: unveiling fractal and modular properties from a typical small-world network

We study a subset of the movie collaboration network, http://www.imdb.com, where only adult movies are included. We show that there are many benefits in using such a network, which can serve as a prototype for studying social interactions. We find that the strength of links, i.e., how many times two actors have collaborated with each other, is an important factor that can significantly influence the network topology. We see that when we link all actors in the same movie with each other, the network becomes small-world, lacking a proper modular structure. On the other hand, by imposing a threshold on the minimum number of links two actors should have to be in our studied subset, the network topology becomes naturally fractal. This occurs due to a large number of meaningless links, namely, links connecting actors that did not actually interact. We focus our analysis on the fractal and modular properties of this resulting network, and show that the renormalization group analysis can characterize the self-similar structure of these networks.

Robustness of network of networks under targeted attack

The robustness of a network of networks (NON) under random attack has been studied recently [Gao et al., Phys. Rev. Lett. 107, 195701 (2011)]. Understanding how robust a NON is to targeted attacks is a major challenge when designing resilient infrastructures. We address here the question how the robustness of a NON is affected by targeted attack on high- or low-degree nodes. We introduce a targeted attack probability function that is dependent upon node degree and study the robustness of two types of NON under targeted attack: (i) a tree of n fully interdependent Erdős-Rényi or scale-free networks and (ii) a starlike network of n partially interdependent Erdős-Rényi networks. For any tree of n fully interdependent Erdős-Rényi networks and scale-free networks under targeted attack, we find that the network becomes significantly more vulnerable when nodes of higher degree have higher probability to fail. When the probability that a node will fail is proportional to its degree, for a NON composed of Erdős-Rényi networks we find analytical solutions for the mutual giant component P(∞) as a function of p, where 1-p is the initial fraction of failed nodes in each network. We also find analytical solutions for the critical fraction p(c), which causes the fragmentation of the n interdependent networks, and for the minimum average degree k[over ¯](min) below which the NON will collapse even if only a single node fails. For a starlike NON of n partially interdependent Erdős-Rényi networks under targeted attack, we find the critical coupling strength q(c) for different n. When q>q(c), the attacked system undergoes an abrupt first order type transition. When q≤q(c), the system displays a smooth second order percolation transition. We also evaluate how the central network becomes more vulnerable as the number of networks with the same coupling strength q increases. The limit of q=0 represents no dependency, and the results are consistent with the classical percolation theory of a single network under targeted attack.

Percolation of partially interdependent scale-free networks

We study the percolation behavior of two interdependent scale-free (SF) networks under random failure of 1-p fraction of nodes. Our results are based on numerical solutions of analytical expressions and simulations. We find that as the coupling strength between the two networks q reduces from 1 (fully coupled) to 0 (no coupling), there exist two critical coupling strengths q(1) and q(2), which separate three different regions with different behavior of the giant component as a function of p. (i) For q≥q(1), an abrupt collapse transition occurs at p=p(c). (ii) For q(2)<q<q(1), the giant component has a hybrid transition combined of both, abrupt decrease at a certain p=p(c)(jump) followed by a smooth decrease to zero for p<p(c)(jump) as p decreases to zero. (iii) For q≤q(2), the giant component has a continuous second-order transition (at p=p(c)). We find that (a) for λ≤3, q(1)≡1; and for λ>3, q(1) decreases with increasing λ. Here, λ is the scaling exponent of the degree distribution, P(k)[proportionality]k(-λ). (b) In the hybrid transition, at the q(2)<q<q(1) region, the mutual giant component P(∞) jumps discontinuously at p=p(c)(jump) to a very small but nonzero value, and when reducing p, P(∞) continuously approaches to 0 at p(c)=0 for λ<3 and at p(c)>0 for λ>3. Thus, the known theoretical p(c)=0 for a single network with λ≤3 is expected to be valid also for strictly partial interdependent networks.

Correlation dimension of complex networks

We propose a new measure to characterize the dimension of complex networks based on the ergodic theory of dynamical systems. This measure is derived from the correlation sum of a trajectory generated by a random walker navigating the network, and extends the classical Grassberger-Procaccia algorithm to the context of complex networks. The method is validated with reliable results for both synthetic networks and real-world networks such as the world air-transportation network or urban networks, and provides a computationally fast way for estimating the dimensionality of networks which only relies on the local information provided by the walkers.

The evolutionary dynamics of protein-protein interaction networks inferred from the reconstruction of ancient networks

Cellular functions are based on the complex interplay of proteins, therefore the structure and dynamics of these protein-protein interaction (PPI) networks are the key to the functional understanding of cells. In the last years, large-scale PPI networks of several model organisms were investigated. A number of theoretical models have been developed to explain both the network formation and the current structure. Favored are models based on duplication and divergence of genes, as they most closely represent the biological foundation of network evolution. However, studies are often based on simulated instead of empirical data or they cover only single organisms. Methodological improvements now allow the analysis of PPI networks of multiple organisms simultaneously as well as the direct modeling of ancestral networks. This provides the opportunity to challenge existing assumptions on network evolution. We utilized present-day PPI networks from integrated datasets of seven model organisms and developed a theoretical and bioinformatic framework for studying the evolutionary dynamics of PPI networks. A novel filtering approach using percolation analysis was developed to remove low confidence interactions based on topological constraints. We then reconstructed the ancient PPI networks of different ancestors, for which the ancestral proteomes, as well as the ancestral interactions, were inferred. Ancestral proteins were reconstructed using orthologous groups on different evolutionary levels. A stochastic approach, using the duplication-divergence model, was developed for estimating the probabilities of ancient interactions from today's PPI networks. The growth rates for nodes, edges, sizes and modularities of the networks indicate multiplicative growth and are consistent with the results from independent static analysis. Our results support the duplication-divergence model of evolution and indicate fractality and multiplicative growth as general properties of the PPI network structure and dynamics.

Atomic water channel controlling remarkable properties of a single brain microtubule: correlating single protein to its supramolecular assembly

Microtubule nanotubes are found in every living eukaryotic cells; these are formed by reversible polymerization of the tubulin protein, and their hollow fibers are filled with uniquely arranged water molecules. Here we measure single tubulin molecule and single brain-neuron extracted microtubule nanowire with and without water channel inside to unravel their unique electronic and optical properties for the first time. We demonstrate that the energy levels of a single tubulin protein and single microtubule made of 40,000 tubulin dimers are identical unlike conventional materials. Moreover, the transmitted ac power and the transient fluorescence decay (single photon count) are independent of the microtubule length. Even more remarkable is the fact that the microtubule nanowire is more conducting than a single protein molecule that constitutes the nanowire. Microtubule's vibrational peaks condense to a single mode that controls the emergence of size independent electronic/optical properties, and automated noise alleviation, which disappear when the atomic water core is released from the inner cylinder. We have carried out several tricky state-of-the-art experiments and identified the electromagnetic resonance peaks of single microtubule reliably. The resonant vibrations established that the condensation of energy levels and periodic oscillation of unique energy fringes on the microtubule surface, emerge as the atomic water core resonantly integrates all proteins around it such that the nanotube irrespective of its size functions like a single protein molecule. Thus, a monomolecular water channel residing inside the protein-cylinder displays an unprecedented control in governing the tantalizing electronic and optical properties of microtubule.

Spectral coarse graining for random walks in bipartite networks

Many real-world networks display a natural bipartite structure, yet analyzing and visualizing large bipartite networks is one of the open challenges in complex network research. A practical approach to this problem would be to reduce the complexity of the bipartite system while at the same time preserve its functionality. However, we find that existing coarse graining methods for monopartite networks usually fail for bipartite networks. In this paper, we use spectral analysis to design a coarse graining scheme specific for bipartite networks, which keeps their random walk properties unchanged. Numerical analysis on both artificial and real-world networks indicates that our coarse graining can better preserve most of the relevant spectral properties of the network. We validate our coarse graining method by directly comparing the mean first passage time of the walker in the original network and the reduced one.

Renormalization and small-world model of fractal quantum repeater networks

Quantum networks provide access to exchange of quantum information. The primary task of quantum networks is to distribute entanglement between remote nodes. Although quantum repeater protocol enables long distance entanglement distribution, it has been restricted to one-dimensional linear network. Here we develop a general framework that allows application of quantum repeater protocol to arbitrary quantum repeater networks with fractal structure. Entanglement distribution across such networks is mapped to renormalization. Furthermore, we demonstrate that logarithmical times of recursive such renormalization transformations can trigger fractal to small-world transition, where a scalable quantum small-world network is achieved. Our result provides new insight into quantum repeater theory towards realistic construction of large-scale quantum networks.

Optimal and suboptimal networks for efficient navigation measured by mean-first passage time of random walks

For a random walk on a network, the mean first-passage time from a node i to another node j chosen stochastically, according to the equilibrium distribution of Markov chain representing the random walk is called the Kemeny constant, which is closely related to the navigability on the network. Thus, the configuration of a network that provides optimal or suboptimal navigation efficiency is a question of interest. It has been proved that complete graphs have the exact minimum Kemeny constant over all graphs. In this paper, by using another method we first prove that complete graphs are the optimal networks with a minimum Kemeny constant, which grows linearly with the network size. Then, we study the Kemeny constant of a class of sparse networks that exhibit remarkable scale-free and fractal features as observed in many real-life networks, which cannot be described by complete graphs. To this end, we determine the closed-form solutions to all eigenvalues and their degeneracies of the networks. Employing these eigenvalues, we derive the exact solution to the Kemeny constant, which also behaves linearly with the network size for some particular cases of networks. We further use the eigenvalue spectra to determine the number of spanning trees in the networks under consideration, which is in complete agreement with previously reported results. Our work demonstrates that scale-free and fractal properties are favorable for efficient navigation, which could be considered when designing networks with high navigation efficiency.

Social networks and the risk of gunshot injury

Direct and indirect exposure to gun violence have considerable consequences on individual health and well-being. However, no study has considered the effects of one's social network on gunshot injury. This study investigates the relationship between an individual's position in a high-risk social network and the probability of being a victim of a fatal or non-fatal gunshot wound by combining observational data from the police with records of fatal and non-fatal gunshot injuries among 763 individuals in Boston's Cape Verdean community. A logistic regression approach is used to analyze the probability of being the victim of a fatal or non-fatal gunshot wound and whether such injury is related to age, gender, race, prior criminal activity, exposure to street gangs and other gunshot victims, density of one's peer network, and the social distance to other gunshot victims. The findings demonstrate that 85 % all of the gunshot injuries in the sample occur within a single social network. Probability of gunshot victimization is related to one's network distance to other gunshot victims: each network association removed from another gunshot victim reduces the odds of gunshot victimization by 25 % (odds ratio = 0.75; 95 % confidence interval, 0.65 to 0.87). This indirect exposure to gunshot victimization exerts an effect above and beyond the saturation of gunshot victimization in one's peer network, age, prior criminal activity, and other individual and network variables.

Social influence and spread dynamics in social networks

Social networks often serve as a critical medium for information dissemination, diffusion of epidemics, and spread of behavior, by shared activities or similarities between individuals. Recently, we have witnessed an explosion of interest in studying social influence and spread dynamics in social networks. To date, relatively little material has been provided on a comprehensive review in this field. This brief survey addresses this issue. We present the current significant empirical studies on real social systems, including network construction methods, measures of network, and newly empirical results. We then provide a concise description of some related social models from both macro- and micro-level perspectives. Due to the difficulties in combining real data and simulation data for verifying and validating real social systems, we further emphasize the current research results of computational experiments. We hope this paper can provide researchers significant insights into better understanding the characteristics of personal influence and spread patterns in large-scale social systems.

Dynamics and processing in finite self-similar networks

A common feature of biological networks is the geometrical property of self-similarity. Molecular regulatory networks through to circulatory systems, nervous systems, social systems and ecological trophic networks show self-similar connectivity at multiple scales. We analyse the relationship between topology and signalling in contrasting classes of such topologies. We find that networks differ in their ability to contain or propagate signals between arbitrary nodes in a network depending on whether they possess branching or loop-like features. Networks also differ in how they respond to noise, such that one allows for greater integration at high noise, and this performance is reversed at low noise. Surprisingly, small-world topologies, with diameters logarithmic in system size, have slower dynamical time scales, and may be less integrated (more modular) than networks with longer path lengths. All of these phenomena are essentially mesoscopic, vanishing in the infinite limit but producing strong effects at sizes and time scales relevant to biology.

Taxonomies of networks from community structure

The study of networks has become a substantial interdisciplinary endeavor that encompasses myriad disciplines in the natural, social, and information sciences. Here we introduce a framework for constructing taxonomies of networks based on their structural similarities. These networks can arise from any of numerous sources: They can be empirical or synthetic, they can arise from multiple realizations of a single process (either empirical or synthetic), they can represent entirely different systems in different disciplines, etc. Because mesoscopic properties of networks are hypothesized to be important for network function, we base our comparisons on summaries of network community structures. Although we use a specific method for uncovering network communities, much of the introduced framework is independent of that choice. After introducing the framework, we apply it to construct a taxonomy for 746 networks and demonstrate that our approach usefully identifies similar networks. We also construct taxonomies within individual categories of networks, and we thereby expose nontrivial structure. For example, we create taxonomies for similarity networks constructed from both political voting data and financial data. We also construct network taxonomies to compare the social structures of 100 Facebook networks and the growth structures produced by different types of fungi.

Current understanding of the formation and adaptation of metabolic systems based on network theory

Formation and adaptation of metabolic networks has been a long-standing question in biology. With recent developments in biotechnology and bioinformatics, the understanding of metabolism is progressively becoming clearer from a network perspective. This review introduces the comprehensive metabolic world that has been revealed by a wide range of data analyses and theoretical studies; in particular, it illustrates the role of evolutionary events, such as gene duplication and horizontal gene transfer, and environmental factors, such as nutrient availability and growth conditions, in evolution of the metabolic network. Furthermore, the mathematical models for the formation and adaptation of metabolic networks have also been described, according to the current understanding from a perspective of metabolic networks. These recent findings are helpful in not only understanding the formation of metabolic networks and their adaptation, but also metabolic engineering.

Agglomerative percolation on bipartite networks: nonuniversal behavior due to spontaneous symmetry breaking at the percolation threshold

Ordinary bond percolation (OP) can be viewed as a process where clusters grow by joining them pairwise, adding links chosen randomly one by one from a set of predefined virtual links. In contrast, in agglomerative percolation (AP) clusters grow by choosing randomly a target cluster and joining it with all its neighbors, as defined by the same set of virtual links. Previous studies showed that AP is in different universality classes from OP for several types of (virtual) networks (linear chains, trees, Erdös-Rényi networks), but most surprising were the results for two-dimensional (2D) lattices: While AP on the triangular lattice was found to be in the OP universality class, it behaved completely differently on the square lattice. In the present paper we explain this striking violation of universality by invoking bipartivity. While the square lattice is a bipartite graph, the triangular lattice is not. In conformity with this we show that AP on the honeycomb and simple cubic (3D) lattices--both of which are bipartite--are also not in the OP universality classes. More precisely, we claim that this violation of universality is basically due to a Z(2) symmetry that is spontaneously broken at the percolation threshold. We also discuss AP on bipartite random networks and suitable generalizations of AP on k-partite graphs.

Box-covering algorithm for fractal dimension of complex networks

The self-similarity of complex networks is typically investigated through computational algorithms, the primary task of which is to cover the structure with a minimal number of boxes. Here we introduce a box-covering algorithm that outperforms previous ones in most cases. For the two benchmark cases tested, namely, the E. coli and the World Wide Web (WWW) networks, our results show that the improvement can be rather substantial, reaching up to 15% in the case of the WWW network.

Edwards thermodynamics of the jamming transition for frictionless packings: ergodicity test and role of angoricity and compactivity

This paper illustrates how the tools of equilibrium statistical mechanics can help to describe a far-from-equilibrium problem: the jamming transition in frictionless granular materials. Edwards ideas consist of proposing a statistical ensemble of volume and stress fluctuations through the thermodynamic notion of entropy, compactivity, X, and angoricity, A (two temperature-like variables). We find that Edwards thermodynamics is able to describe the jamming transition (J point) in frictionless packings. Using the ensemble formalism we elucidate the following: (i) We test the combined volume-stress ensemble by comparing the statistical properties of jammed configurations obtained by dynamics with those averaged over the ensemble of minima in the potential energy landscape as a test of ergodicity. Agreement between both methods supports the idea of ergodicity and "thermalization" at a given angoricity and compactivity. (ii) A microcanonical ensemble analysis supports the maximum entropy principle for grains. (iii) The intensive variables A and X describe the approach to jamming through a series of scaling relations as A → 0+ and X → 0-. Due to the force-strain coupling in the interparticle forces, the jamming transition is probed thermodynamically by a "jamming temperature" T(J) composed of contributions from A and X. (iv) The thermodynamic framework reveals the order of the jamming phase transition by showing the absence of critical fluctuations at jamming in static observables like pressure and volume, and we discuss other critical scenarios for the jamming transition. (v) Finally, we elaborate on a comparison with relevant studies by Gao, Blawzdziewicz, and O'Hern [Phys. Rev. E 74, 061304 (2006)], showing a breakdown of equiprobability of microstates obtained via fast quenches. A network analysis of the energy landscape reveals the origin of the inhomogeneities in the uneven distribution of the areas of the basins. Such inhomogeneities are also found in other out-of-equilibrium systems like Lennard-Jones glasses and their existence does not preclude the use of statistical mechanics for jammed systems.

Artificial Spectrin Shells Reconstituted on Giant Vesicles

In the experimental approach to a synthetic minimal cell, the membrane compartment is a main component. Lipid vesicles represent the natural host for the artificial reconstruction of a cytomimetic membrane skeleton able to support mechanical function. Using the membrane component of human erythroid cells, we have reconstructed a membrane shell composed of a spectrin skeleton and fed by ATP. The structural and mechanical analysis reveals this spectrin skeleton as topological network supporting mechanical rigidity. Such an artificial shell would define a membrane compartment mechanically stable under physiological conditions.

Prokaryotic regulatory systems biology: Common principles governing the functional architectures of Bacillus subtilis and Escherichia coli unveiled by the natural decomposition approach

Escherichia coli and Bacillus subtilis are two of the best-studied prokaryotic model organisms. Previous analyses of their transcriptional regulatory networks have shown that they exhibit high plasticity during evolution and suggested that both converge to scale-free-like structures. Nevertheless, beyond this suggestion, no analyses have been carried out to identify the common systems-level components and principles governing these organisms. Here we show that these two phylogenetically distant organisms follow a set of common novel biologically consistent systems principles revealed by the mathematically and biologically founded natural decomposition approach. The discovered common functional architecture is a diamond-shaped, matryoshka-like, three-layer (coordination, processing, and integration) hierarchy exhibiting feedback, which is shaped by four systems-level components: global transcription factors (global TFs), locally autonomous modules, basal machinery and intermodular genes. The first mathematical criterion to identify global TFs, the κ-value, was reassessed on B. subtilis and confirmed its high predictive power by identifying all the previously reported, plus three potential, master regulators and eight sigma factors. The functionally conserved cores of modules, basal cell machinery, and a set of non-orthologous common physiological global responses were identified via both orthologous genes and non-orthologous conserved functions. This study reveals novel common systems principles maintained between two phylogenetically distant organisms and provides a comparison of their lifestyle adaptations. Our results shed new light on the systems-level principles and the fundamental functions required by bacteria to sustain life.

Google in a quantum network

We introduce the characterization of a class of quantum PageRank algorithms in a scenario in which some kind of quantum network is realizable out of the current classical internet web, but no quantum computer is yet available. This class represents a quantization of the PageRank protocol currently employed to list web pages according to their importance. We have found an instance of this class of quantum protocols that outperforms its classical counterpart and may break the classical hierarchy of web pages depending on the topology of the web.

Robustness of a network formed by n interdependent networks with a one-to-one correspondence of dependent nodes

Many real-world networks interact with and depend upon other networks. We develop an analytical framework for studying a network formed by n fully interdependent randomly connected networks, each composed of the same number of nodes N. The dependency links connecting nodes from different networks establish a unique one-to-one correspondence between the nodes of one network and the nodes of the other network. We study the dynamics of the cascades of failures in such a network of networks (NON) caused by a random initial attack on one of the networks, after which a fraction p of its nodes survives. We find for the fully interdependent loopless NON that the final state of the NON does not depend on the dynamics of the cascades but is determined by a uniquely defined mutual giant component of the NON, which generalizes both the giant component of regular percolation of a single network (n=1) and the recently studied case of the mutual giant component of two interdependent networks (n=2). We also find that the mutual giant component does not depend on the topology of the NON and express it in terms of generating functions of the degree distributions of the network. Our results show that, for any n≥2 there exists a critical p=p(c)>0 below which the mutual giant component abruptly collapses from a finite nonzero value for p≥p(c) to zero for p<p(c), as in a first-order phase transition. This behavior holds even for scale-free networks where p(c)=0 for n=1. We show that, if at least one of the networks in the NON has isolated or singly connected nodes, the NON completely disintegrates for sufficiently large n even if p=1. In contrast, in the absence of such nodes, the NON survives for any n for sufficiently large p. We illustrate this behavior by comparing two exactly solvable examples of NONs composed of Erdős-Rényi (ER) and random regular (RR) networks. We find that the robustness of n coupled RR networks of degree k is dramatically higher compared to the n-coupled ER networks of the same average degree k[over ¯]=k. While for ER NONs there exists a critical minimum average degree k[over ¯]=k[over ¯](min)∼lnn below which the system collapses, for RR NONs k(min)=2 for any n (i.e., for any k>2, a RR NON is stable for any n with p(c)<1). This results arises from the critical role played by singly connected nodes which exist in an ER NON and enhance the cascading failures, but do not exist in a RR NON.

The conundrum of functional brain networks: small-world efficiency or fractal modularity

The human brain has been studied at multiple scales, from neurons, circuits, areas with well-defined anatomical and functional boundaries, to large-scale functional networks which mediate coherent cognition. In a recent work, we addressed the problem of the hierarchical organization in the brain through network analysis. Our analysis identified functional brain modules of fractal structure that were inter-connected in a small-world topology. Here, we provide more details on the use of network science tools to elaborate on this behavior. We indicate the importance of using percolation theory to highlight the modular character of the functional brain network. These modules present a fractal, self-similar topology, identified through fractal network methods. When we lower the threshold of correlations to include weaker ties, the network as a whole assumes a small-world character. These weak ties are organized precisely as predicted by theory maximizing information transfer with minimal wiring costs.