An exactly solvable model for the rewiring dynamics of weighted, directed networks is introduced. Simulations indicate that the model exhibits two types of condensation: (i) a phase in which, for each node, a finite fraction of its total out-strength condenses onto a single link; (ii) a phase in which a finite fraction of the total weight in the system is directed into a single node. A virtue of the model is that its dynamics can be mapped onto those of a zero-range process with many species of interacting particles-an exactly solvable model of particles hopping between the sites of a lattice. This mapping, which is described in detail, guides the analysis of the steady state of the network model and leads to theoretical predictions for the conditions under which the different types of condensation may be observed. A further advantage of the mapping is that, by exploiting what is known about exactly solvable generalizations of the zero-range process, one can infer a number of generalizations of the network model and dynamics which remain exactly solvable.

Keywords: condensation

Networked structures arise in a wide array of different contexts such as technological and transportation infrastructures, social phenomena, and biological systems. These highly interconnected systems have recently been the focus of a great deal of attention that has uncovered and characterized their topological complexity. Along with a complex topological structure, real networks display a large heterogeneity in the capacity and intensity of the connections. These features, however, have mainly not been considered in past studies where links are usually represented as binary states, i.e., either present or absent. Here, we study the scientific collaboration network and the world-wide air-transportation network, which are representative examples of social and large infrastructure systems, respectively. In both cases it is possible to assign to each edge of the graph a weight proportional to the intensity or capacity of the connections among the various elements of the network. We define appropriate metrics combining weighted and topological observables that enable us to characterize the complex statistical properties and heterogeneity of the actual strength of edges and vertices. This information allows us to investigate the correlations among weighted quantities and the underlying topological structure of the network. These results provide a better description of the hierarchies and organizational principles at the basis of the architecture of weighted networks.

We present a general model for the growth of weighted networks in which the structural growth is coupled with the edges' weight dynamical evolution. The model is based on a simple weight-driven dynamics and a weights' reinforcement mechanism coupled to the local network growth. That coupling can be generalized in order to include the effect of additional randomness and non-linearities which can be present in real-world networks. The model generates weighted graphs exhibiting the statistical properties observed in several real-world systems. In particular, the model yields a non-trivial time evolution of vertices properties and scale-free behavior with exponents depending on the microscopic parameters characterizing the coupling rules. Very interestingly, the generated graphs spontaneously achieve a complex hierarchical architecture characterized by clustering and connectivity correlations varying as a function of the vertices' degree.

We propose a model for the World Wide Web graph that couples the topological growth with the traffic's dynamical evolution. The model is based on a simple traffic-driven dynamics and generates weighted directed graphs exhibiting the statistical properties observed in the Web. In particular, the model yields a non-trivial time evolution of vertices and heavy-tail distributions for the topological and traffic properties. The generated graphs exhibit a complex architecture with a hierarchy of cohesiveness levels similar to those observed in the analysis of real data.

We propose a model for the growth of weighted networks that couples the establishment of new edges and vertices and the weights' dynamical evolution. The model is based on a simple weight-driven dynamics and generates networks exhibiting the statistical properties observed in several real-world systems. In particular, the model yields a nontrivial time evolution of vertices' properties and scale-free behavior for the weight, strength, and degree distributions.

Keywords: lattice theory; topology; evolution (biological)

Motivated by the empirical analysis of the air transportation system, we define a network model that includes geographical attributes along with topological and weight (traffic) properties. The introduction of geographical attributes is made by constraining the network in real space. Interestingly, the inclusion of geometrical features induces non-trivial correlations between the weights, the connectivity pattern and the actual spatial distances of vertices. The model also recovers the emergence of anomalous fluctuations in the betweenness-degree correlation function as first observed by Guimerà and Amaral (2004 Eur. Phys. J. B 38 381). The presented results suggest that the interplay between weight dynamics and spatial constraints is a key ingredient in order to understand the formation of real-world weighted networks.

We describe models and efficient algorithms for detecting groups (communities) functioning in communication networks which attempt to hide their functionality - hidden groups. Our results reveal the properties of the background network activity that make detection of the hidden group easy, as well as those that make it difficult.

Coupled biological and chemical systems, neural networks, social interacting species, the Internet and the World Wide Web, are only a few examples of systems composed by a large number of highly interconnected dynamical units. The first approach to capture the global properties of such systems is to model them as graphs whose nodes represent the dynamical units, and whose links stand for the interactions between them. On the one hand, scientists have to cope with structural issues, such as characterizing the topology of a complex wiring architecture, revealing the unifying principles that are at the basis of real networks, and developing models to mimic the growth of a network and reproduce its structural properties. On the other hand, many relevant questions arise when studying complex networks' dynamics, such as learning how a large ensemble of dynamical systems that interact through a complex wiring topology can behave collectively. We review the major concepts and results recently achieved in the study of the structure and dynamics of complex networks, and summarize the relevant applications of these ideas in many different disciplines, ranging from nonlinear science to biology, from statistical mechanics to medicine and engineering.

Worms are becoming increasingly hostile. The exponential growth of infection rates allows small outbreaks to have worldwide consequences within minutes. Moreover, the collateral damage caused by infections can cripple the entire Internet. While harmful, such behaviors have historically been short-lived. We assert the future holds much more caustic malware. Attacks based on mutation and covert propagation are likely to be ultimately more damaging and long lasting. This assertion is supported by observations of natural systems, where similarly behaving parasites represent by far the most successful class of living creatures. This talk considers a parasite for the Internet, providing biological metaphors for its behavior and demonstrating the structure of pathogens. Through simulation, we show that even with low infection rates, a mutating pathogen will eventually infect an entire community. We posit the inevitability of such parasites, and consider ways that they can be mitigated.

The systematic study of large-scale networks has unveiled the ubiquitous presence of connectivity patterns characterized by large-scale heterogeneities and unbounded statistical fluctuations. These features affect dramatically the behavior of the diffusion processes occurring on networks, determining the ensuing statistical properties of their evolution pattern and dynamics. In this article, we present a stochastic computational framework for the forecast of global epidemics that considers the complete worldwide air travel infrastructure complemented with census population data. We address two basic issues in global epidemic modeling: (i) we study the role of the large scale properties of the airline transportation network in determining the global diffusion pattern of emerging diseases; and (ii) we evaluate the reliability of forecasts and outbreak scenarios with respect to the intrinsic stochasticity of disease transmission and traffic flows. To address these issues we define a set of quantitative measures able to characterize the level of heterogeneity and predictability of the epidemic pattern. These measures may be used for the analysis of containment policies and epidemic risk assessment.

The systematic study of large-scale networks has unveiled the ubiquitous presence of connectivity patterns characterized by large-scale heterogeneities and unbounded statistical fluctuations. These features affect dramatically the behavior of the diffusion processes occurring on networks, determining the ensuing statistical properties of their evolution pattern and dynamics. In this article, we present a stochastic computational framework for the forecast of global epidemics that considers the complete worldwide air travel infrastructure complemented with census population data. We address two basic issues in global epidemic modeling: (i) we study the role of the large scale properties of the airline transportation network in determining the global diffusion pattern of emerging diseases; and (ii) we evaluate the reliability of forecasts and outbreak scenarios with respect to the intrinsic stochasticity of disease transmission and traffic flows. To address these issues we define a set of quantitative measures able to characterize the level of heterogeneity and predictability of the epidemic pattern. These measures may be used for the analysis of containment policies and epidemic risk assessment.

In real networks complex topological features are often associated with a diversity of interactions as measured by the weights of the links. Moreover, spatial constraints may as well play an important role, resulting in a complex interplay between topology, weight, and geography. In order to study the vulnerability of such networks to intentional attacks, these attributes must be therefore considered along with the topological quantities. In order to tackle this issue, we consider the case of the world-wide airport network, which is a weighted heterogeneous network whose evolution and structure are influenced by traffic and geographical constraints. We first characterize relevant topological and weighted centrality measures and then use these quantities as selection criteria for the removal of vertices. We consider different attack strategies and different measures of the damage achieved in the network. The analysis of weighted properties shows that centrality driven attacks are capable to shatter the network's communication or transport properties even at very low level of damage in the connectivity pattern. The inclusion of weight and traffic therefore provides evidence for the extreme vulnerability of complex networks to any targeted strategy and need to be considered as key features in the finding and development of defensive strategies.

We consider a class of simple, non-trivial models of evolving weighted scale-free networks. The network evolution in these models is determined by attachment of new vertices to ends of preferentially chosen weighted edges. Resulting networks have scale-free distributions of the edge weight, of the vertex degree, and of the vertex strength. We discuss situations where this mechanism operates. Apart of stochastic models of weighted networks, we introduce a wide class of deterministic, scale-free, weighted graphs with the small-world effect. We show also how one can easily construct an equilibrium weighted network by using a generalization of the configuration model.

We propose a network description of large market investments, where both stocks and shareholders are represented as vertices connected by weighted links corresponding to shareholdings. In this framework, the in-degree (k_in) and the sum of incoming link weights (v) of an investor correspond to the number of assets held (portfolio diversification) and to the invested wealth (portfolio volume), respectively. An empirical analysis of three different real markets reveals that the distributions of both k_in and v display power-law tails with exponents γ and α. Moreover, we find that k_in scales as a power-law function of v with an exponent β. Remarkably, despite the values of α, β and γ differ across the three markets, they are always governed by the scaling relation β=(1-α)/(1-γ). We show that these empirical findings can be reproduced by a recent model relating the emergence of scale-free networks to an underlying Paretian distribution of “hidden” vertex properties.

Evolutionary algorithms are very efficient tools to find a near-optimum solution in many cases. Until now they have been mostly used to find results but in this article we argue that evolutionary algorithms can also be used to simulate the evolution of complex systems. We model complex systems as networks in which agents are connected by edges if they interact with each other. It is known that many networks of this kind exhibit stable properties despite the dynamic processes they are subject to. We show here how evolutionary processes on complex systems can be modeled with a new kind of evolutionary algorithm which we have presented in [8]. We will show that some evolutionary processes within this framework yield networks with stable properties in reasonable time. An understanding of what kind of evolutionary processes will produce what kind of network properties in what time is vital to transfer evolutionary processes to technical ad-hoc networks in order to improve their flexibility and stability in quickly changing environments.

While the evolution of biological networks can be modeled sensefully as a series of mutation and selection, evolution of other networks such as the social network in a city or the network of streets in a country is not determined by selection since there is no alternative network with which these singular networks have to compete. Nonetheless, these singular networks do evolve due to dynamic changes of vertices and edges. In this article we present a formal, analyzable framework for the evolution of singular networks. We show that the careful design of adaptation rules can lead to the emergence of network topologies with satisfying performance in polynomial time while other adaptation rules yield exponential runtime. We further show by example how the framework could be applied to some ad-hoc communication scenarios.

Many social, technological, biological and economical systems are best described by weighted networks, whose properties and dynamics depend not only on their structures but also on the connection weights among their nodes. However, most existing research work on complex network models are concentrated on network structures, with connection weights among their nodes being either 1 or 0. In this paper, we propose a new weighted evolving network model. Numerical simulations indicate that this network model yields three power-law distributions for the node degrees, connection weights and node strengths, respectively. Particularly, some other properties of the distributions, such as the droop-head and heavy-tail effects, can also be reflected by this model.

We consider the computer network as a complex, interacting system and present a novel approach to representing anomalous events that occur within the network. This approach is essentially a form of intelligent data reduction that facilitates scalable monitoring of large systems. Specifically, we develop macrostate descriptions of complex networked systems in situations where exact microstate parameters of each element in the system preclude global understanding from first principles. This aids in identifying violations of network policy such as network attacks and misconfigurations. This approach has been verified in several environments. Example responses from network attacks simulated in the laboratory including those contained in the DARPA Lincoln Lab IDS test data as well as from operational network traffic are presented. These results suggest that our approach presents a unique perspective on anomalies in computer network traffic.

A network is said to show assortative mixing if the nodes in the network that have many connections tend to be connected to other nodes with many connections. Here we measure mixing patterns in a variety of networks and find that social networks are mostly assortatively mixed, but that technological and biological networks tend to be disassortative. We propose a model of an assortatively mixed network, which we study both analytically and numerically. Within this model we find that networks percolate more easily if they are assortative and that they are also more robust to vertex removal.

When the probability of measuring a particular value of some quantity varies inversely as a power of that value, the quantity is said to follow a power law, also known variously as Zipf's law or the Pareto distribution. Power laws appear widely in physics, biology, earth and planetary sciences, economics and finance, computer science, demography and the social sciences. For instance, the distributions of the sizes of cities, earthquakes, solar flares, moon craters, wars and people's personal fortunes all appear to follow power laws. The origin of power-law behaviour has been a topic of debate in the scientific community for more than a century. Here we review some of the empirical evidence for the existence of power-law forms and the theories proposed to explain them.

The description of the Internet topology is an important open problem, recently tackled with the introduction of scale-free networks. We focus on the topological and dynamical properties of real Internet maps in a three-year time interval. We study higher order correlation functions as well as the dynamics of several quantities. We find that the Internet is characterized by nontrivial correlations among nodes and different dynamical regimes. We point out the importance of node hierarchy and aging in the Internet structure and growth. Our results provide hints towards the realistic modeling of the Internet evolution.

Over the last decade, an enormous interest and activity in complex networks have been witnessed within the physics community. On the other hand, diffusion and its theory have equipped the toolbox of the physicist for decades. In this paper, we will demonstrate how to combine these two seemingly different topics in a fruitful manner. In particular, we will review and develop further an auxiliary diffusive process on weighted networks that represents a powerful concept and tool for studying network (community) structures. The working principle of the method is the observation that the relaxation of the diffusive process toward the stationary state is non-local and fastest in the highly connected regions of the network. This can be used to acquire non-trivial information about the structure of clustered and non-clustered networks.

For most complex networks, the connection between a pair of nodes is the result of their mutual affinity and attachment. In this letter, we will propose a mutual attraction model to characterize weighted evolving networks. By introducing the initial attractiveness A and the general mechanism of mutual attraction (controlled by parameter m), our model can naturally reproduce scale-free distributions of degree, weight, and strength, as found in many real systems. Also, simulation results are consistent with theoretical predictions. Interestingly, we obtain nontrivial clustering coefficient C and tunable degree assortativity r, depending on the values of m and A. Our model appears as a more general one that unifies the characterization of both assortative and disassortative weighted networks.

Keywords: large-scale systems; graph theory