文章基本信息

标题：Dominating Scale-Free Networks Using Generalized Probabilistic Methods
本地全文：下载
作者：F. Molnár, Jr. ; N. Derzsy ; É. Czabarka 等
期刊名称：Scientific Reports
电子版ISSN：2045-2322
出版年度：2014
卷号：4
DOI：10.1038/srep06308
出版社：Springer Nature
摘要：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.