Optimizing network attacks by artificial bee colony

详细信息    查看全文

• 作者：Manuel Lozano^a ; ^{lozano@decsai.ugr.es" class="auth_mail" title="E-mail the corresponding author} ; Carlos Garcí ; a-Martí ; nez^b ; ^{cgarcia@uco.es" class="auth_mail" title="E-mail the corresponding author} ; Francisco J. Rodrí ; guez ; ^c ; ^{fjrodriguez@unex.es" class="auth_mail" title="E-mail the corresponding author} ; ^{fjrodriguez@decsai.ugr.es" class="auth_mail" title="E-mail the corresponding author} ; Humberto M. Trujillo^d ; ^{humberto@ugr.es" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Artificial bee colony ; Betweenness centrality ; Network attacks ; Combinatorial optimization
• 刊名：Information Sciences
• 出版年：2017
• 出版时间：20 January 2017
• 年：2017
• 卷：377
• 期：Complete
• 页码：30-50
• 全文大小：1538 K

文摘

Over the past few years, the task of conceiving effective attacks to complex networks has arisen as an optimization problem. Attacks are modelled as the process of removing a number k of vertices, from the graph that represents the network, and the goal is to maximise or minimise the value of a predefined metric over the graph. In this work, we present an optimization problem that concerns the selection of nodes to be removed to minimise the maximum betweenness centrality value of the residual graph. This metric evaluates the participation of the nodes in the communications through the shortest paths of the network.

To address the problem we propose an artificial bee colony algorithm, which is a swarm intelligence approach inspired in the foraging behaviour of honeybees. In this framework, bees produce new candidate solutions for the problem by exploring the vicinity of previous ones, called food sources. The proposed method exploits useful problem knowledge in this neighbourhood exploration by considering the partial destruction and heuristic reconstruction of selected solutions. The performance of the method, with respect to other models from the literature that can be adapted to face this problem, such as sequential centrality-based attacks, module-based attacks, a genetic algorithm, a simulated annealing approach, and a variable neighbourhood search, is empirically shown.