title: 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.
authors.affiliation: 1] Department of Physics, Applied Physics, and Astronomy, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY, 12180-3590 USA [2] Social Cognitive Networks Academic Research Center, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY, 12180-3590 USA.
authors.forename: F
authors.initials: F
authors.lastname: Molnár
authors.affiliation: 1] Department of Physics, Applied Physics, and Astronomy, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY, 12180-3590 USA [2] Social Cognitive Networks Academic Research Center, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY, 12180-3590 USA.
authors.forename: N
authors.initials: N
authors.lastname: Derzsy
authors.affiliation: 1] Department of Mathematics, University of South Carolina, 1523 Greene Street, Columbia, SC, 29208 USA [2] Interdisciplinary Mathematics Institute, University of South Carolina, 1523 Greene Street, Columbia, SC, 29208 USA.
authors.forename: É
authors.initials: É
authors.lastname: Czabarka
authors.affiliation: 1] Department of Mathematics, University of South Carolina, 1523 Greene Street, Columbia, SC, 29208 USA [2] Interdisciplinary Mathematics Institute, University of South Carolina, 1523 Greene Street, Columbia, SC, 29208 USA.
authors.forename: L
authors.initials: L
authors.lastname: Székely
authors.affiliation: 1] Social Cognitive Networks Academic Research Center, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY, 12180-3590 USA [2] Department of Computer Science, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY, 12180-3590 USA.
authors.forename: B K
authors.initials: BK
authors.lastname: Szymanski
authors.affiliation: 1] Department of Physics, Applied Physics, and Astronomy, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY, 12180-3590 USA [2] Social Cognitive Networks Academic Research Center, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY, 12180-3590 USA.
authors.forename: G
authors.initials: G
authors.lastname: Korniss