Semi-Deterministic Construction of Scale-Free Networks with Designated Parameters
Semi-Deterministic Construction of Scale-Free Networks with Designated Parameters
复制标题
指定参数无标度网络的半确定性构建
DOI：
10.1142/s0219265918500019
复制
发表时间：
2018
影响因子：
0.7
通讯作者：
Satoshi Fujita
中科院分区：
文献类型：
--
作者：
Naoki Takeuchi;Satoshi Fujita
无标度网络作为互连网络的拓扑结构具有直径小、信息传播快等优点。在本文中，我们提出了一种方法来构建无标度网络在一个半确定性的方式。该算法扩展了用于构造具有指定最小度和最大度的无标度网络的Bulut算法，即：（1）根据理想度分布确定理想边数;（2）在将每个新节点连接到已有节点之后，通过边的添加/删除来调整边数到理想值。我们证明，这样的调整总是可能的，如果在网络中的节点数超过。该算法的性能进行了实验评估。
Scale-free networks have several favorable properties as the topology of interconnection networks such as the short diameter and the quick message propagation. In this paper, we propose a method to construct scale-free networks in a semi-deterministic manner. The proposed algorithm extends the Bulut's algorithm for constructing scale-free networks with designated minimum degreekand maximum degreem, in such a way that: (1) it determines the ideal number of edges derived from the ideal degree distribution; and (2) after connecting each new node tokexisting nodes as in the Bulut’s algorithm, it adjusts the number of edges to the ideal value by conducting add/removal of edges. We prove that such an adjustment is always possible if the number of nodes in the network exceeds. The performance of the algorithm is experimentally evaluated.