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.     

A weighted network evolution with traffic flow

In this paper, we propose a simple weighted network model that generalizes the complex network model evolution with traffic flow previously presented to investigate the relationship between traffic flow and network structure. In the model, the nodes in the network are represented by the traffic flow states, the links in the network are represented by the transform of the traffic flow states, and the traffic flow transported when performing the transform of the traffic flow states is considered as the weight of the link. Several topological features of this generalized weighted model, such as the degree distribution and strength distribution, have been numerically studied. A scaling behavior between the strength and degree s∼klogk is obtained. By introducing some constraints to the generalized weighted model, we study its subnetworks and find that the scaling behavior between the strength and degree is conserved, though the topology properties are quite sensitive to the constraints.     

Connectivity degrees in the threshold preferential attachment model

In this paper we present a study of the connectivity degrees of the threshold preferential attachment model, a generalization of the Barabási-Albert model to heterogeneous complex networks. The threshold model incorporates the states of the nodes in its preferential linking rule and assumes that the affinity between network nodes follows an inverse relationship with the distance between their states. We numerically analyze the connectivity degrees of the model, studying the influence of the main parameters on the distribution of connectivity degrees and its statistics, the average degree and highest degree of the network. We show that such statistics exhibit markedly different behaviors in the dependence on the model parameters, particularly as regards the interaction threshold. Nevertheless, we show that the two statistics converge in the limit of null threshold and often exhibit scaling that can be described by power laws of the model parameters.     

Synchronization of Coupled Oscillators on Newman-Watts Small-World Networks

We investigate the collection behaviour of coupled phase oscillators on Newman-Watts small-world networks in one and two dimensions. Each component of the network is assumed as an oscillator and each interacts with the others following the Kuramoto model We then study the onset of global synchronization of phases and frequencies based on dynamic simulations and finite-size scaling. Both the phase and frequency synchronization are observed to emerge in the presence of a tiny fraction of shortcuts and enhanced with the increases of nearest neighbours and lattice dimensions.     

The emergence of scale-free networks with a seceding mechanism

In order to explore further the underlying mechanism of scale-free networks, we study stochastic secession as a mechanism for the creation of complex networks. In this evolution the network growth incorporates the addition of new nodes, the addition of new links between existing nodes, the deleting and rewiring of some existing links, and the stochastic secession of nodes. To random growing networks with preferential attachment, the model yields scale-free behavior for the degree distribution. Furthermore, we obtain an analytical expression of the power-law degree distribution with scaling exponent γ ranging from 1.1 to 9. The analytical expressions are in good agreement with the numerical simulation results.     

Attack vulnerability of scale-free networks due to cascading failures

In this paper, adopting the initial load of a node i to be with k_i being the degree of the node i, we propose a cascading model based on a load local redistribution rule and examine cascading failures on the typical network, i.e., the BA network with the scale-free property. We find that the BA scale-free network reaches the strongest robustness level in the case of α=1 and the robustness of the network has a positive correlation with the average degree 〈k〉, where the robustness is quantified by a transition from normal state to collapse. In addition, we further discuss the effects of two different attacks for the robustness against cascading failures on our cascading model and find an interesting result, i.e., the effects of two different attacks, strongly depending to the value α. These results may be very helpful for real-life networks to avoid cascading-failure-induced disasters.     

Unified index to quantifying heterogeneity of complex networks

Although recent studies have revealed that degree heterogeneity of a complex network has significant impact on the network performance and function, a unified definition of the heterogeneity of a network with any degree distribution is absent. In this paper, we define a heterogeneity index 0≤H<1 to quantify the degree heterogeneity of any given network. We analytically show the existence of an upper bound of H=0.5 for exponential networks, thus explain why exponential networks are homogeneous. On the other hand, we also analytically show that the heterogeneity index of an infinite power law network is between 1 and 0.5 if and only if its degree exponent is between 2 and 2.5. We further show that for any power law network with a degree exponent greater than 2.5, there always exists an exponential network such that both networks have the same heterogeneity index. This may help to explain why 2.5 is a critical degree exponent for some dynamic behaviors on power law networks.     

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.     

Evolution of the linguistic diversity on correlated landscapes

We have recently investigated the evolution of linguistic diversity by means of a simple spatial model that considers selective geographic colonization, linguistic anomalous diffusion and mutation. In the model, regions of the lattice are characterized by the amount of resources available to populations which are going to colonize the region. In that approach, the resources were ascribed in a randomly and uncorrelated way. Here, we extend the previous model and introduce a degree of correlation for the resource landscape. A change of the qualitative scenario is observed for high correlation, where the increase of the linguistic diversity on area is faster than for low correlated landscapes. For low correlated landscapes, the dependence of diversity on area shows two scaling regimes, while we observe the rising of another scaling region for high correlated landscapes.     

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.     

Random walks and diameter of finite scale-free networks

Dynamical scalings for the end-to-end distance R_ee and the number of distinct visited nodes N_v of random walks (RWs) on finite scale-free networks (SFNs) are studied numerically. 〈R_ee〉 shows the dynamical scaling behavior , where is the average minimum distance between all possible pairs of nodes in the network, N is the number of nodes, γ is the degree exponent of the SFN and t is the step number of RWs. Especially, in the limit t→∞ satisfies the relation , where d is the diameter of network with for γ≥3 or for γ<3. Based on the scaling relation 〈R_ee〉, we also find that the scaling behavior of the diameter of networks can be measured very efficiently by using RWs.     

Interpersonal interactions and human dynamics in a large social network

We study a large social network consisting of over 10⁶ individuals, who form an Internet community and organize themselves in groups of different sizes. On the basis of the users’ list of friends and other data registered in the database we investigate the structure and time development of the network. The structure of this friendship network is very similar to the structure of different social networks. However, here a degree distribution exhibiting two scaling regimes, power-law for low connectivity and exponential for large connectivity, was found. The groups size distribution and distribution of number of groups of an individual have power-law form. We found very interesting scaling laws concerning human dynamics. Our research has shown how long people are interested in a single task.     

Growing networks with preferential deletion and addition of edges

A preferential attachment model for a growing network incorporating the deletion of edges is studied and the expected asymptotic degree distribution is analyzed. At each time step t=1,2,…, with probability π₁>0 a new vertex with one edge attached to it is added to the network and the edge is connected to an existing vertex chosen proportionally to its degree, with probability π₂ a vertex is chosen proportionally to its degree and an edge is added between this vertex and a randomly chosen other vertex, and with probability π₃=1−π₁−π₂<1/2 a vertex is chosen proportionally to its degree and a random edge of this vertex is deleted. The model is intended to capture a situation where high-degree vertices are more dynamic than low-degree vertices in the sense that their connections tend to be changing. A recursion formula is derived for the expected asymptotic fraction p_k of vertices with degree k, and solving this recursion reveals that, for π₃<1/3, we have p_k∼k^{−(3−7π₃)/(1−3π₃)}, while, for π₃>1/3, the fraction p_k decays exponentially at rate (π₁+π₂)/2π₃. There is hence a non-trivial upper bound for how much deletion the network can incorporate without losing the power-law behavior of the degree distribution. The analytical results are supported by simulations.     

Network Entropy Based on Topology Configuration and Its Computation to Random Networks

A definition of network entropy is presented, and as an example, the relationship between the value of network entropy of ER network model and the connect probability p as well as the total nodes N is discussed. The theoretical result and the simulation result based on the network entropy of the ER network are in agreement well with each other. The result indicated that different from the other network entropy reported before, the network entropy defined here has an obvious difference from different type of random networks or networks having different total nodes. Thus, this network entropy may portray the characters of complex networks better. It is also pointed out that, with the aid of network entropy defined, the concept of equilibrium networks and the concept of non-equilibrium networks may be introduced, and a quantitative measurement to describe the deviation to equilibrium state of a complex network is carried out.     

Statistical properties of world investment networks

We have performed a detailed investigation on the world investment networks constructed from the Coordinated Portfolio Investment Survey (CPIS) data of the International Monetary Fund, ranging from 2001 to 2006. The distributions of degrees and node strengths are scale-free. The weight distributions can be well modeled by the Weibull distribution. The maximum flow spanning trees of the world investment networks possess two universal allometric scaling relations, independent of time and the investment type. The topological scaling exponent is 1.17±0.02 and the flow scaling exponent is 1.03±0.01.     

Communicability betweenness in complex networks

Betweenness measures provide quantitative tools to pick out fine details from the massive amount of interaction data that is available from large complex networks. They allow us to study the extent to which a node takes part when information is passed around the network. Nodes with high betweenness may be regarded as key players that have a highly active role. At one extreme, betweenness has been defined by considering information passing only through the shortest paths between pairs of nodes. At the other extreme, an alternative type of betweenness has been defined by considering all possible walks of any length. In this work, we propose a betweenness measure that lies between these two opposing viewpoints. We allow information to pass through all possible routes, but introduce a scaling so that longer walks carry less importance. This new definition shares a similar philosophy to that of communicability for pairs of nodes in a network, which was introduced by Estrada and Hatano [E. Estrada, N. Hatano, Phys. Rev. E 77 (2008) 036111]. Having defined this new communicability betweenness measure, we show that it can be characterized neatly in terms of the exponential of the adjacency matrix. We also show that this measure is closely related to a Fréchet derivative of the matrix exponential. This allows us to conclude that it also describes network sensitivity when the edges of a given node are subject to infinitesimally small perturbations. Using illustrative synthetic and real life networks, we show that the new betweenness measure behaves differently to existing versions, and in particular we show that it recovers meaningful biological information from a protein-protein interaction network.     

A Law of Gravitation for Complex Networks

Inspiring Newton＇s law of universal gravitation and empirical studies, we propose a concept of virtual network mass and network gravitational force in complex networks. Then a network gravitational model for complex networks is presented. In the model, each node in the network is described with its position, edges （links） and virtual network mass. The proposed model is examined by experiments to show its potential applications.     

Modeling network growth with assortative mixing

We propose a model of an underlying mechanism responsible for the formation of assortative mixing in networks between “similar” nodes or vertices based on generic vertex properties. Existing models focus on a particular type of assortative mixing, such as mixing by vertex degree, or present methods of generating a network with certain properties, rather than modeling a mechanism driving assortative mixing during network growth. The motivation is to model assortative mixing by non-topological vertex properties, and the influence of these non-topological properties on network topology. The model is studied in detail for discrete and hierarchical vertex properties, and we use simulations to study the topology of resulting networks. We show that assortative mixing by generic properties directly drives the formation of community structure beyond a threshold assortativity of r ∼0.5, which in turn influences other topological properties. This direct relationship is demonstrated by introducing a new measure to characterise the correlation between assortative mixing and community structure in a network. Additionally, we introduce a novel type of assortative mixing in systems with hierarchical vertex properties, from which a hierarchical community structure is found to result. Electronic supplementary material Supplementary Online Material     

A complex network model based on the Gnutella protocol

Gnutella is one of the basic protocols for P2P software. In this paper, a novel network model based on Gnutella is introduced. The mechanism of this network is based on resource occupancy and search activities of peers. As for the structure, the power-law exponent of in-degree γ_in≈4.2, the length of the average shortest path 〈l〉=57.74, and the diameter of the network is 156; these topological properties of the proposed structure differ from known results.     

Opinion formation in a social network: The role of human activity

The model of opinion formation in human population based on social impact theory is investigated numerically. On the basis of a database received from the on-line game server, we examine the structure of social network and human dynamics. We calculate the activity of individuals, i.e. the relative time devoted daily to interactions with others in the artificial society. We study the influence of correlation between the activity of an individual and its connectivity on the process of opinion formation. We find that such correlations have a significant influence on the temperature of the phase transition and the effect of the mass media, modeled as an external stimulation acting on the social network.