Limits...
Building damage-resilient dominating sets in complex networks against random and targeted attacks.

Molnár F, Derzsy N, Szymanski BK, Korniss G - Sci Rep (2015)

Bottom Line: While small, cost-efficient dominating sets play a significant role in controllability and observability of these networks, a fixed and intact network structure is always implicitly assumed.We find that cost-efficiency of dominating sets optimized for small size alone comes at a price of being vulnerable to damage; domination in the remaining network can be severely disrupted, even if a small fraction of dominator nodes are lost.We analyze the efficiency of each method on synthetic scale-free networks, as well as real complex networks.

View Article: PubMed Central - PubMed

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.

ABSTRACT
We study the vulnerability of dominating sets against random and targeted node removals in complex networks. While small, cost-efficient dominating sets play a significant role in controllability and observability of these networks, a fixed and intact network structure is always implicitly assumed. We find that cost-efficiency of dominating sets optimized for small size alone comes at a price of being vulnerable to damage; domination in the remaining network can be severely disrupted, even if a small fraction of dominator nodes are lost. We develop two new methods for finding flexible dominating sets, allowing either adjustable overall resilience, or dominating set size, while maximizing the dominated fraction of the remaining network after the attack. We analyze the efficiency of each method on synthetic scale-free networks, as well as real complex networks.

No MeSH data available.


Related in: MedlinePlus

Domination stability in frDS and fcDS as a function of domination redundancy.(a) shows random node removal, (b) shows degree-ranked node removal. The inset shows the sizes of the corresponding dominating sets. The size of fcDS is set to match frDS at any given r value. Synthetic scale-free networks, N = 5000, 〈k〉 = 8, γ = 2.5, f = 0.3, averaged over 200 network samples.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC4321165&req=5

f2: Domination stability in frDS and fcDS as a function of domination redundancy.(a) shows random node removal, (b) shows degree-ranked node removal. The inset shows the sizes of the corresponding dominating sets. The size of fcDS is set to match frDS at any given r value. Synthetic scale-free networks, N = 5000, 〈k〉 = 8, γ = 2.5, f = 0.3, averaged over 200 network samples.

Mentions: Figures 2 and 3 show domination stability achieved by frDS and fcDS as a function of redundancy and dominating set size, respectively. Stability achieved by the fixed methods (MDS, CDS, DDS) are also shown at their corresponding cost values for comparison. The general shape of the curves in both figures are similar, since the dominating set size is roughly proportional to redundancy (see Fig. 2 inset and Supplementary Fig. S6). In case of random damage, the stability rapidly increases with cost, until the size of MDS is reached, then the curve saturates. There is little advantage in selecting a dominating set larger than approximately twice the size of MDS, because stability is already very close to 1, even at large damage values. However, in case of degree-ranked damage, there is a steady increase in stability as more nodes are selected as dominators. In both cases, fcDS provides somewhat higher stability than frDS at moderate damage levels, but frDS is more stable at small damage levels. These observations hold across a wide range of network parameters, see Supplementary Figs. S7 and S8. It is also clear that both frDS and fcDS can provide great flexibility in adjusting the size of the dominating set and stability.


Building damage-resilient dominating sets in complex networks against random and targeted attacks.

Molnár F, Derzsy N, Szymanski BK, Korniss G - Sci Rep (2015)

Domination stability in frDS and fcDS as a function of domination redundancy.(a) shows random node removal, (b) shows degree-ranked node removal. The inset shows the sizes of the corresponding dominating sets. The size of fcDS is set to match frDS at any given r value. Synthetic scale-free networks, N = 5000, 〈k〉 = 8, γ = 2.5, f = 0.3, averaged over 200 network samples.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC4321165&req=5

f2: Domination stability in frDS and fcDS as a function of domination redundancy.(a) shows random node removal, (b) shows degree-ranked node removal. The inset shows the sizes of the corresponding dominating sets. The size of fcDS is set to match frDS at any given r value. Synthetic scale-free networks, N = 5000, 〈k〉 = 8, γ = 2.5, f = 0.3, averaged over 200 network samples.
Mentions: Figures 2 and 3 show domination stability achieved by frDS and fcDS as a function of redundancy and dominating set size, respectively. Stability achieved by the fixed methods (MDS, CDS, DDS) are also shown at their corresponding cost values for comparison. The general shape of the curves in both figures are similar, since the dominating set size is roughly proportional to redundancy (see Fig. 2 inset and Supplementary Fig. S6). In case of random damage, the stability rapidly increases with cost, until the size of MDS is reached, then the curve saturates. There is little advantage in selecting a dominating set larger than approximately twice the size of MDS, because stability is already very close to 1, even at large damage values. However, in case of degree-ranked damage, there is a steady increase in stability as more nodes are selected as dominators. In both cases, fcDS provides somewhat higher stability than frDS at moderate damage levels, but frDS is more stable at small damage levels. These observations hold across a wide range of network parameters, see Supplementary Figs. S7 and S8. It is also clear that both frDS and fcDS can provide great flexibility in adjusting the size of the dominating set and stability.

Bottom Line: While small, cost-efficient dominating sets play a significant role in controllability and observability of these networks, a fixed and intact network structure is always implicitly assumed.We find that cost-efficiency of dominating sets optimized for small size alone comes at a price of being vulnerable to damage; domination in the remaining network can be severely disrupted, even if a small fraction of dominator nodes are lost.We analyze the efficiency of each method on synthetic scale-free networks, as well as real complex networks.

View Article: PubMed Central - PubMed

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.

ABSTRACT
We study the vulnerability of dominating sets against random and targeted node removals in complex networks. While small, cost-efficient dominating sets play a significant role in controllability and observability of these networks, a fixed and intact network structure is always implicitly assumed. We find that cost-efficiency of dominating sets optimized for small size alone comes at a price of being vulnerable to damage; domination in the remaining network can be severely disrupted, even if a small fraction of dominator nodes are lost. We develop two new methods for finding flexible dominating sets, allowing either adjustable overall resilience, or dominating set size, while maximizing the dominated fraction of the remaining network after the attack. We analyze the efficiency of each method on synthetic scale-free networks, as well as real complex networks.

No MeSH data available.


Related in: MedlinePlus