# Minimum Dominating Sets in Scale-Free Network Ensembles

arXiv: https://arxiv.org/abs/1302.2518 · HTML: https://mlsanity.com/paper/1302.2518/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2013.

## Built on by (most cited first, 1 of 1)

- [Graph Neural Networks for Influence Maximization in Social Networks: An Unsupervised Minimum Dominating Set Approach](https://mlsanity.com/paper/2609.13836/) (2026)

## Abstract (arXiv)

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 (kmax=√N) 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.