Scale-free network models with accelerating growth

Complex networks are everywhere. A typical example is software network. Basing on analyzing evolutive structure of the software networks, we consider accelerating growth of network as power-law growth, which can be more easily generalized to real systems than linear growth. For accelerating growth via a power law and scale-free state with preferential linking, we focus on exploring the generic property of complex networks. Generally, two scenarios are possible. In one of them, the links are undirected. In the other scenario, the links are directed. We propose two models that can predict the emergence of power-law growth and scale-free state in good agreement with these two scenarios and can simulate much more real systems than existing scale-free network models. Moreover, we use the obtained predictions to fit accelerating growth and the connectivity distribution of software networks describing scale-free structure. The combined analytical and numerical results indicate the emergence of a novel set of models that considerably enhance our ability to understand and characterize complex networks, whose applicability reaches far beyond the quoted examples.     

Scale-free network modles with accelerating growth

Complex networks are everywhere. A typical example is software network. Basing on analyzing evolutive structure of the software networks, we consider accelerating growth of network as power-law growth, which can be more easily generalized to real systems than linear growth. For accelerating growth via a power law and scale-free state with preferential linking, we focus on exploring the generic property of complex networks. Generally, two scenarios are possible. In one of them, the links are undirected. In the other scenario, the links are directed. We propose two models that can predict the emergence of power-law growth and scale-free state in good agreement with these two scenarios and can simulate much more real systems than existing scale-free network models. Moreover, we use the obtained predictions to fit accelerating growth and the connectivity distribution of software networks describing scale-free structure. The combined analytical and numerical results indicate the emergence of a novel set of models that considerably enhance our ability to understand and characterize complex networks, whose applicability reaches far beyond the quoted examples.     

Complex Network Phenomena in Telecommunication Systems

Many networks such as the Internet have been found to possess scale-free and small-world network properties reflected by power-law distributions. Scale-free properties evolve in large complex networks through self-organizing processes and, more specifically, preferential attachment. New nodes in a network tend to attach to other vertices that are already well-connected. Because traffic is routed mainly through a few highly connected and concentrated vertices, the diameter of the network is small in comparison to other network structures, and movement through the network is therefore efficient. At the same time, this efficiency feature puts scale-free networks at risk for becoming disconnected or significantly disrupted when super-connected nodes are removed, either unintentionally or through a targeted attack or external force. The present paper will examine and compare properties of telecommunication networks for both the United States and Europe. Both types of networks will be examined in terms of their network topology and specifically, whether or not they are scale-free networks to be further explored by identifying and plotting power-law     

A generative model for time evolving networks

Time evolving networks have some properties in common with complex networks, while some characteristics are specific to their time evolving nature. A number of interesting properties have been observed in time-varying complex networks such as densification power-law, shrinking diameter, scale-free degree distribution, big clustering coefficient and the emergence of community structure. Existing generative models either fail to simulate all the properties or undermine the social interactions between the existing nodes over time. In this paper, we propose a generative model called socializing graph model (SGM) for those networks that evolve over time. It is an iterative procedure consisting of two steps. In the first step, we add one new node to the network at every timestamp and connect it to an existing node using a preferential attachment rule. In the second step, we add a number of edges between the existing nodes in order to reflect the emergence of social interactions between nodes over time and mimic the evolution of real networks. We present empirical results to show that SGM generates realistic prototypes of evolving networks.

     

分层抽样的无标度复杂网络可靠性度量算法

针对大型无标度复杂网络的幂律分布特性,提出了一种基于分层抽样技术的算法SSBA,通过分析样本网络推导出大型无标度复杂网络的可靠性度量参数,并给出这些参数的Bootstrap置信区间。大量的实验表明,SSBA算法能有效估算出大型无标度复杂网络的可靠性度量参数。     

无线传感器网络簇级拓扑演化模型研究

复杂网络理论研究表明,复杂系统的容错能力不仅仅存在于具有冗余组件的系统之中;而且也同样存在于具有无标度(scale-free)特征的网络之中;文章借助于复杂网络理论和偏好依附机制提出一种无线传感器网络簇级拓扑演化模型;拓扑动态分析表明,该模型能够很好地体现无线传感器簇间的拓扑生长过程,由该模型演化成的无线网络拓扑具有无标度网络的性质,所以该拓扑模型具有很强的容错性。     

一种改进的HK社交网络建模方法

随着对复杂网络研究的不断加深，社交网络建模成为研究热点之一。在Holme和Kim(HK)网络模型的基础上，提出一种改进的HK社交网络演化模型，不仅考虑了“偏好连接”、“三角结构”的传统社交网络演化机制，还在网络中新增节点的同时考虑了“内部演化”和“外部延展”2种不同的网络链路增长模式，并在传统的单向生长的网络结构基础上，创新性地提出节点度饱和与链路刷新的网络动态演化方式。仿真结果显示，改进后的HK模型其度分布呈现幂律分布特征，具有较大的聚类系数与较小的平均最短路径长度，同时满足小世界效应与无标度特性，整个社交网络模型在链路的建立与阻断过程中呈螺旋式生长，能更好地再现真实社交网络的结构特征。     

微博关系网络模型研究

舆论在微博上的传播过程可以抽象成一个生长的复杂网络。在分析微博网络特性和用户行为习惯的基础上,考虑新用户在进入网络时的同配性,建立微博关系网络的演化模型,并对模型进行仿真。分析指出,微博网络呈现出指数与幂律的混合分布。对微博网络进行实证研究,结果表明,微博关系网络中节点的度分布服从指数截断的幂律分布,具有无标度和小世界特性,与理论分析的结果相一致。     

基于重要度贡献的无标度网络节点评估方法

针对无标度网络的节点重要度评估问题,通过分析节点的邻居数量与其邻居间的拓扑结构,得到节点的结构洞重要性指标,再融合相邻节点的K核重要性指标值来确定相邻节点间的重要度贡献,以此表征相邻节点的局部信息;在此基础上,再结合表征节点位置信息的节点自身的K核重要性,从而提出一种基于节点间重要度贡献关系来评估无标度网络的节点重要度的方法.该方法综合考虑了节点的结构洞特征和K核中心性特征来确定节点的重要度,同时兼顾到了网络的局部和全局重要性.理论分析表明,此方法的时间复杂度仅为o（n²）.与其他几种算法仿真对比的结果表明,该方法可行有效,拥有理想计算能力,适用无标度网络.     

基于新局域世界的BBV网络模型演化研究

在BBV加权无标度模型演化过程中,节点加入时选取的是整个网络,而实际复杂网络中只有小部分节点能够获得全局网络的信息,大部分节点只能获取局部网络的信息。针对该问题,提出一个新局域的BBV加权网络模型,将新局域世界模型引入BBV模型中。理论分析及仿真实验结果表明,该模型节点强度具有幂律分布的特性,且幂律指数可以通过参数的修改在区间[1,3]内进行调节。     

无标度网络度秩指数的变化范围

实证研究表明,绝大多数复杂网络的结点的度分布服从幂律分布,该幂律分布的幂指数的绝对值(度分布指数)介于2和3之间．然而,至今尚未发现为什么度分布指数介于2和3之间的研究结果．本文证明了度分布指数大于2,从而部分回答了上述问题．为此,本文引进度秩指数,并给出了度秩指数和度分布指数之间的关系．通过对度秩指数与网络结构熵之间的关系的刻画,发现了度秩指数与网络结构熵以及网络规模之间的函数依赖关系,从而最终证明了度秩指数的临界值趋于1,并给出了仿真结果．     

基于藕合系数的无标度网络建模

经典的无标度网络模型在全局范围内按照一定的概率选取节点进行优先连接,而现实网络很难做到这一点。为了解决这一问题,在BA无标度网络模型的基础上,通过新增两个参数耦合系数和吸引因子来构建基于耦合系数的无标度网络模型,并通过理论计算得出该演化模型的度分布。分析发现,它具有更明显的无标度网络特性。实验仿真结果也表明,其度分布在服从幂律分布的基础上更具有平稳性和广泛的适用性。     

Hyperbolic trees for efficient routing computation

Complex system theory is increasingly applied to develop control protocols for distributed computational and networking resources. The paper deals with the important subproblem of finding complex connected structures having excellent navigability properties using limited computational resources. Recently, the two-dimensional hyperbolic space turned out to be an efficient geometry for generative models of complex networks. The networks generated using the hyperbolic metric space share their basic structural properties (like small diameter or scale-free degree distribution) with several real networks. In the paper, a new model is proposed for generating navigation trees for complex networks embedded in the two-dimensional hyperbolic plane. The generative model is not based on known hyperbolic network models: the trees are not inferred from the existing links of any network; they are generated from scratch instead and based purely on the hyperbolic coordinates of nodes. We show that these hyperbolic trees have scale-free degree distributions and are present to a large extent both in synthetic hyperbolic complex networks and real ones (Internet autonomous system topology, US flight network) embedded in the hyperbolic plane. As the main result, we show that routing on the generated hyperbolic trees is optimal in terms of total memory usage of forwarding tables.

     

复杂网络中的在线社交网络演化模型

在线社交网络是一种广泛存在的社会网络,其节点度遵循幂率分布规律,但对于其结构演化模型方面的相关研究还不多。基于复杂网络理论研究在线社交网络内部结构特征,提出一种结合内增长、外增长及内部边更替的演化模型,借助平均场理论分析该模型的拓扑特性,实验和理论分析表明由该模型生成的网络,其度分布服从幂率分布,且通过调整参数,幂率指数在1~3,能较好地反映不同类型的真实在线社交网络的度分布特征,因此具有广泛适用性。     

基于中间节点效应的无标度网络演化模型研究

原BA模型以网络中已存在的各个节点与新增节点的连接相互独立为前提。然而,在真实系统中,当网络中一个节点与新增节点连接后,该节点对其邻居节点与新增节点的连接会存在影响。针对该现象,提出了基于中间节点效应的无标度网络演化模型。首先描述与定义了中间节点效应,然后给出了中间节点效应模型的生成算法,并从理论上分析了该模型的度分布情况,最后利用仿真验证了理论分析的正确性,并就度分布、群聚系数、平均路径长度等复杂网络参数与原BA模型进行了对比,结果表明此模型能生成无标度网络并且更符合现实网络的演化过程。     

Clustering in random line graphs

We investigate the degree distribution P(k) and the clustering coefficient C of the line graphs constructed on the Erdös-Rényi networks, the exponential and the scale-free growing networks. We show that the character of the degree distribution in these graphs remains Poissonian, exponential and power law, respectively, i.e. the same as in the original networks. When the mean degree 〈k〉 increases, the obtained clustering coefficient C tends to 0.50 for the transformed Erdös-Rényi networks, to 0.53 for the transformed exponential networks and to 0.61 for the transformed scale-free networks. These results are close to theoretical values, obtained with the model assumption that the degree-degree correlations in the initial networks are negligible.     

给定平均连接度的无标度网络演化模型

由于Internet、www等网络的复杂性，需要构造符合真实网络特性的仿真网络来对其进行研究。在BA模型的基础上，提出了一种给定平均连接度无标度网络演化模型，网络生长时，按照概率pk添加k个连接。通过速率方程证明了该网络是节点度分布符合幂律分布的无标度网络，其幂指数为-3，且平均连接度为给定值。仿真结果和理论计算值很好地吻合。     

面向Web网页的区域用户行为实证研究

用户对Web网页的访问是由用户需求行为确定的一个随着时间演化的复杂双模式二分网络.通过对网站聚类生成的二分网络的实证研究表明,其入度分布呈现出典型的无标度特征和集聚现象,幂指数介于1.7到1.8之间.将这种双模式二分网络映射为两种含权单模式网络:用户群体兴趣广义关联网络和网站资源广义关联网络,从而深入研究用户群体行为的关联性和从用户行为角度网站资源的关联性.实证分析其统计特性表明,两者的边权分布是幂律的,网络节点关联紧密且呈现簇聚特征.用户行为的无标度特征和集聚特点对优化Internet网络拓扑结构,改善其网络性能具有重要意义.     

基于能量感知的无线传感器网络拓扑演化

针对无线传感器网络中能源效率的问题,引入复杂网络理论的研究方法,提出基于能量感知无线传感器网络拓扑动态演化模型。在建模过程中考虑到无线传感器网络拓扑变化与节点的度数和剩余能量密切相关,而且网络中节点和链路是有增有减的动态行为,利用连续场理论推导出此模型具有无标度的特征,无标度网络对于节点的随机故障具有较高的鲁棒性。数值计算与实验仿真结果显示,算法可以有效地改善整个网络的结点均衡能耗。     

政府公文收发记录的可视网络分析

传统的人类动力学分析大多从单一的时间间隔角度入手,不能全面反映人类行为的标度规律。对此,以政府公文的真实收发记录为研究对象,以时间序列和复杂网络为工具,分析人类行为的时间间隔特征和数量特征。首先分析收文的时间间隔分布,发现其累计分布表现为幂律形式。其次采用重标极差法对收文数量的时间序列进行分析,得到Hurst指数和非周期循环长度,显示该时间序列具有分形特征。然后用可视图和水平可视图方法将该时间序列转换为复杂网络,网络具有无标度特征、小世界效应和等级结构,说明不同时间段内的人类行为密切关联。最后讨论可视图和水平可视图这两种算法的异同点和适用范围。