Scale-free networks from varying vertex intrinsic fitness

A new mechanism leading to scale-free networks is proposed in this Letter. It is shown that, in many cases of interest, the connectivity power-law behavior is neither related to dynamical properties nor to preferential attachment. Assigning a quenched fitness value x(i) to every vertex, and drawing links among vertices with a probability depending on the fitnesses of the two involved sites, gives rise to what we call a good-get-richer mechanism, in which sites with larger fitness are more likely to become hubs (i.e., to be highly connected).     

Feedback arcs and node hierarchy in directed networks

Directed networks such as gene regulation networks and neural networks are connected by arcs(directed links). The nodes in a directed network are often strongly interwound by a huge number of directed cycles, which leads to complex information-processing dynamics in the network and makes it highly challenging to infer the intrinsic direction of information flow. In this theoretical paper, based on the principle of minimum-feedback, we explore the node hierarchy of directed networks and distinguish feedforward and feedback arcs. Nearly optimal node hierarchy solutions, which minimize the number of feedback arcs from lower-level nodes to higher-level nodes, are constructed by belief-propagation and simulated-annealing methods. For real-world networks, we quantify the extent of feedback scarcity by comparison with the ensemble of direction-randomized networks and identify the most important feedback arcs. Our methods are also useful for visualizing directed networks.     

幂律指数在1与3之间的一类无标度网络

借助排队系统中顾客批量到达的概念，提出节点批量到达的Poisson网络模型.节点按照到达率为λ的Poisson过程批量到达系统.模型1，批量按照到达批次的幂律非线性增长，其幂律指数为θ(0≤θ<+∞).BA模型是在θ＝0时的特例.利用Poisson过程理论和连续化方法进行分析，发现这个网络稳态平均度分布是幂律分布，而且幂律指数在1和3之间.模型2，批量按照节点到达批次的对数非线性增长，得出当批量增长较缓慢时，稳态度分布幂律指数为3.因此，节点批量到达的Poisson网络模型不仅是BA模型的推广，也为许多幂律指数在1和2之间的现实网络提供了理论依据.     

Mean field theory of directed polymers with random complex weights

We show that for the problem of directed polymers on a tree with i.i.d. random complex weights on each bond, three possible phases can exist; the phase of a particular system is determined by the distribution of the random weights. For each of these three phases, we give the expression of the free energy per unit length in the limit of infinitely long polymers. Our proofs require several hypotheses on the distribution , most importantly, that the amplitude and the phase of each complex weight be statistically independent. The main steps of our proofs use bounds on noninteger moments of the partition function and self averaging properties of the free energy. We illustrate our results by some examples and discuss possible generalizations to a larger class of distributions, to Random Energy Models, and to the finite dimensional case. We note that our results are not in agreement with the predictions of a recent replica approach to a similar problem.     

Scale-free human migration and the geography of social networks

The “gravitational law of social interaction”, by which the probability of a social link decreases inversely with the square of the geographic distance, has been recently documented. The source of this spatial property of social networks, however, is yet unknown. The formation of social links is related to human dynamics both on the day-to-day, typically small scale, level of mobility, and on larger scale migration (or reallocation) movements. In this study we analyze human migration patterns by investigating the migration of 46.8 million individuals across the US during 1995-2000. We find that the probability of migration decreases as a power law of the distance, with exponent −1. We show that this finding offers an explanation for the gravitational law of social interaction. Possible explanations and implications of the scale-free migration pattern are discussed.     

Scale-free properties of information flux networks in genetic algorithms

In this study, we present empirical analysis of statistical properties of mating networks in genetic algorithms (GAs). Under the framework of GAs, we study a class of interaction network model—information flux network (IFN), which describes the information flow among generations during evolution process. The IFNs are found to be scale-free when the selection operator uses a preferential strategy rather than a random. The topology structure of IFN is remarkably affected by operations used in genetic algorithms. The experimental results suggest that the scaling exponent of the power-law degree distribution is shown to decrease when crossover rate increases, but increase when mutation rate increases, and the reason may be that high crossover rate leads to more edges that are shared between nodes and high mutation rate leads to many individuals in a generation possessing low fitness. The magnitude of the out-degree exponent is always more than the in-degree exponent for the systems tested. These results may provide a new viewpoint with which to view GAs and guide the dissemination process of genetic information throughout a population.     

Local structure of directed networks

Previous work on undirected small-world networks established the paradigm that locally structured networks tend to have a high density of short loops. On the other hand, many realistic networks are directed. Here we investigate the local organization of directed networks and find, surprisingly, that real networks often have very few short loops as compared to random models. We develop a theory and derive conditions for determining if a given network has more or less loops than its randomized counterparts. These findings carry broad implications for structural and dynamical processes sustained by directed networks.     

Scaling of directed dynamical small-world networks with random responses

A dynamical model of small-world networks, with directed links which describe various correlations in social and natural phenomena, is presented. Random responses of sites to the input message are introduced to simulate real systems. The interplay of these ingredients results in the collective dynamical evolution of a spinlike variable S(t) of the whole network. The global average spreading length (s) and average spreading time (s) are found to scale as p(-alpha)ln(N with different exponents. Meanwhile, S(t) behaves in a duple scaling form for N>N(*): S approximately f(p(-beta)q(gamma)t), where p and q are rewiring and external parameters, alpha, beta, and gamma are scaling exponents, and f(t) is a universal function. Possible applications of the model are discussed.     

Studies on controllability of directed networks with extremal optimization

Almost all natural, social and man-made-engineered systems can be represented by a complex network to describe their dynamic behaviors. To make a real-world complex network controllable with its desired topology, the study on network controllability has been one of the most critical and attractive subjects for both network and control communities. In this paper, based on a given directed–weighted network with both state and control nodes, a novel optimization tool with extremal dynamics to generate an optimal network topology with minimum control nodes and complete controllability under Kalman’s rank condition has been developed. The experimental results on a number of popular benchmark networks show the proposed tool is effective to identify the minimum control nodes which are sufficient to guide the whole network’s dynamics and provide the evolution of network topology during the optimization process. We also find the conclusion: “the sparse networks need more control nodes than the dense, and the homogeneous networks need fewer control nodes compared to the heterogeneous” (Liu et al., 2011  [18]), is also applicable to network complete controllability. These findings help us to understand the network dynamics and make a real-world network under the desired control. Moreover, compared with the relevant research results on structural controllability with minimum driver nodes, the proposed solution methodology may also be applied to other constrained network optimization problems beyond complete controllability with minimum control nodes.     

Scale-free networks provide a unifying framework for the emergence of cooperation

We study the evolution of cooperation in the framework of evolutionary game theory, adopting the prisoner's dilemma and snowdrift game as metaphors of cooperation between unrelated individuals. In sharp contrast with previous results we find that, whenever individuals interact following networks of contacts generated via growth and preferential attachment, leading to strong correlations between individuals, cooperation becomes the dominating trait throughout the entire range of parameters of both games, as such providing a unifying framework for the emergence of cooperation. Such emergence is shown to be inhibited whenever the correlations between individuals are decreased or removed. These results are shown to apply from very large population sizes down to small communities with nearly 100 individuals.     

Outer synchronization of networks with different node dynamics

A new type of outer synchronization between two distinct networks, composed of different classes of oscillators is investigated with the help of open plus closed loop approach, proposed earlier by Jackson and Grosu. It is further assumed that all the members of the network differ in their parameter values. Asymptotic stability of the zero solution of the error equation is proved analytically. Numerical simulation reveals that the same type of members of the two networks gets synchronized.     

Synchronization in asymmetrically coupled networks with node balance

We study global stability of synchronization in asymmetrically connected networks of limit-cycle or chaotic oscillators. We extend the connection graph stability method to directed graphs with node balance, the property that all nodes in the network have equal input and output weight sums. We obtain the same upper bound for synchronization in asymmetrically connected networks as in the network with a symmetrized matrix, provided that the condition of node balance is satisfied. In terms of graphs, the symmetrization operation amounts to replacing each directed edge by an undirected edge of half the coupling strength. It should be stressed that without node balance this property in general does not hold.     

Self-organization of directed networks through asymmetric coupling

In this Letter, self-organization of directed networks is surveyed. Inspired from the results in neural networks research, we propose an asymmetric coupling scheme with simple edge deleting rules. Results show that all-to-all networks can be organized into scale-free networks with feed-forward structures. Corresponding analysis is also given.     

变权小世界生物神经网络的兴奋及优化特性

根据实际生物神经网络具有小世界连接和神经元之间的连接强度随时间变化的特点,首先构造了一个以Hodgkin-Huxley方程为节点动力学模型的动态变权小世界生物神经网络模型,然后研究了该模型神经元的兴奋特性、权值变化特点和不同的学习系数对神经元的兴奋统计特性的影响.最有意义的结果是,在同样的网络结构、网络参数及外部刺激信号的条件下,学习系数b存在一个最优值b^*,使生物神经网络的兴奋度在b=b^*时达到最大. 关键词： 动态变权生物神经网络 小世界网络 Hodgkin-Huxley方程     

Hierarchy property of traffic networks

The flourishing complex network theory has aroused increasing interest in studying the properties of real-world networks. Based on the traffic network of Chang--Zhu--Tan urban agglomeration in central China, some basic network topological characteristics were computed with data collected from local traffic maps, which showed that the traffic networks were small-world networks with strong resilience against failure; more importantly, the investigations of assortativity coefficient and average nearest-neighbour degree implied the disassortativity of the traffic networks. Since traffic network hierarchy as an important basic property has been neither studied intensively nor proved quantitatively, the authors are inspired to analyse traffic network hierarchy with disassortativity and to finely characterize hierarchy in the traffic networks by using the n-degree--n-clustering coefficient relationship. Through numerical results and analyses an exciting conclusion is drawn that the traffic networks exhibit a significant hierarchy, that is, the traffic networks are proved to be hierarchically organized. The result provides important information and theoretical groundwork for optimal transport planning.     

Detection of node group membership in networks with group overlap

Most networks found in social and biochemical systems have modular structures. An important question prompted by the modularity of these networks is whether nodes can be said to belong to a single group. If they cannot, we would need to consider the role of “overlapping communities.” Despite some efforts in this direction, the problem of detecting overlapping groups remains unsolved because there is neither a formal definition of overlapping community, nor an ensemble of networks with which to test the performance of group detection algorithms when nodes can belong to more than one group. Here, we introduce an ensemble of networks with overlapping groups. We then apply three group identification methods – modularity maximization, k-clique percolation, and modularity-landscape surveying – to these networks. We find that the modularity-landscape surveying method is the only one able to detect heterogeneities in node memberships, and that those heterogeneities are only detectable when the overlap is small. Surprisingly, we find that the k-clique percolation method is unable to detect node membership for the overlapping case.     

Adaptive approach to global synchronization of directed networks with fast switching topologies

Global synchronization of directed networks with switching topologies is investigated. It is found that if there exists at least one directed spanning tree in the network with the fixed time-average topology and the time-average topology is achieved sufficiently fast, the network will reach global synchronization for appreciate coupling strength. Furthermore, this appreciate coupling strength may be obtained by local adaptive approach. A sufficient condition about the global synchronization is given. Numerical simulations verify the effectiveness of the adaptive strategy.     

Pinning synchronization of time-varying polytopic directed stochastic networks

In this Letter, pinning synchronization of a directed network with Markovian jump (DNMJ) and nonlinear perturbations is considered. By analyzing the structure of the network, a detailed pinning scheme is given to ensure the synchronization of all nodes in a DNMJ. This pinning scheme can overcome those difficulties on deciding which nodes needs to be pinned. This scheme can also identify the exact least number of pinned nodes for a DNMJ model. In addition, the time-varying polytopic directed network with Markovian jump is discussed. Finally, examples are provided to illustrate the effectiveness of the gained criteria.