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 various dominating sets against random and degree-ranked node removal.Subfigures (a), (c), and (e) show random node removal, (b), (d), and (f) show degree ranked node removal. Subfigures (a) and (b) show stability in the entire network, while (c) and (d) show stability within the remaining giant component. The inset in (a) shows the corresponding sizes of dominating sets, and insets in (c) and (d) show the size of the corresponding giant component. Subfigures (e) and (f) show a correlation between set size and stability, at γ = 2.5. All plots show synthetic scale-free networks, N = 5000, 〈k〉 = 8, averaged over 200 network samples.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f1: Stability of various dominating sets against random and degree-ranked node removal.Subfigures (a), (c), and (e) show random node removal, (b), (d), and (f) show degree ranked node removal. Subfigures (a) and (b) show stability in the entire network, while (c) and (d) show stability within the remaining giant component. The inset in (a) shows the corresponding sizes of dominating sets, and insets in (c) and (d) show the size of the corresponding giant component. Subfigures (e) and (f) show a correlation between set size and stability, at γ = 2.5. All plots show synthetic scale-free networks, N = 5000, 〈k〉 = 8, averaged over 200 network samples.

Mentions: Figure 1 shows the stability against the fraction of removed nodes for MDS, CDS and DDS in the entire remaining network [Fig. 1(a), (b)] and in the remaining giant component [Fig. 1(c), (d)]. It is clear that the degree-ranked node removal reduces the dominated fraction much faster than the random node removal, because high-degree nodes are more likely to be dominator nodes than low degree nodes. The giant component itself also breaks down much faster, as shown in the insets of Fig. 1(c) and (d). However, as long as a giant component exists, it has higher domination stability than the entire network, in both scenarios. The slight increase of stability at high damage rates is a side effect caused by removal of nodes that had lost domination by earlier removals. When the network damage is high, it becomes more likely that these nodes are deleted, causing the dominated fraction of the remaining network to increase. At this point, however, the network is almost completely destroyed and domination stability becomes meaningless.


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 various dominating sets against random and degree-ranked node removal.Subfigures (a), (c), and (e) show random node removal, (b), (d), and (f) show degree ranked node removal. Subfigures (a) and (b) show stability in the entire network, while (c) and (d) show stability within the remaining giant component. The inset in (a) shows the corresponding sizes of dominating sets, and insets in (c) and (d) show the size of the corresponding giant component. Subfigures (e) and (f) show a correlation between set size and stability, at γ = 2.5. All plots show synthetic scale-free networks, N = 5000, 〈k〉 = 8, averaged over 200 network samples.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f1: Stability of various dominating sets against random and degree-ranked node removal.Subfigures (a), (c), and (e) show random node removal, (b), (d), and (f) show degree ranked node removal. Subfigures (a) and (b) show stability in the entire network, while (c) and (d) show stability within the remaining giant component. The inset in (a) shows the corresponding sizes of dominating sets, and insets in (c) and (d) show the size of the corresponding giant component. Subfigures (e) and (f) show a correlation between set size and stability, at γ = 2.5. All plots show synthetic scale-free networks, N = 5000, 〈k〉 = 8, averaged over 200 network samples.
Mentions: Figure 1 shows the stability against the fraction of removed nodes for MDS, CDS and DDS in the entire remaining network [Fig. 1(a), (b)] and in the remaining giant component [Fig. 1(c), (d)]. It is clear that the degree-ranked node removal reduces the dominated fraction much faster than the random node removal, because high-degree nodes are more likely to be dominator nodes than low degree nodes. The giant component itself also breaks down much faster, as shown in the insets of Fig. 1(c) and (d). However, as long as a giant component exists, it has higher domination stability than the entire network, in both scenarios. The slight increase of stability at high damage rates is a side effect caused by removal of nodes that had lost domination by earlier removals. When the network damage is high, it becomes more likely that these nodes are deleted, causing the dominated fraction of the remaining network to increase. At this point, however, the network is almost completely destroyed and domination stability becomes meaningless.

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