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

Laplacian spectra as a diagnostic tool for network structure and dynamics

We examine numerically the three-way relationships among structure, Laplacian spectra, and frequency synchronization dynamics on complex networks. We study the effects of clustering, degree distribution, and a particular type of coupling asymmetry (input normalization), all of which are known to have effects on the synchronizability of oscillator networks. We find that these topological factors produce marked signatures in the Laplacian eigenvalue distribution and in the localization properties of individual eigenvectors. Using a set of coordinates based on the Laplacian eigenvectors as a diagnostic tool for synchronization dynamics, we find that the process of frequency synchronization can be visualized as a series of quasi-independent transitions involving different normal modes. Particular features of the partially synchronized state can be understood in terms of the behavior of particular modes or groups of modes. For example, there are important partially synchronized states in which a set of low-lying modes remain unlocked while those in the main spectral peak are locked. We find therefore that spectra are correlated with dynamics in ways that go beyond results relating a single threshold to a single extremal eigenvalue.

Disordered ensembles of random matrices

It is shown that the families of generalized matrix ensembles recently considered which give rise to an orthogonal invariant stable Lévy ensemble can be generated by the simple procedure of dividing Gaussian matrices by a random variable. The nonergodicity of this kind of disordered ensembles is investigated. It is shown that the same procedure applied to random graphs gives rise to a family that interpolates between the Erdös-Renyi and the scale free models.

Quantum transport on small-world networks: a continuous-time quantum walk approach

We consider the quantum mechanical transport of (coherent) excitons on small-world networks (SWNs). The SWNs are built from a one-dimensional ring of N nodes by randomly introducing B additional bonds between them. The exciton dynamics is modeled by continuous-time quantum walks, and we evaluate numerically the ensemble-averaged transition probability to reach any node of the network from the initially excited one. For sufficiently large B we find that the quantum mechanical transport through the SWNs is, first, very fast, given that the limiting value of the transition probability is reached very quickly, and second, that the transport does not lead to equipartition, given that on average the exciton is most likely to be found at the initial node.

Approximating the largest eigenvalue of network adjacency matrices

The largest eigenvalue of the adjacency matrix of a network plays an important role in several network processes (e.g., synchronization of oscillators, percolation on directed networks, and linear stability of equilibria of network coupled systems). In this paper we develop approximations to the largest eigenvalue of adjacency matrices and discuss the relationships between these approximations. Numerical experiments on simulated networks are used to test our results.

Random matrix analysis of complex networks

We study complex networks under random matrix theory (RMT) framework. Using nearest-neighbor and next-nearest-neighbor spacing distributions we analyze the eigenvalues of the adjacency matrix of various model networks, namely, random, scale-free, and small-world networks. These distributions follow the Gaussian orthogonal ensemble statistic of RMT. To probe long-range correlations in the eigenvalues we study spectral rigidity via the Delta_{3} statistic of RMT as well. It follows RMT prediction of linear behavior in semilogarithmic scale with the slope being approximately 1pi;{2} . Random and scale-free networks follow RMT prediction for very large scale. A small-world network follows it for sufficiently large scale, but much less than the random and scale-free networks.

Universality in complex networks: random matrix analysis

We apply random matrix theory to complex networks. We show that nearest neighbor spacing distribution of the eigenvalues of the adjacency matrices of various model networks, namely scale-free, small-world, and random networks follow universal Gaussian orthogonal ensemble statistics of random matrix theory. Second, we show an analogy between the onset of small-world behavior, quantified by the structural properties of networks, and the transition from Poisson to Gaussian orthogonal ensemble statistics, quantified by Brody parameter characterizing a spectral property. We also present our analysis for a protein-protein interaction network in budding yeast.

Ensemble averageability in network spectra

The extreme eigenvalues of connectivity matrices govern the influence of the network structure on a number of network dynamical processes. A fundamental open question is whether the eigenvalues of large networks are well represented by ensemble averages. Here we investigate this question explicitly and validate the concept of ensemble averageability in random scale-free networks by showing that the ensemble distributions of extreme eigenvalues converge to peaked distributions as the system size increases. We discuss the significance of this result using synchronization and epidemic spreading as example processes.

Diversity of graphs with highly variable connectivity

A popular approach for describing the structure of many complex networks focuses on graph theoretic properties that characterize their large-scale connectivity. While it is generally recognized that such descriptions based on aggregate statistics do not uniquely characterize a particular graph and also that many such statistical features are interdependent, the relationship between competing descriptions is not entirely understood. This paper lends perspective on this problem by showing how the degree sequence and other constraints (e.g., connectedness, no self-loops or parallel edges) on a particular graph play a primary role in dictating many features, including its correlation structure. Building on recent work, we show how a simple structural metric characterizes key differences between graphs having the same degree sequence. More broadly, we show how the (often implicit) choice of a background set against which to measure graph features has serious implications for the interpretation and comparability of graph theoretic descriptions.

Functional integration of ecological networks through pathway proliferation

Large-scale structural patterns commonly occur in network models of complex systems including a skewed node degree distribution and small-world topology. These patterns suggest common organizational constraints and similar functional consequences. Here, we investigate a structural pattern termed pathway proliferation. Previous research enumerating pathways that link species determined that as pathway length increases, the number of pathways tends to increase without bound. We hypothesize that this pathway proliferation influences the flow of energy, matter, and information in ecosystems. In this paper, we clarify the pathway proliferation concept, introduce a measure of the node-node proliferation rate, describe factors influencing the rate, and characterize it in 17 large empirical food-webs. During this investigation, we uncovered a modular organization within these systems. Over half of the food-webs were composed of one or more subgroups that were strongly connected internally, but weakly connected to the rest of the system. Further, these modules had distinct proliferation rates. We conclude that pathway proliferation in ecological networks reveals subgroups of species that will be functionally integrated through cyclic indirect effects.

Random walks along the streets and canals in compact cities: spectral analysis, dynamical modularity, information, and statistical mechanics

Different models of random walks on the dual graphs of compact urban structures are considered. Analysis of access times between streets helps to detect the city modularity. The statistical mechanics approach to the ensembles of lazy random walkers is developed. The complexity of city modularity can be measured by an information-like parameter which plays the role of an individual fingerprint of Genius loci. Global structural properties of a city can be characterized by the thermodynamic parameters calculated in the random walk problem.

Synchronizabilities of networks: a new index

The random matrix theory is used to bridge the network structures and the dynamical processes defined on them. We propose a possible dynamical mechanism for the enhancement effect of network structures on synchronization processes, based upon which a dynamic-based index of the synchronizability is introduced in the present paper.

Complex networks and simple models in biology

The analysis of molecular networks, such as transcriptional, metabolic and protein interaction networks, has progressed substantially because of the power of models from statistical physics. Increasingly, the data are becoming so detailed--though not always complete or correct--that the simple models are reaching the limits of their usefulness. Here, we will discuss how network information can be described and to some extent quantified. In particular statistics offers a range of tools, such as model selection, which have not yet been widely applied in the analysis of biological networks. We will also outline a number of present challenges posed by biological network data in systems biology, and the extent to which these can be addressed by new developments in statistics, physics and applied mathematics.

Synchronization reveals topological scales in complex networks

We study the relationship between topological scales and dynamic time scales in complex networks. The analysis is based on the full dynamics towards synchronization of a system of coupled oscillators. In the synchronization process, modular structures corresponding to well-defined communities of nodes emerge in different time scales, ordered in a hierarchical way. The analysis also provides a useful connection between synchronization dynamics, complex networks topology, and spectral graph analysis.

Speed of synchronization in complex networks of neural oscillators: analytic results based on Random Matrix Theory

We analyze the dynamics of networks of spiking neural oscillators. First, we present an exact linear stability theory of the synchronous state for networks of arbitrary connectivity. For general neuron rise functions, stability is determined by multiple operators, for which standard analysis is not suitable. We describe a general nonstandard solution to the multioperator problem. Subsequently, we derive a class of neuronal rise functions for which all stability operators become degenerate and standard eigenvalue analysis becomes a suitable tool. Interestingly, this class is found to consist of networks of leaky integrate-and-fire neurons. For random networks of inhibitory integrate-and-fire neurons, we then develop an analytical approach, based on the theory of random matrices, to precisely determine the eigenvalue distributions of the stability operators. This yields the asymptotic relaxation time for perturbations to the synchronous state which provides the characteristic time scale on which neurons can coordinate their activity in such networks. For networks with finite in-degree, i.e., finite number of presynaptic inputs per neuron, we find a speed limit to coordinating spiking activity. Even with arbitrarily strong interaction strengths neurons cannot synchronize faster than at a certain maximal speed determined by the typical in-degree.

Bump formation in a binary attractor neural network

The conditions for the formation of local bumps in the activity of binary attractor neural networks with spatially dependent connectivity are investigated. We show that these formations are observed when asymmetry between the activity during the retrieval and learning is imposed. An analytical approximation for the order parameters is derived. The corresponding phase diagram shows a relatively large and stable region where this effect is observed, although critical storage and information capacities drastically decrease inside that region. We demonstrate that the stability of the network, when starting from the bump formation, is larger than the stability when starting even from the whole pattern. Finally, we show a very good agreement between the analytical results and the simulations performed for different topologies of the network.

Spectral properties of disordered fully connected graphs

The spectral properties of disordered fully connected graphs with a special type of node-node interactions are investigated. The approximate analytical expression for the ensemble-averaged spectral density for the Hamiltonian defined on the fully connected graph is derived and analyzed for both the electronic and vibrational problems which can be related to the contact process and to the problem of stochastic diffusion, respectively. It is demonstrated how to evaluate the extreme eigenvalues and use them for finding the lower-bound estimates of the critical parameter for the contact process on the disordered fully connected graphs.

SpectralNET--an application for spectral graph analysis and visualization

Background

Graph theory provides a computational framework for modeling a variety of datasets including those emerging from genomics, proteomics, and chemical genetics. Networks of genes, proteins, small molecules, or other objects of study can be represented as graphs of nodes (vertices) and interactions (edges) that can carry different weights. SpectralNET is a flexible application for analyzing and visualizing these biological and chemical networks.

Results

Available both as a standalone .NET executable and as an ASP.NET web application, SpectralNET was designed specifically with the analysis of graph-theoretic metrics in mind, a computational task not easily accessible using currently available applications. Users can choose either to upload a network for analysis using a variety of input formats, or to have SpectralNET generate an idealized random network for comparison to a real-world dataset. Whichever graph-generation method is used, SpectralNET displays detailed information about each connected component of the graph, including graphs of degree distribution, clustering coefficient by degree, and average distance by degree. In addition, extensive information about the selected vertex is shown, including degree, clustering coefficient, various distance metrics, and the corresponding components of the adjacency, Laplacian, and normalized Laplacian eigenvectors. SpectralNET also displays several graph visualizations, including a linear dimensionality reduction for uploaded datasets (Principal Components Analysis) and a non-linear dimensionality reduction that provides an elegant view of global graph structure (Laplacian eigenvectors).

Conclusion

SpectralNET provides an easily accessible means of analyzing graph-theoretic metrics for data modeling and dimensionality reduction. SpectralNET is publicly available as both a .NET application and an ASP.NET web application from . Source code is available upon request.

Scaling invariance in spectra of complex networks: a diffusion factorial moment approach

A new method called diffusion factorial moment is used to obtain scaling features embedded in the spectra of complex networks. For an Erdos-Renyi network with connecting probability p(ER) < 1/N, the scaling parameter is delta = 0.51, while for p(ER) > or = 1/N the scaling parameter deviates from it significantly. For WS small-world networks, in the special region p(r) element of [0.05,0.2], typical scale invariance is found. For growing random networks, in the range of theta element of [0.33,049], we have delta = 0.6 +.- 0.1. And the value of delta oscillates around delta = 0.6 abruptly. In the range of delta element of [0.54,1], we have basically element of > 0.7. Scale invariance is one of the common features of the three kinds of networks, which can be employed as a global measurement of complex networks in a unified way.

Subgraph centrality in complex networks

We introduce a new centrality measure that characterizes the participation of each node in all subgraphs in a network. Smaller subgraphs are given more weight than larger ones, which makes this measure appropriate for characterizing network motifs. We show that the subgraph centrality [C(S)(i)] can be obtained mathematically from the spectra of the adjacency matrix of the network. This measure is better able to discriminate the nodes of a network than alternate measures such as degree, closeness, betweenness, and eigenvector centralities. We study eight real-world networks for which C(S)(i) displays useful and desirable properties, such as clear ranking of nodes and scale-free characteristics. Compared with the number of links per node, the ranking introduced by C(S)(i) (for the nodes in the protein interaction network of S. cereviciae) is more highly correlated with the lethality of individual proteins removed from the proteome.

A theoretical and experimental investigation of graph theoretical measures for land development in satellite imagery

Today's commercial satellite images enable experts to classify region types in great detail. In previous work, we considered discriminating rural and urban regions [23]. However, a more detailed classification is required for many purposes. These fine classifications assist government agencies in many ways including urban planning, transportation management, and rescue operations. In a step toward the automation of the fine classification process, this paper explores graph theoretical measures over grayscale images. The graphs are constructed by assigning photometric straight line segments to vertices, while graph edges encode their spatial relationships. We then introduce a set of measures based on various properties of the graph. These measures are nearly monotonic (positively correlated) with increasing structure (organization) in the image. Thus, increased cultural activity and land development are indicated by increases in these measures-without explicit extraction of road networks, buildings, residences, etc. These latter, time consuming (and still only partially automated) tasks can be restricted only to "promising" image regions, according to our measures. In some applications our measures may suffice. We present a theoretical basis for the measures followed by extensive experimental results in which the measures are first compared to manual evaluations of land development. We then present and test a method to focus on, and (pre)extract, suburban-style residential areas. These are of particular importance in many applications, and are especially difficult to extract. In this work, we consider commercial IKONOS data. These images are orthorectified to provide a fixed resolution of 1 meter per pixel on the ground. They are, therefore, metric in the sense that ground distance is fixed in scale to pixel distance. Our data set is large and diverse, including sea and coastline, rural, forest, residential, industrial, and urban areas.

Spectral analysis of protein-protein interactions in Drosophila melanogaster

Within a case study on the protein-protein interaction network (PIN) of Drosophila melanogaster we investigate the relation between the network's spectral properties and its structural features. The frequencies of loops of any size within the network can be derived from the spectrum; also the prevalence of specific subgraphs as a result of the network's evolutionary history affects its spectrum. The discrete part of the spectral density shows fingerprints of the PIN's topological features including a preference for loop structures. Duplicate nodes are also characteristic for PINs and we discuss their representation in the PIN's spectrum as well as their biological implications.

Vibrational modes and spectrum of oscillators on a scale-free network

We study vibrational modes and spectrum of a model system of atoms and springs on a scale-free network where we assume that the atoms and springs are distributed as nodes and links of a scale-free network. To understand the nature of excitations with many degrees of freedom on the scale-free network, we adopt a particular model that we assign the mass M(i) and the specific oscillation frequency omega(i) of the ith atom and the spring constant K(ij) between the ith and jth atoms. We show that the density of states of the spectrum follows a scaling law P (omega(2)) proportional, variant (omega(2))(-gamma), where gamma = 3 and that as the number of nodes N is increasing, the maximum eigenvalue grows as fast as sqrt[N].

Exactly solvable scale-free network model

We study a deterministic scale-free network recently proposed by Barabási, Ravasz, and Vicsek. We find that there are two types of nodes: the hub and rim nodes, which form a bipartite structure of the network. We first derive the exact numbers P (k) of nodes with degree k for the hub and rim nodes in each generation of the network, respectively. Using this, we obtain the exact exponents of the distribution function P (k) of nodes with k degree in the asymptotic limit of k-->infinity . We show that the degree distribution for the hub nodes exhibits the scale-free nature, P (k) proportional to k(-gamma) with gamma=ln 3/ln 2=1.584 962 , while the degree distribution for the rim nodes is given by P(k) proportional to e(-gamma'k) with gamma' =ln (3/2) =0.405 465 . Second, we analytically calculate the second-order average degree of nodes, d(-) . Third, we numerically as well as analytically calculate the spectra of the adjacency matrix A for representing topology of the network. We also analytically obtain the exact number of degeneracies at each eigenvalue in the network. The density of states (i.e., the distribution function of eigenvalues) exhibits the fractal nature with respect to the degeneracy. Fourth, we study the mathematical structure of the determinant of the eigenequation for the adjacency matrix. Fifth, we study hidden symmetry, zero modes, and its index theorem in the deterministic scale-free network. Finally, we study the nature of the maximum eigenvalue in the spectrum of the deterministic scale-free network. We will prove several theorems for it, using some mathematical theorems. Thus, we show that most of all important quantities in the network theory can be analytically obtained in the deterministic scale-free network model of Barabási, Ravasz, and Vicsek. Therefore, we may call this network model the exactly solvable scale-free network.

Spectral analysis and the dynamic response of complex networks

The eigenvalues and eigenvectors of the connectivity matrix of complex networks contain information about its topology and its collective behavior. In particular, the spectral density rho(lambda) of this matrix reveals important network characteristics: random networks follow Wigner's semicircular law whereas scale-free networks exhibit a triangular distribution. In this paper we show that the spectral density of hierarchical networks follows a very different pattern, which can be used as a fingerprint of modularity. Of particular importance is the value rho(0), related to the homeostatic response of the network: it is maximum for random and scale-free networks but very small for hierarchical modular networks. It is also large for an actual biological protein-protein interaction network, demonstrating that the current leading model for such networks is not adequate.

Network synchronization, diffusion, and the paradox of heterogeneity

Many complex networks display strong heterogeneity in the degree (connectivity) distribution. Heterogeneity in the degree distribution often reduces the average distance between nodes but, paradoxically, may suppress synchronization in networks of oscillators coupled symmetrically with uniform coupling strength. Here we offer a solution to this apparent paradox. Our analysis is partially based on the identification of a diffusive process underlying the communication between oscillators and reveals a striking relation between this process and the condition for the linear stability of the synchronized states. We show that, for a given degree distribution, the maximum synchronizability is achieved when the network of couplings is weighted and directed and the overall cost involved in the couplings is minimum. This enhanced synchronizability is solely determined by the mean degree and does not depend on the degree distribution and system size. Numerical verification of the main results is provided for representative classes of small-world and scale-free networks.

Topological approach to neural complexity

Considerable effort in modern statistical physics is devoted to the study of networked systems. One of the most important example of them is the brain, which creates and continuously develops complex networks of correlated dynamics. An important quantity which captures fundamental aspects of brain network organization is the neural complexity C(X) introduced by Tononi et al. [Proc. Natl. Acad. Sci. USA 91, 5033 (1994)]. This work addresses the dependence of this measure on the topological features of a network in the case of a Gaussian stationary process. Both analytical and numerical results show that the degree of complexity has a clear and simple meaning from a topological point of view. Moreover, the analytical result offers a straightforward and faster algorithm to compute the complexity of a graph than the standard one.

Properties of dense partially random graphs

We study the properties of random graphs where for each vertex a neighborhood has been previously defined. The probability of an edge joining two vertices depends on whether the vertices are neighbors or not, as happens in small-world graphs (SWG's). But we consider the case where the average degree of each node is of order of the size of the graph (unlike SWG's, which are sparse). This allows us to calculate the mean distance and clustering, which are qualitatively similar (although not in such a dramatic scale range) to the case of SWG's. We also obtain analytically the distribution of eigenvalues of the corresponding adjacency matrices. This distribution is discrete for large eigenvalues and continuous for small eigenvalues. The continuous part of the distribution follows a semicircle law, whose width is proportional to the "disorder" of the graph, whereas the discrete part is simply a rescaling of the spectrum of the substrate. We apply our results to the calculation of the mixing rate and the synchronizability threshold.

Dynamical scaling behavior of percolation clusters in scale-free networks

In this work we investigate the spectra of Laplacian matrices that determine many dynamic properties of scale-free networks below and at the percolation threshold. We use a replica formalism to develop analytically, based on an integral equation, a systematic way to determine the ensemble averaged eigenvalue spectrum for a general type of treelike networks. Close to the percolation threshold we find characteristic scaling functions for the density of states rho(lambda) of scale-free networks. rho(lambda) shows characteristic power laws rho (lambda) approximately lambda (alpha(1) ) or rho (lambda) approximately lambda (d(2) ) for small lambda, where alpha(1) holds below and alpha(2) at the percolation threshold. In the range where the spectra are accessible from a numerical diagonalization procedure the two methods lead to very similar results.

Temporal series analysis approach to spectra of complex networks

The spacing of nearest levels of the spectrum of a complex network can be regarded as a time series. Joint use of the multifractal detrended fluctuation approach (MF-DFA) and diffusion entropy (DE) is employed to extract characteristics from this time series. For the Watts-Strogatz small-world model, there exists a critical point at rewiring probability P(r) =0.32. For a network generated in the range 0< P(r) <0.32, the correlation exponent is in the range of 1.0-1.64. Above this critical point, all the networks behave similar to that at p(r) =1. For the Erdos-Renyi model, the time series behaves like fractional Brownian motion noise at p(ER) =1/N. For the growing random network (GRN) model, the values of the long-range correlation exponent are in the range of 0.74-0.83. For most of the GRN networks the probability distribution function of a constructed time series obeys a Gaussian form. In the joint use of MF-DFA and DE, the shuffling procedure in DE is essential to obtain a reliable result.

Return times of random walk on generalized random graphs

Random walks are used for modeling various dynamics in, for example, physical, biological, and social contexts. Furthermore, their characteristics provide us with useful information on the phase transition and critical phenomena of even broader classes of related stochastic models. Abundant results are obtained for random walk on simple graphs such as the regular lattices and the Cayley trees. However, random walks and related processes on more complex networks, which are often more relevant in the real world, are still open issues, possibly yielding different characteristics. In this paper, we investigate the return times of random walks on random graphs with arbitrary vertex degree distributions. We analytically derive the distributions of the return times. The results are applied to some types of networks and compared with numerical data.

Spectra of complex networks

We propose a general approach to the description of spectra of complex networks. For the spectra of networks with uncorrelated vertices (and a local treelike structure), exact equations are derived. These equations are generalized to the case of networks with correlations between neighboring vertices. The tail of the density of eigenvalues rho(lambda) at large /lambda/ is related to the behavior of the vertex degree distribution P(k) at large k. In particular, as P(k) approximately k(-gamma), rho(lambda) approximately /lambda/(1-2 gamma). We propose a simple approximation, which enables us to calculate spectra of various graphs analytically. We analyze spectra of various complex networks and discuss the role of vertices of low degree. We show that spectra of locally treelike random graphs may serve as a starting point in the analysis of spectral properties of real-world networks, e.g., of the Internet.

Modularity and extreme edges of the internet

We study the spectral properties of a diffusion process taking place on the Internet network focusing on the slowest decaying modes. These modes identify an underlying modular structure roughly corresponding to individual countries. For instance, in the slowest decaying mode the diffusion current flows from Russia to U.S. military sites. Quantitatively the modular structure manifests itself in a 10 times larger participation ratio of its slow decaying modes compared to a random scale-free network. We propose to use the fraction of nodes participating in slow decaying modes as a general measure of the modularity of a network. For the 100 slowest decaying modes of the Internet this fraction is approximately 30%. Finally, we suggest that the degree of isolation of an individual module can be assessed by comparing its participation in different diffusion modes.

Giant clusters in random ad hoc networks

The present paper introduces ad hoc communication networks as examples of large scale real networks that can be prospected by statistical means. A description of giant cluster formation based on a single parameter of node neighbor numbers is given along with the discussion of some asymptotic aspects of giant cluster sizes.

Mixing patterns in networks

We study assortative mixing in networks, the tendency for vertices in networks to be connected to other vertices that are like (or unlike) them in some way. We consider mixing according to discrete characteristics such as language or race in social networks and scalar characteristics such as age. As a special example of the latter we consider mixing according to vertex degree, i.e., according to the number of connections vertices have to other vertices: do gregarious people tend to associate with other gregarious people? We propose a number of measures of assortative mixing appropriate to the various mixing types, and apply them to a variety of real-world networks, showing that assortative mixing is a pervasive phenomenon found in many networks. We also propose several models of assortatively mixed networks, both analytic ones based on generating function methods, and numerical ones based on Monte Carlo graph generation techniques. We use these models to probe the properties of networks as their level of assortativity is varied. In the particular case of mixing by degree, we find strong variation with assortativity in the connectivity of the network and in the resilience of the network to the removal of vertices.

Extreme self-organization in networks constructed from gene expression data

We study networks constructed from gene expression data obtained from many types of cancers. The networks are constructed by connecting vertices that belong to each others' list of K nearest neighbors, with K being an a priori selected non-negative integer. We introduce an order parameter for characterizing the homogeneity of the networks. On minimizing the order parameter with respect to K, degree distribution of the networks shows power-law behavior in the tails with an exponent of unity. Analysis of the eigenvalue spectrum of the networks confirms the presence of the power-law and small-world behavior. We discuss the significance of these findings in the context of evolutionary biological processes.

Evolving networks with distance preferences

We study evolving networks where new nodes when attached to the network form links with other nodes of preferred distances. A particular case is where always the shortest distances are selected ("make friends with the friends of your present friends"). We present simulation results for network parameters like the first eigenvalue of the graph Laplacian (synchronizability), clustering coefficients, average distances, and degree distributions for different distance preferences and compare them with the parameter values for random and scale-free networks. We find that for the shortest distance rule we obtain a power-law degree distribution as in scale-free networks, while the other parameters are significantly different, especially the clustering coefficient.

Scale-free network model of node and connection diversity

A network model with node and connection diversity is proposed in this paper. Distinctly from to other models whose nodes and connections are represented by identical simple points and lines, we investigate inhomogeneous networks with two kinds of sites and link by growth of preferential attachment. Scale-free networks with varied centralizations and exponents (ranging from 2.0 to theoretically infinity) are obtained, and the influences of the relative ratio of the two kinds of sites p, the number of links connected from each site m, and initial attractiveness delta are studied. A mean-field theory that agrees well with our numerical results was proposed and analyzed. The theory gives the analytical scaling exponent of the form gamma=2+p+delta/m-delta(1-p)/(mp+m+delta).

Pseudofractal scale-free web

We find that scale-free random networks are excellently modeled by simple deterministic graphs. Our graph has a discrete degree distribution (degree is the number of connections of a vertex), which is characterized by a power law with exponent gamma=1+ln 3/ln 2. Properties of this compact structure are surprisingly close to those of growing random scale-free networks with gamma in the most interesting region, between 2 and 3. We succeed to find exactly and numerically with high precision all main characteristics of the graph. In particular, we obtain the exact shortest-path-length distribution. For a large network (ln N>>1) the distribution tends to a Gaussian of width approximately sqrt[ln N] centered at (-)l approximately ln N. We show that the eigenvalue spectrum of the adjacency matrix of the graph has a power-law tail with exponent 2+gamma.

Crashes, recoveries, and "core shifts" in a model of evolving networks

A model of an evolving network of interacting molecular species is shown to exhibit repeated rounds of crashes in which several species get rapidly depopulated, followed by recoveries. The network inevitably self- organizes into an autocatalytic structure, which consists of an irreducible "core" surrounded by a parasitic "periphery." Crashes typically occur when the existing autocatalytic set becomes fragile and suffers a "core shift," defined graph theoretically. The nature of the recovery after a crash, in particular, the time of recovery, depends upon the organizational structure that survives the crash. The largest eigenvalue of the adjacency matrix of the graph is an important signal of network fragility or robustness.