Connectivity maintenance against link uncertainty and heterogeneity in adversarial networks

Abstract

This paper delves into the challenge of maintaining connectivity in adversarial networks, focusing on the preservation of essential links to prevent the disintegration of network components under attack. Unlike previous approaches that assume a stable and homogeneous network topology, this study introduces a more realistic model that incorporates both link uncertainty and heterogeneity. Link uncertainty necessitates additional probing to confirm link existence, while heterogeneity reflects the varying resilience of links against attacks. We model the network as a random graph where each link is defined by its existence probability, probing cost, and resilience. The primary objective is to devise a defensive strategy that maximizes the expected size of the largest connected component at the end of an adversarial process while minimizing the probing cost, irrespective of the attack patterns employed. We begin by establishing the NP-hardness of the problem and then introduce an optimal defensive strategy based on dynamic programming. Due to the high computational cost of achieving optimality, we also develop two approximate strategies that offer efficient solutions within polynomial time. The first is a heuristic method that assesses link importance across three heterogeneous subnetworks, and the second is an adaptive minimax policy designed to minimize the defender’s potential worst-case loss, with guaranteed performance. Through extensive testing on both synthetic and real-world datasets across various attack scenarios, our strategies demonstrate significant advantages over existing methods.

Keywords

Connectivity maintenance / Random graph / Network attack

CRediT authorship contribution statement

Jianzhi Tang: Writing - original draft, Software, Methodology, Investigation, Formal analysis, Data curation, Conceptualization. Luoyi Fu: Writing - review & editing. Lei Zhou: Investigation. Xinbing Wang: Writing - review & editing. Chenghu Zhou: Investigation.

Declaration of competing interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

References

[1] M.F. Özkoç, A. Koutsaftis, R. Kumar, P. Liu, S.S. Panwar, The impact of multiconnectivity and handover constraints on millimeter wave and terahertz cellular networks, IEEE J. Sel. Areas Commun. 39 (6) (2021) 1833-1853.

[2] D. Qin, X. Zhou, L. Chen, G. Huang, Y. Zhang, Dynamic connection-based social group recommendation, IEEE Trans. Knowl. Data Eng. 32 (3) (2018) 453-467.

[3] X. Cheng, M. Xu, R. Pan, D. Yu, C. Wang, X. Xiao, W. Lyu, Meta computing, IEEE Netw. (2023).

[4] M. Xu, F. Zhao, Y. Zou, C. Liu, X. Cheng, F. Dressler, BLOWN: A blockchain protocol for single-hop wireless networks under adversarial SINR, IEEE Trans. Mob. Comput. (2022).

[5] M. Xu, C. Liu, Y. Zou, F. Zhao, J. Yu, X. Cheng, wChain: A fast fault-tolerant blockchain protocol for multihop wireless networks, IEEE Trans. Wireless Commun. 20 (10) (2021) 6915-6926.

[6] M. Xu, C. Wang, Y. Zou, D. Yu, X. Cheng, W. Lyu,Curb: Trusted and scalable software-defined network control plane for edge computing, in: 2022 IEEE 42nd International Conference on Distributed Computing Systems, ICDCS, IEEE, 2022, pp. 492-502.

[7] T.N. Dinh, M.T. Thai,Assessing attack vulnerability in networks with uncertainty, in: 2015 IEEE Conference on Computer Communications, INFOCOM, IEEE, 2015, pp. 2380-2388.

[8] R. Du, G. Dong, L. Tian, R. Liu, Targeted attack on networks coupled by connectivity and dependency links, Physica A 450 (2016) 687-699.

[9] N. Abuzainab, W. Saad, Dynamic connectivity game for adversarial internet of battlefield things systems, IEEE Internet Things J. 5 (1) (2018) 378-390.

[10] Y. Nugraha, A. Cetinkaya, T. Hayakawa, H. Ishii, Q. Zhu, Dynamic resilient network games with applications to multiagent consensus, IEEE Trans. Control Netw. Syst. 8 (1) (2020) 246-259.

[11] Y. Hao, L. Jia, Y. Wang, Edge attack strategies in interdependent scale-free networks, Physica A 540 (2020) 122759.

[12] A.D. Flaxman, A.M. Frieze, J. Vera, Adversarial deletion in a scale-free random graph process, Combin. Probab. Comput. 16 (2) (2007) 261-270.

[13] J. Tang, L. Fu, J. Ding, X. Wang, G. Chen,Connectivity maintenance in uncertain networks under adversarial attack, in: 2022 IEEE Conference on Computer Communications, INFOCOM, IEEE, 2022, pp. 1399-1408.

[14] J. Wang, J. Luo, S.J. Pan, A. Sun, Learning-based outdoor localization exploiting crowd-labeled WiFi hotspots, IEEE Trans. Mob. Comput. 18 (4) (2018) 896-909.

[15] S. Ji, R. Beyah, Z. Cai, Snapshot and continuous data collection in proba-bilistic wireless sensor networks, IEEE Trans. Mob. Comput. 13 (3) (2013) 626-637.

[16] L. Fu, X. Fu, Z. Xu, Q. Peng, X. Wang, S. Lu, Determining source-destination connectivity in uncertain networks: Modeling and solutions, IEEE/ACM Trans. Netw. 25 (6) (2017) 3237-3252.

[17] C.-F. Chiasserini, M. Garetto, E. Leonardi, De-anonymizing clustered social networks by percolation graph matching, ACM Trans. Knowl. Discov. Data (TKDD) 12 (2) (2018) 1-39.

[18] D. Cheng, C. Chen, X. Wang, S. Xiang, Efficient top-k vulnerable nodes detection in uncertain graphs, IEEE Trans. Knowl. Data Eng. (2021).

[19] A. Saha, R. Brokkelkamp, Y. Velaj, A. Khan, F. Bonchi, Shortest paths and centrality in uncertain networks, Proc. VLDB Endow. 14 (7) (2021) 1188-1201.

[20] L. Sun, Z. Zhang, J. Wen, F. Wang, P. Ji, S. Su, P. Yu, Aligning dynamic social networks: An optimization over dynamic graph autoencoder, IEEE Trans. Knowl. Data Eng. (2022).

[21] E. Arribas, V. Mancuso, V. Cholvi, Coverage optimization with a dynamic network of drone relays, IEEE Trans. Mob. Comput. 19 (10) (2019) 2278-2298.

[22] Z. Wu, Z. Li, Distributed robust optimization algorithms over uncertain network graphs, IEEE Trans. Cybern. (2020).

[23] L. Fan, X. Liu, H. Zhou, V.C. Leung, J. Su, A.X. Liu, Efficient resource scheduling for interference alleviation in dynamic coexisting WBANs, IEEE Trans. Mob. Comput. (2021).

[24] K. Ding, H. Yousefi’zadeh, F. Jabbari, Connectivity maintenance in mobile networks, IEEE/ACM Trans. Netw. 28 (3) (2020) 1269-1282.

[25] V.K. Akram, O. Dagdeviren, B. Tavli, A coverage-aware distributed kconnectivity maintenance algorithm for arbitrarily large k in mobile sensor networks, IEEE/ACM Trans. Netw. 30 (1) (2021) 62-75.

[26] S. Li, S. Wager, Random graph asymptotics for treatment effect estimation under network interference, Ann. Statist. 50 (4) (2022) 2334-2358.

[27] M. Drobyshevskiy, D. Turdakov, Random graph modeling: A survey of the concepts, ACM Comput. Surv. ( CSUR) 52 (6) (2019) 1-36.

[28] E. Isufi, A. Loukas, A. Simonetto, G. Leus, Filtering random graph processes over random time-varying graphs, IEEE Trans. Signal Process. 65 (16) (2017) 4406-4421.

[29] A. Khan, F. Bonchi, F. Gullo, A. Nufer, Conditional reliability in uncertain graphs, IEEE Trans. Knowl. Data Eng. 30 (11) (2018) 2078-2092.

[30] S. Qu, H. Xu, L. Fu, H. Long, X. Wang, G. Chen, C. Zhou, Tracing truth and rumor diffusions over mobile social networks: Who are the initiators, IEEE Trans. Mob. Comput. (2021).

[31] Z. Zhang, Y. Deng, G. Min, J. Xie, L.T. Yang, Y. Zhou, HSDC: A highly scalable data center network architecture for greater incremental scalability, IEEE Trans. Parallel Distrib. Syst. 30 (5) (2018) 1105-1119.

[32] H. Gong, L. Fu, X. Fu, L. Zhao, K. Wang, X. Wang, Distributed multicast tree construction in wireless sensor networks, IEEE Trans. Inform. Theory 63 (1) (2016) 280-296.

[33] C. Zhao, J. Zhao, X. Lin, C. Wu,Capacity of P2P on-demand streaming with simple, robust, and decentralized control, IEEE/ACM Trans. Netw. 24 (5) (2015) 2607-2620.

[34] M.O. Ball, Computational complexity of network reliability analysis: An overview, IEEE Trans. Reliab. 35 (3) (1986) 230-239.

[35] R.E. Bellman, S.E. Dreyfus, Applied Dynamic Programming, Princeton University Press, 2015.

[36] D. Golovin, A. Krause, Adaptive submodularity: Theory and applications in active learning and stochastic optimization, J. Artificial Intelligence Res. 42 (2011) 427-486.

[37] J.J. McAuley, J. Leskovec, Learning to discover social circles in ego networks, in: NIPS, vol. 2012, Citeseer, 2012, pp. 548-556.

[38] J. Leskovec, J. Kleinberg, C. Faloutsos, Graph evolution: Densification and shrinking diameters, ACM Trans. Knowl. Discov. Data (TKDD) 1 (1) (2007) 2-es.

[39] D. Liben-Nowell, J. Kleinberg, The link-prediction problem for social networks, J. Am. Soc. Inf. Sci. Technol. 58 (7) (2007) 1019-1031.