Measuring the impact of MVC attack in large complex networks
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 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 , where V denotes a set of nodes and E denotes a set of undirected edges between the nodes. Let and 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 in polynomial time. In this section, we first propose an optimal dynamic programming algorithm for computing on trees. Then, we introduce a randomized greedy algorithm for calculating 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)
- et al.
Probabilistic counting algorithms for data base applications
J. Comput. Syst. Sci.
(1985) - et al.
On approximation of max-vertex-cover
Eur. J. Oper. Res.
(2002) - et al.
Robustness of fuzzy reasoning via logically equivalence measure
Inf. Sci.
(2007) - et al.
Robustness of star graph network under link failure
Inf. Sci.
(2008) - et al.
Hyper hamiltonian laceability on edge fault star graph
Inf. Sci.
(2004) Isoperimetric number of graphs
J. Combin. Theor. Ser. B
(1989)- et al.
Improving bounds on link failure tolerance of the star graph
Inf. Sci.
(2010) - et al.
Error and attack tolerance of complex networks
Nature
(2000) - et al.
Emergence of scaling in random networks
Science
(1999) - D. Bauer, F. Boesch, C. Suffel, R. Tindell, Connectivity extremal problems and the design of reliable probabilistic...
Group-based active query selection for rapid diagnosis in time-critical situations
IEEE Trans. Inform. Theor.
Multiscale vulnerability of complex network
Chaos
Network robustness and fragility: percolation on random graphs
Phys. Rev. Lett.
Resilience of the internet to random breakdowns
Phys. Rev. Lett.
Breakdown of the internet under intentional attack
Phys. Rev. Lett.
Worst-case and probabilistic analysis of algorithms for a location problem
Oper. Res.
The robust yet fragile nature of the internet
PNAS
Random Graph Dynamics
Algebraic connectivity of graphs
Czech. Math. J.
Analysis and design of survivable network
IEEE Trans. Commun. Technol.
Adaptive submodularity: theory and applications in active learning and stochastic optimization
J. Artif. Intell. Res. (JAIR)
Cited by (22)
Test-cost-sensitive rough set based approach for minimum weight vertex cover problem
2018, Applied Soft Computing JournalCitation 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, NeurocomputingCitation 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 SciencesCitation 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 SciencesCitation 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 SciencesCitation 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.
Urban spatial location service prediction algorithm based on fast adaptive genetic algorithm-least squares support vector machine under the background of Internet of Things
2022, Concurrency and Computation: Practice and Experience