Critical node detection problem for complex network in undirected weighted networks. (English) Zbl 07571881
Summary: Detection of critical nodes in complex networks has recently received extensive attention. Currently, studies of the critical nodes problem (CNP) mainly focus on two problem types: “critical nodes problem/positive” (CNP-Pos) and “critical nodes problem/negative” (CNP-Neg). However, to the best of our knowledge, few studies have been conducted on CNP-Neg for weighed networks. In this paper, we investigate CNP-Neg in undirected weighted networks. We first propose a novel metric \(D_{F W}\) to evaluate network fragmentation. Then, we formulate a new nonconvex mixed-integer quadratic programming model, named MIQPM, that aims to simultaneously minimize pairwise connectivity and maximize the weights between the nodes. After that, a general greedy algorithm is employed to solve the corresponding optimization problem. Finally, comparison experiments are carried out for several synthetic networks and four real-world networks to demonstrate the effectiveness of the proposed approaches.
MSC:
| 82-XX | Statistical mechanics, structure of matter |
Keywords:
critical nodes problem; weighted network; network fragmentation; mixed-integer quadratic programming; greedy algorithmReferences:
| [1] | Borgatti, S. P., Identifying sets of key players in a social network, Comput. Math. Organ. Theory, 12, 1, 21-34 (2006) · Zbl 1198.91180 |
| [2] | Yang, L.; Qiao, Y.; Liu, Z.; Ma, J.; Li, X., Identifying opinion leader nodes in online social networks with a new closeness evaluation algorithm, Soft Comput., 22, 2, 453-464 (2018) |
| [3] | Y. Cheng, R.K. Lee, E. Lim, F. Zhu, Delayflow centrality for identifying critical nodes in transportation networks, in: 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2013), 2013, pp. 1462-1463. |
| [4] | Gan, C.; Yang, X.; Liu, W.; Zhu, Q.; Jin, J.; He, L., Propagation of computer virus both across the internet and external computers: A complex-network approach, Commun. Nonlinear Sci. Numer. Simul., 19, 8, 2785-2792 (2014) · Zbl 1510.68009 |
| [5] | J.C. Nacher, T. Akutsu, Analysis on critical nodes in controlling complex networks using dominating sets, in: 2013 International Conference on Signal-Image Technology Internet- Based Systems, 2013, pp. 649-654. |
| [6] | Nagurney, A.; Qiang, Q., Identification of critical nodes and links in financial networks with intermediation and electronic transactions, (Kontoghiorghes, E. J.; Rustem, B.; Winker, P., Computational Methods in Financial Engineering: Essays in Honour of Manfred Gilli (2008), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 273-297 · Zbl 1142.90331 |
| [7] | Byrne, R.; Feddema, J.; Abdallah, C., Algebraic Connectivity and Graph Robustness, 87185 (2009), Sandia National Laboratories: Sandia National Laboratories Albuquerque, New Mexico |
| [8] | Boginski, V.; Clayton, J.; Commander, W., Identifying critical nodes in protein-protein interaction networks, (Clustering Challenges in Biological Networks (2009), World Scientific), 153-167 |
| [9] | A. Kuipers, F., An overview of algorithms for network survivability, ISRN Commun. Netw., 2012 (2012) |
| [10] | Lozano, M.; García-Martínez, C.; Rodríguez, F. J.; Trujillo, H. M., Optimizing network attacks by artificial bee colony, Inform. Sci., 377, 30-50 (2017) |
| [11] | Fu, J.; Zou, Y.; Xie, R., Identification of critical nodes in a power network with considering the network dynamics, Complex Syst. Complex. Sci., 14, 02, 31-38 (2017) |
| [12] | Kleinberg, J.; Sandler, M.; Slivkins, A., Network failure detection and graph connectivity, SIAM J. Comput., 38 (2003) |
| [13] | R. Andersen, F. Chung, K. Lang, Local graph partitioning using pagerank vectors, in: 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), 2006, pp. 475-486. |
| [14] | Buluç, A.; Meyerhenke, H.; Safro, I.; Sanders, P.; Schulz, C., Recent advances in graph partitioning, (Kliemann, L.; Sanders, P., Algorithm Engineering: Selected Results and Surveys (2016), Springer International Publishing: Springer International Publishing Cham), 117-158 |
| [15] | Lalou, M.; Tahraoui, M.; Kheddouci, H., Component-cardinality-constrained critical node problem in graphs, Discrete Appl. Math., 210, 150-163 (2016) · Zbl 1339.05374 |
| [16] | Faramondi, L.; Oliva, G.; Setola, R.; Pascucci, F.; Esposito Amideo, A.; Scaparra, M. P., Performance analysis of single and multi-objective approaches for the critical node detection problem, (Sforza, A.; Sterle, C., Optimization and Decision Science: Methodologies and Applications (2017), Springer International Publishing: Springer International Publishing Cham), 315-324 |
| [17] | Latora, V.; Marchiori, M., Efficient behavior of small-world networks, Phys. Rev. Lett., 87, 19, 198701 (2001) |
| [18] | Crucitti, P.; Latora, V.; Marchiori, M.; Rapisarda, A., Efficiency of scale-free networks: error and attack tolerance, Physica A, 320, 622-642 (2003) · Zbl 1010.68003 |
| [19] | Crucitti, P.; Latora, V.; Marchiori, M.; Rapisarda, A., Error and attack tolerance of complex networks, Physica A, 340, 1, 388-394 (2004) |
| [20] | Schneidman, E.; Still, S.; Berry, M. J.; Bialek, W., Network information and connected correlations, Phys. Rev. Lett., 91, 238701 (2003) |
| [21] | Frederickson, G. N.; Solis-Oba, R., Increasing the weight of minimum spanning trees, J. Algorithms, 33, 2, 244-266 (1999) · Zbl 0956.68113 |
| [22] | H. Saran, V.V. Vazirani, Finding k-cuts within twice the optimal, in: [1991] Proceedings 32nd Annual Symposium of Foundations of Computer Science, 1991, pp. 743-751. · Zbl 0828.68082 |
| [23] | Cheriyan, J.; Thurimella, R., Fast algorithms for k-shredders and k-node connectivity augmentation, J. Algorithms, 33, 1, 37-46 (1999) · Zbl 0924.68100 |
| [24] | Jordán, T., On the optimal vertex-connectivity augmentation, J. Combin. Theory Ser. B, 63, 1, 8-20 (1995) · Zbl 0824.05042 |
| [25] | C.H.Q. Ding, X. He, H. Zha, A spectral method to separate disconnected and nearly- disconnected web graph component, in: Proceedings of the Seventh ACM International Con- ference on Knowledge Discovery and Data Mining, 2001, pp. 275-280. |
| [26] | Marx, D., Parameterized graph separation problems, Theoret. Comput. Sci., 351, 3, 394-406 (2006) · Zbl 1086.68104 |
| [27] | Arulselvan, A.; Commander, C. W.; Pardalos, P. M.; Shylo, O., Managing Network Risk Via Critical Node Identification (2007), Springer, Risk management in telecommunication networks |
| [28] | L. Faramondi, G. Oliva, F. Pascucci, S. Panzieri, R. Setola, Critical node detection based on attacker preferences, in: 2016 24th Mediterranean Conference on Control and Automation (MED), 2016, pp. 773-778. |
| [29] | van der Zwaan, R.; Berger, A.; Grigoriev, A., How to cut a graph into many pieces, (Ogihara, M.; Tarui, J., Theory and Applications of Models of Computation (2011), Springer Berlin Heidelberg: Springer Berlin Heidelberg Berlin, Heidelberg), 184-194 · Zbl 1331.68117 |
| [30] | Shen, S.; Smith, J. C., Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs, Networks, 60, 2, 103-119 (2012) · Zbl 1251.90376 |
| [31] | Shen, S.; Smith, J. C.; Goli, R., Exact interdiction models and algorithms for disconnecting networks via node deletions, Discrete Optim., 9, 3, 172-188 (2012) · Zbl 1254.90280 |
| [32] | Berger, A.; Grigoriev, A.; van der Zwaan, R., Complexity and approximability of the k-way vertex cut, Networks, 63, 2, 170-178 (2014) · Zbl 1386.05148 |
| [33] | Oosten, M.; Rutten, J. H.G. C.; Spieksma, F. C.R., Disconnecting graphs by removing vertices: a polyhedral approach, Stat. Neerl., 61, 1, 35-60 (2010) · Zbl 1122.90088 |
| [34] | Walteros, J. L.; Pardalos, P. M., Selected topics in critical element detection, Applications of Mathematics and Informatics in Military Science, 9-26 (2012), Springer New York: Springer New York New York, NY · Zbl 1315.90060 |
| [35] | Nguyen, D. T.; Shen, Y.; Thai, M. T., Detecting critical nodes in interdependent power networks for vulnerability assessment, IEEE Trans. Smart Grid, 4, 1, 151-159 (2013) |
| [36] | Addis, B.; Summa, M. D.; Grosso, A., Identifying critical nodes in undirected graphs: Complexity results and polynomial algorithms for the case of bounded treewidth, Discrete Appl. Math., 161, 16, 2349-2360 (2013) · Zbl 1285.05042 |
| [37] | Ventresca, M.; Aleman, D., A fast greedy algorithm for the critical node detection problem, (Zhang, Z.; Wu, L.; Xu, W.; Du, D. Z., Combinatorial Optimization and Applications (2014), Springer International Publishing: Springer International Publishing Cham), 603-612 · Zbl 1433.05302 |
| [38] | Ventresca, M.; Aleman, D., Efficiently identifying critical nodes in large complex networks, Comput. Soc. Netw., 2, 1, 6 (2015) |
| [39] | Aringhieri, R.; Grosso, A.; Hosteins, P.; Scatamacchia, R., Local search metaheuristics for the critical node problem, Networks, 67, 3, 209-221 (2016) |
| [40] | Arulselvan, A.; Commander, C. W.; Elefteriadou, L.; Pardalos, P. M., Detecting critical nodes in sparse graphs, Comput. Oper. Res., 36, 7, 2193-2200 (2009) · Zbl 1158.90411 |
| [41] | Di Summa, M.; Grosso, A.; Locatelli, M., Branch and cut algorithms for detecting critical nodes in undirected graphs, Comput. Optim. Appl., 53, 3, 649-680 (2012) · Zbl 1264.90170 |
| [42] | Shen, Y.; Nguyen, N. P.; Xuan, Y.; Thai, M. T., On the discovery of critical links and nodes for assessing network vulnerability, IEEE/ACM Trans. Netw., 21, 3, 963-973 (2013) |
| [43] | Veremyev, A.; Boginski, V.; Pasiliao, E. L., Exact identification of critical nodes in sparse networks via new compact formulations, Optim. Lett., 8, 4, 1245-1259 (2014) · Zbl 1292.90260 |
| [44] | Veremyev, A.; Prokopyev, O. A.; Pasiliao, E. L., An integer programming framework for critical elements detection in graphs, J. Comb. Optim., 28, 1, 233-273 (2014) · Zbl 1303.90120 |
| [45] | Ventresca, M.; Aleman, D., A region growing algorithm for detecting critical nodes, (Zhang, Z.; Wu, L.; Xu, W.; Du, D. Z., Combinatorial Optimization and Applications (2014), Springer International Publishing: Springer International Publishing Cham), 593-602 · Zbl 1433.05301 |
| [46] | Addis, B.; Aringhieri, R.; Grosso, A.; Hosteins, P., Hybrid constructive heuristics for the critical node problem, Ann. Oper. Res., 238, 1, 637-649 (2016) · Zbl 1334.90185 |
| [47] | Jiang, C.; Liu, Z.; Wang, J.; Yu, H.; Guo, X., An optimal approach for the critical node problem using semidefinite programming, Physica A, 471, 315-324 (2017) · Zbl 1400.90243 |
| [48] | Purevsuren, D.; Cui, G., Efficient heuristic algorithm for identifying critical nodes in planar networks, Comput. Oper. Res., 106, 143-153 (2019) · Zbl 1458.90622 |
| [49] | Lalou, M.; Tahraoui, M. A.; Kheddouci, H., The critical node detection problem in networks: A survey, Comp. Sci. Rev., 28, 92-117 (2018) · Zbl 1387.68186 |
| [50] | Matisziw, T. C.; Murray, A. T., Modeling sl̀ct path availability to support disaster vulnerability assessment of network infrastructure, Comput. Oper. Res., 36, 1, 16-26 (2009) · Zbl 1163.90441 |
| [51] | T.N. Dinh, Y. Xuan, M.T. Thai, E.K. Park, T. Znati, On approximation of new optimization methods for assessing network vulnerability, in: 2010 Proceedings IEEE INFOCOM, 2010, pp. 1-9. |
| [52] | Oosten, M.; Rutten, J. H.G. C.; Spieksma, F. C.R., Disconnecting graphs by removing vertices: a polyhedral approach, Stat. Neerl., 61, 1, 35-60 (2007) · Zbl 1122.90088 |
| [53] | Yu, Z. G.; Anh, V.; Lau, K. S., Chaos game representation of protein sequences based on the detailed HP model and their multifractal and correlation analyses, J. Theoret. Biol., 226, 3, 341-348 (2004) · Zbl 1439.92148 |
| [54] | Norton, G. H.; Salagean, A., On the hamming distance of linear codes over a finite chain ring, IEEE Trans. Inform. Theory, 46, 3, 1060-1067 (2000) · Zbl 0963.94043 |
| [55] | Dokmanic, I.; Parhizkar, R.; Ranieri, J.; Vetterli, M., Euclidean distance matrices: Essential theory, algorithms, and applications, IEEE Signal Process. Mag., 32, 6, 12-30 (2015) |
| [56] | Merigó, J. M.; Casanovas, M., A new minkowski distance based on induced aggregation operators, Int. J. Comput. Intell. Syst., 4, 2, 123-133 (2011) |
| [57] | Krebs, V., Uncloaking terrorist networks, First Monday, 7, 2002 (2002) |
| [58] | E. Knuth, D., The Stanford GraphBase: A platform for combinatorial computing (1993), Addison-Wesley · Zbl 0806.68121 |
| [59] | R.A. Rossi, N.K. Ahmed, The network data repository with interactive graph analytics and visualization, in: AAAI, URL http://networkrepository.com, 2015. |
| [60] | Zhao, L.; Li, W.; Cai, X., Structure and dynamics of stock market in times of crisis, Phys. Lett. A, 380, 5, 654-666 (2016) |
| [61] | Mantegna, R. N., Hierarchical structure in financial markets, Eur. Phys. J. B, 11, 1, 193-197 (1999) |
| [62] | Zou, K. H.; Tuncali, K.; Silverman, S. G., Correlation and simple linear regression, Radiology, 227, 3, 617-628 (2003) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
