Degree distribution of a new model for evolving networks

We propose and study an evolving network model with both preferential and random attachments of new links, incorporating the addition of new nodes, new links, and the removal of links. We first show that the degree evolution of a node follows a nonhomogeneous Markov chain. Based on the concept of Markov chain, we provide the exact solution of the degree distribution of this model and show that the model can generate scale-free evolving network.     

The classification and analysis of dynamic networks

In this paper we, firstly, classify the complex networks in which the nodes are of the lifetime distribution. Secondly, in order to study complex networks in terms of queuing system and homogeneous Markov chain, we establish the relation between the complex networks and queuing system, providing a new way of studying complex networks. Thirdly, we prove that there exist stationary degree distributions of M--G--P network, and obtain the analytic expression of the distribution by means of Markov chain theory. We also obtain the average path length and clustering coefficient of the network. The results show that M--G--P network is not only scale-free but also of a small-world feature in proper conditions.     

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.     

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.     

Deterministic scale-free small-world networks of arbitrary order

In many real-life networks, both the scale-free distribution of degree and small-world behavior are important features. There are many random or deterministic models of networks to simulate these features separately. However, there are few models that combine the scale-free effect and small-world behavior, especially in terms of deterministic versions. What is more, all the existing deterministic algorithms running in the iterative mode generate networks with only several discrete numbers of nodes. This contradicts the purpose of creating a deterministic network model on which we can simulate some dynamical processes as widely as possible. According to these facts, this paper proposes a deterministic network generation algorithm, which can not only generate deterministic networks following a scale-free distribution of degree and small-world behavior, but also produce networks with arbitrary number of nodes. Our scheme is based on a complete binary tree, and each newly generated leaf node is further linked to its full brother and one of its direct ancestors. Analytical computation and simulation results show that the average degree of such a proposed network is less than 5, the average clustering coefficient is high (larger than 0.5, even for a network of size 2 million) and the average shortest path length increases much more slowly than logarithmic growth for the majority of small-world network models.     

Robustness measurement of scale-free networks based on motif entropy

As a classical complex network model, scale-free network is widely used and studied. And motifs, as a high-order subgraph structure, frequently appear in scale-free networks, and have a great influence on the structural integrity, functional integrity and dynamics of the networks. In order to overcome the shortcomings in the existing work on the robustness of complex networks, only nodes or edges are considered, while the defects of high-order structure in the network are ignored. From the perspective of network motif, we propose an entropy of node degree distribution based on motif to measure the robustness of scale-free networks under random attacks. The effectiveness and superiority of our method are verified and analyzed in the BA scale-free networks.     

Rumor spreading model considering forgetting and remembering mechanisms in inhomogeneous networks

The SIHR rumor spreading model with consideration of the forgetting and remembering mechanisms was studied in homogeneous networks. We further investigate the properties of the SIHR model in inhomogeneous networks. The SIHR model is refined and mean-field equations are derived to describe the dynamics of the rumor spreading model in inhomogeneous networks. Steady-state analysis is carried out, which shows no spreading threshold existing. Numerical simulations are conducted in a BA scale-free network. The simulation results show that the network topology exerts significant influences on the rumor spreading: In comparison with the ER network, the rumor spreads faster and the final size of the rumor is smaller in BA scale-free network; the forgetting and remembering mechanisms greatly impact the final size of the rumor. Finally, through the numerical simulation, we examine the effects that the spreading rate and the stifling rate have on the the influence of the rumor. In addition, the no threshold result is verified.     

Maximum entropy networks are more controllable than preferential attachment networks

A maximum entropy (ME) method to generate typical scale-free networks has been recently introduced. We investigate the controllability of ME networks and Barabási–Albert preferential attachment networks. Our experimental results show that ME networks are significantly more easily controlled than BA networks of the same size and the same degree distribution. Moreover, the control profiles are used to provide insight into control properties of both classes of network. We identify and classify the driver nodes and analyze the connectivity of their neighbors. We find that driver nodes in ME networks have fewer mutual neighbors and that their neighbors have lower average degree. We conclude that the properties of the neighbors of driver node sensitively affect the network controllability. Hence, subtle and important structural differences exist between BA networks and typical scale-free networks of the same degree distribution.     

Emergence of scaling and assortative mixing through altruism

Many social networks, apart from displaying scale-free characteristics observed in some instances, possess another remarkable feature that distinguishes them from those that appear in biological and technological context—assortativity. However, little or no attention has been payed to the mechanism of assortativity in modeling these networks. Inspired by individuals’ altruistic behavior in sociology, we develop a model with a different growth mechanism called “altruistic attachment”, which can reproduce not only the power law degree distribution but degree correlations. We study in detail the statistical properties of our network model, which we also demonstrate striking differences with the BA model, and can portray real social networks more precisely.     

Stability of the BA Network: a New Approach to Rigorous Proof

We propose a new approach to rigorously prove the existence of the steady-state degree distribution for the BA network. The approach is based on a vector Markov chain of vertex numbers in the network evolving process. This framework provides a rigorous theoretical basis for the rate equation approach which has been widely applied to many problems in the field of complex networks, e.g., epidemic spreading and dynamic synchronization.     

Evolution of Traffic Flow with Scale-Free Topology

We investigate the emergence of scale-free behaviour in a traffic system by using the NaSch model to simulate the evolution of traffic flow. A kind of evolution networks has been proposed, which is based on the evolution of the traffic flow. The network growth does not take into account preferential attachment, and the attachment of new node is independent of degree. The simulation results demonstrate that the output distribution of links is well described by a scale-free distribution.     

Theory of rumour spreading in complex social networks

We introduce a general stochastic model for the spread of rumours, and derive mean-field equations that describe the dynamics of the model on complex social networks (in particular, those mediated by the Internet). We use analytical and numerical solutions of these equations to examine the threshold behaviour and dynamics of the model on several models of such networks: random graphs, uncorrelated scale-free networks and scale-free networks with assortative degree correlations. We show that in both homogeneous networks and random graphs the model exhibits a critical threshold in the rumour spreading rate below which a rumour cannot propagate in the system. In the case of scale-free networks, on the other hand, this threshold becomes vanishingly small in the limit of infinite system size. We find that the initial rate at which a rumour spreads is much higher in scale-free networks than in random graphs, and that the rate at which the spreading proceeds on scale-free networks is further increased when assortative degree correlations are introduced. The impact of degree correlations on the final fraction of nodes that ever hears a rumour, however, depends on the interplay between network topology and the rumour spreading rate. Our results show that scale-free social networks are prone to the spreading of rumours, just as they are to the spreading of infections. They are relevant to the spreading dynamics of chain emails, viral advertising and large-scale information dissemination algorithms on the Internet.     

Modeling Evolution of Weighted Clique Networks

We propose a weighted clique network evolution model, which expands continuously by the addition of a new clique (maximal complete sub-graph) at each time step. And the cliques in the network overlap with each other. The structural expansion of the weighted clique network is combined with the edges' weight and vertices' strengths dynamical evolution. The model is based on a weight-driven dynamics and a weights' enhancement mechanism combining with the network growth. We study the network properties, which include the distribution of vertices' strength and the distribution of edges' weight, and find that both the distributions follow the scale-free distribution. At the same time, we also find that the relationship between strength and degree of a vertex are linear correlation during the growth of the network. On the basis of mean-field theory, we study the weighted network model and prove that both vertices' strength and edges' weight of this model follow the scale-free distribution. And we exploit an algorithm to forecast the network dynamics, which can be used to reckon the distributions and the corresponding scaling exponents. Furthermore, we observe that mean-field based theoretic results are
consistent with the statistical data of the model, which denotes the theoretical result in this paper is effective.     

Mobile user forecast and power-law acceleration invariance of scale-free networks

This paper studies and predicts the number growth of China's mobile users by using the power-law regression. We find that the number growth of the mobile users follows a power law. Motivated by the data on the evolution of the mobile users, we consider scenarios of self-organization of accelerating growth networks into scale-free structures and propose a directed network model, in which the nodes grow following a power-law acceleration. The expressions for the transient and the stationary average degree distributions are obtained by using the Poisson process. This result shows that the model generates appropriate power-law connectivity distributions. Therefore, we find a power-law acceleration invariance of the scale-free networks. The numerical simulations of the models agree with the analytical results well.     

新节点的边对网络无标度性影响

分析新节点边对网络无标度性的影响.虽然亚线性增长网络瞬态平均度分布尾部表现出了幂律分布性质，但是，这个网络的稳态度分布并不是幂律分布，由此可见，计算机模拟预测不出网络稳态度分布，它只能预测网络的瞬态度分布.进而建立随机增长网络模型，利用随机过程理论得到了这个模型的度分布的解析表达式，结果表明这个网络是无标度网络.     

新节点的边对网络无标度性影响

分析新节点边对网络无标度性的影响.虽然亚线性增长网络瞬态平均度分布尾部表现出了幂律分布性质,但是,这个网络的稳态度分布并不是幂律分布,由此可见,计算机模拟预测不出网络稳态度分布,它只能预测网络的瞬态度分布.进而建立随机增长网络模型,利用随机过程理论得到了这个模型的度分布的解析表达式,结果表明这个网络是无标度网络. 关键词： 复杂网络 无标度网络 小世界网络 度分布     

Self-similarity, small-world, scale-free scaling, disassortativity, and robustness in hierarchical lattices

In this paper, firstly, we study analytically the topological features of a family of hierarchical lattices (HLs) from the view point of complex networks. We derive some basic properties of HLs controlled by a parameter q: scale-free degree distribution with exponent γ=2+ln 2/(ln q), null clustering coefficient, power-law behavior of grid coefficient, exponential growth of average path length (non-small-world), fractal scaling with dimension d_B=ln (2q)/(ln 2), and disassortativity. Our results show that scale-free networks are not always small-world, and support the conjecture that self-similar scale-free networks are not assortative. Secondly, we define a deterministic family of graphs called small-world hierarchical lattices (SWHLs). Our construction preserves the structure of hierarchical lattices, including its degree distribution, fractal architecture, clustering coefficient, while the small-world phenomenon arises. Finally, the dynamical processes of intentional attacks and collective synchronization are studied and the comparisons between HLs and Barabási-Albert (BA) networks as well as SWHLs are shown. We find that the self-similar property of HLs and SWHLs significantly increases the robustness of such networks against targeted damage on hubs, as compared to the very vulnerable non fractal BA networks, and that HLs have poorer synchronizability than their counterparts SWHLs and BA networks. We show that degree distribution of scale-free networks does not suffice to characterize their synchronizability, and that networks with smaller average path length are not always easier to synchronize.     

Scale-Free Properties in Traffic System

In this work, we propose a new model of evolution networks, which is based on the evolution of the traffic flow. In our method, the network growth does not take into account preferential attachment, and the attachment of new node is independent of the degree of nodes. Our aim is that employing the theory of evolution network, we give a further understanding about the dynamical evolution of the traffic flow. We investigate the probability distributions and scaling properties of the proposed model. The simulation results indicate that in the proposed model, the distribution of the output connections can be well described by scale-free distribution. Moreover, the distribution of the connections is largely related to the traffic flow states, such as the exponential distribution (i.e., the scale-free distribution) and random distribution etc.     

Number of loops of size h in growing scale-free networks

The hierarchical structure of scale-free networks has been investigated focusing on the scaling of the number N(h)(t) of loops of size h as a function of the system size. In particular, we have found the analytic expression for the scaling of N(h)(t) in the Barabási-Albert (BA) scale-free network. We have performed numerical simulations on the scaling law for N(h)(t) in the BA network and in other growing scale-free networks, such as the bosonic network and the aging nodes network. We show that in the bosonic network and in the aging node network the phase transitions in the topology of the network are accompained by a change in the scaling of the number of loops with the system size.