Minimum Dominating Sets in Scale-Free Network Ensembles

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 algorith...

Full description

Saved in:
Bibliographic Details
Published in:Scientific reports 2013-04, Vol.3 (1), p.1736, Article 1736
Main Authors: Molnár, F., Sreenivasan, S., Szymanski, B. K., Korniss, G.
Format: Article
Language:English
Subjects:
639/705/1041
639/705/1042
639/705/117
639/766/530/2801
Algorithms
Approximation
Computer science
Construction methods
Humanities and Social Sciences
Integer programming
multidisciplinary
Nodes
Scaling
Science
Sensors
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 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 γ ≈ 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.
ISSN:2045-2322
2045-2322
DOI:10.1038/srep01736