{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:49:44Z","timestamp":1773481784710,"version":"3.50.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,5,6]],"date-time":"2023-05-06T00:00:00Z","timestamp":1683331200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,5,6]],"date-time":"2023-05-06T00:00:00Z","timestamp":1683331200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["FT180100256"],"award-info":[{"award-number":["FT180100256"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000923","name":"Australian Research Council","doi-asserted-by":"publisher","award":["DP220103731"],"award-info":[{"award-number":["DP220103731"]}],"id":[{"id":"10.13039\/501100000923","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2024,1]]},"abstract":"Abstract<\/jats:title>The problem of efficiently computing all $$k$$<\/jats:tex-math>\n k<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-edge-connected components ($$k$$<\/jats:tex-math>\n k<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-ECCs) of a graph G<\/jats:italic> for a user-given<\/jats:italic>k<\/jats:italic> has been extensively studied recently in view of its importance in many applications. The $$k$$<\/jats:tex-math>\n k<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-ECCs of G<\/jats:italic> for all possible values of<\/jats:italic>k<\/jats:italic> form a hierarchical structure; that is, any two different $$k$$<\/jats:tex-math>\n k<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-ECCs for the same k<\/jats:italic> value are disjoint and any $$k$$<\/jats:tex-math>\n k<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-ECC is contained in a unique $$(k\\text {-}1)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n k<\/mml:mi>\n -<\/mml:mtext>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-ECC. In this paper, we study the problem of efficiently constructing the hierarchy tree of the $$k$$<\/jats:tex-math>\n k<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-ECCs for all possible k<\/jats:italic> values, for a graph G<\/jats:italic>. The existing approaches $$\\textsf{TD}$$<\/jats:tex-math>\n TD<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$\\textsf{BU}$$<\/jats:tex-math>\n BU<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> construct the hierarchy tree in either a top-down manner or a bottom-up manner, with both having the time complexity of $${{\\mathcal {O}}}\\big (\\delta (G)\\times {\\mathsf {T_{KECC}}} (G)\\big )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \u03b4<\/mml:mi>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u00d7<\/mml:mo>\n \n T<\/mml:mi>\n KECC<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where $$\\delta (G)$$<\/jats:tex-math>\n \n \u03b4<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the degeneracy of G<\/jats:italic> and $${\\mathsf {T_{KECC}}} (G)$$<\/jats:tex-math>\n \n \n T<\/mml:mi>\n KECC<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the time complexity of computing all $$k$$<\/jats:tex-math>\n k<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-ECCs of G<\/jats:italic> for a specific k<\/jats:italic> value. Here, the degeneracy of G<\/jats:italic> is defined as the maximum value among the minimum vertex degrees of all subgraphs of G<\/jats:italic> and is at most $$\\sqrt{m}$$<\/jats:tex-math>\n \n m<\/mml:mi>\n <\/mml:msqrt>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> where m<\/jats:italic> is the number of edges in G<\/jats:italic>. To improve the time complexity, we propose a divide-and-conquer approach $$\\textsf{DC}$$<\/jats:tex-math>\n DC<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> running in $${{\\mathcal {O}}}\\big ( (\\log \\delta (G))\\times {\\mathsf {T_{KECC}}} (G)\\big )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \n (<\/mml:mo>\n log<\/mml:mo>\n \u03b4<\/mml:mi>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n \u00d7<\/mml:mo>\n \n T<\/mml:mi>\n KECC<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time; this time complexity is optimal up to a logarithmic factor. However, a straightforward implementation of $$\\textsf{DC}$$<\/jats:tex-math>\n DC<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> would take $${{\\mathcal {O}}}( (m + n) \\log \\delta (G))$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n (<\/mml:mo>\n m<\/mml:mi>\n +<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n log<\/mml:mo>\n \u03b4<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> main-memory space, which could easily run out-of-memory when processing large graphs; here, n<\/jats:italic> is the number of vertices in G<\/jats:italic>. To reduce the main-memory footprint of our algorithm, we propose adjacency array-based techniques to optimize the space complexity to $$2m+{{\\mathcal {O}}}(n\\log \\delta (G))$$<\/jats:tex-math>\n \n 2<\/mml:mn>\n m<\/mml:mi>\n +<\/mml:mo>\n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n log<\/mml:mo>\n \u03b4<\/mml:mi>\n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and denote our resulting algorithm by $$\\mathsf {DC\\text {-}AA}$$<\/jats:tex-math>\n \n DC<\/mml:mi>\n -<\/mml:mtext>\n AA<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. As a by-product of $$\\mathsf {DC\\text {-}AA}$$<\/jats:tex-math>\n \n DC<\/mml:mi>\n -<\/mml:mtext>\n AA<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we also improve the space complexity of the state-of-the-art algorithm for computing all $$k$$<\/jats:tex-math>\n k<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-ECCs for a specific k<\/jats:italic> to $$2m + {{\\mathcal {O}}}(n)$$<\/jats:tex-math>\n \n 2<\/mml:mn>\n m<\/mml:mi>\n +<\/mml:mo>\n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, by using the same technique as used in $$\\mathsf {DC\\text {-}AA}$$<\/jats:tex-math>\n \n DC<\/mml:mi>\n -<\/mml:mtext>\n AA<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Finally, we propose optimization techniques to improve the practical efficiency of the existing approach $$\\textsf{BU}$$<\/jats:tex-math>\n BU<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and denote the space-optimized version of it as $$\\mathsf {BU^*\\text {-}AA}$$<\/jats:tex-math>\n \n \n BU<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msup>\n -<\/mml:mtext>\n AA<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> which runs in $${{\\mathcal {O}}}\\big (\\delta (G)\\times {\\mathsf {T_{KECC}}} (G)\\big )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n \n (<\/mml:mo>\n <\/mml:mrow>\n \u03b4<\/mml:mi>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u00d7<\/mml:mo>\n \n T<\/mml:mi>\n KECC<\/mml:mi>\n <\/mml:msub>\n \n (<\/mml:mo>\n G<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> time and $$2m+{{\\mathcal {O}}}(n)$$<\/jats:tex-math>\n \n 2<\/mml:mn>\n m<\/mml:mi>\n +<\/mml:mo>\n O<\/mml:mi>\n (<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> space. Extensive experiments on large real graphs and synthetic graphs demonstrate that our algorithms $$\\mathsf {DC\\text {-}AA}$$<\/jats:tex-math>\n \n DC<\/mml:mi>\n -<\/mml:mtext>\n AA<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$\\mathsf {BU^*\\text {-}AA}$$<\/jats:tex-math>\n \n \n BU<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msup>\n -<\/mml:mtext>\n AA<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> outperform the state-of-the-art approaches by up to 28 times in terms of running time and by up to 8 times in terms of main memory usage. In particular, our approach $$\\mathsf {BU^*\\text {-}AA}$$<\/jats:tex-math>\n \n \n BU<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msup>\n -<\/mml:mtext>\n AA<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> processes the Twitter graph, which has more than 1 billion undirected edges, in 29\u00a0min with 13.5\u00a0GB memory, while the state-of-the-art approaches take more than 13\u00a0h after our space optimization; note that the state-of-the-art approaches run out-of-memory if without our space optimization. Our empirical study also shows that $$\\mathsf {BU^*\\text {-}AA}$$<\/jats:tex-math>\n \n \n BU<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msup>\n -<\/mml:mtext>\n AA<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, despite having a higher time complexity, performs better than $$\\mathsf {DC\\text {-}AA}$$<\/jats:tex-math>\n \n DC<\/mml:mi>\n -<\/mml:mtext>\n AA<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in practice. We also remark that $$\\mathsf {BU^*\\text {-}AA}$$<\/jats:tex-math>\n \n \n BU<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msup>\n -<\/mml:mtext>\n AA<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is much simpler and easier to implement than $$\\mathsf {DC\\text {-}AA}$$<\/jats:tex-math>\n \n DC<\/mml:mi>\n -<\/mml:mtext>\n AA<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00778-023-00797-x","type":"journal-article","created":{"date-parts":[[2023,5,6]],"date-time":"2023-05-06T06:01:47Z","timestamp":1683352907000},"page":"49-71","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A near-optimal approach to edge connectivity-based hierarchical graph decomposition"],"prefix":"10.1007","volume":"33","author":[{"given":"Lijun","family":"Chang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiyi","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,6]]},"reference":[{"issue":"1","key":"797_CR1","first-page":"862","volume":"2","author":"CC Aggarwal","year":"2009","unstructured":"Aggarwal, C.C., Xie, Y., Philip, S.Y.: Gconnect: a connectivity index for massive disk-resident graphs. PVLDB 2(1), 862\u2013873 (2009)","journal-title":"PVLDB"},{"key":"797_CR2","doi-asserted-by":"crossref","unstructured":"Agrawal, R., Rajagopalan, S., Srikant, R., Xu, Y.: Mining newsgroups using networks arising from social behavior. In: Proceedings of WWW\u201903, pp. 529\u2013535 (2003)","DOI":"10.1145\/775152.775227"},{"key":"797_CR3","doi-asserted-by":"crossref","unstructured":"Akiba, T., Iwata, Y., Yoshida, Y.: Linear-time enumeration of maximal k-edge-connected subgraphs in large networks by random contraction. In: Proceedings of CIKM\u201913, pp. 909\u2013918 (2013)","DOI":"10.1145\/2505515.2505751"},{"key":"797_CR4","unstructured":"Batagelj, V., Zaversnik, M.: An o(m) algorithm for cores decomposition of networks. CoRR arXiv:cs.DS\/0310049 (2003)"},{"key":"797_CR5","unstructured":"Bencz\u00far, A.A., Karger, D.R.: Randomized approximation schemes for cuts and flows in capacitated graphs. CoRR arXiv:cs.DS\/0207078 (2002)"},{"issue":"27","key":"797_CR6","doi-asserted-by":"publisher","first-page":"11150","DOI":"10.1073\/pnas.0701175104","volume":"104","author":"S Carmi","year":"2007","unstructured":"Carmi, S., Havlin, S., Kirkpatrick, S., Shavitt, Y., Shir, E.: A model of internet topology using k-shell decomposition. Proc. Natl. Acad. Sci. USA 104(27), 11150\u201311154 (2007)","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"797_CR7","doi-asserted-by":"crossref","unstructured":"Chang, L., Lin, X., Qin, L., Yu, J.X., Zhang, W.: Index-based optimal algorithms for computing Steiner components with maximum connectivity. In: Proceedings of SIGMOD\u201915 (2015)","DOI":"10.1145\/2723372.2746486"},{"key":"797_CR8","doi-asserted-by":"crossref","unstructured":"Chang, L., Qiao, M.: Deconstruct densest subgraphs. In: Proceedings of WWW\u201920, pp. 2747\u20132753 (2020)","DOI":"10.1145\/3366423.3380033"},{"key":"797_CR9","doi-asserted-by":"crossref","unstructured":"Chang, L., Qin, L.: Cohesive Subgraph Computation over Large Sparse Graphs. Springer Series in the Data Sciences (2018)","DOI":"10.1007\/978-3-030-03599-0"},{"issue":"6","key":"797_CR10","doi-asserted-by":"publisher","first-page":"1146","DOI":"10.14778\/3514061.3514063","volume":"15","author":"L Chang","year":"2022","unstructured":"Chang, L., Wang, Z.: A near-optimal approach to edge connectivity-based hierarchical graph decomposition. Proc. VLDB Endow. 15(6), 1146\u20131158 (2022)","journal-title":"Proc. VLDB Endow."},{"key":"797_CR11","doi-asserted-by":"crossref","unstructured":"Chang, L., Yu, J.X., Qin, L., Lin, X., Liu, C., Liang, W.: Efficiently computing k-edge connected components via graph decomposition. In: Proceedings of SIGMOD\u201913, pp. 205\u2013216 (2013)","DOI":"10.1145\/2463676.2465323"},{"key":"797_CR12","doi-asserted-by":"crossref","unstructured":"Charikar, M.,: Greedy approximation algorithms for finding dense components in a graph. In: Proceedings of APPROX\u201900, pp. 84\u201395 (2000)","DOI":"10.1007\/3-540-44436-X_10"},{"issue":"2","key":"797_CR13","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1007\/s00778-022-00754-0","volume":"32","author":"J Chen","year":"2023","unstructured":"Chen, J., Gao, J., Cui, B.: Ics-gnn$${}^{\\text{+ }}$$: lightweight interactive community search via graph neural network. VLDB J. 32(2), 447\u2013467 (2023)","journal-title":"VLDB J."},{"key":"797_CR14","unstructured":"Cheng, D., Ruchansky, N., Liu, Y.: Matrix completability analysis via graph k-connectivity. In: Proceedings of AISTATS\u201918, pp. 395\u2013403 (2018)"},{"key":"797_CR15","doi-asserted-by":"crossref","unstructured":"Cheng, J., Ke, Y., Chu, S., \u00d6zsu, M.T.: Efficient core decomposition in massive networks. In: Proceedings of ICDE\u201911, pp. 51\u201362 (2011)","DOI":"10.1109\/ICDE.2011.5767911"},{"key":"797_CR16","unstructured":"Cohen, J.: Trusses: Cohesive subgraphs for social network analysis. National Security Agency Technical Report, p.\u00a016 (2008)"},{"key":"797_CR17","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen, T.H., Stein, C., Rivest, R.L., Leiserson, C.E.: Introduction to Algorithms. McGraw-Hill Higher Education, New York (2001)"},{"key":"797_CR18","doi-asserted-by":"crossref","unstructured":"Danisch, M., Hubert Chan, T.-H., Sozio, M.: Large scale density-friendly graph decomposition via convex programming. In: Proceedings of WWW\u201917, pp. 233\u2013242 (2017)","DOI":"10.1145\/3038912.3052619"},{"issue":"1","key":"797_CR19","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1007\/s00778-019-00556-x","volume":"29","author":"Y Fang","year":"2020","unstructured":"Fang, Y., Xin Huang, L., Qin, Y.Z., Zhang, W., Cheng, R., Lin, X.: A survey of community search over big graphs. VLDB J. 29(1), 353\u2013392 (2020)","journal-title":"VLDB J."},{"key":"797_CR20","doi-asserted-by":"crossref","unstructured":"Fung, W.S., Hariharan, R., Harvey, N.J.A., Panigrahi, D.: A general framework for graph sparsification. In: Proceedings of STOC\u201911, pp. 71\u201380 (2011)","DOI":"10.1145\/1993636.1993647"},{"key":"797_CR21","volume-title":"Algorithmic Graph Theory","author":"A Gibbons","year":"1985","unstructured":"Gibbons, A.: Algorithmic Graph Theory. Cambridge University Press, Cambridge (1985)"},{"key":"797_CR22","unstructured":"Goldberg, A.V.: Finding a maximum density subgraph. Technical report, Berkeley, CA, USA (1984)"},{"issue":"4","key":"797_CR23","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/0109047","volume":"9","author":"RE Gomory","year":"1961","unstructured":"Gomory, R.E., Hu, T.C.: Multi-terminal network flows. J. Soc. Ind. Appl. Math. 9(4), 551\u2013570 (1961)","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"797_CR24","doi-asserted-by":"crossref","unstructured":"Hu, J., Wu, X., Cheng, R., Luo, S., Fang, Y.: Querying minimal Steiner maximum-connected subgraphs in large graphs. In: Proceedings of CIKM\u201916, pp. 1241\u20131250 (2016)","DOI":"10.1145\/2983323.2983748"},{"issue":"11","key":"797_CR25","doi-asserted-by":"publisher","first-page":"2455","DOI":"10.1109\/TKDE.2017.2730873","volume":"29","author":"J Hu","year":"2017","unstructured":"Hu, J., Wu, X., Cheng, R., Luo, S., Fang, Y.: On minimal Steiner maximum-connected subgraph queries. IEEE Trans. Knowl. Data Eng. 29(11), 2455\u20132469 (2017)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"797_CR26","doi-asserted-by":"crossref","unstructured":"Kelner, J.A., Lee, Y.T., Orecchia, L., Sidford, A.: An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In: Proceedings of SODA\u201913 (2013)","DOI":"10.1137\/1.9781611973402.16"},{"key":"797_CR27","doi-asserted-by":"crossref","unstructured":"Kim, J., Luo, S., Cong, G., Yu, W.: DMCS: Density modularity based community search. In: Proceedings of SIGMOD\u201922, pp. 889\u2013903 (2022)","DOI":"10.1145\/3514221.3526137"},{"issue":"3","key":"797_CR28","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1145\/2402.322385","volume":"30","author":"DW Matula","year":"1983","unstructured":"Matula, D.W., Beck, L.L.: Smallest-last ordering and clustering and graph coloring algorithms. J. ACM 30(3), 417\u2013427 (1983)","journal-title":"J. ACM"},{"key":"797_CR29","unstructured":"Nguyen, A., Hong, S.-H.: k-core based multi-level graph visualization for scale-free networks. In: Proceedings of PacificVis\u201917, pp. 21\u201325 (2017)"},{"key":"797_CR30","doi-asserted-by":"crossref","unstructured":"Orlin, J.B.: Max flows in o(nm) time, or better. In: Proceedings of STOC\u201913, pp. 765\u2013774 (2013)","DOI":"10.1145\/2488608.2488705"},{"key":"797_CR31","doi-asserted-by":"crossref","unstructured":"Papadopoulos, A.N., Lyritsis, A., Manolopoulos, Y.: Skygraph: an algorithm for important subgraph discovery in relational graphs. Data Min. Knowl. Discov., 17(1), August 2008","DOI":"10.1007\/s10618-008-0109-y"},{"key":"797_CR32","doi-asserted-by":"crossref","unstructured":"Saito, K., Yamada, T.: Extracting communities from complex networks by the k-dense method. In: Proceedings of ICDMw\u201906, pp. 300\u2013304 (2006)","DOI":"10.1109\/ICDMW.2006.76"},{"issue":"3","key":"797_CR33","first-page":"97","volume":"10","author":"AE Sariy\u00fcce","year":"2016","unstructured":"Sariy\u00fcce, A.E., Pinar, A.: Fast hierarchy construction for dense subgraphs. PVLDB 10(3), 97\u2013108 (2016)","journal-title":"PVLDB"},{"issue":"3","key":"797_CR34","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0378-8733(83)90028-X","volume":"5","author":"SB Seidman","year":"1983","unstructured":"Seidman, S.B.: Network structure and minimum degree. Social Networks 5(3), 269\u2013287 (1983)","journal-title":"Social Networks"},{"key":"797_CR35","doi-asserted-by":"crossref","unstructured":"Sherman, J.: Nearly maximum flows in nearly linear time. In: Proceedings of FOCS\u201913 (2013)","DOI":"10.1109\/FOCS.2013.36"},{"key":"797_CR36","unstructured":"Sorge, M., et\u00a0al.: The graph parameter hierarchy (2013)"},{"issue":"10","key":"797_CR37","doi-asserted-by":"publisher","first-page":"1628","DOI":"10.14778\/3401960.3401962","volume":"13","author":"B Sun","year":"2020","unstructured":"Sun, B., Danisch, M., Hubert Chan, T.-H., Sozio, M.: Kclist++: a simple algorithm for finding k-clique densest subgraphs in large graphs. Proc. VLDB Endow. 13(10), 1628\u20131640 (2020)","journal-title":"Proc. VLDB Endow."},{"key":"797_CR38","doi-asserted-by":"crossref","unstructured":"Wen, D., Qin, L., Zhang, Y., Chang, L., Chen, L.: Enumerating k-vertex connected components in large graphs. In: Proceedings of ICDE\u201919, pp. 52\u201363 (2019)","DOI":"10.1109\/ICDE.2019.00014"},{"key":"797_CR39","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1111\/0081-1750.00098","volume":"31","author":"DR White","year":"2001","unstructured":"White, D.R., Harary, F.: The cohesiveness of blocks in social networks: node connectivity and conditional density. Sociol. Methodol. 31, 305\u2013359 (2001)","journal-title":"Sociol. Methodol."},{"key":"797_CR40","doi-asserted-by":"crossref","unstructured":"Yan, X., Jasmine Zhou, X., Han, J.: Mining closed relational graphs with connectivity constraints. In: Proceedings of KDD\u201905 (2005)","DOI":"10.1145\/1081870.1081908"},{"issue":"8","key":"797_CR41","doi-asserted-by":"publisher","first-page":"1441","DOI":"10.14778\/3457390.3457407","volume":"14","author":"K Yao","year":"2021","unstructured":"Yao, K., Chang, L.: Efficient size-bounded community search over large networks. Proc. VLDB Endow. 14(8), 1441\u20131453 (2021)","journal-title":"Proc. VLDB Endow."},{"issue":"2","key":"797_CR42","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s00778-016-0451-4","volume":"26","author":"L Yuan","year":"2017","unstructured":"Yuan, L., Qin, L., Lin, X., Chang, L., Zhang, W.: I\/O efficient ECC graph decomposition via graph reduction. VLDB J. 26(2), 275\u2013300 (2017)","journal-title":"VLDB J."},{"key":"797_CR43","doi-asserted-by":"crossref","unstructured":"Zhou, R., Liu, C., Yu, J.X., Liang, W., Chen, B., Li, J.: Finding maximal k-edge-connected subgraphs from a large graph. In: Proceedings of EDBT\u201912 (2012)","DOI":"10.1145\/2247596.2247652"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-023-00797-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-023-00797-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-023-00797-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,18]],"date-time":"2024-01-18T19:05:56Z","timestamp":1705604756000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-023-00797-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,6]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["797"],"URL":"https:\/\/doi.org\/10.1007\/s00778-023-00797-x","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,6]]},"assertion":[{"value":"22 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 April 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 May 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}