SCIENCE OF COMPLEX NETWORKS: From Biology to the Internet and WWW: CNET 2004

Kinetic Theory of Random Graphs
View Description Hide DescriptionStatistical properties of evolving random graphs are analyzed using kinetic theory. Treating the linking process dynamically, structural characteristics of links, paths, cycles, and components are obtained analytically using the rate equation approach. Scaling laws for finite systems are derived using extreme statistics and scaling arguments.

Causal and homogeneous networks
View Description Hide DescriptionGrowing networks have a causal structure. We show that the causality strongly influences the scaling and geometrical properties of the network. In particular the average distance between nodes is smaller for causal networks than for corresponding homogeneous networks. We explain the origin of this effect and illustrate it using as an example a solvable model of random trees. We also discuss the issue of stability of the scale‐free node degree distribution. We show that a surplus of links may lead to the emergence of a singular node with the degree proportional to the total number of links. This effect is closely related to the backgammon condensation known from the balls‐in‐boxes model.

Evolving Weighted Scale‐Free Networks
View Description Hide DescriptionWe describe a set of simple stochastic and deterministic models of growing weighted scale‐free networks. In these networks, (i) new vertices are attached to ends of preferentially chosen weighted edges, and (ii) the weights of these edges are updated. Resulting networks have power‐law distributions of the edge weight, of the vertex degree, and of the vertex strength.

Self‐avoiding polymer chains
View Description Hide DescriptionAn explicit expression is derived for the distribution function of end‐to‐end vectors for a self‐avoiding polymer chain in a one‐dimensional space. This formula is applied to evaluate the effect of strength of excluded‐volume interactions on the mean‐square end‐to‐end distance.

How to calculate the main characteristics of random uncorrelated networks
View Description Hide DescriptionWe present an analytic formalism describing structural properties of random uncorrelated networks with arbitrary degree distributions. The formalism allows to calculate the main network characteristics like: the position of the phase transition at which a giant component first forms, the mean component size below the phase transition, the size of the giant component and the average path length above the phase transition. We apply the approach to classical random graphs of Erdös and Rényi, single‐scale networks with exponential degree distributions and scale‐free networks with arbitrary scaling exponents and structural cut‐offs. In all the cases we obtain a very good agreement between results of numerical simulations and our analytical predictions.

Universal dependence of distances on nodes degrees in complex networks
View Description Hide DescriptionWe have studied dependence of distances on node degrees between vertices of Erd ős‐Rényi random graphs, scale‐free Barabási‐Albert models, science collaboration networks, biological networks, Internet Autonomous Systems and public transport networks. We have observed that the mean distance between two nodes of degrees k_{i} and k_{j} equals to 〈l_{ij} 〉 = A − Blog(k_{i}k_{j} ). A simple heuristic theory for this scaling law is presented. Corrections due to the network clustering coefficient and node degree‐degree correlations are taken into account.

Scale‐Free properties of weighted random graphs: Minimum Spanning Trees and Percolation
View Description Hide DescriptionWe study Erdös‐Rényi random graphs with random weights associated with each link. In our approach, nodes connected by links having weights below the percolation threshold form clusters, and each cluster merges into a single node, thus generating a new “clusters network”. We show that this network is scale‐free with λ = 2.5. Furthermore, we show that optimization causes the percolation threshold to emerge spontaneously, thus creating naturally a scale‐free “clusters network”. This phenomenon may be related to the evolution of several real world scale‐free networks.
Our results imply that: (i) the minimum spanning tree (MST) in random graphs is composed of percolation clusters, which are interconnected by a set of links that create a scale‐free tree with λ = 2.5 (ii) the optimal path may be partitioned into segments that follow the percolation clusters, and the lengths of these segments grow exponentially with the number of clusters that are crossed (iii) the optimal path in scale‐free networks with λ < 3 scales as l _{ opt } ∼ logN, and the weights along the optimal path decay exponentially with their rank.

Network Dependence of the Dilemmas Of Cooperation
View Description Hide DescriptionEvolutionary game theory has become a powerful framework to investigate the evolution of cooperation. Games such as the prisoner’s dilemma or the snowdrift game are frequently used to model cooperation, and to study its emergence in the context of Darwinian evolution. Until recently, spatial structure was understood as one of the main mechanisms helping the sustainability of cooperation. However, recent results for the snowdrift game have cast serious doubts on the general applicability of this result. Here we show that cooperation may become the dominating strategy, both for the prisoner’s dilemma and the snowdrift game, depending on the underlying network of contacts between individuals. By recasting the problem in the framework of graph theory, and associating to the network of contacts graphs of Small‐World and Scale‐Free type, we demonstrate that graphs exhibiting power‐law degree distributions resulting from the mechanisms of growth and preferential attachment provide excellent conditions for cooperation to dominate. These results apply from very large population sizes down to communities with nearly one hundred individuals.

Weighted Configuration Model
View Description Hide DescriptionThe configuration model is one of the most successful models for generating uncorrelated random networks. We analyze its behavior when the expected degree sequence follows a power law with exponent smaller than two. In this situation, the resulting network can be viewed as a weighted network with non trivial correlations between strength and degree. Our results are tested against large scale numerical simulations, finding excellent agreement.

Characterizing Motifs in Weighted Complex Networks
View Description Hide DescriptionThe local structure of unweighted complex networks can be characterized by the occurrence frequencies of subgraphs in the network. Frequently occurring subgraphs, motifs, have been related to the functionality of many natural and man‐made networks. Here, we generalize this approach for weighted networks, presenting two novel measures: the intensity of a subgraph, defined as the geometric mean of its link weights, and the coherence , depicting the homogeneity of the weights. The concept of motif scores is then generalized to weighted networks using these measures. We also present a definition for the weighted clustering coefficient, which emerges naturally from the proposed framework. Finally, we demonstrate the concepts by applying them to financial and metabolic networks.

Random Feynman Graphs
View Description Hide DescriptionWe investigate a class of random graph ensembles based on the Feynman graphs of multidimensional integrals, representing statistical‐mechanical partition functions. We show that the resulting ensembles of random graphs strongly resemble those defined in random graphs with hidden color, generalizing the known relation of the Feynman graphs of simple one‐dimensional integrals to random graphs with a given degree distribution.

Self‐Organized‐Critical network dynamics
View Description Hide DescriptionWe introduce a simple model which describes in a stylized way the intertwined dynamics between the structure of a network and the intermittent congestion or breakdown events which might occur in it. In the networks we consider there is a tendency of randomly increasing the number of links which triggers an avalanche of rapid rewiring of the links. These avalanches shape the topology of the network which reaches a self‐organized‐critical state characterized by a scale‐free distribution of avalanche sizes and a degree distribution of the network which can have either a power‐law or exponential connectivity distribution depending on the details of the model.

Point Process Models of 1/f Noise and Internet Traffic
View Description Hide DescriptionWe present a simple model reproducing the long‐range autocorrelations and the power spectrum of the web traffic. The model assumes the traffic as Poisson flow of files with size distributed according to the power‐law. In this model the long‐range autocorrelations are independent of the network properties as well as of inter‐packet time distribution.

Parallel dynamics of disordered Ising spin systems on random graphs
View Description Hide DescriptionWe examine the non‐equilibrium dynamics of bond‐disordered Ising spin systems on random graphs with arbitrary degree distribution, using generating functional techniques. The dynamic order parameter is a measure describing the likelihood of a spin path, given a path of perturbations or external fields, which has a clear physical interpretation. For short times the order parameter set can be calculated exactly, while for longer times this is not possible and approximation schemes must be devised to study the dynamics. We study one such scheme and compare our results with simulations.

Entrainment of complex oscillator networks
View Description Hide DescriptionDynamics of random oscillator networks partly forced by a external pacemaker is numerically investigated. We find that the entrainment frequency window of a network decreases exponentially with its depth, defined as the mean forward distance of the elements from the pacemaker. Effectively, only shallow networks have the ability to be entrained by the pacemaker. The exponential dependence is also derived analytically as an approximation for large random asymmetric networks.

OSI Network‐layer Abstraction: Analysis of Simulation Dynamics and Performance Indicators
View Description Hide DescriptionThe Open Systems Interconnection (OSI) reference model provides a conceptual framework for communication among computers in a data communication network. The Network Layer of this model is responsible for the routing and forwarding of packets of data. We investigate the OSI Network Layer and develop an abstraction suitable for the study of various network performance indicators, e.g. throughput, average packet delay, average packet speed, average packet path‐length, etc. We investigate how the network dynamics and the network performance indicators are affected by various routing algorithms and by the addition of randomly generated links into a regular network connection topology of fixed size. We observe that the network dynamics is not simply the sum of effects resulting from adding individual links to the connection topology but rather is governed nonlinearly by the complex interactions caused by the existence of all randomly added and already existing links in the network. Data for our study was gathered using Netzwerk‐1, a C++ simulation tool that we developed for our abstraction.

Weighted networks are more synchronizable: how and why
View Description Hide DescriptionMost real‐world networks display not only a heterogeneous distribution of degrees, but also a heterogeneous distribution of weights in the strengths of the connections. Each of these heterogeneities alone has been shown to suppress synchronization in random networks of dynamical systems. Here we review our recent findings that complete synchronization is significantly enhanced and becomes independent of both distributions when the distribution of weights is suitably combined with the distribution of degrees. We also present new results addressing the optimality of our findings and extending our analysis to phase synchronization in networks of non‐identical dynamical unities.

A Method for Decentralised Optimisation in Networks
View Description Hide DescriptionWe outline a method for distributed Monte Carlo optimisation of computational problems in networks of agents, such as peer‐to‐peer networks of computers. The optimisation and messaging procedures are inspired by gossip protocols and epidemic data dissemination, and are decentralised, i.e. no central overseer is required. In the outlined method, each agent follows simple local rules and seeks for better solutions to the optimisation problem by Monte Carlo trials, as well as by querying other agents in its local neighbourhood. With proper network topology, good solutions spread rapidly through the network for further improvement. Furthermore, the system retains its functionality even in realistic settings where agents are randomly switched on and off.

Is Scale‐Free A Realistic Topology For Evolving Biochemical Networks?
View Description Hide DescriptionHow can a new incoming biochemical node measure the degree of nodes already present in a network and thus decide, on the basis of this counting, to preferentially connect with the more connected ones? Although such explicit comparison and choice is quite plausible in the case of manmade networks, leading the network to a scale‐free topology, it is much harder to conceive for biochemical networks such as reaction or protein interaction networks. In this paper, computer experiments of growing networks will be proposed as more elementary but more tractable versions of a long tradition of simulations of immune networks and chemical reaction networks described in past publications and largely forgotten since. These simulations will try to respect as simply and as far as possible basic biochemical characteristics such as the heterogeneity of biochemical nodes, the existence of natural hubs, the way nodes bind by mutual affinity, the significance of type‐based networks as compared with instance‐based ones and the consequent importance of the nodes concentration to the selection of the partners of the incoming nodes. A scale‐free topology will be discussed as a very unlikely outcome when compared with exponential decay obtained by a random growth. We will see that the presence of hubs and all the classical functional properties attributed to them (robustness, small‐world and epidemic propagation) might be perfectly compatible with an exponential shape obtained by less constrained growing rules. Initial conceptual issues are first discussed using simplified models and are validated by a more extensive framework based on the logical structure of biochemical systems that was defined for the simulation of dynamics and metadynamics of chemical reaction networks.