{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T17:09:11Z","timestamp":1767978551995,"version":"3.49.0"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"5","funder":[{"name":"Srijan: Center for Generative AI","award":["ET\/23\/2024-ET"],"award-info":[{"award-number":["ET\/23\/2024-ET"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>Identifying and preserving community structures in a streaming graph is a very challenging task. However, many applications require the identification of these communities in very limited space and time. In this article, we design Community Sketch, a small space data structure that efficiently preserves communities. On query, it provides communities in constant time. With the use of community sketch data structure, a linear streaming community detection algorithm is proposed. Experimental results on the large real-world networks show that our algorithm outperforms other state-of-the-art algorithms in terms of quality metrics (NMI, F1-score, and WCC). Further, we propose an algorithm to produce benchmark network, namely, Temporal Community Benchmark Dataset (TCBD) which contains both true community labels and temporal information of edges. These synthetic networks are used to validate the proposed algorithm.<\/jats:p>","DOI":"10.1145\/3735976","type":"journal-article","created":{"date-parts":[[2025,5,15]],"date-time":"2025-05-15T15:23:38Z","timestamp":1747322618000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Communities in Streaming Graphs: Small Space Data Structure, Benchmark Data Generation, and Linear Algorithm"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4908-843X","authenticated-orcid":false,"given":"Shubham","family":"Gupta","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology Jodhpur, Jodhpur, India"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7856-4768","authenticated-orcid":false,"given":"Suman","family":"Kundu","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology Jodhpur, Jodhpur, India"}]}],"member":"320","published-online":{"date-parts":[[2025,6,16]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1145\/1150402.1150412","volume-title":"Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD \u201906)","author":"Backstrom Lars","year":"2006","unstructured":"Lars Backstrom, Dan Huttenlocher, Jon Kleinberg, and Xiangyang Lan. 2006. Group formation in large social networks: Membership, growth, and evolution. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD \u201906). ACM, New York, NY, 44\u201354."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2992785"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.2012.0375"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3389049"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2023.3327810"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"issue":"6","key":"e_1_3_2_9_2","doi-asserted-by":"crossref","first-page":"cnaa027","DOI":"10.1093\/comnet\/cnaa027","article-title":"Evaluating community detection algorithms for progressively evolving graphs","volume":"8","author":"Cazabet Remy","year":"2021","unstructured":"Remy Cazabet, Sou\u00e2ad Boudebza, and Giulio Rossetti. 2021. Evaluating community detection algorithms for progressively evolving graphs. Journal of Complex Networks 8, 6 (Mar. 2021), cnaa027.","journal-title":"Journal of Complex Networks"},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/978-3-319-05401-8_19","volume-title":"Complex Networks V.","author":"Chykhradze Kyrylo","year":"2014","unstructured":"Kyrylo Chykhradze, Anton Korshunov, Nazar Buzun, Roman Pastukhov, Nikolay Kuzyurin, Denis Turdakov, and Hangkyu Kim. 2014. Distributed generation of billion-node social graphs with overlapping community structure. In Complex Networks V. Pierluigi Contucci, Ronaldo Menezes, Andrea Omicini, and Julia Poncela-Casasnovas (Eds.), Springer International Publishing, Cham, 199\u2013208."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_3_2_13_2","unstructured":"Alexandre Hollocou Julien Maudet Thomas Bonald and Marc Lelarge. 2017. A linear streaming algorithm for community detection in very large networks. arXiv:1703.02955. Retrieved from https:\/\/arxiv.org\/abs\/1703.02955"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/0202024"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.78.046110"},{"issue":"4","key":"e_1_3_2_16_2","doi-asserted-by":"crossref","first-page":"046110","DOI":"10.1103\/PhysRevE.81.046110","article-title":"Statistical significance of communities in networks","volume":"81","author":"Lancichinetti Andrea","year":"2010","unstructured":"Andrea Lancichinetti, Filippo Radicchi, and Jos\u00e9 J. Ramasco. 2010. Statistical significance of communities in networks. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics 81, 4 Pt 2 (2010), 046110.","journal-title":"Physical Review E, Statistical, Nonlinear, and Soft Matter Physics"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1232722.1232727"},{"key":"e_1_3_2_18_2","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data."},{"key":"e_1_3_2_19_2","first-page":"1925","volume-title":"Proceedings of the 2020 IEEE 6th International Conference on Computer and Communications (ICCC)","author":"Li Hui","year":"2020","unstructured":"Hui Li, Fucai Chen, and Jianpeng Zhang. 2020. A streaming-based algorithm for overlapping community detection. In Proceedings of the 2020 IEEE 6th International Conference on Computer and Communications (ICCC). IEEE, China, 1925\u20131930."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.3390\/e23050497"},{"key":"e_1_3_2_21_2","first-page":"676","volume-title":"Proceedings of the 2017 IEEE International Conference on Big Data (Big Data)","author":"Liakos Panagiotis","year":"2017","unstructured":"Panagiotis Liakos, Alexandros Ntoulas, and Alex Delis. 2017. COEUS: Community detection via seed-set expansion on graph streams. In Proceedings of the 2017 IEEE International Conference on Big Data (Big Data). IEEE, Boston, 676\u2013685."},{"key":"e_1_3_2_22_2","first-page":"301","volume-title":"Proceedings of the 2019 IEEE 12th International Conference on Cloud Computing (CLOUD)","author":"Liakos Panagiotis","year":"2019","unstructured":"Panagiotis Liakos, Katia Papakonstantinopoulou, Alexandros Ntoulas, and Alex Delis. 2019. DiCeS: Detecting communities in network streams over the cloud. In Proceedings of the 2019 IEEE 12th International Conference on Cloud Computing (CLOUD). IEEE, Italy, 301\u2013310."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3012608"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00723-z"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2015.05.001"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0601602103"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.69.026113"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature03607"},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1007\/11569596_31","volume-title":"Proceedings of the Computer and Information Sciences (ISCIS \u201905)","author":"Pons Pascal","year":"2005","unstructured":"Pascal Pons and Matthieu Latapy. 2005. Computing communities in large networks using random walks. In Proceedings of the Computer and Information Sciences (ISCIS \u201905). Springer Berlin, Berlin, 284\u2013293."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2398496"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.036106"},{"issue":"6","key":"e_1_3_2_32_2","doi-asserted-by":"crossref","first-page":"893","DOI":"10.1093\/comnet\/cnx016","article-title":"RDYN: Graph benchmark handling community dynamics","volume":"5","author":"Rossetti Giulio","year":"2017","unstructured":"Giulio Rossetti. 2017. RDYN: Graph benchmark handling community dynamics. Journal of Complex Networks 5, 6 (Jul. 2017), 893\u2013912.","journal-title":"Journal of Complex Networks"},{"issue":"2","key":"e_1_3_2_33_2","first-page":"37","article-title":"Community discovery in dynamic networks: A survey","volume":"51","author":"Rossetti Giulio","year":"2018","unstructured":"Giulio Rossetti and R\u00e9my Cazabet. 2018. Community discovery in dynamic networks: A survey. ACM Computing Surveys 51, 2 (Feb. 2018), Article 35, 37.","journal-title":"ACM Computing Surveys"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0706851105"},{"issue":"4","key":"e_1_3_2_35_2","first-page":"48","article-title":"Creating a maximal clique graph to improve community detection in SCoDA and OSLOM algorithms","volume":"11","author":"Sabour Sasan","year":"2019","unstructured":"Sasan Sabour and Ali Moeini. 2019. Creating a maximal clique graph to improve community detection in SCoDA and OSLOM algorithms. International Journal of Information and Communication Technology Research 11, 4 (2019), 48\u201356. Retrieved from http:\/\/ijict.itrc.ac.ir\/article-1-447-en.html","journal-title":"International Journal of Information and Communication Technology Research"},{"key":"e_1_3_2_36_2","first-page":"433","volume-title":"Proceedings of the VLDB Endowment","volume":"6","author":"Sar\u00edy\u00fcce Ahmet Erdem","year":"2013","unstructured":"Ahmet Erdem Sar\u00edy\u00fcce, Bu\u011fra Gedik, Gabriela Jacques-Silva, Kun-Lung Wu, and \u00dcmit V. \u00c7ataly\u00fcrek. 2013. Streaming algorithms for K-core decomposition. Proceedings of the VLDB Endowment 6, 6 (2013), 433\u2013444."},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0423-8"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCSS.2020.2964197"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2017.51"},{"key":"e_1_3_2_40_2","first-page":"2305","volume-title":"Proceedings of the VLDB Endowment","volume":"14","author":"Shi Jessica","year":"2021","unstructured":"Jessica Shi, Laxman Dhulipala, David Eisenstat, Jakub \u0141\u0103cki, and Vahab Mirrokni. 2021. Scalable community detection via parallel correlation clustering. Proceedings of the VLDB Endowment 14, 11 (Oct. 2021), 2305\u20132313."},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.07.020"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3047224"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2020.2996595"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-023-29610-z"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-019-41695-z"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"},{"key":"e_1_3_2_48_2","first-page":"2099","volume-title":"Proceedings of the 22nd ACM CIKM (CIKM \u201913)","author":"Whang Joyce Jiyoung","year":"2013","unstructured":"Joyce Jiyoung Whang, David F. Gleich, and Inderjit S. Dhillon. 2013. Overlapping community detection using seed set expansion. In Proceedings of the 22nd ACM CIKM (CIKM \u201913). ACM, New York, NY, 2099\u20132108."},{"key":"e_1_3_2_49_2","first-page":"26976","article-title":"Streaming belief propagation for community detection","volume":"34","author":"Wu Yuchen","year":"2021","unstructured":"Yuchen Wu, Jakab Tardos, MohammadHossein Bateni, Andr\u00e9 Linhares, Filipe Miguel Goncalves de Almeida, Andrea Montanari, and Ashkan Norouzi-Fard. 2021. Streaming belief propagation for community detection. Advances in Neural Information Processing Systems 34 (2021), 26976\u201326988.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_2_50_2","first-page":"824","volume-title":"Proceedings of the 13th ACM SIGKDD (KDD \u201907)","author":"Xu Xiaowei","year":"2007","unstructured":"Xiaowei Xu, Nurcan Yuruk, Zhidan Feng, and Thomas A. J. Schweiger. 2007. SCAN: A structural clustering algorithm for networks. In Proceedings of the 13th ACM SIGKDD (KDD \u201907). ACM, New York, NY, 824\u2013833."},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_3_2_52_2","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1145\/2433396.2433471","volume-title":"Proceedings of the 6th ACM International Conference on Web Search and Data Mining (WSDM \u201913)","author":"Yang Jaewon","year":"2013","unstructured":"Jaewon Yang and Jure Leskovec. 2013. Overlapping community detection at scale: A nonnegative matrix factorization approach. In Proceedings of the 6th ACM International Conference on Web Search and Data Mining (WSDM \u201913). ACM, New York, NY, 587\u2013596."},{"key":"e_1_3_2_53_2","unstructured":"Yanhao Yang Meng Wang David Bindel and Kun He. 2021. Streaming Local Community Detection through Approximate Conductance. arXiv:2110.14972. Retrieved from https:\/\/arxiv.org\/abs\/2110.14972"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/TFUZZ.2020.2980502"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3735976","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,16]],"date-time":"2025-06-16T16:57:04Z","timestamp":1750093024000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3735976"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,16]]},"references-count":53,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3735976"],"URL":"https:\/\/doi.org\/10.1145\/3735976","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,16]]},"assertion":[{"value":"2024-05-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-08","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-06-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}