We study the scaling behavior of the size of minimum dominating set (MDS) in scale-free networks, with respect to network size N and power-law exponent γ, while keeping the average degree fixed. We study ensembles generated by three different network construction methods, and we use a greedy algorithm to approximate the MDS. With a structural cutoff imposed on the maximal degree we find linear scaling of the MDS size with respect to N in all three network classes. Without any cutoff (kmax = N – 1) two of the network classes display a transition at γ ≈ 1.9, with linear scaling above, and vanishingly weak dependence below, but in the third network class we find linear scaling irrespective of γ. We find that the partial MDS, which dominates a given z < 1 fraction of nodes, displays essentially the same scaling behavior as the MDS.
展开▼
机译：我们研究了无标度网络中最小支配集（MDS）的规模相对于网络规模N和幂律指数γ的缩放行为，同时保持平均度固定。我们研究由三种不同的网络构建方法生成的合奏，并使用贪婪算法对MDS进行近似。通过对最大程度施加结构截止，我们发现所有三个网络类别中MDS大小相对于N的线性缩放。在没有任何截止值（kmax = N – 1）的情况下，两个网络类别在γ≈1.9处出现过渡，线性比例在上方，而依赖性逐渐消失，但是在第三种网络类别中，我们发现与γ无关的线性比例。我们发现，支配给定的z <1分数节点的部分MDS表现出与MDS基本相同的缩放行为。
展开▼
