文章基本信息

标题：Minimum Dominating Sets in Scale-Free Network Ensembles
本地全文：下载
作者：F. Molnár ; S. Sreenivasan ; B. K. Szymanski 等
期刊名称：Scientific Reports
电子版ISSN：2045-2322
出版年度：2013
卷号：3
期号：1
DOI：10.1038/srep01736
语种：English
出版社：Springer Nature
摘要：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 ( k _max = 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