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.     

一类高聚类系数的加权无标度网络及其同步能力分析

针对真实世界中大规模网络都具有明显聚类效应的特点, 提出一类具有高聚类系数的加权无标度网络演化模型, 该模型同时考虑了优先连接、三角结构、随机连接和社团结构等四种演化机制. 在模型演化规则中, 以概率p增加单个节点, 以概率1–p增加一个社团. 与以往研究的不同在于新边的建立, 以概率φ在旧节点之间进行三角连接, 以概率1–φ进行随机连接. 仿真分析表明, 所提出的网络度、强度和权值分布都是服从幂律分布的形式, 且具有高聚类系数的特性, 聚类系数的提高与社团结构和随机连接机制有直接的关系. 最后通过数值仿真分析了网络演化机制对同步动态特性的影响, 数值仿真结果表明, 网络的平均聚类系数越小, 网络的同步能力越强. 关键词： 无标度网络 加权网络 聚类系数 同步能力     

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.     

Markov chains theory for scale-free networks

This paper proposes a Markov chain method to predict the growth dynamics of the individual nodes in scale-free networks, and uses this to calculate numerically the degree distribution. We first find that the degree evolution of a node in the BA model is a nonhomogeneous Markov chain. An efficient algorithm to calculate the degree distribution is developed by the theory of Markov chains. The numerical results for the BA model are consistent with those of the analytical approach. A directed network with the logarithmic growth is introduced. The algorithm is applied to calculate the degree distribution for the model. The numerical results show that the system self-organizes into a scale-free network.     

Link prediction in complex networks via modularity-based belief propagation

Link prediction aims at detecting missing, spurious or evolving links in a network, based on the topological information and/or nodes' attributes of the network. Under the assumption that the likelihood of the existence of a link between two nodes can be captured by nodes' similarity, several methods have been proposed to compute similarity directly or indirectly, with information on node degree. However, correctly predicting links is also crucial in revealing the link formation mechanisms and thus in providing more accurate modeling for networks. We here propose a novel method to predict links by incorporating stochastic-block-model link generating mechanisms with node degree. The proposed method first recovers the underlying block structure of a network by modularity-based belief propagation, and based on the recovered block structural information it models the link likelihood between two nodes to match the degree sequence of the network. Experiments on a set of real-world networks and synthetic networks generated by stochastic block model show that our proposed method is effective in detecting missing, spurious or evolving links of networks that can be well modeled by a stochastic block model. This approach efficiently complements the toolbox for complex network analysis, offering a novel tool to model links in stochastic block model networks that are fundamental in the modeling of real world complex networks.     

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

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

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.     

一种信息传播促进网络增长的网络演化模型

为了研究信息传播过程对复杂网络结构演化的影响,提出了一种信息传播促进网络增长的网络演化模型,模型包括信息传播促进网内增边、新节点通过局域世界建立第一条边和信息传播促进新节点连边三个阶段,通过多次自回避随机游走模拟信息传播过程,节点根据路径节点的节点度和距离与其选择性建立连接。理论分析和仿真实验表明,模型不仅具有小世界和无标度特性,而且不同参数下具有漂移幂律分布、广延指数分布等分布特性,呈现小变量饱和、指数截断等非幂律现象,同时,模型可在不改变度分布的情况下调节集聚系数,并能够产生从同配到异配具有不同匹配模式的网络.     

一种具有指数截断和局部集聚特性的网络模型

针对真实网络局域演化的特点,提出了一种具有局部集聚特性的网络演化模型——局部集聚模型(LC模型). 理论分析和模拟实验表明,LC模型的节点度服从一种具有指数截断的幂律分布,同时它的平均聚类系数要远大于局域世界模型,接近真实网络. 模拟了LC模型对恶意攻击和随机错误的抵抗力,发现高聚类系数的LC模型对恶意攻击更加脆弱. 关键词： 局部集聚 指数截断 脆弱性 无标度网络     

The degree distribution of fixed act-size collaboration networks

In this paper, we investigate a special evolving model of collaboration networks, where the act-size is fixed. Based on the first-passage probability of Markov chain theory, this paper provides a rigorous proof for the existence of a limiting degree distribution of this model and proves that the degree distribution obeys the power-law form with the exponent adjustable between 2 and 3.     

一种新型电力网络局域世界演化模型

现实世界中的许多系统都可以用复杂网络来描述,电力系统是人类创造的最为复杂的网络系统之一.当前经典的网络模型与实际电力网络存在较大差异.从电力网络本身的演化机理入手,提出并研究了一种可以模拟电力网络演化规律的新型局域世界网络演化模型.理论分析表明该模型的度分布具有幂尾特性,且幂律指数在3—∞之间可调.最后通过对中国北方电网和美国西部电网的仿真以及和无标度网络、随机网络的对比,验证了该模型可以很好地反映电力网络的演化规律,并且进一步证实了电力网络既不是无标度网络,也不是完全的随机网络. 关键词： 电力网络 演化模型 局域世界 幂律分布     

简易广义合作网络度分布的稳定性

本文对简易广义合作网络的三类特殊情形（择优连接、随机连接、混合连接）进行了研究. 基于马氏链理论, 给出它们度分布稳定性存在的严格证明, 并且得到相应网络度分布和度指数的精确表达式. 特别地, 对于混合连接情况, 说明在连线方式中只要存在择优成分, 网络度分布就服从幂律分布, 即所得网络为无标度网络. 关键词： 简易广义合作网络 无标度网络 马氏链 度分布     

Predicting the growth of new links by new preferential attachment similarity indices

By revisiting the preferential attachment (PA) mechanism for generating a classical scale-free network, we propose a class of novel preferential attachment similarity indices for predicting future links in evolving networks. Extensive experiments on 14 real-life networks show that these new indices can provide more accurate prediction than the traditional one. Due to the improved prediction accuracy and low computational complexity, these proposed preferential attachment indices can be helpful for providing both instructions for mining unknown links and new insights to understand the underlying mechanisms that drive the network evolution.     

Degree and wealth distribution in a network induced by wealth

A network induced by wealth is a social network model in which wealth induces individuals to participate as nodes, and every node in the network produces and accumulates wealth utilizing its links. More specifically, at every time step a new node is added to the network, and a link is created between one of the existing nodes and the new node. Innate wealth-producing ability is randomly assigned to every new node, and the node to be connected to the new node is chosen randomly, with odds proportional to the accumulated wealth of each existing node. Analyzing this network using the mean value and continuous flow approaches, we derive a relation between the conditional expectations of the degree and the accumulated wealth of each node. From this relation, we show that the degree distribution of the network induced by wealth is scale-free. We also show that the wealth distribution has a power-law tail and satisfies the 80/20 rule. We also show that, over the whole range, the cumulative wealth distribution exhibits the same topological characteristics as the wealth distributions of several networks based on the Bouchaud-Mèzard model, even though the mechanism for producing wealth is quite different in our model. Further, we show that the cumulative wealth distribution for the poor and middle class seems likely to follow by a log-normal distribution, while for the richest, the cumulative wealth distribution has a power-law behavior.     

A highly clustered scale-free network evolved by random walking

In present paper, we propose a highly clustered weighted network model that incorporates the addition of a new node with some links, new links between existing nodes and the edge's weight dynamical evolution based on weight-dependent walks at each time step. The analytical approach and numerical simulation show that the system grows into a weighted network with the power-law distributions of strength, weight and degree. The weight-dependent walk length l will not influence the strength distribution, but the clustering coefficient of the network is sensitive to l. Particularly, the clustering coefficient is especially high and almost independent of the network size when l=2.     

Growing community networks with local events

The study of community networks has attracted considerable attention recently. In this paper, we propose an evolving community network model based on local processes, the addition of new nodes intra-community and new links intra- or inter-community. Employing growth and preferential attachment mechanisms, we generate networks with a generalized power-law distribution of nodes’ degrees.     

The physical position neighbourhood evolving network model

Many social, technological, biological and economical systems are properly described by evolved network models. In this paper, a new evolving network model with the concept of physical position neighbourhood connectivity is proposed and studied. This concept exists in many real complex networks such as communication networks. The simulation results for network parameters such as the first nonzero eigenvalue and maximal eigenvalue of the graph Laplacian, clustering coefficients, average distances and degree distributions for different evolving parameters of this model are presented. The dynamical behaviour of each node on the consensus problem is also studied. It is found that the degree distribution of this new model represents a transition between power-law and exponential scaling, while the Barábasi-Albert scale-free model is only one of its special (limiting) cases. It is also found that the time to reach a consensus becomes shorter sharply with increasing of neighbourhood scale of the nodes.     

Network formed by traces of random walks

We propose a model of time evolving networks in which a kind of transport between vertices generates new edges in the graph. We call the model “Network formed by traces of random walks”, because the transports are represented abstractly by random walks. Our numerical calculations yield several important properties observed commonly in complex networks, although the graph at initial time is only a one-dimensional lattice. For example, the distribution of vertex degree exhibits various behaviors such as exponential, power law like, and bi-modal distribution according to change of probability of extinction of edges. Another property such as strong clustering structure and small mean vertex–vertex distance can also be found. The transports represented by random walks in a framework of strong links between regular lattice is a new mechanisms which yields biased acquisition of links for vertices.     

An evolving network model with modular growth

In this paper, we propose an evolving network model growing fast in units of module, according to the analysis of the evolution characteristics in real complex networks. Each module is a small-world network containing several interconnected nodes and the nodes between the modules are linked by preferential attachment on degree of nodes. We study the modularity measure of the proposed model, which can be adjusted by changing the ratio of the number of inner-module edges and the number of inter-module edges. In view of the mean-field theory, we develop an analytical function of the degree distribution, which is verified by a numerical example and indicates that the degree distribution shows characteristics of the small-world network and the scale-free network distinctly at different segments. The clustering coefficient and the average path length of the network are simulated numerically, indicating that the network shows the small-world property and is affected little by the randomness of the new module.     

Modelling of weighted evolving networks with community structures

Many social and biological networks consist of communities–groups of nodes within which links are dense but among which links are sparse. It turns out that most of these networks are best described by weighted networks, whose properties and dynamics depend not only on their structures but also on the link weights among their nodes. Recently, there are considerable interests in the study of properties as well as modelling of such networks with community structures. To our knowledge, however, no study of any weighted network model with such a community structure has been presented in the literature to date. In this paper, we propose a weighted evolving network model with a community structure. The new network model is based on the inner-community and inter-community preferential attachments and preferential strengthening mechanism. Simulation results indicate that this network model indeed reflect the intrinsic community structure, with various power-law distributions of the node degrees, link weights, and node strengths.