Elsevier

Information Sciences

Volume 278, 10 September 2014, Pages 685-702
Information Sciences

Measuring the impact of MVC attack in large complex networks

https://doi.org/10.1016/j.ins.2014.03.085Get rights and content

Abstract

Measuring the impact of network attack is an important issue in network science. In this paper, we study the impact of maximal vertex coverage (MVC) attack in large complex networks, where the attacker aims at deleting as many edges of the network as possible by attacking a small fraction of nodes. First, we present two metrics to measure the impact of MVC attack. To compute these metrics, we propose an efficient randomized greedy algorithm with near-optimal performance guarantee. Second, we generalize the MVC attack into an uncertain setting, in which a node is deleted by the attacker with a prior probability. We refer to the MVC attack under such uncertain environment as the probabilistic MVC attack. Based on the probabilistic MVC attack, we propose two adaptive metrics, and then present an adaptive greedy algorithm for calculating such metrics accurately and efficiently. Finally, we conduct extensive experiments on 20 real datasets. The results show that P2P and co-authorship networks are extremely robust under the MVC attack while both the online social networks and the Email communication networks exhibit vulnerability under the MVC attack. In addition, the results demonstrate the efficiency and effectiveness of the proposed algorithms for computing the proposed metrics.

Introduction

Networks are ubiquitous. Many practical systems in nature and society can be characterized by the network. Examples include (online) social networks, computer networks, Internet, biological networks, transportation networks, and so on. After the seminal work by Watts and Strogatz [51] and Barabási and Albert [2], complex networks have attracted increasing attention in both industry and research communities in the last decade. The studies of complex network mainly focus on investigating the underlying organizing principles, the function, and the dynamics of the network.

However, networks are very often attacked by malicious users. An important issue in network science is to study the robustness of a network subject to nodes or links errors [1], [52]. Many real-world examples are briefly described below. In airline network, an important question is how the operational ability of the network is affected given that a certain airports are closed. In computer networks, a key problem is to study how the communication capacity changes when some computers in the network are attacked by the hackers. In P2P networks, a crucial issue is to study how the communication ability of the network is affected when a certain number of peers depart from the network.

In practice, a network attacker typically has a small budget of k nodes (edges) to attack due to resource limitation. The attacker aims at maximizing some utility functions after attacking k nodes (edges). Many previous studies have been focused on such nodes (edges) attack problems. For example, Albert et al. [1] studied the robustness of a network by considering the diameter of the network after deleting a small fraction of nodes. In [1], the utility function of the attacker corresponds to the diameter of the network, and the attacker aims to maximize the diameter of the network, which will make the network as less cohesive as possible. Many subsequent studies [9], [8], [10] followed this framework to study how a network is affected by nodes or edges errors. However, most of them focus on deriving analytical solutions on the basis of some specific random graph models. More recently, Schneider et al. [45] investigated how the size of the giant connected component changes subject to nodes deletions. Clearly, in [45], the utility function of the attacker is the inverse of the size of the maximal connected component of the network, and the attacker aims to minimize the size of the maximal connected component of the network.

Instead of the diameter and the size of maximal connected component, in this paper, we consider another important metric, i.e., the number of residual edges of the network after attacking. Specifically, in our model, the attacker’s utility function is equal to the number of edges that are removed. The attacker aims at maximizing the number of edges that are deleted after attacking a small fixed budget of k nodes of the network. Or, equivalently, the attacker wants to minimize the number of residual edges of a network after attacking. Clearly, this problem is equivalent to the maximal vertex coverage (MVC) problem on networks [21]. We thus refer to such type of attack as the MVC attack. Note that the number of residual edges is a very natural and intuitive metric to measure the function and performance of the network. Intuitively, after the removal of k nodes, the network with a large number of residual edges implies that the function and performance of the network are not extensively damaged. There are many practical applications that can suffer from such MVC attack. For instance, in computer networks, the hacker may want to attack k workstations so as to minimize the number of surviving links in the network. In online social networks, the attacker may want to target k users by providing some incentives to persuade them to leave the social network so as to minimize the number of residual social ties of the network. Such incentive-based attacks indeed encounter in real-world online social networks. For example, a recent news in CNET (http://news.cnet.com/delete-10-facebook-friends-get-a-free-whopper/) reports an attack event. The fast-food company Burger King developed a Facebook application, namely Whopper Sacrifice, giving a Facebook user a free coupon for a free hamburger if he/she deletes 10 people from his/her friends list. By statistics, 82,771 Facebook users participated in this campaign, and 233,906 Facebook friendships were deleted. After then, Facebook closed this application due to a large number of link deletions. In addition, on the positive side, the MVC attack could be used to fight terrorism. For example, given a terrorist network, we may want to attack a small number of terrorists so that the number of residual ties in the network is minimal. As a consequence, it is important to investigate the impact of MVC attack in a network.

To study impact of the MVC attack, we present two new metrics of the network, named k-MVC-impact and cumulative k-MVC-impact. More specifically, k-MVC-impact is defined by the minimal fraction of the residual edges after removing k nodes, and cumulative k-MVC-impact is the average k-MVC-impact from k=1 to k. To compute the two proposed metrics, we propose an optimal dynamic programming algorithm for tree-like networks. For general networks, by using the submodularity of the MVC problem, we present a randomized greedy algorithm with near-optimal approximation guarantee for calculating our metrics efficiently. To the best of our knowledge, this work is the first work to measure the impact of MVC attack in complex networks. Besides the MVC attack, we also introduce a probabilistic MVC problem where a node is not always successfully removed by the attacker. Instead, we consider that the node is removed by the attacker with a prior probability. In terms of probabilistic MVC attack, we also propose two new metrics, called adaptive k-MVC-impact and adaptive cumulative k-MVC-impact. We show that the probabilistic MVC problem can be formulated as an adaptive submodular function maximization problem [19]. Based on this, we present a near-optimal adaptive greedy algorithm to calculate adaptive k-MVC-impact and adaptive cumulative k-MVC-impact efficiently. Finally, we conduct extensive experimental studies on 20 real-world datasets. The results show that the P2P and co-authorship networks are extremely robust subject to MVC attack, whereas the online social networks, the Email communication networks, as well as the web graph are shown to be very vulnerable subject to MVC attack. Also, the results confirm the effectiveness and efficiency of the proposed algorithms for computing the proposed metrics.

The remainder of this paper is organized as follows. We describe the problem and propose two metrics for studying the impact of MVC attack in Section 2. We then present two new algorithms for computing the proposed metrics in Section 3. In Section 4, we propose two new metrics w.r.t. the probabilistic MVC attack and develop an efficient adaptive greedy algorithm for calculating them accurately. We conduct extensive experimental studies in Section 5. Finally, we survey the related work in Section 6 and conclude this work in Section 7.

Section snippets

Problem formulation

Consider an undirected network G=(V,E), where V denotes a set of nodes and E denotes a set of undirected edges between the nodes. Let n=|V| and m=|E| be the number of nodes and the number of edges in G, respectively. The problem that we address in this paper is to measure the impact of MVC attack in a network.

Specifically, we consider the following setting. Assume that there is an attacker who wants to attack a network, and the attacker has a budget of k nodes to attack. If a node is attacked

Algorithms

Given a network G, the key issue to evaluate k-MVC-impact of G is to solve the MVC attack problem (Eq. (1)). Unfortunately, finding the MVC on general networks has been known to be NP-complete [11]. Hence, there is no hope to exactly compute σk in polynomial time. In this section, we first propose an optimal dynamic programming algorithm for computing σk on trees. Then, we introduce a randomized greedy algorithm for calculating σk on general networks.

Probabilistic MVC attack

In the previous sections, we consider the problem for measuring the impact of a network under a deterministic MVC attack model. That is, if an attacker attacks a node, then the node as well as its incident edges will be removed from the network. However, in practice, the nodes in a network may be tolerant of attacks to some extent. In other words, the attacker may not always delete a node successfully. In this section, we study the problem for measuring the impact of a network under such a

Experiments

In this section, we conduct extensive experiments on one synthetic and twenty real-world datasets to evaluate the effectiveness and efficiency of our approaches. In the following, we first describe the experimental setup and then report our findings.

Related work

Robustness of complex networks: Our work is closely related to measure the robustness of complex network. After the seminal work by Albert et al. [1], measuring robustness of complex networks has attracted much attention in the last decade. In order to characterize the robustness of a complex network, most previous studies focused on studying some statistical properties of the network after removing a fraction of nodes or edges. The widely-used statistical properties of a network include the

Conclusions

In this paper, we present a study of measuring the impact of MVC attack in complex networks. We define two metrics called k-MVC-impact and cumulative k-MVC-impact, and propose a dynamic programming algorithm to compute the proposed metrics on trees optimally. We then develop a near-optimal randomized greedy algorithm by using the FM sketch for calculating the proposed metrics on general networks. In addition, we present two adaptive metrics to measure the impact of a network under probabilistic

Acknowledgements

The work was supported by grants GRF 418512, 411211, and 411310 from HK-RGC.

References (53)

  • G. Bellala, S.K. Bhavnani, C. Scott, Extensions of generalized binary search to group identification and exponential...
  • G. Bellala et al.

    Group-based active query selection for rapid diagnosis in time-critical situations

    IEEE Trans. Inform. Theor.

    (2012)
  • S. Boccaletti et al.

    Multiscale vulnerability of complex network

    Chaos

    (2007)
  • C. Budak, D. Agrawal, A. El Abbadi, Limiting the spread of misinformation in social networks, in: WWW,...
  • D.S. Callaway et al.

    Network robustness and fragility: percolation on random graphs

    Phys. Rev. Lett.

    (2000)
  • R. Cohen et al.

    Resilience of the internet to random breakdowns

    Phys. Rev. Lett.

    (2000)
  • R. Cohen et al.

    Breakdown of the internet under intentional attack

    Phys. Rev. Lett.

    (2001)
  • G. Cornuejols et al.

    Worst-case and probabilistic analysis of algorithms for a location problem

    Oper. Res.

    (1980)
  • J.C. Doyle et al.

    The robust yet fragile nature of the internet

    PNAS

    (2005)
  • M. Durand, P. Flajolet, Loglog counting of large cardinalities (extended abstract), in: ESA, 2003, pp....
  • R. Durrett

    Random Graph Dynamics

    (2006)
  • M. Fiedler

    Algebraic connectivity of graphs

    Czech. Math. J.

    (1973)
  • P. Flajolet, E. Fusy, O. Gandouet, F. Meunier, Hyperloglog: the analysis of a near-optimal cardinality estimation...
  • H. Frank et al.

    Analysis and design of survivable network

    IEEE Trans. Commun. Technol.

    (1970)
  • D. Golovin et al.

    Adaptive submodularity: theory and applications in active learning and stochastic optimization

    J. Artif. Intell. Res. (JAIR)

    (2011)
  • P.R. Goundan, A.S. Schulz, Revisiting the Greedy Approach to Submodular Set Function Maximization, Technical Report,...
  • Cited by (22)

    • Test-cost-sensitive rough set based approach for minimum weight vertex cover problem

      2018, Applied Soft Computing Journal
      Citation Excerpt :

      The minimum vertex cover problem (MVCP) is a well-known optimization problem with a wide range of important applications such as network security, wireless communication, industrial machine assignments and data aggregation [1–5], the purpose of MVCP is to find a minimum subset of vertices that has at least one endpoint of each edge [6,7].

    • Probabilistic routing using multimodal data

      2017, Neurocomputing
      Citation Excerpt :

      Dijkstra’s algorithm and A* algorithm are simply based on static spatial networks, and time-dependent shortest/fastest path queries, probabilistic shortest/fastest path queries, and traffic-aware shortest/fastest path queries are based on different probabilistic models, and they are not taken the transfer cost into account during query processing. Moreover, in the future, it is of interest to integrate spatial [17–21,23,48] and social media data understanding [1,2,4,5,12,29,50,53] and social information processing [10,16,24,44,47,51] and network information processing [6,7,15,25,40,43,46,49] with our study. In this work, we integrated multi-source human-mobility tracking data and location based social media data, including spatial, temporal, and textual data, to make human-mobility prediction and over-crowded station detection.

    • Level-aware collective spatial keyword queries

      2017, Information Sciences
      Citation Excerpt :

      Furthermore, we can utilize the spatial keyword search techniques to help the studies in related research fields such as path planning [1,56], spatial and social information processing and understanding [28,31,55], and network information processing [24,30,54].

    • An efficient local search framework for the minimum weighted vertex cover problem

      2016, Information Sciences
      Citation Excerpt :

      This problem is a core optimization problem that has been studied extensively. It has important applications in various fields such as network security, industrial machine assignment, and data aggregation [7,10,25,26,39,41,49,51,56]. As a dual problem of the maximum independent set (MIS) problem [9,20,23,35,40], the MVC problem has also been applied to social networks, pattern recognition, molecular biology, and economics [1,2,6,24,32,33,65].

    • K-Metric antidimension: A privacy measure for social graphs

      2016, Information Sciences
      Citation Excerpt :

      In this attack, the attacker tries to convince some users to leave the social network in order to reduce the number of residual social ties. Metrics to quantify the impact of MVC attacks have been studied in [7]. MVC is not a privacy attack, though.

    View all citing articles on Scopus
    View full text