The network of commuters in London

We have studied the directed and weighted network in which the wards of London are vertices and two vertices are connected whenever there is at least one person commuting to work from one ward to another. Remarkably the in-strength and in-degree distribution tail is a power law with exponent around −2, while the out-strength and out-degree distribution tail is exponential. We propose a simple square lattice model to explain the observed empirical behaviour.     

A very fast algorithm for detecting community structures in complex networks

In this paper, a new algorithm is proposed, which uses only local information to analyze community structures in complex networks. The algorithm is based on a table that describes a network and a virtual cache similar to the cache in the computer structure. When being tested on some typical computer-generated and real-world networks, this algorithm demonstrates excellent detection results and very fast processing performance, much faster than the existing comparable algorithms of the same kind.     

Local affinity in heterogeneous growing networks

In this paper we present a study of the influence of local affinity in heterogeneous preferential attachment (PA) networks. Heterogeneous PA models are a generalization of the Barabási-Albert model to heterogeneous networks, where the affinity between nodes biases the attachment probability of links. Threshold models are a class of heterogeneous PA models where the affinity between nodes is inversely related to the distance between their states. We propose a generalization of threshold models where network nodes have individual affinity functions, which are then combined to yield the affinity of each potential interaction. We analyze the influence of the affinity functions in the topological properties averaged over a network ensemble. The network topology is evaluated through the distributions of connectivity degrees, clustering coefficients and geodesic distances. We show that the relaxation of the criterion of a single global affinity still leads to a reasonable power-law scaling in the connectivity and clustering distributions under a wide spectrum of assumptions. We also show that the richer behavior of the model often exhibits a better agreement with the empirical observations on real networks.     

From regular to growing small-world networks

We propose a growing model which interpolates between one-dimensional regular lattice and small-world networks. The model undergoes an interesting phase transition from large to small worlds. We investigate the structural properties by both theoretical predictions and numerical simulations. Our growing model is a complementarity for the important static Watts-Strogatz network model.     

Scale-free networks by super-linear preferential attachment rule

A network growth model with geographic limitation of accessible information about the status of existing nodes is investigated. In this model, the probability Π(k) of an existing node of degree k is found to be super-linear with Π(k)∼k^α and α>1 when there are links from new nodes. The numerical results show that the constructed networks have typical power-law degree distributions P(k)∼k^−γ and the exponent γ depends on the constraint level. An analysis of local structural features shows the robust emergence of scale-free network structure in spite of the super-linear preferential attachment rule. This local structural feature is directly associated with the geographical connection constraints which are widely observed in many real networks.     

Information traffic in scale-free networks with fluctuations in packet generation rate

We study the information traffic in scale-free networks where the information generation rate varies with time as a periodic function. We observe that when the fluctuation in packet generation rate increases, the average transit time increases and network performance degrades. In order to improve the transportation efficiency in this situation, we propose a new routing method called mixed routing. It operates in two modes: (1) when the packet generation rate is small, the shortest paths are used to deliver the packets to the destination; (2) when the packet generation rate is large, the traffic loads in central nodes are redistributed to other non-central nodes, using the so-called efficient routing method. We find that the time shifting between the two modes is very critical for the routing performance. Consequently, we provide an efficient method to determine the critical times to shift the routing modes for achieving good network performance.     

Emergence of scale-free behavior in networks from limited-horizon linking and cost trade-offs

We study network growth from a fixed set of initially isolated nodes placed at random on the surface of a sphere. The growth mechanism we use adds edges to the network depending on strictly local gain and cost criteria. Only nodes that are not too far apart on the sphere may be considered for being joined by an edge. Given two such nodes, the joining occurs only if the gain of doing it surpasses the cost. Our model is based on a multiplicative parameter λ that regulates, in a function of node degrees, the maximum geodesic distance that is allowed between nodes for them to be considered for joining. For n nodes distributed uniformly on the sphere, and for within limits that depend on cost-related parameters, we have found that our growth mechanism gives rise to power-law distributions of node degree that are invariant for constant . We also study connectivity- and distance-related properties of the networks.     

Robustness of heterogeneous complex networks

In this paper we study the robustness of heterogeneous preferential attachment networks. The robustness of a network measures its structural tolerance to the random removal of nodes and links. We numerically analyze the influence of the affinity parameters on a set of ensemble-averaged robustness metrics. We show that the presence of heterogeneity does not fundamentally alter the smooth nature of the fragmentation process of the models. We also show that a moderate level of locality translates into slight improvements in the robustness metrics, which prompts us to conjecture an evolutionary argument for the existence of real networks with power-law scaling in their connectivity and clustering distributions.     

Naming game on small-world networks with geographical effects

The naming game model characterizes the main evolutionary features of languages or more generally of communication systems. Very recently, the combination of complex networks and the naming game has received much attention and the influences of various topological properties on the corresponding dynamical behavior have been widely studied. In this paper, we investigate the naming game on small-world geographical networks. The small-world geographical networks are constructed by randomly adding links to two-dimensional regular lattices, and it is found that the convergence time is a nonmonotonic function of the geographical distance of randomly added shortcuts. This phenomenon indicates that, although a long geographical distance of the added shortcuts favors consensus achievement, too long a geographical distance of the added shortcuts inhibits the convergence process, making it even slower than the moderates.     

Dynamics-driven evolution to structural heterogeneity in complex networks

The mutual influence of dynamics and structure is a central issue in complex systems. In this paper we study by simulation slow evolution of network under the feedback of a local-majority-rule opinion process. If performance-enhancing local mutations have higher chances of getting integrated into its structure, the system can evolve into a highly heterogeneous small-world with a global hub (whose connectivity is proportional to the network size), strong local connection correlations and power-law-like degree distribution. Networks with better dynamical performance are achieved if structural evolution occurs much slower than the network dynamics. Structural heterogeneity of many biological and social dynamical systems may also be driven by various dynamics-structure coupling mechanisms.     

Scaling relation for earthquake networks

The scaling relation, 2γ−δ=1, for the exponents of the power-law connectivity distribution, γ, and the power-law eigenvalue distribution of the adjacency matrix, δ, is theoretically predicted to be fulfilled by a locally treelike scale-free network in the “effective medium approximation” (i.e., an analog of the mean field approximation). Here, it is shown that such a relation holds well for the reduced simple earthquake networks (i.e., the network without tadpole-loops and multiple edges) constructed from the seismic data taken from California and Japan. This validates the goodness of the effective medium approximation in the earthquake networks and is consistent with the hierarchical organization of the networks. The present result may be useful for modeling seismicity on complex networks.     

Network traffic behaviour near phase transition point

We explore packet traffic dynamics in a data network model near phase transition point from free flow to congestion. The model of data network is an abstraction of the Network Layer of the OSI (Open Systems Interconnect) Reference Model of packet switching networks. The Network Layer is responsible for routing packets across the network from their sources to their destinations and for control of congestion in data networks. Using the model we investigate spatio-temporal packets traffic dynamics near the phase transition point for various network connection topologies, and static and adaptive routing algorithms. We present selected simulation results and analyze them.     

Measuring distances between complex networks

A previously introduced concept of higher order neighborhoods in complex networks, [R.F.S. Andrade, J.G.V. Miranda, T.P. Lobão, Phys. Rev. E 73 (2006) 046101] is used to define a distance between networks with the same number of nodes. With such measure, expressed in terms of the matrix elements of the neighborhood matrices of each network, it is possible to compare, in a quantitative way, how far apart in the space of neighborhood matrices two networks are. The distance between these matrices depends on both the network topologies and the adopted node numberings. While the numbering of one network is fixed, a Monte Carlo algorithm is used to find the best numbering of the other network, in the sense that it minimizes the distance between the matrices. The minimal value found for the distance reflects differences in the neighborhood structures of the two networks that arise only from distinct topologies. This procedure ends up by providing a projection of the first network on the pattern of the second one. Examples are worked out allowing for a quantitative comparison for distances among distinct networks, as well as among distinct realizations of random networks.     

Traffic dynamics in scale-free networks with limited packet-delivering capacity

We propose a limited packet-delivering capacity model for traffic dynamics in scale-free networks. In this model, the total node’s packet-delivering capacity is fixed, and the allocation of packet-delivering capacity on node i is proportional to , where k_i is the degree of node i and ? is a adjustable parameter. We have applied this model on the shortest path routing strategy as well as the local routing strategy, and found that there exists an optimal value of parameter ? leading to the maximal network capacity under both routing strategies. We provide some explanations for the emergence of optimal ?.     

Traffic dynamics based on a traffic awareness routing strategy on scale-free networks

By incorporating local traffic information into the shortest path routing strategy, we numerically investigate the effectiveness of the traffic awareness routing strategy for scale-free networks with different clustering. In order to characterize the efficiency of the packet-delivery process, we introduce an order parameter and an average transmission time that allow us to measure the network capacity by the critical value of phase transition from free flow to congestion. Compared with the shortest path routing protocol, the network capacity is greatly enhanced by the traffic awareness routing strategy. We also find that there exists an optimum value for the tunable parameter in the congestion awareness strategy. Moreover, simulation results show that the more clustered the network, the less efficient the packet-delivery process.     

Sandpile on directed small-world networks

We numerically investigate the avalanche dynamics of the Bak-Tang-Wiesenfeld sandpile model on directed small-world networks. We find that the avalanche size and duration distribution follow a power law for all rewiring probabilities p. Specially, we find that, approaching the thermodynamic limit (L→∞), the values of critical exponents do not depend on p and are consistent with the mean-field solution in Euclidean space for any p>0. In addition, we measure the dynamic exponent in the relation between avalanche size and avalanche duration and find that the values of the dynamic exponents are also consistent with the mean-field values for any p>0.     

Role of Clustering Coefficient on Cooperation Dynamics in Homogeneous Networks

Based on previous works, we give further investigations on the Prisoners＇ Dilemma Game （PDG） on two different types of homogeneous networks, i.e. the homogeneous small-world network （HSWN） and the regular ring graph. We find that the so-called resonance-like character can occur on both the networks. Different from the viewpoint in previous publications, we think the small-world effect may be unnecessary to produce this character. Therefore, over these two types of networks, we suggest a common understanding in the viewpoint of clustering coefficient. Detailed simulation results can sustain our viewpoint quite well. Furthermore, we investigate the Snowdrift Game （SG） on the same networks. The difference between the outputs of the PDG and the SG can also sustain our viewpoint.     

Is the topology of the Internet network really fit to sustain its function?

The Internet is one of the most interesting realizations of a “complex” network. As a non-supervised growing object, it allows the study of the selective pressure which drives the network to assume its current structure. The DIMES and the ROUTEVIEWS projects are ongoing projects aimed at evaluating the topological structure of the Internet (at the Autonomous System or AS grain-level) on the basis of different types of measurements. The topological analysis of the networks produced by the two projects has allowed us to infer a growth mechanism which has been used to build up synthetic networks with similar properties. These networks have been used as test-beds for the implementation of a model of traffic dynamics, with the aim of assessing the ability of the Internet’s topology to support the basic actions for data traffic handling. Results have been compared with those obtained by using a random network of similar size. The effects of some structural perturbations (arcs and nodes’ removal, traffic localization) have been also evaluated in terms of the induced variations of the network’s efficiency. The resulting scenario is consistent with the hypothesis that the structure of the Internet is only partially fit to host communication processes and that the intelligence of the TCP/IP protocol is partly needed to overcome some “structural” deficiencies.     

Effect of imitation in evolutionary minority game on small-world networks

The system performance in an evolutionary minority game with imitation on small-world networks is studied. Numerical results show that system performance positively correlates with the clustering coefficients. The domain structure of the agents’ strategies can be used to give a qualitative explanation for it. We also find that the time series of the reduced variance σ²/N could have a phasic evolution from a metastable state (two crowds are formed but the distribution of their probabilities does not peak at p≈0 and p≈1) to a steadystate (the two crowds evolve into a crowd and an anticrowd with the distribution of their probabilities peaking at p≈0 and p≈1).     

Decorrelation of networked communication flow via load-dependent routing weights

Clever assignments of link weights are able to change communication routes in such a way that loads are distributed almost evenly across a network. This is achieved by weight assignments based on the link load. As demonstrated for scale-free as well as synthetic Internet networks, they decorrelate the loads of the nodes and links from the network structure and increase the transport capacity of the network. For various Internet scans the increase of transport capacity amounts to a factor of around five when compared to shortest-path routing.