【作者】 吴斌； 叶祺； 徐六通； 徐超群；

【Author】 Bin Wu, Qi Ye, Liutong Xu, Chaoqun Xu (Telecommunication Software Engineering Center, School of Computer Science and Technology, Beijing University of Posts and Telecommunications, Beijing 100876 )

【机构】 北京邮电大学计算机学院通信软件工程中心；

【摘要】 当前的复杂网络研究中,关于复杂网络中各种属性的发现大多基于网络快照的静态特征,对于网络快照生成过程中的各类属性的研究方法还很少。本文提出一种通用的分析实际网络快照生成过程中网络结构变化的方法,将每个网络的快照生成过程看作是小团体不断增加及小团体间不断叠加的过程。通过分析网络的小团体的结构、计算不同时间段内新增小团体中旧节点的比例p及不同时间段内新增小团体中旧节点间产生的新边数与该时间段小团体总边数的比例q 的变化情况,由此得到网络快照生成过程中的动态属性特征及变化规律,优于前期的基于网络静态快照研究网络动态特征的方法。更多还原

【Abstract】 Recently many studies of complex networks are based on identifying the static properties in snapshots of networks. However there are few studies on the properties of how snapshots growing. This paper proposed a general method to study how snapshots growing in real-world networks, regarding each process of snapshots growing as adding teams and connecting the teams continually. Through the study of the structure of teams in the network, the proportion of old vertices in a new team in different time steps is p and the proportion of new edges between old vertices in a new team in different time steps is q, we can get the dynamic characters and evolvement properties of growing snapshots and it is better than the former way that gets dynamic characters by using static snapshots. The patterns of adding and connecting vertices in the evolution networks can greatly influence the structure and function of the networks. How to measure the vertices connecting patterns and the influence of the connecting patterns is a widely interesting topic on current studies of complex networks. Different types of complex networks have different snapshot growing patterns. The teams which add to different types of snapshots each time step while growing can have different structures. E.g. the teams adding to phone call networks are edges while the teams adding to scientific collaboration networks, keywords networks, actor collaboration networks etc. are usually complete graphs. This paper studies the p and q of the growing snapshots of phone call networks, scientific collaboration networks and keywords networks. Through the statistical analysis of p, q in these networks, the result shows that p, q acts to the scale of the network accordingly in the positive trend. With the expanding and densification of the networks, the growing speed of p and q is going to be slower. We observe the early stage of these networks, from the result of the variation of p and q we can get the snapshot growing information more clearly. The paper also shows that the times of vertices’ appearing in different teams follow a power law distribution. All the above show the snapshots of some mature networks is sparse at first and gradually growing and become dense by the overlapped teams in the network. At last we propose a network growing model, the times of vertices’ appearing in different teams follow a power distribution in the model. Analysis and numerical simulations show the vertex degrees follow a scale-free distribution in the network which is based on these two ingredients. We regard the main reasons that make the vertex degrees follow a power-law distribution in real-world networks are the addition of new teams and the times of vertices’ appearing in different teams follow a power law distribution, preferential attachment in the B A model and its generalizations is just a special case of it.更多还原