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 of partial frDS as a function of domination redundancy and dominating set size.The plotted area is bounded by the size of the full frDS at any given r. Subfigure (a) shows random node removal, (b) shows degree-ranked node removal, for synthetic scale-free networks, N = 5000, 〈k〉 = 8, γ = 2.5, f = 0.3, averaged over 50 network samples.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f7: Domination stability of partial frDS as a function of domination redundancy and dominating set size.The plotted area is bounded by the size of the full frDS at any given r. Subfigure (a) shows random node removal, (b) shows degree-ranked node removal, for synthetic scale-free networks, N = 5000, 〈k〉 = 8, γ = 2.5, f = 0.3, averaged over 50 network samples.

Mentions: There are two possible ways to achieve a certain desired cost (dominating set size) with frDS. Either we aim for the lowest r value that provides the desired cost, or we may choose a larger r value, and use only a fraction of the larger dominating set it provides. In the latter case we would select nodes in the same order as the greedy algorithm picked them. In other words, we can either select a full frDS with small r or a partial frDS with the same size but larger r. Figure 7 shows the comparison of these two cases (see Supplementary Figures S11–S16 for analysis over a wide range of network parameters). The contour curves of fixed stability values are monotonically increasing for larger r values, indicating that the cost for a certain stability level increases if we use partial frDS with higher r values. This also means that using full frDS with the smallest possible r value provides the highest possible 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 of partial frDS as a function of domination redundancy and dominating set size.The plotted area is bounded by the size of the full frDS at any given r. Subfigure (a) shows random node removal, (b) shows degree-ranked node removal, for synthetic scale-free networks, N = 5000, 〈k〉 = 8, γ = 2.5, f = 0.3, averaged over 50 network samples.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

f7: Domination stability of partial frDS as a function of domination redundancy and dominating set size.The plotted area is bounded by the size of the full frDS at any given r. Subfigure (a) shows random node removal, (b) shows degree-ranked node removal, for synthetic scale-free networks, N = 5000, 〈k〉 = 8, γ = 2.5, f = 0.3, averaged over 50 network samples.
Mentions: There are two possible ways to achieve a certain desired cost (dominating set size) with frDS. Either we aim for the lowest r value that provides the desired cost, or we may choose a larger r value, and use only a fraction of the larger dominating set it provides. In the latter case we would select nodes in the same order as the greedy algorithm picked them. In other words, we can either select a full frDS with small r or a partial frDS with the same size but larger r. Figure 7 shows the comparison of these two cases (see Supplementary Figures S11–S16 for analysis over a wide range of network parameters). The contour curves of fixed stability values are monotonically increasing for larger r values, indicating that the cost for a certain stability level increases if we use partial frDS with higher r values. This also means that using full frDS with the smallest possible r value provides the highest possible 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