An official website of the United States government
Complex systems such as smart cities and smart power grids rely heavily on their interdependent components. The failure of a component in one network may lead to the failure of the supported component in another network. Components which support a large number of interdependent components may be more vulnerable to attacks and failures. In this paper, we study the robustness of two interdependent networks under node failures. By modeling each network using a random geometric graph (RGG), we study conditions for the percolation of two interdependent RGGs after in-homogeneous node failures. We derive analytical bounds on the interdependent degree thresholds (k 1 ,k 2 ), such that the interdependent RGGs percolate after removing nodes in G i that support more than k j nodes in G j (∀i, j ∈ {1, 2}, i ≠ j). We verify the bounds using numerical simulation, and show that there is a tradeoff between k 1 and k 2 for maintaining percolation after the failures.
more »
« less
Realtime Robustification of Interdependent Networks under Cascading Attacks
This paper studies the problem of robustifying an interdependent network by rewiring a small number of links in realtime during a cascading attack. Interdependent networks have been widely used to model interconnected complex systems such as a critical infrastructure network including both the power grid and the Internet. Realtime robustification of interdependent networks, therefore, has significant practical importance. This paper formulates the problem using the Markov decision process (MDP) framework. We first show the problem is NP-hard and then develop an effective and efficient greedy algorithm, named R EAL W IRE , to robustify the network in realtime. R EAL W IRE scores each link (and each node) based on the expected number of links failures resulted from the failure of the link (or the node), and rewires the links greedily according to the scores. Extensive experimental results show that R EAL W IRE outperforms other algorithms on multiple trobustness metrics.
more »
« less
- PAR ID:
- 10099225
- Date Published:
- Journal Name:
- 2018 IEEE International Conference on Big Data (Big Data)
- Page Range / eLocation ID:
- 1347 to 1356
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Link prediction is one of the fundamental problems in computational social science. A particularly common means to predict existence of unobserved links is via structural similarity metrics, such as the number of common neighbors; node pairs with higher similarity are thus deemed more likely to be linked. However, a number of applications of link prediction, such as predicting links in gang or terrorist networks, are adversarial, with another party incentivized to minimize its effectiveness by manipulating observed information about the network. We offer a comprehensive algorithmic investigation of the problem of attacking similarity-based link prediction through link deletion, focusing on two broad classes of such approaches, one which uses only local information about target links, and another which uses global network information. While we show several variations of the general problem to be NP-Hard for both local and global metrics, we exhibit a number of well-motivated special cases which are tractable. Additionally, we provide principled and empirically effective algorithms for the intractable cases, in some cases proving worst-case approximation guarantees.more » « less
-
An influential node identification method considering multi-attribute decision fusion and dependencyAbstract It is essential to study the robustness and centrality of interdependent networks for building reliable interdependent systems. Here, we consider a nonlinear load-capacity cascading failure model on interdependent networks, where the initial load distribution is not random, as usually assumed, but determined by the influence of each node in the interdependent network. The node influence is measured by an automated entropy-weighted multi-attribute algorithm that takes into account both different centrality measures of nodes and the interdependence of node pairs, then averaging for not only the node itself but also its nearest neighbors and next-nearest neighbors. The resilience of interdependent networks under such a more practical and accurate setting is thoroughly investigated for various network parameters, as well as how nodes from different layers are coupled and the corresponding coupling strength. The results thereby can help better monitoring interdependent systems.more » « less
-
We study the problem of broadcasting realtime flows in multi-hop wireless networks. We assume that each packet has a stringent deadline, and each node in the network obtains some utility based on the number of packets delivered to it on time for each flow. We propose a distributed protocol called the delegated-set routing (DSR) that incurs virtually no overhead of coordination among nodes. We also develop distributed algorithms that aim to maximize the total timely utility under DSR. The utility of the DSR protocol and distributed algorithms are demonstrated by both theoretical analysis and simulation results. We show that our algorithms achieve higher timely throughput even when compared against centralized throughput optimal policies that do not consider deadline constraints.more » « less
-
The lack of large-scale, continuously evolving empirical data usually limits the study of networks to the analysis of snapshots in time. This approach has been used for verification of network evolution mechanisms, such as preferential attachment. However, these studies are mostly restricted to the analysis of the first links established by a new node in the network and typically ignore connections made after each node’s initial introduction. Here, we show that the subsequent actions of individuals, such as their second network link, are not random and can be decoupled from the mechanism behind the first network link. We show that this feature has strong influence on the network topology. Moreover, snapshots in time can now provide information on the mechanism used to establish the second connection. We interpret these empirical results by introducing the “propinquity model,” in which we control and vary the distance of the second link established by a new node and find that this can lead to networks with tunable density scaling, as found in real networks. Our work shows that sociologically meaningful mechanisms are influencing network evolution and provides indications of the importance of measuring the distance between successive connections.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/BigData.2018.8622022
