Measures and Optimization for Robustness and Vulnerability in Disconnected Networks
Authors: 
Liwang Zhu, Qi Bao, Zhongzhi ZhangAuthors Info & Claims
Pages 3350 - 3362
Abstract
The function or performance of a network is strongly dependent on its robustness, which quantifies the ability of the network to continue functioning under perturbations. While a wide variety of robustness metrics have been proposed, they have their respective limitations. In this paper, we propose to use the forest index as a measure of network robustness, which overcomes the deficiencies of existing metrics. Using such a measure as an optimization criterion, we propose and study the problem of breaking down a network by attacking some key edges. We show that the objective function of the problem is monotonic but not submodular, which impose more challenging on the problem. We thus resort to greedy algorithms extended for non-submodular functions by iteratively deleting the most promising edges. We first propose a simple greedy algorithm with a proved bound for the approximation ratio and cubic-time complexity. To confront the computation challenge for large networks, we further propose an improved nearly-linear time greedy algorithm, which significantly speeds up the process for edge selection but sacrifices little accuracy. Extensive experimental results for a large set of real-world networks verify the effectiveness and efficiency of our algorithms, demonstrating that our algorithms outperform several baseline schemes.
References
[1]
X. Wang, L. Feng, R. E. Kooij, and J. L. Marzo, “Inconsistencies among spectral robustness metrics,” in Quality, Reliability, Security and Robustness in Heterogeneous Systems. Cham, Switzerland: Springer, 2019, pp. 119–136.
[2]
P. Hines, K. Balasubramaniam, and E. C. Sanchez, “Cascading failures in power grids,” IEEE Potentials, vol. 28, no. 5, pp. 24–30, Sep. 2009.
[3]
T. R. Reshmi, “Information security breaches due to ransomware attacks—A systematic literature review,” Int. J. Inf. Manage. Data Insights, vol. 1, no. 2, Nov. 2021, Art. no.
[4]
W. Ellens and R. E. Kooij, “Graph measures and network robustness,” 2013, arXiv:1311.5064.
[5]
M. Oehlers and B. Fabian, “Graph metrics for network robustness—A survey,” Mathematics, vol. 9, no. 8, p. 895, 2021.
[6]
F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi, “Defining and identifying communities in networks,” Proc. Nat. Acad. Sci. USA, vol. 101, no. 9, pp. 2658–2663, Feb. 2004.
[7]
M. E. J. Newman, “A measure of betweenness centrality based on random walks,” Social Netw., vol. 27, no. 1, pp. 39–54, Jan. 2005.
[8]
U. Brandes and D. Fleischer, “Centrality measures based on current flow,” in Proc. 22nd Annu. Symp. Theor. Aspects Comput. Sci., 2005, pp. 533–544.
[9]
I. Kovács and A. Barabási, “Network science: Destruction perfected,” Nature, vol. 524, no. 7563, pp. 38–39, 2015.
[10]
H. Aziz, S. Gaspers, and K. Najeebullah, “Weakening covert networks by minimizing inverse geodesic length,” in Proc. 26th Int. Joint Conf. Artif. Intell., Aug. 2017, pp. 779–785.
[11]
Y. Zhang, A. Adiga, S. Saha, A. Vullikanti, and B. A. Prakash, “Near-optimal algorithms for controlling propagation at group scale on networks,” IEEE Trans. Knowl. Data Eng., vol. 28, no. 12, pp. 3339–3352, Dec. 2016.
[12]
A. Ganesh, L. Massoulie, and D. Towsley, “The effect of network topology on the spread of epidemics,” in Proc. IEEE 24th Annu. Joint Conf. IEEE Comput. Commun. Societies, Mar. 2005, pp. 1455–1466.
[13]
R. Pastor-Satorras, C. Castellano, P. Van Mieghem, and A. Vespignani, “Epidemic processes in complex networks,” Rev. Modern Phys., vol. 87, no. 3, pp. 925–979, Aug. 2015.
[14]
Y. Hayel and Q. Zhu, “Epidemic protection over heterogeneous networks using evolutionary Poisson games,” IEEE Trans. Inf. Forensics Security, vol. 12, no. 8, pp. 1786–1800, Aug. 2017.
[15]
J. O. Kephart and S. R. White, “Directed-graph epidemiological models of computer viruses,” in Proc. IEEE Comput. Soc. Symp. Res. Secur. Privacy, May 1991, pp. 343–359.
[16]
J. O. Kephart and S. R. White, “Measuring and modeling computer virus prevalence,” in Proc. IEEE Comput. Soc. Symp. Res. Secur. Privacy, May 1993, pp. 2–15.
[17]
J. T. Jackson and S. Creese, “Virus propagation in heterogeneous Bluetooth networks with human behaviors,” IEEE Trans. Depend. Secure Comput., vol. 9, no. 6, pp. 930–943, Dec. 2012.
[18]
X. Wang, W. Ni, K. Zheng, R. P. Liu, and X. Niu, “Virus propagation modeling and convergence analysis in large-scale networks,” IEEE Trans. Inf. Forensics Security, vol. 11, no. 10, pp. 2241–2254, Oct. 2016.
[19]
Y. Yi, L. Shan, P. E. Paré, and K. H. Johansson, “Edge deletion algorithms for minimizing spread in SIR epidemic models,” SIAM J. Control Optim., vol. 60, no. 2, pp. S246–S273, Apr. 2022.
[20]
E. M. Daly and M. Haahr, “Social network analysis for routing in disconnected delay-tolerant MANETs,” in Proc. 8th ACM Int. Symp. Mobile Ad Hoc Netw. Comput., Sep. 2007, pp. 32–40.
[21]
L. Huang, L. Liao, and C. H. Wu, “Completing sparse and disconnected protein–protein network by deep learning,” BMC Bioinf., vol. 19, no. 1, p. 103, Dec. 2018.
[22]
P. Y. Chebotarev and E. V. Shamis, “The matrix-forest theorem and measuring relations in small social groups,” Autom. Remote Control, vol. 58, no. 9, pp. 1505–1514, Feb. 1997.
[23]
P. Y. Chebotarev and E. V. Shamis, “On proximity measures for graph vertices,” Automat. Remote Control, vol. 59, no. 10, pp. 1443–1459, 1998.
[24]
R. Merris, “Doubly stochastic graph matrices, II,” Linear Multilinear Algebra, vol. 45, nos. 2–3, pp. 275–285, Dec. 1998.
[25]
P. Chebotarev, “Spanning forests and the golden ratio,” Discrete Appl. Math., vol. 156, no. 5, pp. 813–821, Mar. 2008.
[26]
H. Tong, B. A. Prakash, C. Tsourakakis, T. Eliassi-Rad, C. Faloutsos, and D. H. Chau, “On the vulnerability of large graphs,” in Proc. IEEE Int. Conf. Data Mining, Dec. 2010, pp. 1091–1096.
[27]
S. Freitas, D. Yang, S. Kumar, H. Tong, and D. H. Chau, “Graph vulnerability and robustness: A survey,” IEEE Trans. Knowl. Data Eng., vol. 35, no. 6, pp. 5915–5934, Jun. 2023.
[28]
A. K. Ng and J. Efstathiou, “Structural robustness of complex networks,” Phys. Rev., vol. 3, pp. 175–188, Mar. 2006.
[29]
L. C. Freeman, “Centrality in social networks conceptual clarification,” Social Netw., vol. 1, no. 3, pp. 215–239, Jan. 1978.
[30]
G. Weichenberg, V. W. S. Chan, and M. Medard, “High-reliability topological architectures for networks under stress,” IEEE J. Sel. Areas Commun., vol. 22, no. 9, pp. 1830–1845, Nov. 2004.
[31]
J. S. Baras and P. Hovareshti, “Efficient and robust communication topologies for distributed decision making in networked systems,” in Proc. 48h IEEE Conf. Decis. Control (CDC) Held Jointly With 28th Chin. Control Conf., Dec. 2009, pp. 3751–3756.
[32]
A. Ghosh, S. Boyd, and A. Saberi, “Minimizing effective resistance of a graph,” SIAM Rev., vol. 50, no. 1, pp. 37–66, Jan. 2008.
[33]
H. Li and Z. Zhang, “Kirchhoff index as a measure of edge centrality in weighted networks: Nearly linear time algorithms,” in Proc. 29th Annu. ACM-SIAM Symp. Discrete Algorithms. Philadelphia, PA, USA: SIAM, 2018, pp. 2377–2396.
[34]
C. Yang, J. Mao, X. Qian, and P. Wei, “Designing robust air transportation networks via minimizing total effective resistance,” IEEE Trans. Intell. Transp. Syst., vol. 20, no. 6, pp. 2353–2366, Jun. 2019.
[35]
Y. Lin, W. Chen, and Z. Zhang, “Assessing percolation threshold based on high-order non-backtracking matrices,” in Proc. 26th Int. Conf. World Wide Web, Apr. 2017, pp. 223–232.
[36]
Y. Lin, Z. Zhang, and P. Wong, “Non-backtracking centrality based random walk on networks,” Comput. J., vol. 62, no. 1, pp. 63–80, Jan. 2019.
[37]
Z. Zhang, Z. Zhang, and G. Chen, “Minimizing spectral radius of non-backtracking matrix by edge removal,” in Proc. 30th ACM Int. Conf. Inf. Knowl. Manage., Oct. 2021, pp. 2657–2667.
[38]
P. De Meo, F. Messina, D. Rosaci, G. M. L. Sarné, and A. V. Vasilakos, “Estimating graph robustness through the Randic index,” IEEE Trans. Cybern., vol. 48, no. 11, pp. 3232–3242, Nov. 2018.
[39]
B. Ning and X. Peng, “The Randić index and signless Laplacian spectral radius of graphs,” Discrete Math., vol. 342, no. 3, pp. 643–653, Mar. 2019.
[40]
R. K. Kincaid, S. J. Kunkler, M. D. Lamar, and D. J. Phillips, “Algorithms and complexity results for finding graphs with extremal Randić index,” Networks, vol. 67, no. 4, pp. 338–347, Jul. 2016.
[41]
W. Xu, Y. Sheng, Z. Zhang, H. Kan, and Z. Zhang, “Power-law graphs have minimal scaling of Kemeny constant for random walks,” in Proc. Web Conf., Apr. 2020, pp. 46–56.
[42]
Z. Zhang, W. Xu, and Z. Zhang, “Nearly linear time algorithm for mean hitting times of random walks on a graph,” in Proc. 13th Int. Conf. Web Search Data Mining, Jan. 2020, pp. 726–734.
[43]
H.-J. Li, L. Wang, Z. Bu, J. Cao, and Y. Shi, “Measuring the network vulnerability based on Markov criticality,” ACM Trans. Knowl. Discovery From Data, vol. 16, no. 2, pp. 1–24, Apr. 2022.
[44]
F.-S. P. Tsen, T.-Y. Sung, M.-Y. Lin, L.-H. Hsu, and W. Myrvold, “Finding the most vital edges with respect to the number of spanning trees,” IEEE Trans. Rel., vol. 43, no. 4, pp. 600–603, Dec. 1994.
[45]
V. V. B. Rao, “Most-vital edge of a graph with respect to spanning trees,” IEEE Trans. Rel., vol. 47, no. 1, pp. 6–7, Mar. 1998.
[46]
P. Van Mieghemet al., “Decreasing the spectral radius of a graph by link removals,” Phys. Rev. E, Stat. Phys. Plasmas Fluids Relat. Interdiscip. Top., vol. 84, no. 1, Jul. 2011, Art. no.
[47]
H. Tong, B. A. Prakash, T. Eliassi-Rad, M. Faloutsos, and C. Faloutsos, “Gelling, and melting, large graphs by edge manipulation,” in Proc. 21st ACM Int. Conf. Inf. Knowl. Manage., Oct. 2012, pp. 245–254.
[48]
S. Gaspers and K. Najeebullah, “Optimal surveillance of covert networks by minimizing inverse geodesic length,” in Proc. 33rd Int. Joint Conf. Artif. Intell., vol. 33, no. 1, 2019, pp. 533–540.
[49]
A. A. Schoone, H. L. Bodlaender, and J. Van Leeuwen, “Diameter increase caused by edge deletion,” J. Graph Theory, vol. 11, no. 3, pp. 409–427, 1987.
[50]
W. Liang, X. Shen, and Q. Hu, “Finding the most vital edge for graph minimization problems on meshes and hypercubes,” Int. J. Paral. Distrib. Syst. Netw., vol. 3, no. 4, pp. 197–205, 2000.
[51]
S. Medya, T. Ma, A. Silva, and A. Singh, “A game theoretic approach for k-core minimization,” in Proc. 19th Int. Conf. Auton. Agents MultiAgent Syst., 2020, pp. 1–3.
[52]
T. N. Dinh, Y. Xuan, M. T. Thai, P. M. Pardalos, and T. Znati, “On new approaches of assessing network vulnerability: Hardness and approximation,” IEEE/ACM Trans. Netw., vol. 20, no. 2, pp. 609–619, Apr. 2012.
[53]
Y. Shen, N. P. Nguyen, Y. Xuan, and M. T. Thai, “On the discovery of critical links and nodes for assessing network vulnerability,” IEEE/ACM Trans. Netw., vol. 21, no. 3, pp. 963–973, Jun. 2013.
[54]
A. Veremyev, O. A. Prokopyev, and E. L. Pasiliao, “Finding critical links for closeness centrality,” INFORMS J. Comput., vol. 31, no. 2, pp. 367–389, Apr. 2019.
[55]
S. Medya, Scalable Algorithms for Network Design. Santa Barbara, CA, USA: Univ. California, Santa Barbara, 2019.
[56]
C. Chen, R. Peng, L. Ying, and H. Tong, “Network connectivity optimization: Fundamental limits and effective algorithms,” in Proc. 24th ACM SIGKDD Int. Conf. Knowl. Discovery Data Mining, Jul. 2018, pp. 1167–1176.
[57]
C. Chen, “Connectivity in complex networks: Measures, inference and optimization,” in Proc. 11th ACM Int. Conf. Web Search Data Mining, New York, NY, USA, pp. 747–748.
[58]
A. Ghosh and S. Boyd, “Growing well-connected graphs,” in Proc. 45th IEEE Conf. Decis. Control, Dec. 2006, pp. 6605–6611.
[59]
H. Li, S. Patterson, Y. Yi, and Z. Zhang, “Maximizing the number of spanning trees in a connected graph,” IEEE Trans. Inf. Theory, vol. 66, no. 2, pp. 1248–1260, Feb. 2020.
[60]
S. Medya, A. Silva, A. Singh, P. Basu, and A. Swami, “Group centrality maximization via network design,” in Proc. SIAM Int. Conf. Data Mining, 2018, pp. 126–134.
[61]
C. Chen, H. Tong, B. A. Prakash, T. Eliassi-Rad, M. Faloutsos, and C. Faloutsos, “Eigen-optimization on large graphs by edge manipulation,” ACM Trans. Knowl. Discovery From Data, vol. 10, no. 4, pp. 1–30, Jul. 2016.
[62]
L. Chenet al., “HotSpots: Failure cascades on heterogeneous critical infrastructure networks,” in Proc. ACM Conf. Inf. Knowl. Manage., Nov. 2017, pp. 1599–1607.
[63]
C. Chen, R. Peng, L. Ying, and H. Tong, “Fast connectivity minimization on large-scale networks,” ACM Trans. Knowl. Discovery From Data, vol. 15, no. 3, pp. 1–25, Jun. 2021.
[64]
C. Chen, J. He, N. Bliss, and H. Tong, “Towards optimal connectivity on multi-layered networks,” IEEE Trans. Knowl. Data Eng., vol. 29, no. 10, pp. 2332–2346, Oct. 2017.
[65]
D. A. Spielman and N. Srivastava, “Graph sparsification by effective resistances,” SIAM J. Comput., vol. 40, no. 6, pp. 1913–1926, Jan. 2011.
[66]
H. Li and A. Schild, “Spectral subspace sparsification,” in Proc. IEEE 59th Annu. Symp. Found. Comput. Sci. (FOCS), Oct. 2018, pp. 385–396.
[67]
G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of approximations for maximizing submodular set functions - I,” Math. Program., vol. 14, no. 1, pp. 265–294, 1978.
[68]
A. A. Bian, J. M. Buhmann, A. Krause, and S. Tschiatschek, “Guarantees for greedy maximization of non-submodular functions with applications,” in Proc. 34th Int. Conf. Mach. Learn., 2017, pp. 498–507.
[69]
R. Merris, “Doubly stochastic graph matrices,” Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat., vol. 1, no. 8, pp. 64–71, 1997.
[70]
C. D. Meyer Jr., “Generalized inversion of modified matrices,” SIAM J. Appl. Math., vol. 24, no. 3, pp. 315–323, May 1973.
[71]
W. B. Johnson and J. Lindenstrauss, “Extensions of Lipschitz mappings into a Hilbert space,” Contemp. Math., vol. 26, pp. 189–206, Oct. 1984.
[72]
D. Achlioptas, “Database-friendly random projections,” in Proc. 20th ACM SIGMOD-SIGACT-SIGART Symp. Princ. Database Syst., May 2001, pp. 274–281.
[73]
D. A. Spielman and S.-H. Teng, “Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems,” SIAM J. Matrix Anal. Appl., vol. 35, no. 3, pp. 835–885, Jan. 2014.
[74]
J. Kunegis, “KONECT: The Koblenz network collection,” in Proc. 22nd Int. Conf. World Wide Web, May 2013, pp. 1343–1350.
[75]
J. Leskovec and R. Sosič, “SNAP: A general-purpose network analysis and graph-mining library,” ACM Trans. Intell. Syst. Technol., vol. 8, no. 1, pp. 1–20, Jan. 2017.
[76]
R. Kyng and S. Sachdeva, “Approximate Gaussian elimination for Laplacians–fast, sparse, and simple,” in Proc. IEEE 57th Annu. Symp. Found. Comput. Sci. (FOCS), Oct. 2016, pp. 573–582.
[77]
U. Brandes, “A faster algorithm for betweenness centrality,” J. Math. Sociol., vol. 25, no. 2, pp. 163–177, Dec. 2001.
[78]
Q. Bao, W. Xu, and Z. Zhang, “Benchmark for discriminating power of edge centrality metrics,” Comput. J., vol. 65, no. 12, pp. 3141–3155, Dec. 2022.
Recommendations
A comparative study of network robustness measures
The robustness is an important functionality of networks because it manifests the ability of networks to resist failures or attacks. Many robustness measures have been proposed from different aspects, which provide us various ways to evaluate the ...
On the robustness of centrality measures against link weight quantization in social networks
In social network analysis, individuals are represented as nodes in a graph, social ties among them are represented as links, and the strength of the social ties can be expressed as link weights. However, in social network analyses where the strength of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1556-6021 © 2023 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Press
Publication History
Published: 01 January 2023
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Nov 2024
Other Metrics
Citations
Cited By
View allView Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in