Effects of accelerating growth on the evolution of weighted complex networks

Many real systems possess accelerating statistics where the total number of edges grows faster than the network size. In this paper, we propose a simple weighted network model with accelerating growth. We derive analytical expressions for the evolutions and distributions for strength, degree, and weight, which are relevant to accelerating growth. We also find that accelerating growth determines the clustering coefficient of the networks. Interestingly, the distributions for strength, degree, and weight display a transition from scale-free to exponential form when the parameter with respect to accelerating growth increases from a small to large value. All the theoretical predictions are successfully contrasted with numerical simulations.     

Recursive weighted treelike networks

We propose a geometric growth model for weighted scale-free networks, which is controlled by two tunable parameters. We derive exactly the main characteristics of the networks, which are partially determined by the parameters. Analytical results indicate that the resulting networks have power-law distributions of degree, strength, weight and betweenness, a scale-free behavior for degree correlations, logarithmic small average path length and diameter with network size. The obtained properties are in agreement with empirical data observed in many real-life networks, which shows that the presented model may provide valuable insight into the real systems.     

The effects of degree correlations on network topologies and robustness

Complex networks have been applied to model numerous interactive nonlinear systems in the real world. Knowledge about network topology is crucial to an understanding of the function, performance and evolution of complex systems. In the last few years, many network metrics and models have been proposed to investigate the network topology, dynamics and evolution. Since these network metrics and models are derived from a wide range of studies, a systematic study is required to investigate the correlations among them. The present paper explores the effect of degree correlation on the other network metrics through studying an ensemble of graphs where the degree sequence (set of degrees) is fixed. We show that to some extent, the characteristic path length, clustering coefficient, modular extent and robustness of networks are directly influenced by the degree correlation.     

A Collaboration Network Model with Multiple Evolving Factors

To describe the empirical data of collaboration networks,several evolving mechanisms have been proposed,which usually introduce different dynamics factors controlling the network growth.These models can reasonably reproduce the empirical degree distributions for a number of well-studied real-world collaboration networks.On the basis of the previous studies,in this work we propose a collaboration network model in which the network growth is simultaneously controlled by three factors,including partial preferential attachment,partial random attachment and network growth speed.By using a rate equation method,we obtain an analytical formula for the act degree distribution.We discuss the dependence of the act degree distribution on these different dynamics factors.By fitting to the empirical data of two typical collaboration networks,we can extract the respective contributions of these dynamics factors to the evolution of each networks.     

基于Sierpinski分形垫的确定性复杂网络演化模型研究

近年来,人们发现大量真实网络都表现出小世界和无尺度的特性,由此复杂网络演化模型成为学术界研究的热点问题.本文基于Sierpinski分形垫,通过迭代的方式构造了两个确定性增长的复杂网络模型,即小世界网络模型(S-DSWN)和无尺度网络模型(S-DSFN);其次,给出了确定性网络模型的迭代生成算法,解析计算了其主要拓扑特性,结果表明两个网络模型在度分布、集聚系数和网络直径等结构特性方面与许多现实网络相符合;最后,提出了一个确定性的统一模型(S-DUM),将S-DSWN与S-DSFN纳入到一个框架之下,为复杂网络的相关研究提供理论基础.特别地,发现这些网络模型都是极大平面图.     

Accelerating networks: Effects of preferential connections

Networks are commonly observed structures in complex systems with interacting and interdependent parts that self-organize. For nonlinearly growing networks, when the total number of connections increases faster than the total number of nodes, the network is said to accelerate. We propose a systematic model for the dynamics of growing networks represented by distribution kinetics equations. We define the nodal-linkage distribution, construct a population dynamics equation based on the association-dissociation process, and perform the moment calculations to describe the dynamics of such networks. For nondirectional networks with finite numbers of nodes and connections, the moments are the total number of nodes, the total number of connections, and the degree (the average number of connections per node), represented by the average moment. Size independent rate coefficients yield an exponential network describing the network without preferential attachment, and size dependent rate coefficients produce a power law network with preferential attachment. The model quantitatively describes accelerating network growth data for a supercomputer (Earth Simulator), for regulatory gene networks, and for the Internet.     

有倾向性重连产生的反匹配网络

在具有网络结构的系统中度关联属性对于动力学行为具有重要的影响, 所以产生适当度关联网络的方法对于大量网络系统的研究具有重要的作用. 尽管产生正匹配网络的方法已经得到很好的验证, 但是产生反匹配网络的方法还没有被系统的讨论过. 重新连接网络中的边是产生度关联网络的一个常用方法. 这里我们研究使用重连方法产生反匹配无标度网络的有效性. 我们的研究表明, 有倾向的重连可以增强网络的反匹配属性. 但是有倾向重连不能使皮尔森度相关系数下降到-1, 而是存在一个依赖于网络参数的最小值. 我们研究了网络的主要参数对于网络度相关系数的影响, 包括网络尺寸, 网络的连接密度和网络节点的度差异程度. 研究表明在网络尺寸大的情况下和节点度差异性强的情况下, 重连的效果较差. 我们研究了真实Internet网络, 发现模型产生的网络经过重连不能达到真实网络的度关联系数.     

S-curve networks and an approximate method for estimating degree distributions of complex networks

In the study of complex networks almost all theoretical models have the property of infinite growth,but the size of actual networks is finite.According to statistics from the China Internet IPv4(Internet Protocol version 4) addresses,this paper proposes a forecasting model by using S curve(logistic curve).The growing trend of IPv4 addresses in China is forecasted.There are some reference values for optimizing the distribution of IPv4 address resource and the development of IPv6.Based on the laws of IPv4 growth,that is,the bulk growth and the finitely growing limit,it proposes a finite network model with a bulk growth.The model is said to be an S-curve network.Analysis demonstrates that the analytic method based on uniform distributions(i.e.,Barab’asi-Albert method) is not suitable for the network.It develops an approximate method to predict the growth dynamics of the individual nodes,and uses this to calculate analytically the degree distribution and the scaling exponents.The analytical result agrees with the simulation well,obeying an approximately power-law form.This method can overcome a shortcoming of Baraba’si-Albert method commonly used in current network research.     

Grand Canonical Ensembles of Sparse Networks and Bayesian Inference

Maximum entropy network ensembles have been very successful in modelling sparse network topologies and in solving challenging inference problems. However the sparse maximum entropy network models proposed so far have fixed number of nodes and are typically not exchangeable. Here we consider hierarchical models for exchangeable networks in the sparse limit, i.e., with the total number of links scaling linearly with the total number of nodes. The approach is grand canonical, i.e., the number of nodes of the network is not fixed a priori: it is finite but can be arbitrarily large. In this way the grand canonical network ensembles circumvent the difficulties in treating infinite sparse exchangeable networks which according to the Aldous-Hoover theorem must vanish. The approach can treat networks with given degree distribution or networks with given distribution of latent variables. When only a subgraph induced by a subset of nodes is known, this model allows a Bayesian estimation of the network size and the degree sequence (or the sequence of latent variables) of the entire network which can be used for network reconstruction.     

The influence of tie strength on evolutionary games on networks: An empirical investigation

Extending previous work on unweighted networks, we present here a systematic numerical investigation of standard evolutionary games on weighted networks. In the absence of any reliable model for generating weighted social networks, we attribute weights to links in a few ways supported by empirical data ranging from totally uncorrelated to weighted bipartite networks. The results of the extensive simulation work on standard complex network models show that, except in a case that does not seem to be common in social networks, taking the tie strength into account does not change in a radical manner the long-run steady-state behavior of the studied games. Besides model networks, we also included a real-life case drawn from a coauthorship network. In this case also, taking the weights into account only changes the results slightly with respect to the raw unweighted graph, although to draw more reliable conclusions on real social networks many more cases should be studied as these weighted networks become available.     

A neighbourhood evolving network model

Many social, technological, biological and economical systems are best described by evolved network models. In this short Letter, we propose and study a new evolving network model. The model is based on the new concept of neighbourhood connectivity, which exists in many physical complex networks. The statistical properties and dynamics of the proposed model is analytically studied and compared with those of Barabási–Albert scale-free model. Numerical simulations indicate that this network model yields a transition between power-law and exponential scaling, while the Barabási–Albert scale-free model is only one of its special (limiting) cases. Particularly, this model can be used to enhance the evolving mechanism of complex networks in the real world, such as some social networks development.     

Modelling temporal networks of human face-to-face contacts with public activity and individual reachability

Modelling temporal networks of human face-to-face contacts is vital both for understanding the spread of airborne pathogens and word-of-mouth spreading of information. Although many efforts have been devoted to model these temporal networks, there are still two important social features, public activity and individual reachability, have been ignored in these models. Here we present a simple model that captures these two features and other typical properties of empirical face-to-face contact networks. The model describes agents which are characterized by an attractiveness to slow down the motion of nearby people, have event-triggered active probability and perform an activity-dependent biased random walk in a square box with periodic boundary. The model quantitatively reproduces two empirical temporal networks of human face-to-face contacts which are testified by their network properties and the epidemic spread dynamics on them.     

Traffic dynamics in scale-free networks with tunable strength of community structure

In this paper we systematically investigate the impact of community structure on traffic dynamics in scale-free networks based on local routing strategy. A growth model is introduced to construct scale-free networks with tunable strength of community structure, and a packet routing strategy with a parameter α is used to deal with the navigation and transportation of packets simultaneously. Simulations show that the maximal network capacity stands at α=−1 in the case of identical vertex capacity and monotonously decreases with the strength of community structure which suggests that the networks with fuzzy community structure (i.e., community strength is weak) are more efficient in delivering packets than those with pronounced community structure. To explain these results, the distribution of packets of each vertex is carefully studied. Our results indicate that the moderate strength of community structure is more convenient for the information transfer of real complex systems.     

Role of fractal dimension in random walks on scale-free networks

Fractal dimension is central to understanding dynamical processes occurring on networks; however, the relation between fractal dimension and random walks on fractal scale-free networks has been rarely addressed, despite the fact that such networks are ubiquitous in real-life world. In this paper, we study the trapping problem on two families of networks. The first is deterministic, often called (x,y)-flowers; the other is random, which is a combination of (1,3)-flower and (2,4)-flower and thus called hybrid networks. The two network families display rich behavior as observed in various real systems, as well as some unique topological properties not shared by other networks. We derive analytically the average trapping time for random walks on both the (x,y)-flowers and the hybrid networks with an immobile trap positioned at an initial node, i.e., a hub node with the highest degree in the networks. Based on these analytical formulae, we show how the average trapping time scales with the network size. Comparing the obtained results, we further uncover that fractal dimension plays a decisive role in the behavior of average trapping time on fractal scale-free networks, i.e., the average trapping time decreases with an increasing fractal dimension.     

Neutron diffraction study of the magnetic structure of Na2 RuO 4

We present a novel model to simulate real social networks of complex interactions, based in a system of colliding particles (agents). The network is build by keeping track of the collisions and evolves in time with correlations which emerge due to the mobility of the agents. Therefore, statistical features are a consequence only of local collisions among its individual agents. Agent dynamics is realized by an event-driven algorithm of collisions where energy is gained as opposed to physical systems which have dissipation. The model reproduces empirical data from networks of sexual interactions, not previously obtained with other approaches.     

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.     

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.     

Monomer-dimer model on a scale-free small-world network

The explicit determination of the number of monomer-dimer arrangements on a network is a theoretical challenge, and exact solutions to monomer-dimer problem are available only for few limiting graphs with a single monomer on the boundary, e.g., rectangular lattice and quartic lattice; however, analytical research (even numerical result) for monomer-dimer problem on scale-free small-world networks is still missing despite the fact that a vast variety of real systems display simultaneously scale-free and small-world structures. In this paper, we address the monomer-dimer problem defined on a scale-free small-world network and obtain the exact formula for the number of all possible monomer-dimer arrangements on the network, based on which we also determine the asymptotic growth constant of the number of monomer-dimer arrangements in the network. We show that the obtained asymptotic growth constant is much less than its counterparts corresponding to two-dimensional lattice and Sierpinski fractal having the same average degree as the studied network, which indicates from another aspect that scale-free networks have a fundamentally distinct architecture as opposed to regular lattices and fractals without power-law behavior.     

基于复杂网络的灾害蔓延模型评价及改进

介绍了几种已存在的复杂网络上的灾害蔓延模型,在对模型进行优缺点评价的基础上,给出了一种网络中存在冗余系统的改进模型.对不同的模型,在不同的网络结构下,仿真分析了蔓延过程的差异以及重要参数的作用.结果表明网络中存在冗余系统的灾害蔓延过程变缓,相应有了更多的应急、补救时间,同时也解释了现实生活中大规模灾害事件很少发生的原因. 关键词： 复杂网络 灾害蔓延 冗余系统     

Complex grid computing

This article investigates the functional properties of complex networks used as grid computing systems. Complex networks following the Erdös-Rényi model and other models with a preferential attachment rule (with and without growth) or priority to the connection of isolated nodes are studied. Regular networks are also considered for comparison. The processing load of the parallel program executed on the grid is assigned to the nodes on demand, and the efficiency of the overall computation is quantified in terms of the parallel speedup. It is found that networks with preferential attachment allow lower computing efficiency than networks with uniform link attachment. At the same time, considering only node clusters of the same size, preferential attachment networks display better efficiencies. The regular networks, on the other hand, display a poor efficiency, due to their implied larger internode distances. A correlation is observed between the topological properties of the network, specially average cluster size, and their respective computing efficiency.