{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:53:17Z","timestamp":1775638397753,"version":"3.50.1"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,5,15]],"date-time":"2025-05-15T00:00:00Z","timestamp":1747267200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-sa\/4.0\/"}],"funder":[{"name":"Hong Kong RGC","award":["12201923, 12202221, 12202024, RIF R1015-23, and C2003-23Y"],"award-info":[{"award-number":["12201923, 12202221, 12202024, RIF R1015-23, and C2003-23Y"]}]},{"DOI":"10.13039\/501100021171","name":"Guangdong Basic and Applied Basic Research Foundation","doi-asserted-by":"crossref","award":["2023B1515130002"],"award-info":[{"award-number":["2023B1515130002"]}],"id":[{"id":"10.13039\/501100021171","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Australian Research Council Fundings","award":["DP220103731"],"award-info":[{"award-number":["DP220103731"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2025,6,30]]},"abstract":"<jats:p>\n            Networks in many real-world applications come with an inherent uncertainty in their structure, due to, for example, noisy measurements, inference and prediction models, or for privacy purposes. Modeling and analyzing uncertain graphs have attracted a great deal of attention. Among the various graph analytic tasks studied, the extraction of dense substructures, such as cores or trusses, has a central role. In this article, we study the problem of (\n            <jats:italic>k<\/jats:italic>\n            , \u03b3)-truss indexing and querying over an uncertain graph\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\({\\mathcal {G}}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . A (\n            <jats:italic>k<\/jats:italic>\n            , \u03b3)-truss is the largest subgraph of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\({\\mathcal {G}}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            such that the probability of each edge being contained in at least\n            <jats:italic>k<\/jats:italic>\n            -2 triangles is no less than \u03b3. Our first proposal, CPT-index, keeps all the (\n            <jats:italic>kz<\/jats:italic>\n            , \u03b3)-trusses: retrieval for any given\n            <jats:italic>k<\/jats:italic>\n            and \u03b3 can be executed in an optimal linear time w.r.t. the graph size of the queried (\n            <jats:italic>k<\/jats:italic>\n            , \u03b3)-truss. We develop a bottom-up CPT-indexconstruction scheme and an improved algorithm for fast CPT-indexconstruction using top-down graph partitions. For trading off between (\n            <jats:italic>k<\/jats:italic>\n            ,\u03b3)-truss offline indexing and online querying, we further develop an approximate indexing approach \u03b5 , \u0394\n            <jats:sub>\n              <jats:italic>r<\/jats:italic>\n            <\/jats:sub>\n            -APXequipped with two parameters, \u03b5 and \u0394\n            <jats:sub>\n              <jats:italic>r<\/jats:italic>\n            <\/jats:sub>\n            , that govern tolerated errors. In addition, we further investigate the problem of maintaining (\n            <jats:italic>k<\/jats:italic>\n            , \u03b3)-truss indexes over dynamic uncertain graphs, where the update of vertex\/edge insertions\/deletions and also edge probability increments\/decrements may frequently occur. We propose a comprehensive solution for CPT-indexand (\u03b5 , \u0394\n            <jats:sub>\n              <jats:italic>r<\/jats:italic>\n            <\/jats:sub>\n            -APXmaintenance by addressing one fundamental task of one edge\u2019s probability increment\/decrement. To reduce the scope of affected edges that have trussness changed, we categorize three types of candidate edges and propose tight lower\/upper bounds for trussness refinement, which can efficiently accomplish CPT-indexmaintenance in a local update scheme. Our proposed techniques for one single edge change can also be extended to handle a batch update of multiple edges. Extensive experiments using large-scale uncertain graphs with 261 million edges validate the efficiency of our proposed indexing and querying algorithms, as well as our (\n            <jats:italic>k<\/jats:italic>\n            ,\u03b3)-truss index maintenance algorithms, against state-of-the-art methods. Case studies on real-world graphs demonstrate the significant efficiency improvement by our proposed solutions as well as interesting discoveries.\n          <\/jats:p>","DOI":"10.1145\/3721428","type":"journal-article","created":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T11:54:05Z","timestamp":1741002845000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Probabilistic Truss Decomposition on Uncertain Graphs: Indexing and Dynamic Maintenance"],"prefix":"10.1145","volume":"50","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1615-6558","authenticated-orcid":false,"given":"Zitan","family":"Sun","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3650-0301","authenticated-orcid":false,"given":"Xin","family":"Huang","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9404-5848","authenticated-orcid":false,"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9464-8315","authenticated-orcid":false,"given":"Francesco","family":"Bonchi","sequence":"additional","affiliation":[{"name":"CENTAI, Turin, Italy and Eurecat, Barcelona, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6830-3900","authenticated-orcid":false,"given":"Lijun","family":"Chang","sequence":"additional","affiliation":[{"name":"The University of Sydney, Sydney, Australia"}]}],"member":"320","published-online":{"date-parts":[[2025,5,15]]},"reference":[{"key":"e_1_3_1_2_2","unstructured":"BioGRID. 2025. BioGRID Home Page. Retrieved March 5 2025 from http:\/\/thebiogrid.org"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1109\/HPEC.2019.8916473"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.5555\/944919.944937"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350254"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623655"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401971"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2018.8622452"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-021-00933-z"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2014.7004264"},{"key":"e_1_3_1_11_2","first-page":"1460","article-title":"Efficient top-k vulnerable nodes detection in uncertain graphs","author":"Cheng Dawei","year":"2023","unstructured":"Dawei Cheng, Chen Chen, Xiaoyang Wang, and Sheng Xiang. 2023. Efficient top-k vulnerable nodes detection in uncertain graphs. IEEE Transactions on Knowledge and Data Engineering 35, 2 (2023), 1460\u20131472.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_3_1_13_2","unstructured":"DBLP. 2025. DBLP Home Page. Retrieved March 5 2025 from http:\/\/dblp.uni-trier.de"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.17.4.430"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/3367243.3367353"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-13-119"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-022-07415-9"},{"key":"e_1_3_1_18_2","first-page":"722","volume-title":"Proceedings of the 22nd International Conference on Extending Database Technology (EDBT \u201919)","author":"Esfahani Fatemeh","year":"2019","unstructured":"Fatemeh Esfahani, Jian Wu, Venkatesh Srinivasan, Alex Thomo, and Kui Wu. 2019. Fast truss decomposition in large-scale probabilistic graphs. In Proceedings of the 22nd International Conference on Extending Database Technology (EDBT \u201919). 722\u2013725."},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/1718487.1718518"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099626"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856323"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882913"},{"key":"e_1_3_1_24_2","unstructured":"Jiaxin Jiang. 2025. samjjx \/ pp-data. Retrieved March 5 2025 from https:\/\/github.com\/samjjx\/pp-data"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00649-y"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/HiPC.2017.00012"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2016.7840991"},{"key":"e_1_3_1_28_2","first-page":"87","volume-title":"Algorithmic Aspects of Cloud Computing","author":"Kassiano Vasileios","year":"2016","unstructured":"Vasileios Kassiano, Anastasios Gounaris, Apostolos N. Papadopoulos, and Kostas Tsichlas. 2016. Mining uncertain graphs: An overview. In Algorithmic Aspects of Cloud Computing. Lecture Notes in Computer Science, Vol. 10230. Springer, 87\u2013116."},{"key":"e_1_3_1_29_2","article-title":"SNAP Datasets: Stanford Large Network Dataset Collection","author":"Leskovec Jure","year":"2014","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved March 5, 2025 from http:\/\/snap.stanford.edu\/data","journal-title":"R"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00016"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380587"},{"key":"e_1_3_1_32_2","first-page":"Article 29, 29","article-title":"Closeness centrality on uncertain graphs","author":"Liu Zhenfang","year":"2023","unstructured":"Zhenfang Liu, Jianxiong Ye, and Zhaonian Zou. 2023. Closeness centrality on uncertain graphs. ACM Transactions on the Web 17, 4 (2023), Article 29, 29 pages.","journal-title":"ACM Transactions on the Web"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2021.3131611"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767844"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00139635"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113288"},{"key":"e_1_3_1_37_2","first-page":"353","volume-title":"Proceedings of the 2005 IEEE International Conference on Data Engineering (ICDE \u201905)","author":"Pei Jian","year":"2005","unstructured":"Jian Pei, Daxin Jiang, and Aidong Zhang. 2005. Mining cross-graph quasi-cliques in gene expression and protein interaction data. In Proceedings of the 2005 IEEE International Conference on Data Engineering (ICDE \u201905). 353\u2013354."},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920967"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3450073"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2021.3093355"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2018.8622042"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536344"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3459637.3482324"},{"key":"e_1_3_1_45_2","first-page":"Article 133, 26","article-title":"Efficient star-based truss maintenance on dynamic graphs","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), Article 133, 26 pages.","journal-title":"Proceedings of the ACM on Management of Data"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3449976"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1098\/rsos.160270"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-46671-7_16"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_3_1_50_2","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_3_1_51_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00015"},{"key":"e_1_3_1_52_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-021-00947-7"},{"key":"e_1_3_1_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300082"},{"key":"e_1_3_1_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.93"},{"key":"e_1_3_1_55_2","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448942"},{"key":"e_1_3_1_56_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/677"},{"key":"e_1_3_1_57_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-016-0943-y"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3721428","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3721428","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:09:47Z","timestamp":1750295387000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3721428"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,15]]},"references-count":56,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,30]]}},"alternative-id":["10.1145\/3721428"],"URL":"https:\/\/doi.org\/10.1145\/3721428","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,15]]},"assertion":[{"value":"2023-05-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-02-15","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-05-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}