{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T11:45:33Z","timestamp":1753875933769,"version":"3.41.2"},"reference-count":46,"publisher":"Oxford University Press (OUP)","issue":"1","license":[{"start":{"date-parts":[[2021,2,1]],"date-time":"2021-02-01T00:00:00Z","timestamp":1612137600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"U.S. Department of Energy by Lawrence Livermore National Laboratory","award":["DE-AC52-07NA27344"],"award-info":[{"award-number":["DE-AC52-07NA27344"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021,4,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The algebraic connectivity, also known as the Fiedler value, is a spectral measure of network connectivity that can be increased through edge addition. We present an algorithm for producing many diverse ways to add a fixed number of edges to a network to achieve a near optimal Fiedler value. Previous Fielder value optimization algorithms (i.e. the greedy algorithm) output only one solution. Obtaining a single solution is rarely good enough for real-world network redesign problems, as practical constraints (political, physical or financial) may prevent implementation. Our algorithm takes a multi-start optimization approach, adding a random initial edge and then applies a greedy heuristic to improve the Fiedler value. The random choice moves us to a new region of the search space, enabling discovery of diverse solutions. Additionally, we present a Determinantal Point Process framework for quantifying diversity. We then apply a Markov chain Monte Carlo technique to sift through the large number of output solutions and locate a smaller, more manageable collection of highly diverse solutions that can be presented to network redesign engineers. We demonstrate the effectiveness of our algorithm on real-world graphs with varied structures.<\/jats:p>","DOI":"10.1093\/comnet\/cnab005","type":"journal-article","created":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T05:23:12Z","timestamp":1612848192000},"source":"Crossref","is-referenced-by-count":1,"title":["Finding diverse ways to improve algebraic connectivity through multi-start optimization"],"prefix":"10.1093","volume":"9","author":[{"given":"Sarah","family":"Mackay","sequence":"first","affiliation":[{"name":"Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, Livermore, CA 94550, USA"}]},{"given":"Colin","family":"Ponce","sequence":"additional","affiliation":[{"name":"Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, Livermore, CA 94550, USA"}]},{"given":"Sarah","family":"Osborn","sequence":"additional","affiliation":[{"name":"Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, Livermore, CA 94550, USA"}]},{"given":"Meghan","family":"McGarry","sequence":"additional","affiliation":[{"name":"Global Security Computing, Lawrence Livermore National Laboratory, Livermore, CA 94550, USA"}]}],"member":"286","published-online":{"date-parts":[[2021,4,25]]},"reference":[{"key":"2021070819455293900_B1","doi-asserted-by":"crossref","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","article-title":"Algebraic connectivity of graphs","volume":"23","author":"Fiedler,","year":"1973","journal-title":"Czech. Math. J."},{"key":"2021070819455293900_B2","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1016\/0095-8956(89)90029-4","article-title":"Isoperimetric numbers of graphs","volume":"47","author":"Mohar,","year":"1989","journal-title":"J. Combin. Theor. B"},{"key":"2021070819455293900_B3","doi-asserted-by":"crossref","first-page":"1074","DOI":"10.1109\/43.159993","article-title":"New spectral methods for ratio cut partitioning and clustering","volume":"11","author":"Hagen,","year":"1992","journal-title":"IEEE Trans. Comput. Aided Des. Integrated Circ. Syst."},{"key":"2021070819455293900_B4","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","article-title":"A tutorial on spectral clustering","volume":"17","author":"von Luxburg,","year":"2007","journal-title":"Stat. Comput."},{"key":"2021070819455293900_B5","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1109\/JPROC.2006.887293","article-title":"Consensus and cooperation in networked multi-agent systems","volume":"95","author":"Olfati-Saber,","year":"2007","journal-title":"Proc. IEEE"},{"key":"2021070819455293900_B6","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1137\/060678324","article-title":"Convergence speed in distributed consensus and averaging","volume":"48","author":"Olshevsky,","year":"2009","journal-title":"SIAM J. Contr. Optim."},{"key":"2021070819455293900_B7","doi-asserted-by":"crossref","first-page":"1750","DOI":"10.1109\/TSP.2014.2304432","article-title":"On the linear convergence of the ADMM in decentralized consensus optimization","volume":"62","author":"Shi,","year":"2014","journal-title":"IEEE Trans. Signal Process."},{"key":"2021070819455293900_B8","doi-asserted-by":"crossref","first-page":"6605","DOI":"10.1109\/CDC.2006.377282","article-title":"Growing well-connected graphs","volume-title":"Proceedings of the 45th IEEE Conference on Decision and Control","author":"Ghosh,","year":"2006"},{"key":"2021070819455293900_B9","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.endm.2016.10.004","article-title":"Experiments with two heuristic algorithms for the maximum algebraic connectivity augmentation problem","volume":"55","author":"Justel,","year":"2016","journal-title":"Electron. Notes Discrete Math."},{"key":"2021070819455293900_B10","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1109\/TAC.2009.2033763","article-title":"Bisection algorithm of increasing algebraic connectivity by adding an edge","volume":"55","author":"Kim,","year":"2010","journal-title":"IEEE Trans. Automat. Contr."},{"key":"2021070819455293900_B11","doi-asserted-by":"crossref","DOI":"10.4108\/ICST.BIONETICS2008.4691","article-title":"Algebraic connectivity optimization via link addition","volume-title":"Proceedings of the Third International Conference on Bio-Inspired Models of Network Information and Computing Systems (BIONETICS)","author":"Wang,","year":"2008"},{"key":"2021070819455293900_B12","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1016\/j.orl.2008.09.001","article-title":"Maximum algebraic connectivity augmentation is NP-hard","volume":"36","author":"Mosk-Aoyama,","year":"2008","journal-title":"Oper. Res. Lett."},{"key":"2021070819455293900_B13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2012.10.012","article-title":"Multi-start methods for combinatorial optimization","volume":"226","author":"Mart\u00ed,","year":"2013","journal-title":"Eur. J. Oper. Res."},{"key":"2021070819455293900_B14","first-page":"1193","article-title":"K-DPPs: fixed-size determinantal point processes","volume-title":"Proceedings of the 28th International Conference on Machine Learning (ICML)","author":"Kulesza,","year":"2011"},{"key":"2021070819455293900_B15","doi-asserted-by":"crossref","first-page":"2165","DOI":"10.1145\/3269206.3272018","article-title":"Practical diversified recommendations on YouTube with determinantal point processes","volume-title":"Proceedings of the 27th ACM International Conference on Information and Knowledge Management","author":"Wilhelm,","year":"2018"},{"key":"2021070819455293900_B16","first-page":"180","article-title":"DPPy: DPP sampling with Python","volume":"20","author":"Gautier,","year":"2019","journal-title":"J. Mach. Learn. Res."},{"key":"2021070819455293900_B17","first-page":"4195","article-title":"Fast mixing Markov chains for strongly Rayleigh measures, DPPs, and constrained sampling","volume-title":"Proceedings of the 30th International Conference on Neural Information Processing Systems (NIPS)","author":"Li,","year":"2016"},{"key":"2021070819455293900_B18","doi-asserted-by":"crossref","first-page":"41249","DOI":"10.1109\/ACCESS.2018.2857411","article-title":"Maximizing algebraic connectivity via minimum degree and maximum distance","volume":"6","author":"Li,","year":"2018","journal-title":"IEEE Access"},{"key":"2021070819455293900_B19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0163-9","volume-title":"Algebraic Graph Theory","author":"Godsil,","year":"2001"},{"key":"2021070819455293900_B20","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0024-3795(94)90486-3","article-title":"Laplacian matrices of graphs: a survey","volume":"197-198","author":"Merris,","year":"1994","journal-title":"Linear Algebra Appl."},{"key":"2021070819455293900_B21","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0166-218X(87)90052-7","article-title":"Transportation in graphs and the admittance spectrum","volume":"16","author":"Maas,","year":"1987","journal-title":"Discrete Appl. Math."},{"key":"2021070819455293900_B22","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1093\/comnet\/cny032","article-title":"Local rewiring algorithms to increase clustering and grow a small world","volume":"7","author":"Alstott,","year":"2019","journal-title":"J. Complex Netw."},{"key":"2021070819455293900_B23","doi-asserted-by":"crossref","first-page":"1395","DOI":"10.1007\/s10618-015-0447-5","article-title":"Optimizing network robustness by edge rewiring: a general framework","volume":"30","author":"Chan,","year":"2016","journal-title":"Data Min. Knowl. Disc."},{"key":"2021070819455293900_B24","doi-asserted-by":"crossref","first-page":"037105","DOI":"10.1063\/1.2975842","article-title":"Rewiring networks for synchronization","volume":"18","author":"Hagberg,","year":"2008","journal-title":"Chaos"},{"key":"2021070819455293900_B25","doi-asserted-by":"crossref","first-page":"5465","DOI":"10.1016\/j.amc.2012.11.002","article-title":"Optimizing algebraic connectivity by edge rewiring","volume":"219","author":"Sydney,","year":"2013","journal-title":"Appl. Math. Comput."},{"key":"2021070819455293900_B26","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/j.tre.2013.10.008","article-title":"Algebraic connectivity maximization of an air transportation network: the flight routes\u2019 addition\/deletion problem","volume":"61","author":"Wei,","year":"2014","journal-title":"Transport. Res. E Logist. Transport. Rev."},{"key":"2021070819455293900_B27","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1137\/S1064827500366124","article-title":"Toward the optimal preconditioned eigensolver: locally optimal block preconditioned conjugate gradient method","volume":"23","author":"Knyazev,","year":"2001","journal-title":"SIAM J. Sci. Comput."},{"key":"2021070819455293900_B28","doi-asserted-by":"crossref","first-page":"B499","DOI":"10.1137\/110843563","article-title":"Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver","volume":"34","author":"Livne,","year":"2012","journal-title":"SIAM J. Sci. Comput."},{"key":"2021070819455293900_B29","doi-asserted-by":"crossref","first-page":"835","DOI":"10.1137\/090771430","article-title":"Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems","volume":"35","author":"Spielman,","year":"2014","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"2021070819455293900_B30","doi-asserted-by":"crossref","first-page":"209","DOI":"10.4208\/jcm.1412-m2014-0041","article-title":"A cascadic multigrid algorithm for computing the Fiedler vector of graph Laplacians","volume":"33","author":"Urschel,","year":"2015","journal-title":"J. Comput. Math."},{"key":"2021070819455293900_B31","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1561\/2200000044","article-title":"Determinantal point processes for machine learning","volume":"5","author":"Kulesza,","year":"2012","journal-title":"Found. Trends Mach. Learn."},{"key":"2021070819455293900_B32","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1007\/978-94-017-1043-5_20","article-title":"Gram\u2019s inequality","volume-title":"Classical and New Inequalities in Analysis","author":"Mitrinovi\u0107,","year":"1993"},{"key":"2021070819455293900_B33","doi-asserted-by":"crossref","first-page":"4909","DOI":"10.1109\/TPWRS.2013.2251015","article-title":"Contingency ranking with respect to overloads in very large power systems taking into account uncertainty, preventive, and corrective actions","volume":"28","author":"Fliscounakis,","year":"2013","journal-title":"IEEE Trans. Power Syst."},{"key":"2021070819455293900_B34","article-title":"AC power flow data in MATPOWER and QCQP format: iTesla, RTE snapshots, and PEGASE","author":"Josz,","year":"2016","journal-title":"Preprint arXiv:1603.01533"},{"key":"2021070819455293900_B35","first-page":"4292","article-title":"The network data repository with interactive graph analytics and visualization","volume-title":"Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence","author":"Rossi,","year":"2015"},{"article-title":"SNAP datasets: Stanford large network dataset collection","year":"2014","author":"Leskovec,","key":"2021070819455293900_B36"},{"key":"2021070819455293900_B37","doi-asserted-by":"crossref","first-page":"018701","DOI":"10.1103\/PhysRevLett.94.018701","article-title":"Accuracy and scaling phenomena in internet mapping","volume":"94","author":"Clauset,","year":"2005","journal-title":"Phys. Rev. Lett."},{"key":"2021070819455293900_B38","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1038\/nature06830","article-title":"Hierarchical structure and the prediction of missing links in networks","volume":"453","author":"Clauset,","year":"2008","journal-title":"Nature"},{"key":"2021070819455293900_B39","first-page":"47","article-title":"The network completion problem: inferring missing nodes and edges in networks","volume-title":"Proceedings of the 2011 SIAM International Conference on Data Mining (SDM)","author":"Kim,","year":"2011"},{"key":"2021070819455293900_B40","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/j.socnet.2005.07.002","article-title":"Effects of missing data in social networks","volume":"28","author":"Kossinets,","year":"2006","journal-title":"Soc. Netw."},{"key":"2021070819455293900_B41","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/2776894","article-title":"ASCOS++: an asymmetric similarity measure for weighted networks to address the problem of SimRank","volume":"10","author":"Chen,","year":"2015","journal-title":"ACM Trans. Knowl. Discov. Data"},{"key":"2021070819455293900_B42","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1145\/2245276.2245305","article-title":"Discovering missing links in networks using vertex similarity measures","volume-title":"Proceedings of the 27th Annual ACM Symposium on Applied Computing","author":"Chen,","year":"2012"},{"key":"2021070819455293900_B43","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/BF02289026","article-title":"A new status index derived from sociometric analysis","volume":"18","author":"Katz,","year":"1953","journal-title":"Psychometrika"},{"key":"2021070819455293900_B44","first-page":"315","article-title":"Diffusion kernels on graphs and other discrete input spaces","volume-title":"Proceedings of the 19th International Conference on Machine Learning","author":"Kondor,","year":"2002"},{"key":"2021070819455293900_B45","doi-asserted-by":"crossref","first-page":"026120","DOI":"10.1103\/PhysRevE.73.026120","article-title":"Vertex similarity in networks","volume":"73","author":"Leicht,","year":"2006","journal-title":"Phys. Rev. E"},{"key":"2021070819455293900_B46","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1145\/1102351.1102380","article-title":"Optimal assignment kernels for attributed molecular graphs","volume-title":"Proceedings of the 22nd International Conference on Machine Learning","author":"Fr\u00f6hlich,","year":"2005"}],"container-title":["Journal of Complex Networks"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/9\/1\/cnab005\/37360785\/cnab005.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"http:\/\/academic.oup.com\/comnet\/article-pdf\/9\/1\/cnab005\/37360785\/cnab005.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,30]],"date-time":"2023-10-30T01:33:53Z","timestamp":1698629633000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comnet\/article\/doi\/10.1093\/comnet\/cnab005\/6251567"}},"subtitle":[],"editor":[{"given":"Ali","family":"Pinar","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2021,2,1]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,4,12]]}},"URL":"https:\/\/doi.org\/10.1093\/comnet\/cnab005","relation":{},"ISSN":["2051-1310","2051-1329"],"issn-type":[{"type":"print","value":"2051-1310"},{"type":"electronic","value":"2051-1329"}],"subject":[],"published-other":{"date-parts":[[2021,2,1]]},"published":{"date-parts":[[2021,2,1]]},"article-number":"cnab005"}}