{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T04:12:20Z","timestamp":1759032740520,"version":"3.41.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,12,1]],"date-time":"2017-12-01T00:00:00Z","timestamp":1512086400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,12]]},"abstract":"<jats:p>\n            An uncertain graph \ud835\udca2 =\n            <jats:italic>(V, E, p<\/jats:italic>\n            :\n            <jats:italic>E<\/jats:italic>\n            \u2192 (0, 1]) can be viewed as a probability space whose outcomes (referred to as\n            <jats:italic>possible worlds<\/jats:italic>\n            ) are subgraphs of \ud835\udca2 where any edge\n            <jats:italic>e<\/jats:italic>\n            \u03b5\n            <jats:italic>E<\/jats:italic>\n            occurs with probability\n            <jats:italic>p<\/jats:italic>\n            (\n            <jats:italic>e<\/jats:italic>\n            ), independently of the other edges. These graphs naturally arise in many application domains where data management systems are required to cope with uncertainty in interrelated data, such as computational biology, social network analysis, network reliability, and privacy enforcement, among the others. For this reason, it is important to devise fundamental querying and mining primitives for uncertain graphs. This paper contributes to this endeavor with the development of novel strategies for clustering uncertain graphs. Specifically, given an uncertain graph \ud835\udca2 and an integer\n            <jats:italic>k<\/jats:italic>\n            , we aim at partitioning its nodes into\n            <jats:italic>k<\/jats:italic>\n            clusters, each featuring a distinguished center node, so to maximize the minimum\/average connection probability of any node to its cluster's center, in a random possible world. We assess the NP-hardness of maximizing the minimum connection probability, even in the presence of an oracle for the connection probabilities, and develop efficient approximation algorithms for both problems and some useful variants. Unlike previous works in the literature, our algorithms feature provable approximation guarantees and are capable to keep the granularity of the returned clustering under control. Our theoretical findings are complemented with several experiments that compare our algorithms against some relevant competitors, with respect to both running-time and quality of the returned clusterings.\n          <\/jats:p>","DOI":"10.1145\/3186728.3164143","type":"journal-article","created":{"date-parts":[[2019,11,20]],"date-time":"2019-11-20T10:54:54Z","timestamp":1574247294000},"page":"472-484","source":"Crossref","is-referenced-by-count":36,"title":["Clustering uncertain graphs"],"prefix":"10.14778","volume":"11","author":[{"given":"Matteo","family":"Ceccarello","sequence":"first","affiliation":[{"name":"University of Padova (Italy)"}]},{"given":"Carlo","family":"Fantozzi","sequence":"additional","affiliation":[{"name":"University of Padova (Italy)"}]},{"given":"Andrea","family":"Pietracaprina","sequence":"additional","affiliation":[{"name":"University of Padova (Italy)"}]},{"given":"Geppino","family":"Pucci","sequence":"additional","affiliation":[{"name":"University of Padova (Italy)"}]},{"given":"Fabio","family":"Vandin","sequence":"additional","affiliation":[{"name":"University of Padova (Italy)"}]}],"member":"320","published-online":{"date-parts":[[2017,12]]},"reference":[{"issue":"2","key":"e_1_2_1_1_1","first-page":"15","article-title":"Managing uncertainty in social networks","volume":"30","author":"Adar E.","year":"2007","unstructured":"E. Adar and C. Re . Managing uncertainty in social networks . IEEE Data Engineering Bullettin , 30 ( 2 ): 15 -- 22 , 2007 . E. Adar and C. Re. Managing uncertainty in social networks. IEEE Data Engineering Bullettin, 30(2):15--22, 2007.","journal-title":"IEEE Data Engineering Bullettin"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1513922"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.2203804"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TR.1986.4335422"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164209"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1090191.1080108"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350254"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376746"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634144"},{"key":"e_1_2_1_10_1","volume-title":"Clustering uncertain graphs. CoRR, abs\/1612.06675","author":"Ceccarello M.","year":"2016","unstructured":"M. Ceccarello , C. Fantozzi , A. Pietracaprina , G. Pucci , and F. Vandin . Clustering uncertain graphs. CoRR, abs\/1612.06675 , 2016 . M. Ceccarello, C. Fantozzi, A. Pietracaprina, G. Pucci, and F. Vandin. Clustering uncertain graphs. CoRR, abs\/1612.06675, 2016."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/365411.365555"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1074\/mcp.M600381-MCP200"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICICIS.2011.138"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature04532"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2007.201"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.123"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.2.180"},{"key":"e_1_2_1_20_1","volume-title":"May","author":"Institute of Bioinformatics and Systems Biology.","year":"2006","unstructured":"Institute of Bioinformatics and Systems Biology. The MIPS comprehensive yeast genome database. ftp:\/\/ftpmips.gsf.de\/fungi\/Saccharomycetes\/CYGD\/ , May 2006 . Institute of Bioinformatics and Systems Biology. The MIPS comprehensive yeast genome database. ftp:\/\/ftpmips.gsf.de\/fungi\/Saccharomycetes\/CYGD\/, May 2006."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002941"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.243"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature04670"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.11"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkh092"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1076315"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2818182"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-010-0185-7"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920967"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2007.05.001"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723734"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/040608635"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/500776"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3186728.3164143","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3186728.3164143","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:31Z","timestamp":1750273651000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3186728.3164143"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["10.1145\/3186728.3164143"],"URL":"https:\/\/doi.org\/10.1145\/3186728.3164143","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2017,12]]}}}