Dominating Scale-Free Networks Using Generalized Probabilistic Methods

Abstract

We study ensemble-based graph-theoretical methods aiming to approximate the size of the minimum dominating set (MDS) in scale-free networks. We analyze both analytical upper bounds of dominating sets and numerical realizations for applications. We propose two novel probabilistic dominating set selection strategies that are applicable to heterogeneous networks. One of them obtains the smallest probabilistic dominating set and also outperforms the deterministic degree-ranked method. We show that a degree-dependent probabilistic selection method becomes optimal in its deterministic limit. In addition, we also find the precise limit where selecting high-degree nodes exclusively becomes inefficient for network domination. We validate our results on several real-world networks, and provide highly accurate analytical estimates for our methods.

References in corpus (14)

• Emergence of scaling in random networks
• Assortative mixing in networks
• Mixing patterns in networks
• Generation of uncorrelated random scale-free networks
• Epidemic threshold in structured scale-free networks
• Generating simple random graphs with prescribed degree distribution
• Cut-offs and finite size effects in scale-free networks
• Nodal dynamics, not degree distributions, determine the structural controllability of complex networks
• Emergence of bimodality in controlling complex networks
• Uncovering disassortativity in large scale-free networks
• Degree-degree correlations in random graphs with heavy-tailed degrees
• Minimum Dominating Sets in Scale-Free Network Ensembles
• Network Observability Transitions
• Distance-d covering problems in scale-free networks with degree correlations

Cited by in corpus (9)

• Control Principles of Complex Networks
• Performance of superadiabatic quantum machines
• When is a quantum heat engine quantum?
• Building Damage-Resilient Dominating Sets in Complex Networks against Random and Targeted Attacks
• Domination number and minimum dominating sets in pseudofractal scale-free web and Sierpiński graph
• ExEm: Expert Embedding using dominating set theory with deep learning approaches
• Influence Maximization for Fixed Heterogeneous Thresholds
• The evolution of network controllability in growing networks
• Observability transitions in clustered networks