{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,24]],"date-time":"2026-10-24T17:11:44Z","timestamp":1792861904021,"version":"4.5.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,8]]},"abstract":"<jats:p>\n            Large-scale, highly-interconnected networks pervade both our society and the natural world around us. Uncertainty, on the other hand, is inherent in the underlying data due to a variety of reasons, such as noisy measurements, lack of precise information needs, inference and prediction models, or explicit manipulation, e.g., for privacy purposes. Therefore, uncertain, or probabilistic, graphs are increasingly used to represent noisy linked data in many emerging application scenarios, and they have recently become a hot topic in the database research community. While many classical graph algorithms such as reachability and shortest path queries become #\n            <jats:bold>P<\/jats:bold>\n            -complete, and hence, more expensive in uncertain graphs; various complex queries are also emerging over uncertain networks, such as pattern matching, information diffusion, and influence maximization queries. In this tutorial, we discuss the sources of uncertain graphs and their applications, uncertainty modeling, as well as the complexities and algorithmic advances on uncertain graphs processing in the context of both classical and emerging graph queries. We emphasize the current challenges and highlight some future research directions.\n          <\/jats:p>","DOI":"10.14778\/2824032.2824133","type":"journal-article","created":{"date-parts":[[2015,9,16]],"date-time":"2015-09-16T12:18:17Z","timestamp":1442405897000},"page":"2042-2043","source":"Crossref","is-referenced-by-count":22,"title":["On uncertain graphs modeling and queries"],"prefix":"10.14778","volume":"8","author":[{"given":"Arijit","family":"Khan","sequence":"first","affiliation":[{"name":"ETH Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,8]]},"reference":[{"issue":"2","key":"e_1_2_1_1_1","first-page":"15","article-title":"Managing Uncertainty","volume":"30","author":"Adar E.","year":"2007","unstructured":"E. Adar and C. Re . Managing Uncertainty in Social Networks. IEEE Data Eng. Bull. , 30 ( 2 ): 15 -- 22 , 2007 . E. Adar and C. Re. Managing Uncertainty in Social Networks. IEEE Data Eng. Bull., 30(2):15--22, 2007.","journal-title":"Social Networks. IEEE Data Eng. Bull."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-09690-2","volume-title":"Managing and Mining Uncertain Data","author":"Aggarwal C. C.","year":"2009","unstructured":"C. C. Aggarwal . Managing and Mining Uncertain Data . Springer , 2009 . C. C. Aggarwal. Managing and Mining Uncertain Data. Springer, 2009."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350254"},{"key":"e_1_2_1_4_1","volume-title":"SIGMOD","author":"Bollacker K.","year":"2008","unstructured":"K. Bollacker , C. Evans , P. Paritosh , T. Sturge , and J. Taylor . Freebase: A Collaboratively Created Graph Database for Structuring Human Knowledge . In SIGMOD , 2008 . 10.1145\/1376616.1376746 K. Bollacker, C. Evans, P. Paritosh, T. Sturge, and J. Taylor. Freebase: A Collaboratively Created Graph Database for Structuring Human Knowledge. In SIGMOD, 2008. 10.1145\/1376616.1376746"},{"key":"e_1_2_1_5_1","volume-title":"KDD","author":"Castillo C.","year":"2012","unstructured":"C. Castillo , W. Chen , and L. V. S. Lakshmanan . Information and Influence Spread in Social Networks . In KDD , 2012 . C. Castillo, W. Chen, and L. V. S. Lakshmanan. Information and Influence Spread in Social Networks. In KDD, 2012."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739084"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002941"},{"key":"e_1_2_1_8_1","volume-title":"SIGMOD","author":"Kaoudi Z.","year":"2014","unstructured":"Z. Kaoudi and I. Manolescu . Cloud-based RDF Data Management . In SIGMOD , 2014 . 10.1145\/2588555.2588891 Z. Kaoudi and I. Manolescu. Cloud-based RDF Data Management. In SIGMOD, 2014. 10.1145\/2588555.2588891"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.143"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989341"},{"key":"e_1_2_1_12_1","volume-title":"ICDE","author":"Moustafa W. E.","year":"2014","unstructured":"W. E. Moustafa , A. Kimmig , A. Deshpande , and L. Getoor . Subgraph Pattern Matching over Uncertain Graphs with Identity Linkage Uncertainty . In ICDE , 2014 . W. E. Moustafa, A. Kimmig, A. Deshpande, and L. Getoor. Subgraph Pattern Matching over Uncertain Graphs with Identity Linkage Uncertainty. In ICDE, 2014."},{"key":"e_1_2_1_13_1","volume-title":"SIGMOD","author":"Parchas P.","year":"2014","unstructured":"P. Parchas , F. Gullo , D. Papadias , and F. Bonchi . The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs . In SIGMOD , 2014 . 10.1145\/2588555.2593668 P. Parchas, F. Gullo, D. Papadias, and F. Bonchi. The Pursuit of a Good Possible World: Extracting Representative Instances of Uncertain Graphs. In SIGMOD, 2014. 10.1145\/2588555.2593668"},{"key":"e_1_2_1_14_1","volume-title":"SIGMO","author":"Pei J.","year":"2008","unstructured":"J. Pei , M. Hua , Y. Tao , and X. Lin . Query Answering Techniques on Uncertain and Probabilistic Data: Tutorial Summary . In SIGMO , 2008 . 10.1145\/1376616.1376774 J. Pei, M. Hua, Y. Tao, and X. Lin. Query Answering Techniques on Uncertain and Probabilistic Data: Tutorial Summary. In SIGMO, 2008. 10.1145\/1376616.1376774"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920967"},{"key":"e_1_2_1_16_1","volume-title":"DILS","author":"Sevon P.","year":"2006","unstructured":"P. Sevon , L. Eronen , P. Hintsanen , K. Kulovesi , and H. Toivonen . Link Discovery in Graphs Derived from Biological Databases . In DILS , 2006 . 10.1007\/11799511_5 P. Sevon, L. Eronen, P. Hintsanen, K. Kulovesi, and H. Toivonen. Link Discovery in Graphs Derived from Biological Databases. In DILS, 2006. 10.1007\/11799511_5"},{"key":"e_1_2_1_17_1","series-title":"SIAM J. on Computing","volume-title":"The Complexity of Enumeration and Reliability Problems","author":"Valiant L. G.","year":"1979","unstructured":"L. G. Valiant . The Complexity of Enumeration and Reliability Problems . SIAM J. on Computing , 1979 . L. G. Valiant. The Complexity of Enumeration and Reliability Problems. SIAM J. on Computing, 1979."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350263"},{"key":"e_1_2_1_19_1","first-page":"519","volume-title":"CIKM","author":"Yuan Y.","year":"2014","unstructured":"Y. Yuan , G. Wang , and L. Chen . Pattern match query in a large uncertain graph . In CIKM , pages 519 -- 528 , 2014 . 10.1145\/2661829.2661868 Y. Yuan, G. Wang, and L. Chen. Pattern match query in a large uncertain graph. In CIKM, pages 519--528, 2014. 10.1145\/2661829.2661868"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311908"},{"key":"e_1_2_1_21_1","volume-title":"Efficient Subgraph Search over Large Uncertain Graphs. PVLDB, 4(11)","author":"Yuan Y.","year":"2011","unstructured":"Y. Yuan , G. Wang , H. Wang , and L. Chen . Efficient Subgraph Search over Large Uncertain Graphs. PVLDB, 4(11) , 2011 . Y. Yuan, G. Wang, H. Wang, and L. Chen. Efficient Subgraph Search over Large Uncertain Graphs. PVLDB, 4(11), 2011."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835885"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2824032.2824133","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:03:43Z","timestamp":1672221823000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2824032.2824133"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8]]},"references-count":22,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["10.14778\/2824032.2824133"],"URL":"https:\/\/doi.org\/10.14778\/2824032.2824133","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,8]]}}}