{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T09:18:48Z","timestamp":1773825528188,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:p>\n            Querying cohesive subgraphs on temporal graphs with various time constraints has attracted intensive research interests recently. In this paper, we study a novel Temporal\n            <jats:italic>k<\/jats:italic>\n            -Core Query (TCQ) problem: given a time interval, find all distinct\n            <jats:italic>k<\/jats:italic>\n            -cores that exist within any subintervals from a temporal graph, which generalizes the previous historical\n            <jats:italic>k<\/jats:italic>\n            -core query. This problem is challenging because the number of subintervals increases quadratically to the span of time interval. For that, we propose a novel Temporal Core Decomposition (TCD) algorithm that decrementally induces temporal\n            <jats:italic>k<\/jats:italic>\n            -cores from the previously induced ones and thus reduces \"intra-core\" redundant computation significantly. Then, we introduce an intuitive concept named Tightest Time Interval (TTI) for temporal\n            <jats:italic>k<\/jats:italic>\n            -core, and design an optimization technique with theoretical guarantee that leverages TTI as a key to predict which subintervals will induce duplicated\n            <jats:italic>k<\/jats:italic>\n            -cores and prunes the subintervals completely in advance, thereby eliminating \"inter-core\" redundant computation. The complexity of optimized TCD (OTCD) algorithm no longer depends on the span of query time interval but only the scale of final results, which means OTCD algorithm is scalable. Moreover, we propose a compact in-memory data structure named Temporal Edge List (TEL) to implement OTCD algorithm efficiently in physical level with bounded memory requirement. TEL organizes temporal edges in a \"timeline\" and can be updated instantly when new edges arrive in dynamical temporal graphs. We compare OTCD algorithm with the incremental historical\n            <jats:italic>k<\/jats:italic>\n            -core query on several real-world temporal graphs, and observe that OTCD algorithm outperforms it by three orders of magnitude, even though OTCD algorithm needs none precomputed index.\n          <\/jats:p>","DOI":"10.14778\/3579075.3579089","type":"journal-article","created":{"date-parts":[[2023,3,6]],"date-time":"2023-03-06T17:10:26Z","timestamp":1678122626000},"page":"1168-1180","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Scalable Time-Range\n            <i>k<\/i>\n            -Core Query on Temporal Graphs"],"prefix":"10.14778","volume":"16","author":[{"given":"Junyong","family":"Yang","sequence":"first","affiliation":[{"name":"School of Computer Science, Wuhan University, Wuhan, China"}]},{"given":"Ming","family":"Zhong","sequence":"additional","affiliation":[{"name":"School of Computer Science, Wuhan University, Wuhan, China"}]},{"given":"Yuanyuan","family":"Zhu","sequence":"additional","affiliation":[{"name":"School of Computer Science, Wuhan University, Wuhan, China"}]},{"given":"Tieyun","family":"Qian","sequence":"additional","affiliation":[{"name":"School of Computer Science, Wuhan University, Wuhan, China"}]},{"given":"Mengchi","family":"Liu","sequence":"additional","affiliation":[{"name":"South China Normal University, Guangzhou, China"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}]}],"member":"320","published-online":{"date-parts":[[2023,3,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2019.11.003"},{"key":"e_1_2_1_2_1","volume-title":"arXiv preprint cs\/0310049","author":"Batagelj Vladimir","year":"2003","unstructured":"Vladimir Batagelj and Matjaz Zaversnik . 2003. An O (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049 ( 2003 ). Vladimir Batagelj and Matjaz Zaversnik. 2003. An O (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049 (2003)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324962"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence. 3544--3550","author":"Chen Yankai","year":"2021","unstructured":"Yankai Chen , Jie Zhang , Yixiang Fang , Xin Cao , and Irwin King . 2021 . Efficient community search over large directed graphs: An augmented index-based approach . In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence. 3544--3550 . Yankai Chen, Jie Zhang, Yixiang Fang, Xin Cao, and Irwin King. 2021. Efficient community search over large directed graphs: An augmented index-based approach. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence. 3544--3550."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3358701.3358704"},{"key":"e_1_2_1_6_1","volume-title":"Butterfly-core community search over labeled graphs. arXiv preprint arXiv:2105.08628","author":"Dong Zheng","year":"2021","unstructured":"Zheng Dong , Xin Huang , Guorui Yuan , Hengshu Zhu , and Hui Xiong . 2021. Butterfly-core community search over labeled graphs. arXiv preprint arXiv:2105.08628 ( 2021 ). Zheng Dong, Xin Huang, Guorui Yuan, Hengshu Zhu, and Hui Xiong. 2021. Butterfly-core community search over labeled graphs. arXiv preprint arXiv:2105.08628 (2021)."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0482-5"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055337"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2845414"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380756"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3271767"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099626"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2021.101914"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_17_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735484"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00077"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.158"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-021-00917-z"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313522"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461542"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389697"},{"key":"e_1_2_1_25_1","first-page":"645","article-title":"An efficient approach to finding dense temporal subgraphs","volume":"32","author":"Ma Shuai","year":"2019","unstructured":"Shuai Ma , Renjun Hu , Luoshu Wang , Xuelian Lin , and Jinpeng Huai . 2019 . An efficient approach to finding dense temporal subgraphs . IEEE Transactions on Knowledge and Data Engineering 32 , 4 (2019), 645 -- 658 . Shuai Ma, Renjun Hu, Luoshu Wang, Xuelian Lin, and Jinpeng Huai. 2019. An efficient approach to finding dense temporal subgraphs. IEEE Transactions on Knowledge and Data Engineering 32, 4 (2019), 645--658.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366030.3366049"},{"key":"e_1_2_1_27_1","volume-title":"Periodic communities mining in temporal networks: Concepts and algorithms","author":"Qin Hongchao","year":"2020","unstructured":"Hongchao Qin , Ronghua Li , Ye Yuan , Guoren Wang , Weihua Yang , and Lu Qin . 2020. Periodic communities mining in temporal networks: Concepts and algorithms . IEEE Transactions on Knowledge and Data Engineering ( 2020 ). Hongchao Qin, Ronghua Li, Ye Yuan, Guoren Wang, Weihua Yang, and Lu Qin. 2020. Periodic communities mining in temporal networks: Concepts and algorithms. IEEE Transactions on Knowledge and Data Engineering (2020)."},{"key":"e_1_2_1_28_1","volume-title":"2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 1130--1141","author":"Qin Hongchao","year":"2019","unstructured":"Hongchao Qin , Rong-Hua Li , Guoren Wang , Lu Qin , Yurong Cheng , and Ye Yuan . 2019 . Mining periodic cliques in temporal networks . In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 1130--1141 . Hongchao Qin, Rong-Hua Li, Guoren Wang, Lu Qin, Yurong Cheng, and Ye Yuan. 2019. Mining periodic cliques in temporal networks. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). IEEE, 1130--1141."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0423-8"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_1_31_1","volume-title":"Stable community detection in signed social networks","author":"Sun Renjie","year":"2020","unstructured":"Renjie Sun , Chen Chen , Xiaoyang Wang , Ying Zhang , and Xun Wang . 2020. Stable community detection in signed social networks . IEEE Transactions on Knowledge and Data Engineering ( 2020 ). Renjie Sun, Chen Chen, Xiaoyang Wang, Ying Zhang, and Xun Wang. 2020. Stable community detection in signed social networks. IEEE Transactions on Knowledge and Data Engineering (2020)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00015"},{"key":"e_1_2_1_33_1","volume-title":"Discovering significant communities on bipartite graphs: An index-based approach","author":"Wang Kai","year":"2021","unstructured":"Kai Wang , Wenjie Zhang , Ying Zhang , Lu Qin , and Yuting Zhang . 2021. Discovering significant communities on bipartite graphs: An index-based approach . IEEE Transactions on Knowledge and Data Engineering ( 2021 ). Kai Wang, Wenjie Zhang, Ying Zhang, Lu Qin, and Yuting Zhang. 2021. Discovering significant communities on bipartite graphs: An index-based approach. IEEE Transactions on Knowledge and Data Engineering (2021)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2015.7363809"},{"key":"e_1_2_1_35_1","unstructured":"Junyong Yang Ming Zhong Yuanyuan Zhu Tieyun Qian Mengchi Liu and Jeffery Xu Yu. 2023. Scalable Time-Range k-Core Query on Temporal Graphs. https:\/\/arxiv.org\/pdf\/2301.03770.pdf.  Junyong Yang Ming Zhong Yuanyuan Zhu Tieyun Qian Mengchi Liu and Jeffery Xu Yu. 2023. Scalable Time-Range k-Core Query on Temporal Graphs. https:\/\/arxiv.org\/pdf\/2301.03770.pdf."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457407"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476260"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00023"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 2647--2656","author":"Zhang Yuting","year":"2021","unstructured":"Yuting Zhang , Kai Wang , Wenjie Zhang , Xuemin Lin , and Ying Zhang . 2021 . Pareto-optimal community search on large bipartite graphs . In Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 2647--2656 . Yuting Zhang, Kai Wang, Wenjie Zhang, Xuemin Lin, and Ying Zhang. 2021. Pareto-optimal community search on large bipartite graphs. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management. 2647--2656."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0473-6"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3579075.3579089","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,6]],"date-time":"2023-03-06T17:17:32Z","timestamp":1678123052000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3579075.3579089"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1]]},"references-count":40,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["10.14778\/3579075.3579089"],"URL":"https:\/\/doi.org\/10.14778\/3579075.3579089","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,1]]},"assertion":[{"value":"2023-03-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}