Minimum Dominating Sets in Scale-Free Network Ensembles

Abstract

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 $\gamma$, 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 ($k_{\max }=\sqrt{N}$) 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 $\gamma \approx 1.9$, with linear scaling above, and vanishingly weak dependence below, but in the third network class we find linear scaling irrespective of $\gamma$. We find that the partial MDS, which dominates a given $z<1$ fraction of nodes, displays essentially the same scaling behavior as the MDS.

References in corpus (5)

• Generating simple random graphs with prescribed degree distribution
• Nodal dynamics, not degree distributions, determine the structural controllability of complex networks
• Efficient and exact sampling of simple graphs with given arbitrary degree sequence
• All scale-free networks are sparse
• Scale-free networks with an exponent less than two

Cited by in corpus (11)

• The Impact of Heterogeneous Thresholds on Social Contagion with Multiple Initiators
• Statistical Mechanics of the Minimum Dominating Set Problem
• Exact sampling of graphs with prescribed degree correlations
• Structurally Robust Control of Complex Networks
• Building Damage-Resilient Dominating Sets in Complex Networks against Random and Targeted Attacks
• The Directed Dominating Set Problem: Generalized Leaf Removal and Belief Propagation
• Dominating Scale-Free Networks Using Generalized Probabilistic Methods
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• Generalized minimum dominating set and application in automatic text summarization
• Target observation of complex networks
• Identifying efficient controls of complex interaction networks using genetic algorithms