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 frDS and fcDS in edge-mixed real networks against random and degree-ranked attacks, for various assortativity levels: (a,b) Gnutella peer-to-peer network; (c,d) ENTSO-E powergrid; (e,f) Brain (MRI) network.Network damage fraction f = 0.3. For (a-d) data is averaged over 50 independent runs edge mixing and node removal; (e,f) is from a single run. See Table 1 for parameters of the original networks.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f6: Stability of frDS and fcDS in edge-mixed real networks against random and degree-ranked attacks, for various assortativity levels: (a,b) Gnutella peer-to-peer network; (c,d) ENTSO-E powergrid; (e,f) Brain (MRI) network.Network damage fraction f = 0.3. For (a-d) data is averaged over 50 independent runs edge mixing and node removal; (e,f) is from a single run. See Table 1 for parameters of the original networks.

Mentions: Figure 6 presents the effects of assortativity on domination stability. We see an unexpected behavior: as assortativity increases, domination stability decreases against random damage, but increases against an attack on high-degree nodes. We can understand this behavior by considering the effects of assortativity on dominator node degrees. In disassortative networks dominators are mostly high-degree hubs, while in assortative networks dominators have a full range of degrees. Thus, when the network is disassortative and the damage is random, it is less likely to remove high-degree hubs and more likely to remove low degree nodes, the latter rarely being a dominator, leading to increased stability. On the other hand, the result is reversed when high-degree nodes are targeted, in which case we are more likely removing dominators, leading to decreased 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)

Stability of frDS and fcDS in edge-mixed real networks against random and degree-ranked attacks, for various assortativity levels: (a,b) Gnutella peer-to-peer network; (c,d) ENTSO-E powergrid; (e,f) Brain (MRI) network.Network damage fraction f = 0.3. For (a-d) data is averaged over 50 independent runs edge mixing and node removal; (e,f) is from a single run. See Table 1 for parameters of the original networks.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f6: Stability of frDS and fcDS in edge-mixed real networks against random and degree-ranked attacks, for various assortativity levels: (a,b) Gnutella peer-to-peer network; (c,d) ENTSO-E powergrid; (e,f) Brain (MRI) network.Network damage fraction f = 0.3. For (a-d) data is averaged over 50 independent runs edge mixing and node removal; (e,f) is from a single run. See Table 1 for parameters of the original networks.
Mentions: Figure 6 presents the effects of assortativity on domination stability. We see an unexpected behavior: as assortativity increases, domination stability decreases against random damage, but increases against an attack on high-degree nodes. We can understand this behavior by considering the effects of assortativity on dominator node degrees. In disassortative networks dominators are mostly high-degree hubs, while in assortative networks dominators have a full range of degrees. Thus, when the network is disassortative and the damage is random, it is less likely to remove high-degree hubs and more likely to remove low degree nodes, the latter rarely being a dominator, leading to increased stability. On the other hand, the result is reversed when high-degree nodes are targeted, in which case we are more likely removing dominators, leading to decreased 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