Scaling of Various Dominating Sets in Scale-Free and Empirical Networks

We develop ensemble-based graph theoretical methods to approximate the size of minimum dominating sets (MDS) in scale-free networks. The MDS is found by a sequential greedy algorithm and the scale-free network samples are generated using the configuration model. Depending on the considered maximum degree cutoff, we analyze two subtypes of scale-free networks. We study the upper bound of random dominating sets and find that the numerical bound is lower than the analytical one. We propose a degree-based probabilistic selection that for a limiting case provides the smallest probabilistic dominating set. The method relies on a degree cutoff parameter and nodes having degrees above this cutoff are added to the dominating set (CDS). Our results reveal that with an optimal degree cutoff the CDS size is very close to the MDS. We provide analytical estimates for the uncorrelated version of scale-free networks to support our conjecture. We propose an efficient method to control the assortativity (measured by Spearman's rho) in networks. Applying this technique for the construction of our scale-free network ensembles, we provide a comprehensive analysis on the behavior of the probabilistic in comparison with the greedily selected dominating sets with respect to multiple network features.