Header

UZH-Logo

Maintenance Infos

Empirical determination of the optimal attack for fragmentation of modular networks


de Abreu, Carolina; Gonçalves, Sebastián; da Cunha, Bruno Requião (2021). Empirical determination of the optimal attack for fragmentation of modular networks. Physica A: Statistical Mechanics and its Applications, 563:125486.

Abstract

We perform all possible removals of nodes from networks of size , then we identify and measure the largest connected component left in every case. The smallest of these components represents the maximum possible damage (on a network of vertices), limited to the removal of nodes, and the set that produces such damage is called the optimal set of size . We apply the procedure in a series of networks with controlled and varied modularity. Then, we compare the resulting statistics with the effect of removing the same amount of vertices according to state of the art methods of network fragmentation, i.e., High Betweenness Adaptive attack, Collective Influence, and Module-Based Attack. For practical matters we performed mainly attacks of size on networks of size , because the number of all possible sets () is at the verge of the computational capability of standard desktops. The results show, in general, that the resilience of networks to attacks has an inverse relationship with modularity, with being the critical value, from which the damage of the optimal attack increases rapidly. Networks are highly vulnerable to targeted attacks when the modularity is greater than the critical value of each heuristic method. On the other hand, for modularities lower than , all the heuristic strategies studied have a similar performance to a random attack.

Abstract

We perform all possible removals of nodes from networks of size , then we identify and measure the largest connected component left in every case. The smallest of these components represents the maximum possible damage (on a network of vertices), limited to the removal of nodes, and the set that produces such damage is called the optimal set of size . We apply the procedure in a series of networks with controlled and varied modularity. Then, we compare the resulting statistics with the effect of removing the same amount of vertices according to state of the art methods of network fragmentation, i.e., High Betweenness Adaptive attack, Collective Influence, and Module-Based Attack. For practical matters we performed mainly attacks of size on networks of size , because the number of all possible sets () is at the verge of the computational capability of standard desktops. The results show, in general, that the resilience of networks to attacks has an inverse relationship with modularity, with being the critical value, from which the damage of the optimal attack increases rapidly. Networks are highly vulnerable to targeted attacks when the modularity is greater than the critical value of each heuristic method. On the other hand, for modularities lower than , all the heuristic strategies studied have a similar performance to a random attack.

Statistics

Citations

Dimensions.ai Metrics
3 citations in Web of Science®
4 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

16 downloads since deposited on 10 Nov 2020
6 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Journal Article, refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Business Administration
08 Research Priority Programs > Social Networks
Dewey Decimal Classification:330 Economics
Scopus Subject Areas:Physical Sciences > Statistics and Probability
Physical Sciences > Condensed Matter Physics
Scope:Discipline-based scholarship (basic research)
Language:English
Date:1 February 2021
Deposited On:10 Nov 2020 11:07
Last Modified:23 Jun 2024 01:44
Publisher:Elsevier
ISSN:0378-4371
OA Status:Green
Free access at:Publisher DOI. An embargo period may apply.
Publisher DOI:https://doi.org/10.1016/j.physa.2020.125486
Related URLs:https://www.sciencedirect.com/science/article/pii/S037843712030786X?via%3Dihub (Publisher)
Other Identification Number:merlin-id:19966
  • Content: Accepted Version
  • Licence: Creative Commons: Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)