Requião da Cunha Bruno, González-Avella Juan Carlos, Gonçalves Sebastián
Instituto de Física, Universidade Federal do Rio Grande do Sul, Porto Alegre, RS, Brazil.
Departamento de Polícia Federal, Porto Alegre, Brazil.
PLoS One. 2015 Nov 16;10(11):e0142824. doi: 10.1371/journal.pone.0142824. eCollection 2015.
In the multidisciplinary field of Network Science, optimization of procedures for efficiently breaking complex networks is attracting much attention from a practical point of view. In this contribution, we present a module-based method to efficiently fragment complex networks. The procedure firstly identifies topological communities through which the network can be represented using a well established heuristic algorithm of community finding. Then only the nodes that participate of inter-community links are removed in descending order of their betweenness centrality. We illustrate the method by applying it to a variety of examples in the social, infrastructure, and biological fields. It is shown that the module-based approach always outperforms targeted attacks to vertices based on node degree or betweenness centrality rankings, with gains in efficiency strongly related to the modularity of the network. Remarkably, in the US power grid case, by deleting 3% of the nodes, the proposed method breaks the original network in fragments which are twenty times smaller in size than the fragments left by betweenness-based attack.
在网络科学这个多学科领域，从实际应用角度来看，有效分解复杂网络的程序优化正备受关注。在本论文中，我们提出一种基于模块的方法来高效分割复杂网络。该程序首先通过一种成熟的社区发现启发式算法识别拓扑社区，借此网络能够得以呈现。然后，仅按节点介数中心性的降序移除参与社区间链接的节点。我们通过将其应用于社会、基础设施和生物领域的各种示例来说明该方法。结果表明，基于模块的方法始终优于基于节点度或介数中心性排名对顶点进行的有针对性攻击，效率提升与网络的模块化密切相关。值得注意的是，在美国电网案例中，通过删除3%的节点，所提方法将原始网络分解成的碎片大小比基于介数的攻击留下的碎片小二十倍。
