{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T03:06:13Z","timestamp":1787022373297,"version":"build-2736575974"},"reference-count":32,"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":[[2024,1]]},"abstract":"<jats:p>Structural diversity of a vertex refers to the diversity of connections within its neighborhood and has been applied in various fields such as viral marketing and user engagement. The paper studies querying the structural diversity of a vertex for any query time windows in streaming graphs. Existing studies are limited to static graphs which fail to capture vertices' structural diversities in snapshots evolving over time. We design an elegant index structure to significantly reduce the index size compared to the basic approach. We propose an optimized incremental algorithm to update the index for continuous edge arrivals. Extensive experiments on real-world streaming graphs demonstrate the effectiveness of our framework.<\/jats:p>","DOI":"10.14778\/3641204.3641213","type":"journal-article","created":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T18:05:43Z","timestamp":1714673143000},"page":"1034-1046","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Querying Structural Diversity in Streaming Graphs"],"prefix":"10.14778","volume":"17","author":[{"given":"Kaiyu","family":"Chen","sequence":"first","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dong","family":"Wen","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"Zhejiang Gongshang University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaoyang","family":"Wang","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Peng Bao Huawei Shen Junming Huang and Xueqi Cheng. 2013. Popularity prediction in microblogging network: a case study on sina weibo. In WWW. 177--178.","DOI":"10.1145\/2487788.2487877"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Lijun Chang Chen Zhang Xuemin Lin and Lu Qin. 2017. Scalable Top-K Structural Diversity Search. In ICDE. 95--98.","DOI":"10.1109\/ICDE.2017.48"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1007\/978-3-642-40450-4_29","article-title":"Dynamic Graphs in the Sliding-Window Model","volume":"8125","author":"Crouch Michael S.","year":"2013","unstructured":"Michael S. Crouch, Andrew McGregor, and Daniel M. Stubbs. 2013. Dynamic Graphs in the Sliding-Window Model. In ESA (Lecture Notes in Computer Science), Vol. 8125. 337--348.","journal-title":"ESA (Lecture Notes in Computer Science)"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Zhanpeng Fang Xinyu Zhou Jie Tang Wei Shao Alvis Cheuk M. Fong Longjun Sun Ying Ding Ling Zhou and Jarder Luo. 2014. Modeling Paying Behavior in Game Social Networks. In CIKM. 411--420.","DOI":"10.1145\/2661829.2662024"},{"key":"e_1_2_1_5_1","unstructured":"Xiangyang Gou and Lei Zou. 2021. Sliding Window-based Approximate Triangle Counting over Streaming Graphs with Duplicate Edges. In SIGMOD. 645--657."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Ruocheng Guo Elham Shaabani Abhinav Bhatnagar and Paulo Shakarian. 2015. Toward Order-of-Magnitude Cascade Prediction. In ASONAM. 1610--1613.","DOI":"10.1145\/2808797.2809358"},{"key":"e_1_2_1_7_1","volume-title":"Toward early and order-of-magnitude cascade prediction in social networks. Soc. Netw. Anal. Min. 6, 1","author":"Guo Ruocheng","year":"2016","unstructured":"Ruocheng Guo, Elham Shaabani, Abhinav Bhatnagar, and Paulo Shakarian. 2016. Toward early and order-of-magnitude cascade prediction in social networks. Soc. Netw. Anal. Min. 6, 1 (2016), 64:1--64:18."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3027950"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1007\/978-3-030-34223-4_43","article-title":"Parameter-Free Structural Diversity Search","volume":"11881","author":"Huang Jinbin","year":"2019","unstructured":"Jinbin Huang, Xin Huang, Yuanyuan Zhu, and Jianliang Xu. 2019. Parameter-Free Structural Diversity Search. In WISE (Lecture Notes in Computer Science), Vol. 11881. 677--693.","journal-title":"WISE (Lecture Notes in Computer Science)"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-020-00843-6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536258.2536272"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0379-0"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the Fifth ACM RecSys Workshop on Recommender Systems and the Social Web (CEUR Workshop Proceedings)","volume":"1066","author":"Huang Xinyi","year":"2013","unstructured":"Xinyi (Lisa) Huang, Mitul Tiwari, and Sam Shah. 2013. Structural Diversity in Social Recommender Systems. In Proceedings of the Fifth ACM RecSys Workshop on Recommender Systems and the Social Web (CEUR Workshop Proceedings), Vol. 1066."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207033"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.07.017"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2627692.2627694"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Anil Pacaci Angela Bonifati and M. Tamer \u00d6zsu. 2020. Regular Path Query Evaluation on Streaming Graphs. In SIGMOD. 1415--1430.","DOI":"10.1145\/3318464.3389733"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Javier Sanz-Cruzado and Pablo Castells. 2018. Enhancing structural diversity in social networks by recommending weak ties. In RecSys. 233--241.","DOI":"10.1145\/3240323.3240371"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.23997"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/62.2160"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1116502109"},{"key":"e_1_2_1_22_1","volume-title":"Distributed Near-Maximum Independent Set Maintenance over Large-scale Dynamic Graphs","author":"Wang Xubo","unstructured":"Xubo Wang, Dong Wen, Wenjie Zhang, Ying Zhang, and Lu Qin. 2023. Distributed Near-Maximum Independent Set Maintenance over Large-scale Dynamic Graphs. In ICDE. IEEE, 2538--2550."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3157794.3157795"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2833070"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00715-z"},{"key":"e_1_2_1_26_1","first-page":"2","volume-title":"Proc. ACM Manag. Data 1","author":"Xie Haoxuan","year":"2023","unstructured":"Haoxuan Xie, Yixiang Fang, Yuyang Xia, Wensheng Luo, and Chenhao Ma. 2023. On Querying Connected Components in Large Temporal Graphs. Proc. ACM Manag. Data 1, 2 (2023), 170:1--170:27."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364329"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1007\/978-3-030-59416-9_31","article-title":"AOT: Pushing the Efficiency Boundary of Main-Memory Triangle Listing","volume":"12113","author":"Yu Michael","year":"2020","unstructured":"Michael Yu, Lu Qin, Ying Zhang, Wenjie Zhang, and Xuemin Lin. 2020. AOT: Pushing the Efficiency Boundary of Main-Memory Triangle Listing. In DASFAA (Lecture Notes in Computer Science), Vol. 12113. 516--533.","journal-title":"DASFAA (Lecture Notes in Computer Science)"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Michael Yu Lu Qin Ying Zhang Wenjie Zhang and Xuemin Lin. 2021. DPTL+: Efficient Parallel Triangle Listing on Batch-Dynamic Graphs. In ICDE. 1332--1343.","DOI":"10.1109\/ICDE51399.2021.00119"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476260"},{"key":"e_1_2_1_31_1","volume-title":"Structural diversity effect on hashtag adoption in Twitter. Physica A: Statistical Mechanics and its Applications 493","author":"Zhang Aihua","year":"2018","unstructured":"Aihua Zhang, Mingxing Zheng, and Bowen Pang. 2018. Structural diversity effect on hashtag adoption in Twitter. Physica A: Statistical Mechanics and its Applications 493 (2018), 267--275."},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Qi Zhang Rong-Hua Li Qixuan Yang Guoren Wang and Lu Qin. 2020. Efficient Top-k Edge Structural Diversity Search. In ICDE. 205--216.","DOI":"10.1109\/ICDE48307.2020.00025"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3641204.3641213","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,17]],"date-time":"2024-11-17T18:15:57Z","timestamp":1731867357000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3641204.3641213"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["10.14778\/3641204.3641213"],"URL":"https:\/\/doi.org\/10.14778\/3641204.3641213","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,1]]},"assertion":[{"value":"2024-05-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}