{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T15:59:31Z","timestamp":1780761571731,"version":"3.54.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,10]]},"abstract":"<jats:p>\n            The\n            <jats:italic>k<\/jats:italic>\n            -plex model is a relaxation of the clique model by allowing every vertex to miss up to\n            <jats:italic>k<\/jats:italic>\n            neighbors. Designing exact and efficient algorithms for computing a maximum\n            <jats:italic>k<\/jats:italic>\n            -plex in a graph has been receiving increasing interest recently. However, the existing algorithms are still inefficient due to having major limitations. We in this paper design a new algorithm kPlexS for the maximum\n            <jats:italic>k<\/jats:italic>\n            -plex problem, with three novel contributions. Firstly, we propose a new framework for computing maximum\n            <jats:italic>k<\/jats:italic>\n            -plex over large sparse graphs, by iteratively extracting small dense subgraphs from it and then solving each of the extracted dense subgraphs by a branch-and-bound search. Secondly, we propose an efficient reduction algorithm CTCP to reduce the input graph size by exhaustively conducting vertex reduction and edge reduction. CTCP computes a smaller reduced graph and also has a lower time complexity than the existing techniques. Moreover, we iteratively invoke CTCP to reduce the input graph once a vertex has been processed and removed from it. Thirdly, we develop a branch-and-bound algorithm BBMatrix specifically targeting the dense subgraphs that are extracted from the input graph. BBMatrix represents its input graph by an adjacency matrix, and utilizes both first-order (i.e., individual vertices) and second-order information (i.e., pairs of vertices) for reduction and upper bounding. In addition, incremental techniques are proposed to efficiently apply the reduction and upper bounding during the recursion. Extensive empirical studies on large real graphs demonstrate that our algorithm kPlexS outperforms the state-of-the-art algorithms BnB, Maplex, and KpLeX.\n          <\/jats:p>","DOI":"10.14778\/3565816.3565817","type":"journal-article","created":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T00:35:16Z","timestamp":1669250116000},"page":"127-139","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Efficient maximum\n            <i>k<\/i>\n            -plex computation over large sparse graphs"],"prefix":"10.14778","volume":"16","author":[{"given":"Lijun","family":"Chang","sequence":"first","affiliation":[{"name":"The University of Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mouyi","family":"Xu","sequence":"additional","affiliation":[{"name":"The University of Sydney, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Darren","family":"Strash","sequence":"additional","affiliation":[{"name":"Hamilton College"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,11,23]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n.d.]. Full Version. https:\/\/lijunchang.github.io\/pdf\/2022-Maximum-kPlex.pdf.  [n.d.]. Full Version. https:\/\/lijunchang.github.io\/pdf\/2022-Maximum-kPlex.pdf."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1100.0851"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2746478"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(90)90057-C"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330986"},{"key":"e_1_2_1_8_1","series-title":"Springer Series in the Data Sciences","volume-title":"Cohesive Subgraph Computation over Large Sparse Graphs","author":"Chang Lijun","unstructured":"Lijun Chang and Lu Qin . 2018. Cohesive Subgraph Computation over Large Sparse Graphs . Springer Series in the Data Sciences . Lijun Chang and Lu Qin. 2018. Cohesive Subgraph Computation over Large Sparse Graphs. Springer Series in the Data Sciences."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098031"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220093"},{"key":"e_1_2_1_11_1","volume-title":"Listing All Maximal Cliques in Large Sparse Real-World Graphs. ACM Journal of Experimental Algorithmics 18","author":"Eppstein David","year":"2013","unstructured":"David Eppstein , Maarten L\u00f6ffler , and Darren Strash . 2013. Listing All Maximal Cliques in Large Sparse Real-World Graphs. ACM Journal of Experimental Algorithmics 18 ( 2013 ). David Eppstein, Maarten L\u00f6ffler, and Darren Strash. 2013. Listing All Maximal Cliques in Large Sparse Real-World Graphs. ACM Journal of Experimental Algorithmics 18 (2013)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/201"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2021\/233"},{"key":"e_1_2_1_14_1","first-page":"43","article-title":"Mapping Networks of Terrorist Cells","volume":"24","author":"Krebs V E","year":"2002","unstructured":"V E Krebs . 2002 . Mapping Networks of Terrorist Cells . International Network For Social Network Analysis 24 (2002), 43 -- 52 . Issue 3. V E Krebs. 2002. Mapping Networks of Terrorist Cells. International Network For Social Network Analysis 24 (2002), 43--52. Issue 3.","journal-title":"International Network For Social Network Analysis"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90060-4"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICTAI.2013.143"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2017.02.017"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137660"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-010-9338-2"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-011-9391-5"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00290-6"},{"key":"e_1_2_1_23_1","volume-title":"Pardalos and Jue Xue","author":"Panos","year":"1994","unstructured":"Panos M. Pardalos and Jue Xue . 1994 . The maximum clique problem. J. global Optimization 4, 3 (1994), 301--328. Panos M. Pardalos and Jue Xue. 1994. The maximum clique problem. J. global Optimization 4, 3 (1994), 301--328."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2014.986778"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.10.021"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/14100018X"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2015.07.013"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1978.9989883"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-53925-6_1"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11440-3_18"},{"key":"e_1_2_1_32_1","volume-title":"Truss Decomposition in Massive Networks. PVLDB 5, 9","author":"Wang Jia","year":"2012","unstructured":"Jia Wang and James Cheng . 2012. Truss Decomposition in Massive Networks. PVLDB 5, 9 ( 2012 ). Jia Wang and James Cheng. 2012. Truss Decomposition in Massive Networks. PVLDB 5, 9 (2012)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2017.03.003"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3512198"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77018-3_47"},{"key":"e_1_2_1_36_1","volume-title":"Proc. of ICDE'13","author":"Xiang Jingen","year":"2013","unstructured":"Jingen Xiang , Cong Guo , and Ashraf Aboulnaga . 2013 . Scalable maximum clique computation using mapreduce . In Proc. of ICDE'13 . 74--85. Jingen Xiang, Cong Guo, and Ashraf Aboulnaga. 2013. Scalable maximum clique computation using mapreduce. In Proc. of ICDE'13. 74--85."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v31i1.10655"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i14.17477"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3565816.3565817","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:29:18Z","timestamp":1672219758000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3565816.3565817"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["10.14778\/3565816.3565817"],"URL":"https:\/\/doi.org\/10.14778\/3565816.3565817","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,10]]},"assertion":[{"value":"2022-11-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}