{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,14]],"date-time":"2024-08-14T11:53:16Z","timestamp":1723636396848},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,10]]},"abstract":"\n In graph applications (e.g., biological and social networks), various analytics tasks (e.g., clustering and community search) are carried out to extract insight from large and complex graphs. Central to these tasks is the counting of the number of\n motifs<\/jats:italic>\n , which are graphs with a few nodes. Recently, researchers have developed several fast motif counting algorithms. Most of these solutions assume that graphs are deterministic, i.e., the graph edges are certain to exist. However, due to measurement and statistical prediction errors, this assumption may not hold, and hence the analysis quality can be affected. To address this issue, we examine how to count motifs on uncertain graphs, whose edges only exist probabilistically. Particularly, we propose a solution framework that can be used by existing deterministic motif counting algorithms. We further propose an approximation algorithm. Extensive experiments on real datasets show that our algorithms are more effective and efficient than existing solutions.\n <\/jats:p>","DOI":"10.14778\/3364324.3364330","type":"journal-article","created":{"date-parts":[[2020,9,11]],"date-time":"2020-09-11T03:16:00Z","timestamp":1599794160000},"page":"155-168","source":"Crossref","is-referenced-by-count":41,"title":["LINC"],"prefix":"10.14778","volume":"13","author":[{"given":"Chenhao","family":"Ma","sequence":"first","affiliation":[{"name":"The University of Hong Kong"}]},{"given":"Reynold","family":"Cheng","sequence":"additional","affiliation":[{"name":"The University of Hong Kong"}]},{"given":"Laks V. S.","family":"Lakshmanan","sequence":"additional","affiliation":[{"name":"The University of British Columbia"}]},{"given":"Tobias","family":"Grubenmann","sequence":"additional","affiliation":[{"name":"The University of Hong Kong"}]},{"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"University of New South Wales"}]},{"given":"Xiaodong","family":"Li","sequence":"additional","affiliation":[{"name":"The University of Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2019,10]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Linc: A motif counting algorithm for uncertain graphs [full version]. https:\/\/i.cs.hku.hk\/~chma2\/linc.pdf. Linc: A motif counting algorithm for uncertain graphs [full version]. https:\/\/i.cs.hku.hk\/~chma2\/linc.pdf."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/38713.38724"},{"issue":"2","key":"e_1_2_1_3_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 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":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1975.1092838"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.141"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.2203804"},{"issue":"2","key":"e_1_2_1_7_1","first-page":"103","article-title":"Determining the optimal sample size in the monte carlo experiments","volume":"7","author":"Ata M. Y.","year":"2006","unstructured":"M. Y. Ata . Determining the optimal sample size in the monte carlo experiments . Selcuk Journal of Applied Mathematics , 7 ( 2 ): 103 -- 111 , 2006 . M. Y. Ata. Determining the optimal sample size in the monte carlo experiments. Selcuk Journal of Applied Mathematics, 7(2):103--111, 2006.","journal-title":"Selcuk Journal of Applied Mathematics"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.aad9029"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350254"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018732"},{"key":"e_1_2_1_12_1","article-title":"Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with vf3","author":"Carletti V.","year":"2017","unstructured":"V. Carletti , P. Foggia , A. Saggese , and M. Vento . Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with vf3 . IEEE Transactions on Pattern Analysis and Machine Intelligence , 2017 . V. Carletti, P. Foggia, A. Saggese, and M. Vento. Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with vf3. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2017.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021940"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.88"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0004-3"},{"key":"e_1_2_1_16_1","volume-title":"Statistical distributions","author":"Evans M.","year":"2000","unstructured":"M. Evans , N. Hastings , and B. Peacock . Statistical distributions . 2000 . M. Evans, N. Hastings, and B. Peacock. Statistical distributions. 2000."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1080\/00949657908810285"},{"key":"e_1_2_1_18_1","first-page":"141","volume-title":"Annals of Discrete Mathematics","author":"Frank O.","year":"1988","unstructured":"O. Frank . Triad count statistics . In Annals of Discrete Mathematics , volume 38 , pages 141 -- 149 . Elsevier , 1988 . O. Frank. Triad count statistics. In Annals of Discrete Mathematics, volume 38, pages 141--149. Elsevier, 1988."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1986.10478342"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4064\/fm-25-1-379-387"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2007.201"},{"key":"e_1_2_1_22_1","first-page":"201","volume-title":"Sociological Theory","author":"Granovetter M.","year":"1983","unstructured":"M. Granovetter . The strength of weak ties: A network theory revisited . Sociological Theory , pages 201 -- 233 , 1983 . M. Granovetter. The strength of weak ties: A network theory revisited. Sociological Theory, pages 201--233, 1983."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71681-5_7"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737791"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_26_1","volume-title":"Discovering maximal motif cliques in large heterogeneous information networks","author":"Hu J.","year":"2019","unstructured":"J. Hu , R. Cheng , K. C. Chang , A. Sankar , Y. Fang , and B. Y. Lam . Discovering maximal motif cliques in large heterogeneous information networks . In ICDE. IEEE , Forthcoming 2019 . J. Hu, R. Cheng, K. C. Chang, A. Sankar, Y. Fang, and B. Y. Lam. Discovering maximal motif cliques in large heterogeneous information networks. In ICDE. IEEE, Forthcoming 2019."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463704"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559984"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741101"},{"key":"e_1_2_1_31_1","first-page":"1","volume-title":"ICDT","author":"Kara A.","year":"2019","unstructured":"A. Kara , H. Q. Ngo , M. Nikolic , D. Olteanu , and H. Zhang . Counting triangles under updates in worst-case optimal time . In ICDT , pages 4: 1 -- 4 :18, 2019 . A. Kara, H. Q. Ngo, M. Nikolic, D. Olteanu, and H. Zhang. Counting triangles under updates in worst-case optimal time. In ICDT, pages 4:1--4:18, 2019."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature04670"},{"key":"e_1_2_1_33_1","first-page":"1343","volume-title":"WWW","author":"Kunegis J.","year":"2013","unstructured":"J. Kunegis . Konect : the koblenz network collection . In WWW , pages 1343 -- 1350 . ACM, 2013 . J. Kunegis. Konect: the koblenz network collection. In WWW, pages 1343--1350. ACM, 2013."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021937"},{"key":"e_1_2_1_35_1","volume-title":"Probview: A flexible probabilistic database system. ACM Transactions on Database Systems (TODS), 22(3):419--469","author":"Lakshmanan L. V.","year":"1997","unstructured":"L. V. Lakshmanan , N. Leone , R. Ross , and V. S. Subrahmanian . Probview: A flexible probabilistic database system. ACM Transactions on Database Systems (TODS), 22(3):419--469 , 1997 . L. V. Lakshmanan, N. Leone, R. Ross, and V. S. Subrahmanian. Probview: A flexible probabilistic database system. ACM Transactions on Database Systems (TODS), 22(3):419--469, 1997."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367591"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2011.08.019"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4137\/CIN.S4744"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.48"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_1_42_1","first-page":"1431","volume-title":"WWW","author":"Pinar A.","year":"2017","unstructured":"A. Pinar , C. Seshadhri , and V. Vishal . Escape: Efficiently counting all 5-vertex subgraphs . In WWW , pages 1431 -- 1440 . International World Wide Web Conferences Steering Committee , 2017 . A. Pinar, C. Seshadhri, and V. Vishal. Escape: Efficiently counting all 5-vertex subgraphs. In WWW, pages 1431--1440. International World Wide Web Conferences Steering Committee, 2017."},{"key":"e_1_2_1_43_1","volume-title":"K-nearest neighbors in uncertain graphs. PVLDB, 3(1--2):997--1008","author":"Potamias M.","year":"2010","unstructured":"M. Potamias , F. Bonchi , A. Gionis , and G. Kollios . K-nearest neighbors in uncertain graphs. PVLDB, 3(1--2):997--1008 , 2010 . M. Potamias, F. Bonchi, A. Gionis, and G. Kollios. K-nearest neighbors in uncertain graphs. PVLDB, 3(1--2):997--1008, 2010."},{"key":"e_1_2_1_44_1","first-page":"488","volume-title":"Artificial Intelligence and Statistics","author":"Shervashidze N.","year":"2009","unstructured":"N. Shervashidze , S. Vishwanathan , T. Petri , K. Mehlhorn , and K. Borgwardt . Efficient graphlet kernels for large graph comparison . In Artificial Intelligence and Statistics , pages 488 -- 495 , 2009 . N. Shervashidze, S. Vishwanathan, T. Petri, K. Mehlhorn, and K. Borgwardt. Efficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics, pages 488--495, 2009."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/2031527"},{"key":"e_1_2_1_46_1","volume-title":"The string database in 2017: quality-controlled protein-protein association networks, made broadly accessible. Nucleic Acids Research, 45(D1):D362--D368","author":"Szklarczyk D.","year":"2017","unstructured":"D. Szklarczyk , J. H. Morris , H. Cook , M. Kuhn , S. Wyder , M. Simonovic , A. Santos , N. T. Doncheva , A. Roth , P. Bork , The string database in 2017: quality-controlled protein-protein association networks, made broadly accessible. Nucleic Acids Research, 45(D1):D362--D368 , 2017 . D. Szklarczyk, J. H. Morris, H. Cook, M. Kuhn, S. Wyder, M. Simonovic, A. Santos, N. T. Doncheva, A. Roth, P. Bork, et al. The string database in 2017: quality-controlled protein-protein association networks, made broadly accessible. Nucleic Acids Research, 45(D1):D362--D368, 2017."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2808719.2808731"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms3241"},{"key":"e_1_2_1_49_1","first-page":"96","volume-title":"ICDT","author":"Veldhuizen T. L.","year":"2014","unstructured":"T. L. Veldhuizen . Triejoin : A simple, worst-case optimal join algorithm . In ICDT , pages 96 -- 106 , 2014 . T. L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In ICDT, pages 96--106, 2014."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511815478"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098069"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1002\/pmic.200300636"},{"key":"e_1_2_1_53_1","volume-title":"Social computing data repository at asu","author":"Zafarani R.","year":"2009","unstructured":"R. Zafarani and H. Liu . Social computing data repository at asu , 2009 . R. Zafarani and H. Liu. Social computing data repository at asu, 2009."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3364324.3364330","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:01:43Z","timestamp":1672225303000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3364324.3364330"}},"subtitle":["a motif counting algorithm for uncertain graphs"],"short-title":[],"issued":{"date-parts":[[2019,10]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,10]]}},"alternative-id":["10.14778\/3364324.3364330"],"URL":"http:\/\/dx.doi.org\/10.14778\/3364324.3364330","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,10]]}}}