Optimal Disintegration Strategy With Heterogeneous Costs in Complex Networks

Recently, research in the field of network disintegration, which includes controlling the spread of disease and collapsing terrorist organizations, has found broad applications and attracted increased attention. In this paper, we focus on the network disintegration with heterogeneous cost, in which there may be unequal disintegration costs associated with deleting different nodes. First, we present a cost model for a disintegration strategy with both cost-sensitive and cost-constraint parameters in complex networks. Then, we propose an optimization model for the disintegration strategy with heterogeneous cost and introduce the genetic algorithm to identify the optimal disintegration strategy. Extensive experiments in synthetic and real-world networks suggest that the heterogeneity of the disintegration cost and the tightness of the cost constraint significantly affect the optimal disintegration strategy. We demonstrate that, in contrast to the classical hub node strategy, low-cost nodes play a key role in the optimal disintegration strategies if the cost constraint is tight and the disintegration cost is strongly heterogeneous.

I. Introduction

Complex networks describe a wide range of systems in nature and society, such as the Internet, power grids, citation networks, epidemic spreading networks, terrorist networks, and rumor-spreading networks [1]–[3]. Most networks are beneficial, and the goal is to preserve their function. Many researchers have focused on designing ways to increase the survivability of such networks [4]–[7]. The original motivation for this paper is to determine how to collapse a network that may be detrimental, such as immunizing residents or communication network to prevent the spread of disease or distribution of a computer virus. Other examples include destabilizing terrorist networks [8], avoiding financial crises [9], controlling the spread of rumors [10], and interrupting cancer networks [11].