{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T09:26:33Z","timestamp":1769073993980,"version":"3.49.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T00:00:00Z","timestamp":1620000000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["1947135 and 2003924"],"award-info":[{"award-number":["1947135 and 2003924"]}]},{"name":"NSF Program on Fairness in AI in collaboration with Amazon","award":["1939725"],"award-info":[{"award-number":["1939725"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            The connectivity of networks has been widely studied in many high-impact applications, ranging from immunization, critical infrastructure analysis, social network mining, to bioinformatic system studies. Regardless of the end application domains, connectivity minimization has always been a fundamental task to effectively control the functioning of the underlying system. The combinatorial nature of the connectivity minimization problem imposes an exponential computational complexity to find the optimal solution, which is intractable in large systems. To tackle the computational barrier, greedy algorithm is extensively used to ensure a near-optimal solution by exploiting the diminishing returns property of the problem. Despite the empirical success, the theoretical and algorithmic challenges of the problems still remain wide open. On the theoretical side, the intrinsic hardness and the approximability of the general connectivity minimization problem are still unknown except for a few special cases. On the algorithmic side, existing algorithms are hard to balance between the optimization quality and computational efficiency. In this article, we address the two challenges by (1) proving that the general connectivity minimization problem is NP-hard and\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            is the best approximation ratio for any polynomial algorithms, and (2) proposing the algorithm\n            <jats:sc>CONTAIN<\/jats:sc>\n            and its variant\n            <jats:sc>CONTAIN<\/jats:sc>\n            + that can well balance optimization effectiveness and computational efficiency for eigen-function based connectivity minimization problems in large networks.\n          <\/jats:p>","DOI":"10.1145\/3442342","type":"journal-article","created":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T22:07:27Z","timestamp":1620079647000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Fast Connectivity Minimization on Large-Scale Networks"],"prefix":"10.1145","volume":"15","author":[{"given":"Chen","family":"Chen","sequence":"first","affiliation":[{"name":"Google Inc., Mountain View, California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ruiyue","family":"Peng","sequence":"additional","affiliation":[{"name":"Translational MRI, LLC., Los Angeles, California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lei","family":"Ying","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, Michigan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hanghang","family":"Tong","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, Illinois"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,5,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Internet: Diameter of the world-wide web. Nature 401, 6749","author":"Albert R\u00e9ka","year":"1999","unstructured":"R\u00e9ka Albert , Hawoong Jeong , and Albert-L\u00e1szl\u00f3 Barab\u00e1si . 1999 . Internet: Diameter of the world-wide web. Nature 401, 6749 (1999), 130. R\u00e9ka Albert, Hawoong Jeong, and Albert-L\u00e1szl\u00f3 Barab\u00e1si. 1999. Internet: Diameter of the world-wide web. Nature 401, 6749 (1999), 130."},{"key":"e_1_2_1_2_1","volume-title":"Error and attack tolerance of complex networks. Nature 406, 6794","author":"Albert R\u00e9ka","year":"2000","unstructured":"R\u00e9ka Albert , Hawoong Jeong , and Albert-L\u00e1szl\u00f3 Barab\u00e1si . 2000. Error and attack tolerance of complex networks. Nature 406, 6794 ( 2000 ), 378\u2013382. R\u00e9ka Albert, Hawoong Jeong, and Albert-L\u00e1szl\u00f3 Barab\u00e1si. 2000. Error and attack tolerance of complex networks. Nature 406, 6794 (2000), 378\u2013382."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1800683115"},{"key":"e_1_2_1_4_1","volume-title":"The Evolution of Random Graphs\u2013the Giant Component (2 ed.)","author":"Bollob\u00e1s B\u00e9la","unstructured":"B\u00e9la Bollob\u00e1s . 2001. The Evolution of Random Graphs\u2013the Giant Component (2 ed.) . Cambridge University Press , 130\u2013159. DOI:https:\/\/doi.org\/10.1017\/CBO9780511814068.008 10.1017\/CBO9780511814068.008 B\u00e9la Bollob\u00e1s. 2001. The Evolution of Random Graphs\u2013the Giant Component (2 ed.). Cambridge University Press, 130\u2013159. DOI:https:\/\/doi.org\/10.1017\/CBO9780511814068.008"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1284680.1284681"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973440.37"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974010.2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.104"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220019"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/sam.11310"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903148"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2465378"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132867"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835934"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557047"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623671"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.91.247901"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gku935"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2011.2170849"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/316194.316229"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(78)90021-7"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62234"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-017-0533-y"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1088\/0256-307X\/27\/7\/078902"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00031-9"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1051910"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1038\/nrmicro2333"},{"key":"e_1_2_1_29_1","volume-title":"Kovacs and Albert-Laszlo Barabasi","author":"Istvan","year":"2015","unstructured":"Istvan A. Kovacs and Albert-Laszlo Barabasi . 2015 . Network science: Destruction perfected. Nature 524, 7563 (2015), 38\u201339. Istvan A. Kovacs and Albert-Laszlo Barabasi. 2015. Network science: Destruction perfected. Nature 524, 7563 (2015), 38\u201339."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974010.78"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1232722.1232727"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281239"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132919"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974010.32"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-014-0800-9"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/BIBM.2017.8217995"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556612"},{"key":"e_1_2_1_40_1","volume-title":"Network motifs: Simple building blocks of complex networks. Science 298, 5594","author":"Milo Ron","year":"2002","unstructured":"Ron Milo , Shai Shen-Orr , Shalev Itzkovitz , Nadav Kashtan , Dmitri Chklovskii , and Uri Alon . 2002. Network motifs: Simple building blocks of complex networks. Science 298, 5594 ( 2002 ), 824\u2013827. Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. Network motifs: Simple building blocks of complex networks. Science 298, 5594 (2002), 824\u2013827."},{"key":"e_1_2_1_41_1","volume-title":"Makse","author":"Morone Flaviano","year":"2015","unstructured":"Flaviano Morone and Hern\u00e1n A . Makse . 2015 . Influence maximization in complex networks through optimal percolation. Nature 524, 7563 (2015), 65. Flaviano Morone and Hern\u00e1n A. Makse. 2015. Influence maximization in complex networks through optimal percolation. Nature 524, 7563 (2015), 65."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_43_1","first-page":"1","article-title":"The mathematics of networks","volume":"2","author":"Newman Mark E. J.","year":"2008","unstructured":"Mark E. J. Newman . 2008 . The mathematics of networks . The New Palgrave Encyclopedia of Economics 2 , 2008 (2008), 1 \u2013 12 . Mark E. J. Newman. 2008. The mathematics of networks. The New Palgrave Encyclopedia of Economics 2, 2008 (2008), 1\u201312.","journal-title":"The New Palgrave Encyclopedia of Economics"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0520-y"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2012.2215882"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/524279"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Daniel Spielman. 2012. Spectral graph theory. In Combinatorial Scientific Computing. Number 18. Citeseer.  Daniel Spielman. 2012. Spectral graph theory. In Combinatorial Scientific Computing. Number 18. Citeseer.","DOI":"10.1201\/b11644-19"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1402008"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557109"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.72"},{"key":"e_1_2_1_52_1","volume-title":"Social Network Analysis: Methods and Applications","author":"Wasserman Stanley","unstructured":"Stanley Wasserman and Katherine Faust . 1994. Social Network Analysis: Methods and Applications . Vol. 8 . Cambridge University Press . Stanley Wasserman and Katherine Faust. 1994. Social Network Analysis: Methods and Applications. Vol. 8. Cambridge University Press."},{"key":"e_1_2_1_53_1","first-page":"44","article-title":"The local closure coefficient: A new perspective on network clustering","volume":"26","author":"Yin Hao","year":"2019","unstructured":"Hao Yin , Austin R. Benson , and Jure Leskovec . 2019 . The local closure coefficient: A new perspective on network clustering . Networks 26 , 41 (2019), 44 . Hao Yin, Austin R. Benson, and Jure Leskovec. 2019. The local closure coefficient: A new perspective on network clustering. Networks 26, 41 (2019), 44.","journal-title":"Networks"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098069"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442342","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3442342","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3442342","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:15Z","timestamp":1750193295000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442342"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,3]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3442342"],"URL":"https:\/\/doi.org\/10.1145\/3442342","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,3]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}