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

Stability of fcDS against degree-ranked node removal as a function of the damage anticipation accuracy: (a) synthetic scale-free network with N = 5000, 〈k〉 = 8, γ = 2.5; (b) Gnutella peer-to-peer network; (c) ENTSO-E powergrid.The actual damage fraction is indicated above the plots and marked by red dashed lines; the actual degree distribution of the damage corresponds to α ≥ 4 values.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f8: Stability of fcDS against degree-ranked node removal as a function of the damage anticipation accuracy: (a) synthetic scale-free network with N = 5000, 〈k〉 = 8, γ = 2.5; (b) Gnutella peer-to-peer network; (c) ENTSO-E powergrid.The actual damage fraction is indicated above the plots and marked by red dashed lines; the actual degree distribution of the damage corresponds to α ≥ 4 values.

Mentions: Figure 8 shows the landscape of stability as a function of the control parameters. As expected, we obtain the highest stability when the attacked degrees and the size of the attack are correctly estimated. For small damage fractions (f = 0.1) we lose stability mostly for overestimating the size of the attack, while for moderate (f = 0.3) and large (f = 0.5) damages we lose stability for incorrectly anticipating which degrees are targeted.


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)

Stability of fcDS against degree-ranked node removal as a function of the damage anticipation accuracy: (a) synthetic scale-free network with N = 5000, 〈k〉 = 8, γ = 2.5; (b) Gnutella peer-to-peer network; (c) ENTSO-E powergrid.The actual damage fraction is indicated above the plots and marked by red dashed lines; the actual degree distribution of the damage corresponds to α ≥ 4 values.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f8: Stability of fcDS against degree-ranked node removal as a function of the damage anticipation accuracy: (a) synthetic scale-free network with N = 5000, 〈k〉 = 8, γ = 2.5; (b) Gnutella peer-to-peer network; (c) ENTSO-E powergrid.The actual damage fraction is indicated above the plots and marked by red dashed lines; the actual degree distribution of the damage corresponds to α ≥ 4 values.
Mentions: Figure 8 shows the landscape of stability as a function of the control parameters. As expected, we obtain the highest stability when the attacked degrees and the size of the attack are correctly estimated. For small damage fractions (f = 0.1) we lose stability mostly for overestimating the size of the attack, while for moderate (f = 0.3) and large (f = 0.5) damages we lose stability for incorrectly anticipating which degrees are targeted.

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