Phys. Rev. E 94, 012305 (2016) - Identifying optimal targets of network attack by belief propagation

Learn about our response to COVID-19, including freely available research and expanded remote access support.

Identifying optimal targets of network attack by belief propagation

Salomon Mugisha and Hai-Jun Zhou

Phys. Rev. E 94, 012305 – Published 11 July 2016

Abstract

For a network formed by nodes and undirected links between pairs of nodes, the network optimal attack problem aims at deleting a minimum number of target nodes to break the network down into many small components. This problem is intrinsically related to the feedback vertex set problem that was successfully tackled by spin-glass theory and an associated belief propagation-guided decimation (BPD) algorithm [Zhou, Eur. Phys. J. B 86, 455 (2013)]. In the present work we apply the BPD algorithm (which has approximately linear time complexity) to the network optimal attack problem and demonstrate that it has much better performance than a recently proposed collective information algorithm [Morone and Makse, Nature 524, 65 (2015)] for different types of random networks and real-world network instances. The BPD-guided attack scheme often induces an abrupt collapse of the whole network, which may make it very difficult to defend.

Received 18 March 2016
Revised 25 April 2016

DOI:https://doi.org/10.1103/PhysRevE.94.012305

©2016 American Physical Society

Physics Subject Headings (PhySH)

Network optimization Network resilience Spreading Targeted attacks

Networks

Authors & Affiliations

Salomon Mugisha and Hai-Jun Zhou^*

Key Laboratory of Theoretical Physics, Institute of Theoretical Physics, Chinese Academy of Sciences, Zhong-Guan-Cun East Road 55, Beijing 100190, China
and School of Physical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China

^*Corresponding author: zhouhj@itp.ac.cn

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 94, Iss. 1 — July 2016

Reuse & Permissions

Access Options

APS and the Physical Review Editorial Office Continue to Support Researchers

COVID-19 has impacted many institutions and organizations around the world, disrupting the progress of research. Through this difficult time APS and the Physical Review editorial office are fully equipped and actively working to support researchers by continuing to carry out all editorial and peer-review functions and publish research in the journals as well as minimizing disruption to journal access.

We appreciate your continued effort and commitment to helping advance science, and allowing us to publish the best physics journals in the world. And we hope you, and your loved ones, are staying safe and healthy.

Ways to Access APS Journal Articles Off-Campus

Many researchers now find themselves working away from their institutions and, thus, may have trouble accessing the Physical Review journals. To address this, we have been improving access via several different mechanisms. See Off-Campus Access to Physical Review for further instructions.

The relative size of the largest connected component as a function of algorithmic time for an ER network with nodes and mean node degree . At each time interval of the targeted attack process, a node chosen by the CI algorithm or by the BPD algorithm is deleted along with all the attached links. The three sets of simulation data obtained by the CI algorithm correspond to ball radius (dotted line), (dashed line), and (long-dashed line), respectively. The BPD results (solid line) are obtained at fixed reweighting parameter .
The relative size of the largest connected component at algorithmic time of the BPD-guided attack process, for six real-world networks of different sizes (see Table ): Citation (pluses), P2P (crosses), Friend (squares), Authors (circles), WebPage (triangles), Grid (diamonds). At each time interval of the targeted attack process, a node chosen by the BPD algorithm (with ) is deleted along with all the attached links.
Performance of the BPD algorithm on ER networks of mean degree and different sizes . The fraction of deleted nodes in each BPD step is (pluses) or (crosses). (a) The relationship between the total BPD running time and . The simulation results (pluses) are obtained on a relatively old desktop computer (Intel-6300, GHz, 2 GB memory). The dashed line is the fitting curve with fitting parameter s. (b) The relationship between the relative size of the attack node set and . The dashed horizontal line denotes the predicted minimum value of (for ) by the replica-symmetric mean-field theory [].
Fraction of removed nodes for Erdös-Rényi random networks of mean degree (a) and regular random networks of degree (b). Each CI (diamond) or BPD (circle) data point is the averaged result over 48 network instances (size ); the standard deviation is of order and is therefore not shown. The cross symbols are the predictions of the replica-symmetric (RS) mean-field theory on the minimum relative size of the target node sets []. The plus symbols of (b) are the mathematical lower bound (LB) on the minimum relative size of the target node sets []. The reweighting parameter of the BPD algorithm is fixed to for ER networks and for RR networks; the ball radius parameter of the CI algorithm is fixed to .
Fraction of removed nodes for scale-free random networks of mean degree and degree decay exponent (a) and (b). Each CI (diamond) or BPD (circle) data point is the averaged result over 48 network instances (size ) generated through the static method []; the standard deviation (not shown) of each data point is of order . The reweighting parameter of the BPD algorithm is fixed to ; the ball radius parameter of the CI algorithm is fixed to .

Sign up to receive regular email alerts from Physical Review E