Power-Hop: A Pervasive Observation for Real Complex Networks

Complex networks have been shown to exhibit universal properties, with one of the most consistent patterns being the scale-free degree distribution, but are there regularities obeyed by the r-hop neighborhood in real networks? We answer this question by identifying another power-law pattern that describes the relationship between the fractions of node pairs C(r) within r hops and the hop count r. This scale-free distribution is pervasive and describes a large variety of networks, ranging from social and urban to technological and biological networks. In particular, inspired by the definition of the fractal correlation dimension D₂ on a point-set, we consider the hop-count r to be the underlying distance metric between two vertices of the network, and we examine the scaling of C(r) with r. We find that this relationship follows a power-law in real networks within the range 2 ≤ r ≤ d, where d is the effective diameter of the network, that is, the 90-th percentile distance. We term this relationship as power-hop and the corresponding power-law exponent as power-hop exponent h. We provide theoretical justification for this pattern under successful existing network models, while we analyze a large set of real and synthetic network datasets and we show the pervasiveness of the power-hop.     

Scaling of differentiation in networks: nervous systems,organisms, ant colonies,ecosystems, businesses,universities, cities,electronic circuits,and Legos

Nodes in networks are often of different types, and in this sense networks are differentiated. Here we examine the relationship between network differentiation and network size in networks under economic or natural selective pressure, such as electronic circuits (networks of electronic components), Legos (networks of Lego pieces), businesses (networks of employees), universities (networks of faculty), organisms (networks of cells), ant colonies (networks of ants), and nervous systems (networks of neurons). For each of these we find that (i) differentiation increases with network size, and (ii) the relationship is consistent with a power law. These results are explained by a hypothesis that, because nodes are costly to build and maintain in such "selected networks", network size is optimized, and from this the power-law relationship may be derived. The scaling exponent depends on the particular kind of network, and is determined by the degree to which nodes are used in a combinatorial fashion to carry out network-level functions. We find that networks under natural selection (organisms, ant colonies, and nervous systems) have much higher combinatorial abilities than the networks for which human ingenuity is involved (electronic circuits, Legos, businesses, and universities). A distinct but related optimization hypothesis may be used to explain scaling of differentiation in competitive networks (networks where the nodes themselves, rather than the entire network, are under selective pressure) such as ecosystems (networks of organisms).     

Degree Correlations in Directed Scale-Free Networks

Scale-free networks, in which the distribution of the degrees obeys a power-law, are ubiquitous in the study of complex systems. One basic network property that relates to the structure of the links found is the degree assortativity, which is a measure of the correlation between the degrees of the nodes at the end of the links. Degree correlations are known to affect both the structure of a network and the dynamics of the processes supported thereon, including the resilience to damage, the spread of information and epidemics, and the efficiency of defence mechanisms. Nonetheless, while many studies focus on undirected scale-free networks, the interactions in real-world systems often have a directionality. Here, we investigate the dependence of the degree correlations on the power-law exponents in directed scale-free networks. To perform our study, we consider the problem of building directed networks with a prescribed degree distribution, providing a method for proper generation of power-law-distributed directed degree sequences. Applying this new method, we perform extensive numerical simulations, generating ensembles of directed scale-free networks with exponents between 2 and 3, and measuring ensemble averages of the Pearson correlation coefficients. Our results show that scale-free networks are on average uncorrelated across directed links for three of the four possible degree-degree correlations, namely in-degree to in-degree, in-degree to out-degree, and out-degree to out-degree. However, they exhibit anticorrelation between the number of outgoing connections and the number of incoming ones. The findings are consistent with an entropic origin for the observed disassortativity in biological and technological networks.     

Emergence of Scale-Free Close-Knit Friendship Structure in Online Social Networks

Although the structural properties of online social networks have attracted much attention, the properties of the close-knit friendship structures remain an important question. Here, we mainly focus on how these mesoscale structures are affected by the local and global structural properties. Analyzing the data of four large-scale online social networks reveals several common structural properties. It is found that not only the local structures given by the indegree, outdegree, and reciprocal degree distributions follow a similar scaling behavior, the mesoscale structures represented by the distributions of close-knit friendship structures also exhibit a similar scaling law. The degree correlation is very weak over a wide range of the degrees. We propose a simple directed network model that captures the observed properties. The model incorporates two mechanisms: reciprocation and preferential attachment. Through rate equation analysis of our model, the local-scale and mesoscale structural properties are derived. In the local-scale, the same scaling behavior of indegree and outdegree distributions stems from indegree and outdegree of nodes both growing as the same function of the introduction time, and the reciprocal degree distribution also shows the same power-law due to the linear relationship between the reciprocal degree and in/outdegree of nodes. In the mesoscale, the distributions of four closed triples representing close-knit friendship structures are found to exhibit identical power-laws, a behavior attributed to the negligible degree correlations. Intriguingly, all the power-law exponents of the distributions in the local-scale and mesoscale depend only on one global parameter, the mean in/outdegree, while both the mean in/outdegree and the reciprocity together determine the ratio of the reciprocal degree of a node to its in/outdegree. Structural properties of numerical simulated networks are analyzed and compared with each of the four real networks. This work helps understand the interplay between structures on different scales in online social networks.     

Duplication models for biological networks.

Are biological networks different from other large complex networks? Both large biological and nonbiological networks exhibit power-law graphs (number of nodes with degree k, N(k) approximately k(-beta)), yet the exponents, beta, fall into different ranges. This may be because duplication of the information in the genome is a dominant evolutionary force in shaping biological networks (like gene regulatory networks and protein-protein interaction networks) and is fundamentally different from the mechanisms thought to dominate the growth of most nonbiological networks (such as the Internet). The preferential choice models used for nonbiological networks like web graphs can only produce power-law graphs with exponents greater than 2. We use combinatorial probabilistic methods to examine the evolution of graphs by node duplication processes and derive exact analytical relationships between the exponent of the power law and the parameters of the model. Both full duplication of nodes (with all their connections) as well as partial duplication (with only some connections) are analyzed. We demonstrate that partial duplication can produce power-law graphs with exponents less than 2, consistent with current data on biological networks. The power-law exponent for large graphs depends only on the growth process, not on the starting graph.     

Simple stochastic models and their power-law type behaviour

A power-law relationship between the mean and variance of ecological time series has been shown to hold for a vast number of species. Here we examine the behaviour of single-species stochastic models and concentrate in particular on the mean-variance relationship as the carrying capacity becomes large. Single-species stochastic models can be written as Markov chains, and the long-term distribution of population sizes and hence power-law scaling can be found analytically. The various power-law scalings that arise have very different biological implications for the effects of stochasticity and the departure from the deterministic paradigm. Finally we extend our analysis to consider the complicating factors of spatial heterogeneity, nontrivial deterministic dynamics, and multispecies models.     

Non-uniform survival rate of heterodimerization links in the evolution of the yeast protein-protein interaction network

Protein-protein interaction networks (PINs) are scale-free networks with a small-world property. In a small-world network, the average cluster coefficient () is much higher than in a random network, but the average shortest path length () is similar between the two networks. To understand the evolutionary mechanisms shaping the structure of PINs, simulation studies using various network growth models have been performed. It has been reported that the heterodimerization (HD) model, in which a new link is added between duplicated nodes with a uniform probability, could reproduce scale-freeness and a high . In this paper, however, we show that the HD model is unsatisfactory, because (i) to reproduce the high in the yeast PIN, a much larger number (n(HI)) of HD links (links between duplicated nodes) are required than the estimated number of n(HI) in the yeast PIN and (ii) the spatial distribution of triangles in the yeast PIN is highly skewed but the HD model cannot reproduce the skewed distribution. To resolve these discrepancies, we here propose a new model named the non-uniform heterodimerization (NHD) model. In this model, an HD link is preferentially attached between duplicated nodes when they share many common neighbors. Simulation studies demonstrated that the NHD model can successfully reproduce the high , the low n(HI), and the skewed distribution of triangles in the yeast PIN. These results suggest that the survival rate of HD links is not uniform in the evolution of PINs, and that an HD link between high-degree nodes tends to be evolutionarily conservative. The non-uniform survival rate of HD links can be explained by assuming a low mutation rate for a high-degree node, and thus this model appears to be biologically plausible.     

Topology-based cancer classification and related pathway mining using microarray data

Cancer classification is the critical basis for patient-tailored therapy, while pathway analysis is a promising method to discover the underlying molecular mechanisms related to cancer development by using microarray data. However, linking the molecular classification and pathway analysis with gene network approach has not been discussed yet. In this study, we developed a novel framework based on cancer class-specific gene networks for classification and pathway analysis. This framework involves a novel gene network construction, named ordering network, which exhibits the power-law node-degree distribution as seen in correlation networks. The results obtained from five public cancer datasets showed that the gene networks with ordering relationship are better than those with correlation relationship in terms of accuracy and stability of the classification performance. Furthermore, we integrated the ordering networks, classification information and pathway database to develop the topology-based pathway analysis for identifying cancer class-specific pathways, which might be essential in the biological significance of cancer. Our results suggest that the topology-based classification technology can precisely distinguish cancer subclasses and the topology-based pathway analysis can characterize the correspondent biochemical pathways even if there are subtle, but consistent, changes in gene expression, which may provide new insights into the underlying molecular mechanisms of tumorigenesis.     

Zipf's law in importance of genes for cancer classification using microarray data

Using a measure of how differentially expressed a gene is in two biochemically/phenotypically different conditions, we can rank all genes in a microarray dataset. We have shown that the falling-off of this measure (normalized maximum likelihood in a classification model such as logistic regression) as a function of the rank is typically a power-law function. This power-law function in other similar ranked plots are known as the Zipf's law, observed in many natural and social phenomena. The presence of this power-law function prevents an intrinsic cutoff point between the "important" genes and "irrelevant" genes. We have shown that similar power-law functions are also present in permuted dataset, and provide an explanation from the well-known chi(2) distribution of likelihood ratios. We discuss the implication of this Zipf's law on gene selection in a microarray data analysis, as well as other characterizations of the ranked likelihood plots such as the rate of fall-off of the likelihood.     

Reconstructing gene regulatory networks: from random to scale-free connectivity

The manipulation of organisms using combinations of gene knockout, RNAi and drug interaction experiments can be used to reveal regulatory interactions between genes. Several algorithms have been proposed that try to reconstruct the underlying regulatory networks from gene expression data sets arising from such experiments. Often these approaches assume that each gene has approximately the same number of interactions within the network, and the methods rely on prior knowledge, or the investigator's best guess, of the average network connectivity. Recent evidence points to scale-free properties in biological networks, however, where network connectivity follows a power-law distribution. For scale-free networks, the average number of regulatory interactions per gene does not satisfactorily characterise the network. With this in mind, a new reverse engineering approach is introduced that does not require prior knowledge of network connectivity and its performance is compared with other published algorithms using simulated gene expression data with biologically relevant network structures. Because this new approach does not make any assumptions about the distribution of network connections, it is suitable for application to scale-free networks.     

An assessment of preferential attachment as a mechanism for human sexual network formation

Recent research into the properties of human sexual-contact networks has suggested that the degree distribution of the contact graph exhibits power-law scaling. One notable property of this power-law scaling is that the epidemic threshold for the population disappears when the scaling exponent rho is in the range 2 < rho < or = 3. This property is of fundamental significance for the control of sexually transmitted diseases (STDs) such as HIV/AIDS since it implies that an STD can persist regardless of its transmissibility. A stochastic process, known as preferential attachment, that yields one form of power-law scaling has been suggested to underlie the scaling of sexual degree distributions. The limiting distribution of this preferential attachment process is the Yule distribution, which we fit using maximum likelihood to local network data from samples of three populations: (i) the Rakai district, Uganda; (ii) Sweden; and (iii) the USA. For all local networks but one, our interval estimates of the scaling parameters are in the range where epidemic thresholds exist. The estimate of the exponent for male networks in the USA is close to 3, but the preferential attachment model is a very poor fit to these data. We conclude that the epidemic thresholds implied by this model exist in both single-sex and two-sex epidemic model formulations. A strong conclusion that we derive from these results is that public health interventions aimed at reducing the transmissibility of STD pathogens, such as implementing condom use or high-activity anti-retroviral therapy, have the potential to bring a population below the epidemic transition, even in populations exhibiting large degrees of behavioural heterogeneity.     

Biology,Methodology or Chance? The Degree Distributions of Bipartite Ecological Networks

The distribution of the number of links per species, or degree distribution, is widely used as a summary of the topology of complex networks. Degree distributions have been studied in a range of ecological networks, including both mutualistic bipartite networks of plants and pollinators or seed dispersers and antagonistic bipartite networks of plants and their consumers. The shape of a degree distribution, for example whether it follows an exponential or power-law form, is typically taken to be indicative of the processes structuring the network. The skewed degree distributions of bipartite mutualistic and antagonistic networks are usually assumed to show that ecological or co-evolutionary processes constrain the relative numbers of specialists and generalists in the network. I show that a simple null model based on the principle of maximum entropy cannot be rejected as a model for the degree distributions in most of the 115 bipartite ecological networks tested here. The model requires knowledge of the number of nodes and links in the network, but needs no other ecological information. The model cannot be rejected for 159 (69%) of the 230 degree distributions of the 115 networks tested. It performed equally well on the plant and animal degree distributions, and cannot be rejected for 81 (70%) of the 115 plant distributions and 78 (68%) of the animal distributions. There are consistent differences between the degree distributions of mutualistic and antagonistic networks, suggesting that different processes are constraining these two classes of networks. Fit to the MaxEnt null model is consistently poor among the largest mutualistic networks. Potential ecological and methodological explanations for deviations from the model suggest that spatial and temporal heterogeneity are important drivers of the structure of these large networks.     

Build-up mechanisms determining the topology of mutualistic networks

The frequency distribution of the number of interactions per species (i.e., degree distribution) within plant-animal mutualistic assemblages often decays as a power-law with an exponential truncation. Such a truncation suggests that there are ecological factors limiting the frequency of supergeneralist species. However, it is not clear whether these patterns can emerge from intrinsic features of the interacting assemblages, such as differences between plant and animal species richness (richness ratio). Here, we show that high richness ratios often characterize plant-animal mutualisms. Then, we demonstrate that exponential truncations are expected in bipartite networks generated by a simple model that incorporates build-up mechanisms that lead to a high richness ratio. Our results provide a simple interpretation for the truncations commonly observed in the degree distributions of mutualistic networks that complements previous ones based on biological effects.     

The emergent properties of a dolphin social network

Many complex networks, including human societies, the Internet, the World Wide Web and power grids, have surprising properties that allow vertices (individuals, nodes, Web pages, etc.) to be in close contact and information to be transferred quickly between them. Nothing is known of the emerging properties of animal societies, but it would be expected that similar trends would emerge from the topology of animal social networks. Despite its small size (64 individuals), the Doubtful Sound community of bottlenose dolphins has the same characteristics. The connectivity of individuals follows a complex distribution that has a scale-free power-law distribution for large k. In addition, the ability for two individuals to be in contact is unaffected by the random removal of individuals. The removal of individuals with many links to others does affect the length of the 'information' path between two individuals, but, unlike other scale-free networks, it does not fragment the cohesion of the social network. These self-organizing phenomena allow the network to remain united, even in the case of catastrophic death events.     

Revisiting "scale-free" networks

Recent observations of power-law distributions in the connectivity of complex networks came as a big surprise to researchers steeped in the tradition of random networks. Even more surprising was the discovery that power-law distributions also characterize many biological and social networks. Many attributed a deep significance to this fact, inferring a "universal architecture" of complex systems. Closer examination, however, challenges the assumptions that (1) such distributions are special and (2) they signify a common architecture, independent of the system's specifics. The real surprise, if any, is that power-law distributions are easy to generate, and by a variety of mechanisms. The architecture that results is not universal, but particular; it is determined by the actual constraints on the system in question.     

Recent Progress on the Analysis of Power-law Features in Complex Cellular Networks

Complex interactions between different kinds of bio-molecules and essential nutrients are responsible for cellular functions. Rapid advances in theoretical modeling and experimental analyses have shown that drastically different biological and non-biological networks share a common architecture. That is, the probability that a selected node in the network has exactly k edges decays as a power-law. This finding has definitely opened an intense research and debate on the origin and implications of this ubiquitous pattern. In this review, we describe the recent progress on the emergence of power-law distributions in cellular networks. We first show the internal characteristics of the observed complex networks uncovered using graph theory. We then briefly review some works that have significantly contributed to the theoretical analysis of cellular networks and systems, from metabolic and protein networks to gene expression profiles. This prevalent topology observed in so many diverse biological systems suggests the existence of generic laws and organizing principles behind the cellular networks.     

Self-similarity and the relationship between abundance and range size

Patterns in the relationships among the range, abundance, and distribution of species within a biome are of fundamental interest in ecology. A self-similarity condition, imposed at the community level and previously demonstrated to lead to the power-law form of the species-area relationship, is extended to the species level and shown to predict testable power-law relationships between range size and both species abundance and area of census cell across scales of spatial resolution. The predicted slopes of plots of log(range size) versus log(abundance) are shown to be in good agreement with data from British breeding bird and mammal censuses and with data on the distribution of fern species in old-growth forest. The predicted slopes of plots of log(range size) versus log (area of census cell) are consistent with the limited available data for British plant species. Self-similarity provides a testable theoretical framework for a unified understanding of patterns among the range, abundance, and distribution of species.