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, fcDS and other dominating sets in real networks against random and degree-ranked attacks, for various damage fractions: (a,b) Gnutella peer-to-peer network; (c,d) ENTSO-E powergrid; (e,f) Brain (MRI) network.Data is averaged over 20 independent runs of node removal. See Table 1 for network parameters.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f5: Stability of frDS, fcDS and other dominating sets in real networks against random and degree-ranked attacks, for various damage fractions: (a,b) Gnutella peer-to-peer network; (c,d) ENTSO-E powergrid; (e,f) Brain (MRI) network.Data is averaged over 20 independent runs of node removal. See Table 1 for network parameters.

Mentions: Figure 5 shows domination stability as a function of dominating set size for the real network samples. In general, we see that stability of frDS and fcDS matches the stability of MDS, and exceeds the stability of CDS and DDS, at identical set sizes. In case of Gnutella08 and the powergrid, the stability curves saturate slowly, and the curve shapes are not as smooth as for synthetic scale-free networks, due to having more disturbed (non-scale-free) degree distributions. However, the brain graph shows very high domination stability against both random and targeted attacks. In all cases, the relative advantage of frDS and fcDS over CDS and DDS (i.e., cost-efficiency) remains as high as in synthetic scale-free networks.


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, fcDS and other dominating sets in real networks against random and degree-ranked attacks, for various damage fractions: (a,b) Gnutella peer-to-peer network; (c,d) ENTSO-E powergrid; (e,f) Brain (MRI) network.Data is averaged over 20 independent runs of node removal. See Table 1 for network parameters.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f5: Stability of frDS, fcDS and other dominating sets in real networks against random and degree-ranked attacks, for various damage fractions: (a,b) Gnutella peer-to-peer network; (c,d) ENTSO-E powergrid; (e,f) Brain (MRI) network.Data is averaged over 20 independent runs of node removal. See Table 1 for network parameters.
Mentions: Figure 5 shows domination stability as a function of dominating set size for the real network samples. In general, we see that stability of frDS and fcDS matches the stability of MDS, and exceeds the stability of CDS and DDS, at identical set sizes. In case of Gnutella08 and the powergrid, the stability curves saturate slowly, and the curve shapes are not as smooth as for synthetic scale-free networks, due to having more disturbed (non-scale-free) degree distributions. However, the brain graph shows very high domination stability against both random and targeted attacks. In all cases, the relative advantage of frDS and fcDS over CDS and DDS (i.e., cost-efficiency) remains as high as in synthetic scale-free networks.

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