Effects of degree correlation on the controllability of networks

In this paper, we investigate the effects of degree correlation on the controllability of undirected networks with different degree-mixing patterns based on simulation analysis. Considering random pinning, max-degree pinning and mix-degree pinning, some relevance factors on controllability such as the control gain and the number of pinned nodes are discussed in detail. It is found that disassortative mixing enhances the network controllability contrast to assortative mixing, to which the network controllability is sensible. Furthermore, too large or too low value of the feedback gain can reduce the controllability. From the viewpoint of practical application, mix-degree pinning strategy is suggested in assortative network, while in disassortative network, max-degree pinning scheme is better than random pinning.     

Relationship between degree-rank distributions and degree distributions of complex networks

Both the degree distribution and the degree-rank distribution, which is a relationship function between the degree and the rank of a vertex in the degree sequence obtained from sorting all vertices in decreasing order of degree, are important statistical properties to characterize complex networks. We derive an exact mathematical relationship between degree-rank distributions and degree distributions of complex networks. That is, for arbitrary complex networks, the degree-rank distribution can be derived from the degree distribution, and the reverse is true. Using the mathematical relationship, we study the degree-rank distributions of scale-free networks and exponential networks. We demonstrate that the degree-rank distributions of scale-free networks follow a power law only if scaling exponent λ>2. We also demonstrate that the degree-rank distributions of exponential networks follow a logarithmic law. The simulation results in the BA model and the exponential BA model verify our results.     

Synchronization in scale free networks with degree correlation

In this paper we study a model of synchronization process on scale free networks with degree-degree correlations. This model was already studied on this kind of networks without correlations by Pastore y Piontti et al. [A.L. Pastore y Piontti, P.A. Macri, L.A. Braunstein, Phys. Rev. E 76 (2007) 046117]. Here, we study the effects of the degree-degree correlation on the behavior of the load fluctuations W_s in the steady state. We found that for assortative networks there exist a specific correlation where the system is optimally synchronized. In addition, we found that close to this optimal value the fluctuations does not depend on the system size and therefore the system becomes fully scalable. This result could be very important for some technological applications. On the other hand, far from the optimal correlation, W_s scales logarithmically with the system size.     

Reducing congestion on complex networks by dynamic relaxation processes

We study the effects of relaxational dynamics on the congestion pressure in general transport networks. We show that the congestion pressure is reduced in scale-free networks if a relaxation mechanism is utilized, while this is in general not the case for non-scale-free graphs such as random graphs. We also present evidence supporting the idea that the emergence of scale-free networks arise from optimization mechanisms to balance the load of the networks nodes.     

Optimal traffic networks topology: A complex networks perspective

We investigate and analyse an optimal traffic network structure for resisting traffic congestion with different volumes of traffic. For this aim, we introduce a cost function and user-equilibrium assignment (UE) which ensures the flow balance on traffic systems. Our finding is that an optimal network is strongly dependent on the total system flow. And the random network is most desirable when the system flow is small. But for the larger volume of traffic, the network with power-law degree distribution is the optimal one. Further study indicates, for scale-free networks, that the degree distribution exponent has large effects on the congestion of traffic network. Therefore, the volume of traffic and characteristic of network determine the optimal network structure so as to minimize the side-effect produced by traffic congestion.     

SPR-based Markov chain method for degree distributions of evolving networks

In this paper, we develop a stochastic process rules (SPR) based Markov chain method to calculate the degree distributions of evolving networks. This new approach overcomes two shortcomings of Shi, Chen and Liu’s use of the Markov chain method (Shi et al. 2005 [21]). In addition we show how an SPR-based Markov chain method can be effectively used to calculate degree distributions of random birth-and-death networks, which we believe to be novel. First SPR are introduced to replace traditional evolving rules (TR), making it possible to compute degree distributions in one sample space. Then the SPR-based Markov chain method is introduced and tested by using it to calculate two kinds of evolving network. Finally and most importantly, the SPR-based method is applied to the problem of calculating the degree distributions of random birth-and-death networks.     

Topological relation of layered complex networks

We present analytically the relation functions between degrees or clustering coefficients of a common station in both space L layer and space P layer of transportation systems. A good agreement between the analytical results and the empirical investigations in a railway system and three bus systems in China is observed.     

Cooperation influenced by the correlation degree of two-layered complex networks in evolutionary prisoner’s dilemma games

An evolutionary prisoner's dilemma game is investigated on two-layered complex networks respectively representing interaction and learning networks in one and two dimensions. A parameter q is introduced to denote the correlation degree between the two-layered networks. Using Monte Carlo simulations we studied the effects of the correlation degree on cooperative behaviour and found that the cooperator density nontrivially changes with q for different payoff parameter values depending on the detailed strategy updating and network dimension. An explanation for the obtained results is provided.     

Analyzing open-source software systems as complex networks

Software systems represent one of the most complex man-made artifacts. Understanding the structure of software systems can provide useful insights into software engineering efforts and can potentially help the development of complex system models applicable to other domains. In this paper, we analyze one of the most popular open-source Linux meta packages/distributions called the Gentoo Linux. In our analysis, we model software packages as nodes and dependencies among them as edges. Our empirical results show that the resulting Gentoo network cannot be easily explained by existing complex network models. This in turn motivates our research in developing two new network growth models in which a new node is connected to an old node with the probability that depends not only on the degree but also on the “age” of the old node. Through computational and empirical studies, we demonstrate that our models have better explanatory power than the existing ones. In an effort to further explore the properties of these new models, we also present some related analytical results.     

Time evolution of the degree distribution of model A of random attachment growing networks

For random growing networks, Barabás and Albert proposed a kind of model in Barabás et al. [Physica A 272 (1999) 173], i.e. model A. In this paper, for model A, we give the differential format of master equation of degree distribution and obtain its analytical solution. The obtained result P(k, t) is the time evolution of degree distribution. P(k, t) is composed of two terms. At given finite time, one term decays exponentially, the other reflects size effect. At infinite time, the degree distribution is the same as that of Barabás and Albert. In this paper, we also discuss the normalization of degree distribution P(k, t) in detail.     

Tuning degree distributions: Departing from scale-free networks

Scale-free networks are characterized by a degree distribution with power-law behavior. Although scale-free networks have been shown to arise in many areas, ranging from the World Wide Web to transportation or social networks, degree distributions of other observed networks often differ from the power-law type. Data based investigations require modifications of the typical scale-free network.We present an algorithm that generates networks in which the shape of the degree distribution is tunable by modifying the preferential attachment step of the Barabási-Albert construction algorithm. The shape of the distribution is represented by dispersion measures such as the variance and the skewness, both of which are highly correlated with the maximal degree of the network and, therefore, adequately represents the influence of superspreaders or hubs. By combining our algorithm with work of Holme and Kim, we show how to generate networks with a variety of degree distributions and clustering coefficients.     

Detecting communities by the core-vertex and intimate degree in complex networks

In this paper, we present a new approach to extract communities in the complex networks with considerable accuracy. We introduce the core-vertex and the intimate degree between the community and its neighboring vertices. First, we find the core-vertices as the initial community. These core-vertices are then expanded using intimate degree function during extracting community structure from the given network. In addition, our algorithm successfully finds common nodes between communities. Experimental results using some real-world networks data shows that the performance of our algorithm is satisfactory.     

Prosocial norms and degree heterogeneity in social networks

We provide empirical evidence to support the claims that social diversity promotes prosocial behavior. We elicit a real-life social network and its members’ adherence to a social norm, namely inequity aversion. The data reveal a positive relationship between subjects’ prosociality and several measures of centrality. This result is in line with the theoretical literature that relates the evolution of social norms to the structure of social interactions and argues that central individuals are crucial for the emergence of prosocial behavior.     

Detecting local community structures in complex networks based on local degree central nodes

Detecting local communities in real-world graphs such as large social networks, web graphs, and biological networks has received a great deal of attention because obtaining complete information from a large network is still difficult and unrealistic nowadays. In this paper, we define the term local degree central node whose degree is greater than or equal to the degree of its neighbor nodes. A new method based on the local degree central node to detect the local community is proposed. In our method, the local community is not discovered from the given starting node, but from the local degree central node that is associated with the given starting node. Experiments show that the local central nodes are key nodes of communities in complex networks and the local communities detected by our method have high accuracy. Our algorithm can discover local communities accurately for more nodes and is an effective method to explore community structures of large networks.     

Degree correlations in growing networks with deletion of nodes

In this paper we study the degree distribution and the two-node degree correlations in growing networks generated via a general linear preferential attachment of new nodes together with a uniformly random deletion of nodes. By using a continuum approach we show that, under some suitable combinations of parameters (deletion rate and node attractiveness), the degree distribution not only loses its scale-free character but can even be supported on a small range of degrees. Moreover, we obtain new results on two-vertex degree correlations showing that, for degree distributions with finite variance, such correlations can change under a nonselective removal of nodes.     

Weighted self-similar networks under preferential attachment

We introduce an abstract evolutionary formalism that generates weighted networks whose growth under stochastic preferential attachment triggers unrestricted weight rearrangements in existing links. The class of resulting algorithms for different parameter values includes the Barabási-Albert and Barrat-Barthélemy-Vespignani models as special cases. We solve the recursions that describe the average growth to derive exact solutions for the expected degree and strength distribution, the individual strength and weight development and the joint distribution of neighboring degrees. We find that the network exhibits a particular form of self-similarity, namely every sufficiently interconnected node has on average the same constitution of small-degree neighbors as any other node of large degree. Finally we suggest potential applications in several fields of interest.     

Synchronization optimal networks obtained using local structure information

In this paper, the networks with optimal synchronizability are obtained using the local structure information. In scale-free networks, a node will be coupled by its neighbors with maximal degree among the neighbors if and only if the maximal degree is larger than its own degree. If the obtained coupled networks are connected, they are synchronization optimal networks. The connection probability of coupled networks is greatly affected by the average degree which usually increases with the average degree. This method could be further generalized by taking into account the degree of next-nearest neighbors, which will sharply increase the connection probability. Compared to the other proposed methods that obtain synchronization optimal networks, our method uses only local structure information and can hold the structure properties of the original scale-free networks to some extent. Our method may present a useful way to manipulate the synchronizability of real-world scale-free networks.     

Cascading failures in congested complex networks with feedback

In this article, we investigate cascading failures in complex networks by introducing a feedback. To characterize the effect of the feedback, we define a procedure that involves a self-organization of trip distribution during the process of cascading failures. For this purpose, user equilibrium with variable demand is used as an alternative way to determine the traffic flow pattern throughout the network. Under the attack, cost function dynamics are introduced to discuss edge overload in complex networks, where each edge is assigned a finite capacity (controlled by parameter α). We find that scale-free networks without considering the effect of the feedback are expected to be very sensitive to α as compared with random networks, while this situation is largely improved after introducing the feedback.     

Traffic of indistinguishable particles in complex networks

In this paper, we apply a simple walk mechanism to the study of the traffic of many indistinguishable particles in complex networks. The network with particles stands for a particle system, and every vertex in the network stands for a quantum state with the corresponding energy determined by the vertex degree. Although the particles are indistinguishable, the quantum states can be distinguished. When the many indistinguishable particles walk randomly in the system for a long enough time and the system reaches dynamic equilibrium, we find that under different restrictive conditions the particle distributions satisfy different forms, including the Bose--Einstein distribution, the Fermi--Dirac distribution and the non-Fermi distribution (as we temporarily call it). As for the Bose--Einstein distribution, we find that only if the particle density is larger than zero, with increasing particle density, do more and more particles condense in the lowest energy level. While the particle density is very low, the particle distribution transforms from the quantum statistical form to the classically statistical form, i.e., transforms from the Bose distribution or the Fermi distribution to the Boltzmann distribution. The numerical results fit well with the analytical predictions.