Cargando…
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 algorit...
Autores principales: | , , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Nature Publishing Group
2013
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3636516/ http://dx.doi.org/10.1038/srep01736 |
Sumario: | 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 [Image: see text] 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. |
---|