{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T23:58:17Z","timestamp":1768780697562,"version":"3.49.0"},"reference-count":73,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T00:00:00Z","timestamp":1697068800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T00:00:00Z","timestamp":1697068800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["ME 3619\/4-1"],"award-info":[{"award-number":["ME 3619\/4-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["ME 3619\/4-1"],"award-info":[{"award-number":["ME 3619\/4-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["ME 3619\/4-1"],"award-info":[{"award-number":["ME 3619\/4-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"name":"TU Delft Safety & Security Institute","award":["ARCIN"],"award-info":[{"award-number":["ARCIN"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soc. Netw. Anal. Min."],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The total effective resistance, also called the Kirchhoff index, provides a robustness measure for a graph<jats:italic>G<\/jats:italic>. We consider two optimization problems of adding<jats:italic>k<\/jats:italic>new edges to<jats:italic>G<\/jats:italic>such that the resulting graph has minimal total effective resistance (i.e., is most robust)\u2014one where the new edges can be anywhere in the graph and one where the new edges need to be incident to a specified focus node. The total effective resistance and effective resistances between nodes can be computed using the pseudoinverse of the graph Laplacian. The pseudoinverse may be computed explicitly via pseudoinversion, yet this takes cubic time in practice and quadratic space. We instead exploit combinatorial and algebraic connections to speed up gain computations in an established generic greedy heuristic. Moreover, we leverage existing randomized techniques to boost the performance of our approaches by introducing a sub-sampling step. Our different graph- and matrix-based approaches are indeed significantly faster than the state-of-the-art greedy algorithm, while their quality remains reasonably high and is often quite close. Our experiments show that we can now process larger graphs for which the application of the state-of-the-art greedy approach was impractical before.<\/jats:p>","DOI":"10.1007\/s13278-023-01137-1","type":"journal-article","created":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T03:28:52Z","timestamp":1697081332000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Greedy optimization of resistance-based graph robustness with global and local edge insertions"],"prefix":"10.1007","volume":"13","author":[{"given":"Maria","family":"Predari","sequence":"first","affiliation":[]},{"given":"Lukas","family":"Berner","sequence":"additional","affiliation":[]},{"given":"Robert","family":"Kooij","sequence":"additional","affiliation":[]},{"given":"Henning","family":"Meyerhenke","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,12]]},"reference":[{"issue":"4","key":"1137_CR1","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1016\/S0022-0000(03)00025-4","volume":"66","author":"D Achlioptas","year":"2003","unstructured":"Achlioptas D (2003) Database-friendly random projections: Johnson-Lindenstrauss with binary coins. J Comput Syst Sci 66(4):671\u2013687","journal-title":"J Comput Syst Sci"},{"key":"1137_CR2","doi-asserted-by":"crossref","unstructured":"Angriman E, Becker R, D\u2019Angelo G, Gilbert H, van der Grinten A, Meyerhenke H (2021) Group-harmonic and group-closeness maximization - approximation and engineering. In: Proc of the Symp on Algorithm Engineering and Experiments, ALENEX, 2021. SIAM, pp 154\u2013168","DOI":"10.1137\/1.9781611976472.12"},{"key":"1137_CR3","unstructured":"Angriman E, Predari M, van der Grinten A, Meyerhenke H (2020) Approximation of the diagonal of a Laplacian\u2019s pseudoinverse for complex network analysis. In: ESA 2020, Italy, vol 173, pp 6:1\u20136:24"},{"issue":"7","key":"1137_CR4","doi-asserted-by":"publisher","first-page":"127","DOI":"10.3390\/a12070127","volume":"12","author":"E Angriman","year":"2019","unstructured":"Angriman E, van der Grinten A, von Looz M, Meyerhenke H, N\u00f6llenburg M, Predari M, Tzovas C (2019) Guidelines for experimental algorithmics: a case study in network analysis. Algorithms 12(7):127","journal-title":"Algorithms"},{"key":"1137_CR5","doi-asserted-by":"publisher","first-page":"985","DOI":"10.1007\/s10955-018-2124-8","volume":"173","author":"L Avena","year":"2018","unstructured":"Avena L, Castell F, Gaudilli\u00e8re A, M\u00e9lot C (2018) Random forests and networks analysis. J Stat Phys 173:985\u20131027","journal-title":"J Stat Phys"},{"issue":"2","key":"1137_CR6","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1080\/15326340600649052","volume":"22","author":"K Avrachenkov","year":"2006","unstructured":"Avrachenkov K, Litvak N (2006) The effect of new links on google pagerank. Stoch Model 22(2):319\u2013331","journal-title":"Stoch Model"},{"key":"1137_CR7","volume-title":"Network science","author":"A-L Barab\u00e1si","year":"2016","unstructured":"Barab\u00e1si A-L, P\u00f3sfai M (2016) Network science. Cambridge University Press, Cambridge"},{"key":"1137_CR8","doi-asserted-by":"crossref","unstructured":"Baras JS, Hovareshti P (2009) Efficient and robust communication topologies for distributed decision making in networked systems. In: Proceedings of the 48h IEEE conference on decision and control (CDC) held jointly with 2009 28th Chinese control conference, pp 3751\u20133756","DOI":"10.1109\/CDC.2009.5400448"},{"key":"1137_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3166071","volume":"23","author":"E Bergamini","year":"2018","unstructured":"Bergamini E, Crescenzi P, D\u2019angelo G, Meyerhenke H, Severini L, Velaj Y (2018) Improving the betweenness centrality of a node by adding links. ACM J Exp Algorithmics 23:1\u201332","journal-title":"ACM J Exp Algorithmics"},{"key":"1137_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern graph theory. Graduate texts in mathematics","author":"B Bollob\u00e1s","year":"1998","unstructured":"Bollob\u00e1s B (1998) Modern graph theory. Graduate texts in mathematics, corrected. Springer, Heidelberg","edition":"corrected"},{"key":"1137_CR11","doi-asserted-by":"crossref","unstructured":"Bozzo E, Franceschet M (2012) Effective and efficient approximations of the generalized inverse of the graph Laplacian matrix with an application to current-flow betweenness centrality. arXiv:1205.4894","DOI":"10.1080\/15427951.2012.715115"},{"key":"1137_CR12","doi-asserted-by":"crossref","unstructured":"Brandes U, Fleischer D (2005) Centrality measures based on current flow. In: STACS. Springer, Berlin, pp 533\u2013544","DOI":"10.1007\/978-3-540-31856-9_44"},{"key":"1137_CR13","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1016\/j.ress.2017.07.009","volume":"167","author":"O Cats","year":"2017","unstructured":"Cats O, Koppenol G-J, Warnier M (2017) Robustness assessment of link capacity reduction for complex networks: application for public transport systems. Reliab Eng Syst Saf 167:544\u2013553","journal-title":"Reliab Eng Syst Saf"},{"key":"1137_CR14","first-page":"117","volume-title":"Comparing destructive strategies for attacking networks","author":"H Cetinay","year":"2020","unstructured":"Cetinay H, Mas-Machuca C, Marzo JL, Kooij R, Van Mieghem P (2020) Comparing destructive strategies for attacking networks. Springer, Cham, pp 117\u2013140"},{"key":"1137_CR15","volume-title":"Complex graphs and networks","author":"F Chung","year":"2004","unstructured":"Chung F, Lu L (2004) Complex graphs and networks. American Mathematical Society, Providence"},{"issue":"114","key":"1137_CR16","first-page":"1","volume":"93","author":"GP Clemente","year":"2020","unstructured":"Clemente GP, Cornaro A (2020) Bounding robustness in complex networks under topological changes through majorization techniques. Eur Phys J B 93(114):1\u201312","journal-title":"Eur Phys J B"},{"issue":"1","key":"1137_CR17","first-page":"1","volume":"11","author":"P Crescenzi","year":"2016","unstructured":"Crescenzi P, D\u2019angelo G, Severini L, Velaj Y (2016) Greedily improving our own closeness centrality in a network. ACM Trans Knowl Discov Data (TKDD) 11(1):1\u201332","journal-title":"ACM Trans Knowl Discov Data (TKDD)"},{"issue":"1","key":"1137_CR18","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1002\/rsa.10073","volume":"22","author":"S Dasgupta","year":"2003","unstructured":"Dasgupta S, Gupta A (2003) An elementary proof of a theorem of Johnson and Lindenstrauss. Random Struct Algorithms 22(1):60\u201365","journal-title":"Random Struct Algorithms"},{"key":"1137_CR19","doi-asserted-by":"crossref","unstructured":"Demaine ED, Zadimoghaddam M (2010) Minimizing the diameter of a network using shortcut edges. In: Algorithm theory-SWAT 2010: 12th Scandinavian symposium and workshops on algorithm theory, Bergen, Norway, June 21\u201323, 2010. Proceedings 12. Springer, pp 420\u2013431","DOI":"10.1007\/978-3-642-13731-0_39"},{"issue":"10","key":"1137_CR20","doi-asserted-by":"publisher","first-page":"2491","DOI":"10.1016\/j.laa.2011.02.024","volume":"435","author":"W Ellens","year":"2011","unstructured":"Ellens W, Spieksma F, Van Mieghem P, Jamakovic A, Kooij R (2011) Effective graph resistance. Linear Algebra Appl 435(10):2491\u20132506","journal-title":"Linear Algebra Appl"},{"key":"1137_CR21","doi-asserted-by":"publisher","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","volume":"23","author":"M Fiedler","year":"1973","unstructured":"Fiedler M (1973) Algebraic connectivity of graphs. Czechoslov Math J 23:298\u2013305","journal-title":"Czechoslov Math J"},{"issue":"3","key":"1137_CR22","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1016\/0095-8956(88)90043-3","volume":"44","author":"P Frankl","year":"1988","unstructured":"Frankl P, Maehara H (1988) The Johnson-Lindenstrauss lemma and the sphericity of some graphs. J Combin Theory Ser B 44(3):355\u2013362","journal-title":"J Combin Theory Ser B"},{"key":"1137_CR23","doi-asserted-by":"crossref","unstructured":"Freitas S, Yang D, Kumar S, Tong H, Chau DH (2022) Graph vulnerability and robustness: a survey. IEEE Trans Knowl Data Eng","DOI":"10.1109\/TKDE.2022.3163672"},{"issue":"1","key":"1137_CR24","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1137\/050645452","volume":"50","author":"A Ghosh","year":"2008","unstructured":"Ghosh A, Boyd S, Saberi A (2008) Minimizing effective resistance of a graph. SIAM Rev 50(1):37\u201366","journal-title":"SIAM Rev"},{"key":"1137_CR25","unstructured":"Guennebaud G, Jacob B et al (2010) Eigen v3. http:\/\/eigen.tuxfamily.org"},{"key":"1137_CR26","doi-asserted-by":"publisher","first-page":"15","DOI":"10.2298\/BMAT0429015G","volume":"129","author":"I Gutman","year":"2004","unstructured":"Gutman I, Xiao W (2004) Generalized inverse of the Laplacian matrix and some applications. Bulletin Classe Des Sciences Mathematiques et Naturalles 129:15\u201323","journal-title":"Bulletin Classe Des Sciences Mathematiques et Naturalles"},{"key":"1137_CR27","unstructured":"Hassidim A, Singer Y (2017) Robust guarantees of stochastic greedy algorithms. In: Proc of the 34th intl conference on machine learning, vol\u00a070. PMLR, pp 1424\u20131432"},{"key":"1137_CR28","unstructured":"He Z (2020) Performance of complex networks. PhD thesis. Delft University of Technology"},{"issue":"3","key":"1137_CR29","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1145\/1089014.1089019","volume":"31","author":"V Hernandez","year":"2005","unstructured":"Hernandez V, Roman JE, Vidal V (2005) SLEPc: a scalable and flexible toolkit for the solution of eigenvalue problems. ACM Trans Math Softw 31(3):351\u2013362","journal-title":"ACM Trans Math Softw"},{"key":"1137_CR30","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1090\/conm\/026\/737400","volume":"26","author":"WB Johnson","year":"1984","unstructured":"Johnson WB (1984) Extensions of Lipschitz mappings into Hilbert space. Contemp Math 26:189\u2013206","journal-title":"Contemp Math"},{"issue":"7","key":"1137_CR31","doi-asserted-by":"publisher","DOI":"10.1088\/0256-307X\/27\/7\/078902","volume":"27","author":"W Jun","year":"2010","unstructured":"Jun W, Barahona M, Yue-Jin T, Hong-Zhong D (2010) Natural connectivity of complex networks. Chin Phys Lett 27(7):078902","journal-title":"Chin Phys Lett"},{"key":"1137_CR32","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.physa.2014.07.083","volume":"415","author":"Y Ko\u00e7","year":"2014","unstructured":"Ko\u00e7 Y, Warnier M, Van Mieghem P, Kooij RE, Brazier FM (2014) A topological investigation of phase transitions of cascading failures in power grids. Physica A 415:273\u2013284","journal-title":"Physica A"},{"key":"1137_CR33","volume-title":"The LDA+DMFT approach to strongly correlated materials","author":"E Koch","year":"2011","unstructured":"Koch E (2011) The Lanczos method. In: Pavarini E, Vollhardt D, Koch E, Lichtenstein A (eds) The LDA+DMFT approach to strongly correlated materials. Forschungszentrum J\u00fclich, J\u00fclich"},{"key":"1137_CR34","doi-asserted-by":"crossref","unstructured":"Kooij RE, Achterberg MA (2023) Minimizing the effective graph resistance by adding links is NP-hard. arXiv:2302.12628","DOI":"10.1016\/j.orl.2023.10.002"},{"key":"1137_CR35","unstructured":"Leskovec J, Krevl A (2014) Stanford large network dataset collection. SNAP Datasets. http:\/\/snap.stanford.edu\/data"},{"key":"1137_CR36","doi-asserted-by":"publisher","first-page":"41249","DOI":"10.1109\/ACCESS.2018.2857411","volume":"6","author":"G Li","year":"2018","unstructured":"Li G, Hao ZF, Huang H, Wei H (2018) Maximizing algebraic connectivity via minimum degree and maximum distance. IEEE Access 6:41249\u201341255","journal-title":"IEEE Access"},{"key":"1137_CR37","doi-asserted-by":"crossref","unstructured":"Livne O, Brandt A (2011) Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver. SIAM J Sci Comput 34","DOI":"10.1137\/110843563"},{"key":"1137_CR38","unstructured":"Lov\u00e1sz LM (1996) Random walks on graphs: a survey. Combinatorica 1\u201346"},{"key":"1137_CR39","unstructured":"Manghiuc B, Peng P, Sun H (2020) Augmenting the algebraic connectivity of graphs. In: 28th European Symp. on Algorithms, ESA, volume 173 of LIPIcs. Schloss Dagstuhl, pp 70:1\u201370:22"},{"key":"1137_CR40","doi-asserted-by":"crossref","unstructured":"Mavroforakis C, Garcia-Lebron R, Koutis I, Terzi E (2015) Spanning edge centrality: large-scale computation and applications. In: Proc. of the 24th Intl. Conference on World Wide Web. Intl. World Wide Web Conferences Steering Committee, pp 732\u2013742","DOI":"10.1145\/2736277.2741125"},{"key":"1137_CR41","doi-asserted-by":"publisher","first-page":"234","DOI":"10.1007\/BFb0006528","volume-title":"Optimization techniques","author":"M Minoux","year":"1978","unstructured":"Minoux M (1978) Accelerated greedy algorithms for maximizing submodular set functions. In: Stoer J (ed) Optimization techniques. Springer, Berlin, pp 234\u2013243"},{"issue":"3","key":"1137_CR42","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1002\/net.3230190305","volume":"19","author":"M Minoux","year":"1989","unstructured":"Minoux M (1989) Networks synthesis and optimum network design problems: models, solution methods and applications. Networks 19(3):313\u2013360","journal-title":"Networks"},{"key":"1137_CR43","doi-asserted-by":"crossref","unstructured":"Mirzasoleiman B, Badanidiyuru A, Karbasi A, Vondr\u00e1k J, Krause A (2015) Lazier than lazy greedy. In: Proceedings of the 29th AAAI conference on artificial intelligence, AAAI\u201915. AAAI Press, pp 1812\u20131818","DOI":"10.1609\/aaai.v29i1.9486"},{"issue":"6","key":"1137_CR44","doi-asserted-by":"publisher","first-page":"677","DOI":"10.1016\/j.orl.2008.09.001","volume":"36","author":"D Mosk-Aoyama","year":"2008","unstructured":"Mosk-Aoyama D (2008) Maximum algebraic connectivity augmentation is NP-hard. Oper Res Lett 36(6):677\u2013679","journal-title":"Oper Res Lett"},{"key":"1137_CR45","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198805090.001.0001","volume-title":"Networks","author":"M Newman","year":"2018","unstructured":"Newman M (2018) Networks, 2nd edn. Oxford University Press, Oxford","edition":"2"},{"issue":"1","key":"1137_CR46","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1109\/JPROC.2006.887293","volume":"95","author":"R Olfati-Saber","year":"2007","unstructured":"Olfati-Saber R, Fax JA, Murray RM (2007) Consensus and cooperation in networked multi-agent systems. Proc IEEE 95(1):215\u2013233","journal-title":"Proc IEEE"},{"key":"1137_CR47","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.tcs.2013.08.003","volume":"518","author":"M Olsen","year":"2014","unstructured":"Olsen M, Viglas A (2014) On the approximability of the link building problem. Theoret Comput Sci 518:96\u2013116","journal-title":"Theoret Comput Sci"},{"key":"1137_CR48","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/0024-3795(80)90167-6","volume":"34","author":"C Paige","year":"1980","unstructured":"Paige C (1980) Accuracy and effectiveness of the Lanczos algorithm for the symmetric eigenproblem. Linear Algebra Appl 34:235\u2013258","journal-title":"Linear Algebra Appl"},{"key":"1137_CR49","doi-asserted-by":"publisher","DOI":"10.1145\/2757281","author":"M Papagelis","year":"2015","unstructured":"Papagelis M (2015) Refining social graph connectivity via shortcut edge addition. ACM Trans Knowl Discov Data. https:\/\/doi.org\/10.1145\/2757281","journal-title":"ACM Trans Knowl Discov Data"},{"key":"1137_CR50","unstructured":"Perera S, Bell MGH, Bliemer MCJ (2015) Modelling supply chains as complex networks for investigating resilience: an improved methodological framework"},{"key":"1137_CR51","doi-asserted-by":"crossref","unstructured":"Perumal S, Basu P, Guan Z (2013) Minimizing eccentricity in composite networks via constrained edge additions. In: MILCOM 2013-2013 IEEE military communications conference. IEEE, pp 1894\u20131899","DOI":"10.1109\/MILCOM.2013.319"},{"key":"1137_CR52","doi-asserted-by":"crossref","unstructured":"Pizzuti C, Socievole A (2018) A genetic algorithm for enhancing the robustness of complex networks through link protection. In: International conference on complex networks and their applications. Springer, pp 807\u2013819","DOI":"10.1007\/978-3-030-05411-3_64"},{"key":"1137_CR53","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/978-3-031-21131-7_33","volume-title":"Complex networks and their applications XI","author":"C Pizzuti","year":"2023","unstructured":"Pizzuti C, Socievole A (2023) Incremental computation of effective graph resistance for improving robustness of complex networks: a comparative study. In: Cherifi H, Mantegna RN, Rocha LM, Cherifi C, Micciche S (eds) Complex networks and their applications XI. Springer, Cham, pp 419\u2013431"},{"key":"1137_CR54","doi-asserted-by":"crossref","unstructured":"Predari M, Kooij R, Meyerhenke H (2022) Faster greedy optimization of resistance-based graph robustness. In: 2022 IEEE\/ACM international conference on advances in social networks analysis and mining (ASONAM), Los Alamitos, CA, USA, Nov 2022. IEEE Computer Society, pp 1\u20138","DOI":"10.1109\/ASONAM55673.2022.10068613"},{"key":"1137_CR55","first-page":"729","volume-title":"Combinatorial optimization","author":"G Ranjan","year":"2014","unstructured":"Ranjan G, Zhang Z, Boley D (2014) Incremental computation of pseudo-inverse of Laplacian and applications\u20148th international conference, COCOA 2014, Wailea, Maui, HI, USA, December 19\u201321, 2014, Proceedings. Lecture notes in computer science. In: Zhang Z, Wu L, Xu W, Du D (eds) Combinatorial optimization, vol 8881. Springer, pp 729\u2013749"},{"key":"1137_CR56","doi-asserted-by":"crossref","unstructured":"Rossi RA, Ahmed NK (2015) The network data repository with interactive graph analytics and visualization. In: Proceedings of the 29th AAAI conference on artificial intelligence, AAAI\u201915. AAAI Press, pp 4292\u20134293","DOI":"10.1609\/aaai.v29i1.9277"},{"issue":"2","key":"1137_CR57","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/s10922-016-9391-y","volume":"25","author":"DF Rueda","year":"2017","unstructured":"Rueda DF, Calle E, Marzo JL (2017) Robustness comparison of 15 real telecommunication networks: structural and centrality measurements. J Netw Syst Manag 25(2):269\u2013289","journal-title":"J Netw Syst Manag"},{"issue":"10","key":"1137_CR58","doi-asserted-by":"publisher","first-page":"3838","DOI":"10.1073\/pnas.1009440108","volume":"108","author":"CM Schneider","year":"2011","unstructured":"Schneider CM, Moreira AA, Andrade JS, Havlin S, Herrmann HJ (2011) Mitigation of malicious attacks on networks. Proc Natl Acad Sci 108(10):3838\u20133841","journal-title":"Proc Natl Acad Sci"},{"key":"1137_CR59","doi-asserted-by":"crossref","unstructured":"Shan L, Yi Y, Zhang Z (2018) Improving information centrality of a node in complex networks by adding edges. In: Proceedings of the 27th international joint conference on artificial intelligence, IJCAI-18, pp 3535\u20133541. International joint conferences on artificial intelligence organization, 7. https:\/\/www.ijcai.org\/proceedings\/2018\/0491.pdf","DOI":"10.24963\/ijcai.2018\/491"},{"issue":"1","key":"1137_CR60","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1214\/aoms\/1177729893","volume":"21","author":"J Sherman","year":"1950","unstructured":"Sherman J, Morrison WJ (1950) Adjustment of an inverse matrix corresponding to a change in one element of a given matrix. Ann Math Stat 21(1):124\u2013127","journal-title":"Ann Math Stat"},{"key":"1137_CR61","doi-asserted-by":"crossref","unstructured":"Spielman D (2012) Spectral graph theory. In: Combinatorial scientific computing, vol 18. CRC Press, Boca Raton, p 18","DOI":"10.1201\/b11644-19"},{"issue":"4","key":"1137_CR62","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1017\/nws.2016.20","volume":"4","author":"CL Staudt","year":"2016","unstructured":"Staudt CL, Sazonovs A, Meyerhenke H (2016) NetworKit: a tool suite for large-scale complex network analysis. Netw Sci 4(4):508\u2013530","journal-title":"Netw Sci"},{"key":"1137_CR63","doi-asserted-by":"crossref","unstructured":"Summers T, Shames I, Lygeros J, D\u00f6rfler F (2015) Topology design for optimal network coherence. In: 2015 European control conference (ECC). IEEE, pp 575\u2013580","DOI":"10.1109\/ECC.2015.7330605"},{"key":"1137_CR64","unstructured":"Summers T, Shames I, Lygeros J, Dorfler F (2017) Correction to \u201cTopology design for optimal network coherence\u201d. https:\/\/personal.utdallas.edu\/~ths150130\/papers\/ECC_Correction.pdf"},{"key":"1137_CR65","doi-asserted-by":"crossref","unstructured":"Summers TH, Kamgarpour M (2019) Performance guarantees for greedy maximization of non-submodular controllability metrics. In : 17th European Control Conf., ECC. IEEE, pp 2796\u20132801","DOI":"10.23919\/ECC.2019.8795800"},{"key":"1137_CR66","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.96.032311","volume":"96","author":"P Van Mieghem","year":"2017","unstructured":"Van Mieghem P, Devriendt K, Cetinay H (2017) Pseudoinverse of the Laplacian and best spreader node in a network. Phys Rev E 96:032311","journal-title":"Phys Rev E"},{"key":"1137_CR67","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.016101","volume":"84","author":"P Van Mieghem","year":"2011","unstructured":"Van Mieghem P, Stevanovi\u0107 D, Kuipers F, Li C, van de Bovenkamp R, Liu D, Wang H (2011) Decreasing the spectral radius of a graph by link removals. Phys Rev E 84:016101","journal-title":"Phys Rev E"},{"key":"1137_CR68","doi-asserted-by":"crossref","unstructured":"Wang H, Van Mieghem P (2008) Algebraic connectivity optimization via link addition. In: Proceedings of the 3rd international conference on bio-inspired models of network, information and computing systems, BIONETICS\u201908, Brussels, BEL, 2008. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering). https:\/\/www.nas.ewi.tudelft.nl\/people\/Huijuan\/Huijuan_paper\/Bionetics2008_AlgebraicConnectivity.pdf","DOI":"10.4108\/ICST.BIONETICS2008.4691"},{"key":"1137_CR69","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1140\/epjb\/e2014-50276-0","volume":"87","author":"X Wang","year":"2014","unstructured":"Wang X, Pournaras E, Kooij RE, Mieghem PV (2014) Improving robustness of complex networks via the effective graph resistance. Eur Phys J B 87:1\u201312","journal-title":"Eur Phys J B"},{"key":"1137_CR70","unstructured":"Wei Y, Li R-h, Yang W (2021) Biharmonic distance of graphs. arXiv preprint arXiv:2110.02656"},{"key":"1137_CR71","doi-asserted-by":"crossref","unstructured":"Wilson DB (1996) Generating random spanning trees more quickly than the cover time. In Proc of the 28th annual ACM symposium on theory of computing, STOC\u201996. Association for Computing Machinery, pp 296\u2013303","DOI":"10.1145\/237814.237880"},{"key":"1137_CR72","doi-asserted-by":"crossref","unstructured":"Yazdani A, Jeffrey P (2011) Complex network analysis of water distribution systems. Chaos (Woodbury N.Y), 21:016111","DOI":"10.1063\/1.3540339"},{"key":"1137_CR73","doi-asserted-by":"crossref","unstructured":"Yi Y, Shan L, Li H, Zhang Z (2018) Biharmonic distance related centrality for edges in weighted networks. In: IJCAI, pp 3620\u20133626","DOI":"10.24963\/ijcai.2018\/503"}],"container-title":["Social Network Analysis and Mining"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-023-01137-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13278-023-01137-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-023-01137-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,30]],"date-time":"2024-10-30T17:48:03Z","timestamp":1730310483000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13278-023-01137-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,12]]},"references-count":73,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["1137"],"URL":"https:\/\/doi.org\/10.1007\/s13278-023-01137-1","relation":{},"ISSN":["1869-5469"],"issn-type":[{"value":"1869-5469","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,12]]},"assertion":[{"value":"6 April 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 May 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 September 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 October 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Competing interests The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"130"}}