{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T18:32:37Z","timestamp":1791916357460,"version":"4.3.4"},"reference-count":54,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,4]]},"abstract":"<jats:p>Community search aims to retrieve dense subgraphs that contain the query vertices. While many effective community models and algorithms have been proposed in the literature, none of them address the unique challenges posed by streaming graphs, where edges are continuously generated over time. In this paper, we investigate the problem of truss-based community search over streaming directed graphs. To address this problem, we first present a peeling-based algorithm that iteratively removes edges that do not meet the support constraints. To improve the efficiency of the peeling-based algorithm, we propose three optimizations that leverage the time information of the streaming graph and the structural information of trusses. As the peeling-based algorithm may suffer from inefficiency when the input peeling graph is large, we further propose a novel order-based algorithm that preserves the community by maintaining the deletion order of edges in the peeling algorithm. Extensive experimental results on real-world datasets show that our proposed algorithms outperform the baseline by up to two orders of magnitude in terms of throughput.<\/jats:p>","DOI":"10.14778\/3659437.3659440","type":"journal-article","created":{"date-parts":[[2024,5,31]],"date-time":"2024-05-31T12:22:27Z","timestamp":1717158147000},"page":"1816-1829","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Truss-Based Community Search over Streaming Directed Graphs"],"prefix":"10.14778","volume":"17","author":[{"given":"Xuankun","family":"Liao","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qing","family":"Liu","sequence":"additional","affiliation":[{"name":"Zhejiang University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xin","family":"Huang","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137640"},{"key":"e_1_2_1_2_1","volume-title":"Encyclopedia of Social Network Analysis and Mining","author":"Banerjee Soumya","unstructured":"Soumya Banerjee, Sumit Singh, and Eiman Tamah Al-Shammari. 2018. Community Detection in Social Network: An Experience with Directed Graphs. In Encyclopedia of Social Network Analysis and Mining, 2nd Edition. Springer.","edition":"2"},{"key":"e_1_2_1_3_1","volume-title":"Digraphs: theory, algorithms and applications","author":"Bang-Jensen J\u00f8rgen","unstructured":"J\u00f8rgen Bang-Jensen and Gregory Z Gutin. 2008. Digraphs: theory, algorithms and applications. Springer Science & Business Media."},{"key":"e_1_2_1_4_1","volume-title":"Efficient and effective community search. Data mining and knowledge discovery 29, 5","author":"Barbieri Nicola","year":"2015","unstructured":"Nicola Barbieri, Francesco Bonchi, Edoardo Galimberti, and Francesco Gullo. 2015. Efficient and effective community search. Data mining and knowledge discovery 29, 5 (2015), 1406--1433."},{"key":"e_1_2_1_5_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)."},{"key":"e_1_2_1_6_1","volume-title":"Algorithms---ESA 2002: 10th Annual European Symposium Rome, Italy, September 17--21","author":"Bender Michael A","year":"2002","unstructured":"Michael A Bender, Richard Cole, Erik D Demaine, Martin Farach-Colton, and Jack Zito. 2002. Two simplified algorithms for maintaining order in a list. In Algorithms---ESA 2002: 10th Annual European Symposium Rome, Italy, September 17--21, 2002 Proceedings. Springer, 152--164."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2746486"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231755"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. 1553--1562","author":"Chen Shu","year":"2016","unstructured":"Shu Chen, Ran Wei, Diana Popova, and Alex Thomo. 2016. Efficient computation of importance based communities in web-scale networks using a single machine. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management. 1553--1562."},{"key":"e_1_2_1_10_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."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463722"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612179"},{"key":"e_1_2_1_13_1","series-title":"SIAM journal on computing 31, 6","volume-title":"Maintaining stream statistics over sliding windows","author":"Datar Mayur","year":"2002","unstructured":"Mayur Datar, Aristides Gionis, Piotr Indyk, and Rajeev Motwani. 2002. Maintaining stream statistics over sliding windows. SIAM journal on computing 31, 6 (2002), 1794--1813."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28434"},{"key":"e_1_2_1_15_1","volume-title":"Advances in Knowledge Discovery and Data Mining: 21st Pacific-Asia Conference, PAKDD 2017, Jeju, South Korea, May 23--26, 2017, Proceedings, Part I 21","author":"Ding Yue","year":"2017","unstructured":"Yue Ding, Ling Huang, Chang-Dong Wang, and Dong Huang. 2017. Community detection in graph streams by pruning zombie nodes. In Advances in Knowledge Discovery and Data Mining: 21st Pacific-Asia Conference, PAKDD 2017, Jeju, South Korea, May 23--26, 2017, Proceedings, Part I 21. Springer, 574--585."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0482-5"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055337"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2845414"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2872982"},{"key":"e_1_2_1_21_1","volume-title":"D-cores: measuring collaboration of directed graphs based on degeneracy. Knowledge and information systems 35, 2","author":"Giatsidis Christos","year":"2013","unstructured":"Christos Giatsidis, Dimitrios M Thilikos, and Michalis Vazirgiannis. 2013. D-cores: measuring collaboration of directed graphs based on degeneracy. Knowledge and information systems 35, 2 (2013), 311--343."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452800"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"148841","DOI":"10.1109\/ACCESS.2020.3016214","article-title":"Weight-based k-truss community search via edge attachment","volume":"8","author":"El-Sharkawi Mohamed E","year":"2020","unstructured":"WafaaMAHabib, HodaMOMokhtar, and Mohamed E El-Sharkawi. 2020. Weight-based k-truss community search via edge attachment. IEEE Access 8 (2020), 148841--148852.","journal-title":"IEEE Access"},{"key":"e_1_2_1_24_1","unstructured":"Jorge E. Hirsch. 2005. H-index. https:\/\/en.wikipedia.org\/wiki\/H-index"},{"key":"e_1_2_1_25_1","volume-title":"A linear streaming algorithm for community detection in very large networks. arXiv preprint arXiv:1703.02955","author":"Hollocou Alexandre","year":"2017","unstructured":"Alexandre Hollocou, Julien Maudet, Thomas Bonald, and Marc Lelarge. 2017. A linear streaming algorithm for community detection in very large networks. arXiv preprint arXiv:1703.02955 (2017)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983748"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2730873"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 2014 International Conference on Management of Data. 1311--1322","author":"Huang Xin","year":"2014","unstructured":"Xin Huang, Hong Cheng, Lu Qin, Wentao Tian, and Jeffrey Xu Yu. 2014. Querying k-truss community in large and dynamic graphs. In Proceedings of the 2014 International Conference on Management of Data. 1311--1322."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099626"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-01874-9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856323"},{"key":"e_1_2_1_32_1","volume-title":"Quick survey of graph-based fraud detection methods. arXiv preprint arXiv:1910.11299","author":"Irofti Paul","year":"2019","unstructured":"Paul Irofti, Andrei Patrascu, and Andra Baltoiu. 2019. Quick survey of graph-based fraud detection methods. arXiv preprint arXiv:1910.11299 (2019)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623632"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517833"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517833"},{"key":"e_1_2_1_36_1","volume-title":"Main-memory triangle computations for very large (sparse (power-law)) graphs. Theoretical computer science 407, 1--3","author":"Latapy Matthieu","year":"2008","unstructured":"Matthieu Latapy. 2008. Main-memory triangle computations for very large (sparse (power-law)) graphs. Theoretical computer science 407, 1--3 (2008), 458--473."},{"key":"e_1_2_1_37_1","volume-title":"2017 IEEE 33rd international conference on data engineering (ICDE). IEEE, 871--882","author":"Li Jianxin","year":"2017","unstructured":"Jianxin Li, Xinjue Wang, Ke Deng, Xiaochun Yang, Timos Sellis, and Jeffrey Xu Yu. 2017. Most influential community search over large social networks. In 2017 IEEE 33rd international conference on data engineering (ICDE). IEEE, 871--882."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735484"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0467-4"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00077"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","first-page":"2375","DOI":"10.1109\/TKDE.2020.3012608","article-title":"Rapid detection of local communities in graph streams","volume":"34","author":"Liakos Panagiotis","year":"2020","unstructured":"Panagiotis Liakos, Katia Papakonstantinopoulou, Alexandros Ntoulas, and Alex Delis. 2020. Rapid detection of local communities in graph streams. IEEE Transactions on Knowledge and Data Engineering 34, 5 (2020), 2375--2386.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the VLDB Endowment","author":"Liao Xuankun","year":"2022","unstructured":"Xuankun Liao, Qing Liu, Jiaxin Jiang, Xin Huang, Jianliang Xu, and Byron Choi. 2022. Distributed D-Core Decomposition over Large Directed Graphs. Proceedings of the VLDB Endowment (2022), 1546--1558."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380587"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461542"},{"key":"e_1_2_1_45_1","volume-title":"2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 937--948","author":"Liu Qing","year":"2020","unstructured":"Qing Liu, Yifan Zhu, Minjun Zhao, Xin Huang, Jianliang Xu, and Yunjun Gao. 2020. VAC: vertex-centric attributed community search. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 937--948."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389733"},{"key":"e_1_2_1_47_1","volume-title":"sGrapp: Butterfly approximation in streaming graphs. ACM Transactions on Knowledge Discovery from Data (TKDD) 16, 4","author":"Sheshbolouki Aida","year":"2022","unstructured":"Aida Sheshbolouki and M Tamer \u00d6zsu. 2022. sGrapp: Butterfly approximation in streaming graphs. ACM Transactions on Knowledge Discovery from Data (TKDD) 16, 4 (2022), 1--43."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_1_49_1","first-page":"1","article-title":"Efficient Star-based Truss Maintenance on Dynamic Graphs","volume":"1","author":"Sun Zitan","year":"2023","unstructured":"Zitan Sun, Xin Huang, Qing Liu, and Jianliang Xu. 2023. Efficient Star-based Truss Maintenance on Dynamic Graphs. Proceedings of the ACM on Management of Data 1, 2 (2023), 1--26.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","first-page":"2199","DOI":"10.14778\/3598581.3598592","article-title":"Maximal D-truss Search in Dynamic Directed Graphs","volume":"16","author":"Tian Anxin","year":"2022","unstructured":"Anxin Tian, Alexander Zhou, Yue Wang, and Lei Chen. 2022. Maximal D-truss Search in Dynamic Directed Graphs. Proceedings of the VLDB Endowment 16, 9 (2022), 2199--2211.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_2_1_51_1","volume-title":"Proceedings of the 2013 SIAM international conference on data mining. SIAM, 151--161","author":"Wang Chang-Dong","year":"2013","unstructured":"Chang-Dong Wang, Jian-Huang Lai, and Philip S Yu. 2013. Dynamic community detection in weighted graph streams. In Proceedings of the 2013 SIAM international conference on data mining. SIAM, 151--161."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516422"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516422"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2783933"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3659437.3659440","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,31]],"date-time":"2024-05-31T12:27:29Z","timestamp":1717158449000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3659437.3659440"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4]]},"references-count":54,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["10.14778\/3659437.3659440"],"URL":"https:\/\/doi.org\/10.14778\/3659437.3659440","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,4]]},"assertion":[{"value":"2024-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}