{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T20:27:08Z","timestamp":1771705628774,"version":"3.50.1"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:p>Structural clustering is one of the most widely used graph clustering frameworks. In this paper, we focus on structural clustering of probabilistic graphs, which comes with significant computational challenges and has, so far, resisted efficient solutions that are able to scale to large graphs, e.g. the state-of-art can only handle graphs with a few million edges. We address the main bottleneck step of probabilistic structural clustering, computing the structural similarity of vertices based on their Jaccard similarity over the set of possible worlds of a given probabilistic graph. The state-of-art used Dynamic Programming, a quadratic run-time algorithm, that does not scale to pairs of vertices of high degree. In this paper we present a novel approach based on Lyapunov Central Limit Theorem. By using a carefully chosen set of random variables we are able to cast the computation of structural similarity to computing a one-tailed area under the Normal Distribution. Our approach has linear runtime as opposed to quadratic, and as such, it scales to much larger inputs. Extensive experiments show that our approach can handle massive graphs at web-scale which the state-of-art cannot.<\/jats:p>","DOI":"10.14778\/3611479.3611516","type":"journal-article","created":{"date-parts":[[2023,8,25]],"date-time":"2023-08-25T02:08:08Z","timestamp":1692929288000},"page":"3165-3177","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Scaling Up Structural Clustering to Large Probabilistic Graphs Using Lyapunov Central Limit Theorem"],"prefix":"10.14778","volume":"16","author":[{"given":"Joseph","family":"Howie","sequence":"first","affiliation":[{"name":"University of Victoria, Victoria, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkatesh","family":"Srinivasan","sequence":"additional","affiliation":[{"name":"University of Victoria, Victoria, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alex","family":"Thomo","sequence":"additional","affiliation":[{"name":"University of Victoria, Victoria, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,8,24]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Managing and mining sensor data","author":"Aggarwal Charu C","unstructured":"Charu C Aggarwal . 2013. Managing and mining sensor data . Springer Science & Business Media . Charu C Aggarwal. 2013. Managing and mining sensor data. Springer Science & Business Media."},{"key":"e_1_2_1_2_1","volume-title":"Gaining confidence in high-throughput protein interaction networks. Nature biotechnology 22, 1","author":"Bader Joel S","year":"2004","unstructured":"Joel S Bader , Amitabha Chaudhuri , Jonathan M Rothberg , and John Chant . 2004. Gaining confidence in high-throughput protein interaction networks. Nature biotechnology 22, 1 ( 2004 ), 78--85. Joel S Bader, Amitabha Chaudhuri, Jonathan M Rothberg, and John Chant. 2004. Gaining confidence in high-throughput protein interaction networks. Nature biotechnology 22, 1 (2004), 78--85."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2016.11.011"},{"key":"e_1_2_1_4_1","volume-title":"Injecting uncertainty in graphs for identity obfuscation. arXiv preprint arXiv:1208.4145","author":"Boldi Paolo","year":"2012","unstructured":"Paolo Boldi , Francesco Bonchi , Aris Gionis , and Tamir Tassa . 2012. Injecting uncertainty in graphs for identity obfuscation. arXiv preprint arXiv:1208.4145 ( 2012 ). Paolo Boldi, Francesco Bonchi, Aris Gionis, and Tamir Tassa. 2012. Injecting uncertainty in graphs for identity obfuscation. arXiv preprint arXiv:1208.4145 (2012)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623655"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164143"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2016.2618795"},{"key":"e_1_2_1_8_1","volume-title":"Clustering Methods for Big Data Analytics","author":"Chawathe Sudarshan S","unstructured":"Sudarshan S Chawathe . 2019. Clustering blockchain data . In Clustering Methods for Big Data Analytics . Springer , 43--72. Sudarshan S Chawathe. 2019. Clustering blockchain data. In Clustering Methods for Big Data Analytics. Springer, 43--72."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3225058.3225063"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICMLC.2013.6890400"},{"key":"e_1_2_1_11_1","series-title":"SIAM Journal on computing 14, 1","volume-title":"Arboricity and subgraph listing algorithms","author":"Chiba Norishige","year":"1985","unstructured":"Norishige Chiba and Takao Nishizeki . 1985. Arboricity and subgraph listing algorithms . SIAM Journal on computing 14, 1 ( 1985 ), 210--223. Norishige Chiba and Takao Nishizeki. 1985. Arboricity and subgraph listing algorithms. SIAM Journal on computing 14, 1 (1985), 210--223."},{"key":"e_1_2_1_12_1","volume-title":"Lyapunov Central Limit Theorem: Theoretical Properties and Applications in Big-Data-Populated Smart City Settings. In 2021 5th International Conference on Cloud and Big Data Computing (ICCBDC). 34--38","author":"Cuzzocrea Alfredo","year":"2021","unstructured":"Alfredo Cuzzocrea , Edoardo Fadda , and Alessandro Baldo . 2021 . Lyapunov Central Limit Theorem: Theoretical Properties and Applications in Big-Data-Populated Smart City Settings. In 2021 5th International Conference on Cloud and Big Data Computing (ICCBDC). 34--38 . Alfredo Cuzzocrea, Edoardo Fadda, and Alessandro Baldo. 2021. Lyapunov Central Limit Theorem: Theoretical Properties and Applications in Big-Data-Populated Smart City Settings. In 2021 5th International Conference on Cloud and Big Data Computing (ICCBDC). 34--38."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.compeleceng.2022.108066"},{"key":"e_1_2_1_14_1","volume-title":"Neural Network-Based ADP Cotrol for Nonliear Systems with Prescribed Performance Constriant. In 2021 33rd Chinese Control and Decision Conference (CCDC). IEEE, 6342--6346","author":"Ding Can","year":"2021","unstructured":"Can Ding , Jing Zhang , Yingjie Zhang , Zhe Zhang , and Xiaoyao Li . 2021 . Neural Network-Based ADP Cotrol for Nonliear Systems with Prescribed Performance Constriant. In 2021 33rd Chinese Control and Decision Conference (CCDC). IEEE, 6342--6346 . Can Ding, Jing Zhang, Yingjie Zhang, Zhe Zhang, and Xiaoyao Li. 2021. Neural Network-Based ADP Cotrol for Nonliear Systems with Prescribed Performance Constriant. In 2021 33rd Chinese Control and Decision Conference (CCDC). IEEE, 6342--6346."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-022-07415-9"},{"key":"e_1_2_1_16_1","unstructured":"Fatemeh Esfahani Venkatesh Srinivasan Alex Thomo and Kui Wu. 2019. Efficient Computation of Probabilistic Core Decomposition at Web-Scale.. In EDBT. 325--336.  Fatemeh Esfahani Venkatesh Srinivasan Alex Thomo and Kui Wu. 2019. Efficient Computation of Probabilistic Core Decomposition at Web-Scale.. In EDBT. 325--336."},{"key":"e_1_2_1_17_1","unstructured":"Martin Ester Hans-Peter Kriegel J\u00f6rg Sander Xiaowei Xu etal 1996. A density-based algorithm for discovering clusters in large spatial databases with noise.. In kdd Vol. 96. 226--231.  Martin Ester Hans-Peter Kriegel J\u00f6rg Sander Xiaowei Xu et al. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise.. In kdd Vol. 96. 226--231."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ijar.2017.07.013"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3311880.3311884"},{"key":"e_1_2_1_20_1","volume-title":"PKDD","author":"Hintsanen Petteri","unstructured":"Petteri Hintsanen . 2007. The most reliable subgraph problem . In PKDD , Vol. 2007 . Springer , 471--478. Petteri Hintsanen. 2007. The most reliable subgraph problem. In PKDD, Vol. 2007. Springer, 471--478."},{"key":"e_1_2_1_21_1","volume-title":"Muhammad Hanif, and Sajid Anwar.","author":"Hussain Syed Fawad","year":"2022","unstructured":"Syed Fawad Hussain , Ifra Arif Butt , Muhammad Hanif, and Sajid Anwar. 2022 . Clustering uncertain graphs using ant colony optimization (ACO). Neural Computing and Applications ( 2022), 1--18. Syed Fawad Hussain, Ifra Arif Butt, Muhammad Hanif, and Sajid Anwar. 2022. Clustering uncertain graphs using ant colony optimization (ACO). Neural Computing and Applications (2022), 1--18."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002941"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCNC.2005.1405152"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_25_1","volume-title":"The Protein-Protein Interaction Network of Hereditary Parkinsonism Genes Is a Hierarchical Scale-Free Network. Yonsei medical journal 63, 8","author":"Kim Yun Joong","year":"2022","unstructured":"Yun Joong Kim , Kiyong Kim , Heonwoo Lee , Junbeom Jeon , Jinwoo Lee , and Jeehee Yoon . 2022. The Protein-Protein Interaction Network of Hereditary Parkinsonism Genes Is a Hierarchical Scale-Free Network. Yonsei medical journal 63, 8 ( 2022 ), 724. Yun Joong Kim, Kiyong Kim, Heonwoo Lee, Junbeom Jeon, Jinwoo Lee, and Jeehee Yoon. 2022. The Protein-Protein Interaction Network of Hereditary Parkinsonism Genes Is a Hierarchical Scale-Free Network. Yonsei medical journal 63, 8 (2022), 724."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature04670"},{"key":"e_1_2_1_27_1","first-page":"1377","article-title":"Sunny: A new algorithm for trust inference in social networks using probabilistic confidence models","volume":"7","author":"Kuter Ugur","year":"2007","unstructured":"Ugur Kuter and Jennifer Golbeck . 2007 . Sunny: A new algorithm for trust inference in social networks using probabilistic confidence models . In AAAI , Vol. 7. 1377 -- 1382 . Ugur Kuter and Jennifer Golbeck. 2007. Sunny: A new algorithm for trust inference in social networks using probabilistic confidence models. In AAAI, Vol. 7. 1377--1382.","journal-title":"AAAI"},{"key":"e_1_2_1_28_1","volume-title":"Efficient Structural Clustering in Large Uncertain Graphs. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE","author":"Liang Yongjiang","year":"2020","unstructured":"Yongjiang Liang , Tingting Hu , and Peixiang Zhao . 2020 . Efficient Structural Clustering in Large Uncertain Graphs. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE , 1966--1969. Yongjiang Liang, Tingting Hu, and Peixiang Zhao. 2020. Efficient Structural Clustering in Large Uncertain Graphs. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). IEEE, 1966--1969."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364330"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the World Scientific Engineering Academy and Society 12 th International Conference on Applied Mathematics.","author":"McCulloh Ian","year":"2007","unstructured":"Ian McCulloh , Joshua Lospinoso , and KM Carley . 2007 . Social network probability mechanics . In Proceedings of the World Scientific Engineering Academy and Society 12 th International Conference on Applied Mathematics. Ian McCulloh, Joshua Lospinoso, and KM Carley. 2007. Social network probability mechanics. In Proceedings of the World Scientific Engineering Academy and Society 12 th International Conference on Applied Mathematics."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064045"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jebo.2014.12.011"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-011-0224-z"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920967"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2872553"},{"key":"e_1_2_1_36_1","volume-title":"Proteome-wide prediction and analysis of the Cryptosporidium parvum protein-protein interaction network through integrative methods. Computational and Structural Biotechnology Journal","author":"Ren Panyu","year":"2022","unstructured":"Panyu Ren , Xiaodi Yang , Tianpeng Wang , Yunpeng Hou , and Ziding Zhang . 2022. Proteome-wide prediction and analysis of the Cryptosporidium parvum protein-protein interaction network through integrative methods. Computational and Structural Biotechnology Journal ( 2022 ). Panyu Ren, Xiaodi Yang, Tianpeng Wang, Yunpeng Hou, and Ziding Zhang. 2022. Proteome-wide prediction and analysis of the Cryptosporidium parvum protein-protein interaction network through integrative methods. Computational and Structural Biotechnology Journal (2022)."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3452828"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3133121"},{"key":"e_1_2_1_39_1","volume-title":"Adaptive networks","author":"Skyrms Brian","unstructured":"Brian Skyrms and Robin Pemantle . 2009. A dynamic model of social network formation . In Adaptive networks . Springer , 231--251. Brian Skyrms and Robin Pemantle. 2009. A dynamic model of social network formation. In Adaptive networks. Springer, 231--251."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2014.2374607"},{"key":"e_1_2_1_41_1","volume-title":"Social Network Analysis-Community Detection and Evolution","author":"Xia Peng","unstructured":"Peng Xia , Kun Tu , Bruno Ribeiro , Hua Jiang , Xiaodong Wang , Cindy Chen , Benyuan Liu , and Don Towsley . 2014. Characterization of user online dating behavior and preference on a large online dating site . In Social Network Analysis-Community Detection and Evolution . Springer , 193--217. Peng Xia, Kun Tu, Bruno Ribeiro, Hua Jiang, Xiaodong Wang, Cindy Chen, Benyuan Liu, and Don Towsley. 2014. Characterization of user online dating behavior and preference on a large online dating site. In Social Network Analysis-Community Detection and Evolution. Springer, 193--217."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281280"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/0114098"},{"key":"e_1_2_1_44_1","volume-title":"Novel density-based and hierarchical density-based clustering algorithms for uncertain data. Neural networks 93","author":"Zhang Xianchao","year":"2017","unstructured":"Xianchao Zhang , Han Liu , and Xiaotong Zhang . 2017. Novel density-based and hierarchical density-based clustering algorithms for uncertain data. Neural networks 93 ( 2017 ), 240--255. Xianchao Zhang, Han Liu, and Xiaotong Zhang. 2017. Novel density-based and hierarchical density-based clustering algorithms for uncertain data. Neural networks 93 (2017), 240--255."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v28i1.8962"},{"key":"e_1_2_1_46_1","volume-title":"2013 IEEE 27th International Conference on Advanced Information Networking and Applications (AINA). IEEE, 862--869","author":"Zhao Weizhong","year":"2013","unstructured":"Weizhong Zhao , Venkataswamy Martha , and Xiaowei Xu . 2013 . PSCAN: a parallel Structural clustering algorithm for big networks in MapReduce . In 2013 IEEE 27th International Conference on Advanced Information Networking and Applications (AINA). IEEE, 862--869 . Weizhong Zhao, Venkataswamy Martha, and Xiaowei Xu. 2013. PSCAN: a parallel Structural clustering algorithm for big networks in MapReduce. In 2013 IEEE 27th International Conference on Advanced Information Networking and Applications (AINA). IEEE, 862--869."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835885"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447891"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3611479.3611516","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,23]],"date-time":"2023-09-23T22:21:09Z","timestamp":1695507669000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3611479.3611516"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7]]},"references-count":48,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["10.14778\/3611479.3611516"],"URL":"https:\/\/doi.org\/10.14778\/3611479.3611516","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2023,7]]},"assertion":[{"value":"2023-08-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}