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

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

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

【摘要】 当前复杂网络研究中有很多关于网络演化过程中网络的生长模型,应用较为广泛的主要有BA模型及其衍生模型。这些模型主要考虑网络演化过程中节点的增加与节点间边的连接规律,对于网络演化过程中节点的消退规律的研究还相对较少。这些模型生成的网络将是不断增大的,无法反映网络在某个时间段的实际规模。实际网络中节点分布的一个广泛特征是度的无标度幂率分布,BA模型认为形成这种特征的两个主要因素是网络增长和节点间的偏好连接。然而实际的开放网络在演化过程中还应考虑另外两个重要的因素:(I)实际网络中不可能只有节点增加而无节点消退;(Ⅱ)实际网络中节点的消退是否同样存在偏好。如果不将实际网络的演化看成不断增长的过程,而是由一系列连续的、独立的网络快照组成,对于相邻时间段的网络快照中的节点是否度越小消退的可能性就越大?更多还原

【Abstract】 There are a lot of networks growing models on the evolvement of complex networks currently, the most widely used models are the BA model and its generalizations. These models are mainly considering about the rule of vertices adding and connecting, but little consideration about the property of how vertices vanishing. A common property of many large networks is that the vertex degrees follow a scale-free power-law distribution, The BA model features two generic mechanisms: the networks expanding and the preferential attachment. But in the real-world networks we should consider another two important factors: (I) There are not only vertices adding but also vanishment in the real-world networks. (II) Whether vertices in the real-world networks will vanish with degree preference. If we don’t view the evolvement of real-world networks as constantly growing process, but a series of independent snapshots, whether the vertices with small degrees will likely to vanish in the next snapshot? Currently the general methods used by models to simulate the vertices vanishment in complex networks are to delete vertices or edges randomly or to attack the vertices which are selected by given rules. However there is little consideration about the vanishment of vertices as a special course to study. This paper analyses the statistical results of phone call graphs, scientific collaboration networks, keywords networks, and finds the vanished vertices are not randomly distributed but have strong degree preference. The vanishment rate of degrees follows a scale-free power-law distribution, with q(k) = |Vk’|/|Vk|∝k-γ , where Vk is set of vertices of degree k in the active graph, Vk is set of vanished vertices of degree k in the active graph, γ is the exponent. The result indicates that in some real open networks the vertices with small value are likely to vanish. But this feature is seldom proposed by present complex networks models. In fact this feature is strongly related to the origin of scale-free networks. This paper proposed two vertices vanishement models in evolving networks, the first model is based on the degree preference of the vanished vertices from the macroscopic characters of the networks. However if the vertices are likely to vanish, it is hard for them to know their influence in the whole network, so we propose the second model. The second model is based on the first model and considers the microscopic characters of local network. At first the model finds the communities that contain vanished vertices in the network then it will find the vanished vertices with degree preference. Through analysis and simulation of how vertices vanish in the models from real-world datasets, the results indicate that the models can exactly fit the real situation. These models can adapt to different networks by changing the parameters.更多还原