{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:13:55Z","timestamp":1761621235940,"version":"3.41.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,10,23]],"date-time":"2015-10-23T00:00:00Z","timestamp":1445558400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"GRF","award":["HKUST 617713"],"award-info":[{"award-number":["HKUST 617713"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2015,10,23]]},"abstract":"<jats:p>\n            Data in several applications can be represented as an uncertain graph whose edges are labeled with a probability of existence. Exact query processing on uncertain graphs is prohibitive for most applications, as it involves evaluation over an exponential number of instantiations. Thus, typical approaches employ Monte-Carlo sampling, which (i) draws a number of possible graphs (samples), (ii) evaluates the query on each of them, and (iii) aggregates the individual answers to generate the final result. However, this approach can also be extremely time consuming for large uncertain graphs commonly found in practice. To facilitate efficiency, we study the problem of extracting a single\n            <jats:italic>representative<\/jats:italic>\n            instance from an uncertain graph. Conventional processing techniques can then be applied on this representative to closely approximate the result on the original graph.\n          <\/jats:p>\n          <jats:p>\n            In order to maintain data utility, the representative instance should preserve structural characteristics of the uncertain graph. We start with representatives that capture the expected vertex degrees, as this is a fundamental property of the graph topology. We then generalize the notion of vertex degree to the concept of\n            <jats:italic>n<\/jats:italic>\n            -clique cardinality, that is, the number of cliques of size\n            <jats:italic>n<\/jats:italic>\n            that contain a vertex. For the first problem, we propose two methods: Average Degree Rewiring (ADR), which is based on random edge rewiring, and Approximate B-Matching (ABM), which applies graph matching techniques. For the second problem, we develop a greedy approach and a game-theoretic framework. We experimentally demonstrate, with real uncertain graphs, that indeed the representative instances can be used to answer, efficiently and accurately, queries based on several metrics such as shortest path distance, clustering coefficient, and betweenness centrality.\n          <\/jats:p>","DOI":"10.1145\/2818182","type":"journal-article","created":{"date-parts":[[2015,10,24]],"date-time":"2015-10-24T18:27:12Z","timestamp":1445711232000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["Uncertain Graph Processing through Representative Instances"],"prefix":"10.1145","volume":"40","author":[{"given":"Panos","family":"Parchas","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology"}]},{"given":"Francesco","family":"Gullo","sequence":"additional","affiliation":[{"name":"Yahoo Labs, Barcelona"}]},{"given":"Dimitris","family":"Papadias","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology"}]},{"given":"Francesco","family":"Bonchi","sequence":"additional","affiliation":[{"name":"Yahoo Labs, Barcelona"}]}],"member":"320","published-online":{"date-parts":[[2015,10,23]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/38713.38724"},{"key":"e_1_2_1_2_1","first-page":"2","article-title":"Managing uncertainty in social networks","volume":"30","author":"Adar Eytan","year":"2007","journal-title":"IEEE Data Eng. Bulle."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2008.190"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335326"},{"volume-title":"Interconnection Networks for High-performance Parallel Computers","author":"Akers Sheldon B.","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.2203804"},{"key":"e_1_2_1_7_1","first-page":"4","article-title":"A sequential importance sampling algorithm for generating random graphs with prescribed degrees","volume":"6","author":"Blitzstein Joseph","year":"2011","journal-title":"Int. Math."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350254"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623655"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.252631999"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0937490100"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0010012"},{"key":"e_1_2_1_14_1","first-page":"264","article-title":"Graphs with prescribed degrees of vertices (Hungarian)","volume":"11","author":"Erd\u00f6s Paul","year":"1960","journal-title":"Mat. Lapok"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316229"},{"volume-title":"Algorithms ESA","series-title":"Lecture Notes in Computer Science","author":"Fraigniaud Pierre","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","first-page":"1","article-title":"Centrality measures and the importance of generalist species in pollination networks","volume":"7","author":"Gonzalez Ana M.","year":"2010","journal-title":"Ecological Complex."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0110037"},{"volume-title":"Research Trends in Combinatorial Optimization","author":"Hougardy Stefan","key":"e_1_2_1_19_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463704"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.124"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020569"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002941"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"volume-title":"Proceedings of the International Conference on Extending Database Technology (EDBT'14)","year":"2014","author":"Khan Arijit","key":"e_1_2_1_25_1"},{"volume-title":"Proceedings of the International Congress of Mathematicians (ICM'06)","year":"2006","author":"Kleinberg Jon","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2011.243"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.1116869"},{"key":"e_1_2_1_29_1","unstructured":"Jure Leskovec Deepayan Chakrabarti Jon Kleinberg Christos Faloutsos and Zoubin Ghahramani. 2010. Kronecker graphs: An approach to modeling networks. J. Mach. Learn. Res. 11 (March 2010) 985--1042. http:\/\/dl.acm.org\/citation.cfm?id=1756006.1756039   Jure Leskovec Deepayan Chakrabarti Jon Kleinberg Christos Faloutsos and Zoubin Ghahramani. 2010. Kronecker graphs: An approach to modeling networks. J. Mach. Learn. Res. 11 (March 2010) 985--1042. http:\/\/dl.acm.org\/citation.cfm?id=1756006.1756039"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150479"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816709"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956972"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1038\/35082140"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.11"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature10011"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(70)80033-3"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159913.1159930"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.soc.27.1.415"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_48"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1980.12"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.915688"},{"volume-title":"Position Paper. In Proceedings of the 3rd Workshop on Approximate and Randomized Algorithms for Communication Networks (ARACNE'02)","author":"Mihail Milena","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1996.0044"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816710"},{"key":"e_1_2_1_45_1","first-page":"2","article-title":"On the complexity of the subgraph problem","volume":"26","author":"Ne\u0161et\u0161ril Jaroslav","year":"1985","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2593668"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920967"},{"volume-title":"State-of-the Art in Performance Modeling and Simulation. Gordon and Breach","author":"Rubino Gerardo","key":"e_1_2_1_48_1"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/11799511_5"},{"key":"e_1_2_1_50_1","unstructured":"Pang-Ning Tan Michael Steinbach and Vipin Kumar. 2005. Introduction to Data Mining. Addison-Wesley Longman Publishing Co. Inc. Boston MA.  Pang-Ning Tan Michael Steinbach and Vipin Kumar. 2005. Introduction to Data Mining. Addison-Wesley Longman Publishing Co. Inc. Boston MA."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/633025.633040"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/MNET.2010.5634437"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_54_1","first-page":"1","article-title":"STRING: A database of predicted functional associations between proteins","volume":"31","author":"von Mering Christian","year":"2003","journal-title":"Nucleic Acids Res."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12026-8_14"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311908"},{"key":"e_1_2_1_57_1","first-page":"11","article-title":"Efficient subgraph search over large uncertain graphs","volume":"4","author":"Yuan Ye","year":"2011","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447891"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.80"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818182","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2818182","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:39:01Z","timestamp":1750221541000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2818182"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,10,23]]},"references-count":59,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,10,23]]}},"alternative-id":["10.1145\/2818182"],"URL":"https:\/\/doi.org\/10.1145\/2818182","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2015,10,23]]},"assertion":[{"value":"2014-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-10-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}