{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T05:46:06Z","timestamp":1777614366173,"version":"3.51.4"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T00:00:00Z","timestamp":1662163200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T00:00:00Z","timestamp":1662163200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["20K11940"],"award-info":[{"award-number":["20K11940"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Soc. Netw. Anal. Min."],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s13278-022-00956-y","type":"journal-article","created":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T13:39:20Z","timestamp":1662212360000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient computation of expected motif frequency in uncertain graphs by exploiting possible world marginalization and motif transition"],"prefix":"10.1007","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3448-8182","authenticated-orcid":false,"given":"Takayasu","family":"Fushimi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazumi","family":"Saito","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroshi","family":"Motoda","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,9,3]]},"reference":[{"key":"956_CR1","doi-asserted-by":"publisher","unstructured":"Ahmed NK, Neville J, Rossi RA, Duffield N (2015) Efficient graphlet counting for large networks. In: 2015 IEEE international conference on data mining, pp 1\u201310 https:\/\/doi.org\/10.1109\/ICDM.2015.141","DOI":"10.1109\/ICDM.2015.141"},{"key":"956_CR2","doi-asserted-by":"publisher","unstructured":"Boekhout H, Kosters W, Takes F (2019) Efficiently counting complex multilayer temporal motifs in large-scale networks. Comput Soc Netw https:\/\/doi.org\/10.1186\/s40649-019-0068-z","DOI":"10.1186\/s40649-019-0068-z"},{"issue":"4","key":"956_CR3","doi-asserted-by":"publisher","first-page":"472","DOI":"10.1145\/3186728.3164143","volume":"11","author":"M Ceccarello","year":"2017","unstructured":"Ceccarello M, Fantozzi C, Pietracaprina A, Pucci G, Vandin F (2017) Clustering uncertain graphs. Proc  VLDB Endow 11(4):472\u2013484","journal-title":"Proc VLDB Endow"},{"key":"956_CR4","doi-asserted-by":"publisher","unstructured":"Fushimi T, Saito K, Motoda H (2021) Efficient analytical computation of expected frequency of motifs of small size by marginalization in uncertain network. In: Proceedings of the 2021 IEEE\/ACM international conference on advances in social networks analysis and mining, ASONAM\u201921, 1\u20138. Association for computing machinery, New York, NY, USA. https:\/\/doi.org\/10.1145\/3487351.3488275","DOI":"10.1145\/3487351.3488275"},{"key":"956_CR5","doi-asserted-by":"crossref","unstructured":"Grochow JA, Kellis M (2007) Network motif discovery using subgraph enumeration and symmetry-breaking. In: Proceedings of the 11th annual international conference on research in computational molecular biology, RECOMB\u201907. Springer, Berlin, pp 92\u2013106","DOI":"10.1007\/978-3-540-71681-5_7"},{"issue":"2","key":"956_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pone.0171428","volume":"12","author":"T Hocevar","year":"2017","unstructured":"Hocevar T, Dem\u0161ar J (2017) Combinatorial algorithm for counting small induced graphs and orbits. PLoS ONE 12(2):1\u201317. https:\/\/doi.org\/10.1371\/journal.pone.0171428","journal-title":"PLoS ONE"},{"key":"956_CR7","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1016\/j.physa.2007.02.102","volume":"381","author":"R Itzhack","year":"2007","unstructured":"Itzhack R, Mogilevski Y, Louzoun Y (2007) An optimal algorithm for counting network motifs. Physica A 381:482\u2013490. https:\/\/doi.org\/10.1016\/j.physa.2007.02.102","journal-title":"Physica A"},{"key":"956_CR8","doi-asserted-by":"crossref","unstructured":"Jin R, Liu L, Aggarwal CC (2011a) Discovering highly reliable subgraphs in uncertain graphs. In: Proceedings of the 17th ACM SIGKDD international conference on knowledge discovery and data mining, KDD\u201911. ACM, New York, NY, USA, pp 992\u20131000","DOI":"10.1145\/2020408.2020569"},{"issue":"9","key":"956_CR9","doi-asserted-by":"publisher","first-page":"551","DOI":"10.14778\/2002938.2002941","volume":"4","author":"R Jin","year":"2011","unstructured":"Jin R, Liu L, Ding B, Wang H (2011b) Distance-constraint reachability computation in uncertain graphs. Proc VLDB Endow 4(9):551\u2013562","journal-title":"Proc VLDB Endow"},{"issue":"02","key":"956_CR10","first-page":"026113:1","volume":"18","author":"P Kaluza","year":"2008","unstructured":"Kaluza P, Vingron M, Mikhailov AS (2008) Self-correcting networks: function, robustness, and motif distributions in biological signal processing. Chaos Interdiscipl J Nonlinear Sci 18(02):026113:1-026113:17","journal-title":"Chaos Interdiscipl J Nonlinear Sci"},{"key":"956_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-01860-2","volume-title":"On uncertain graphs","author":"A Khan","year":"2018","unstructured":"Khan A, Ye Y, Chen L, Jagadish HV (2018) On uncertain graphs. Morgan & Claypool, San Rafael"},{"key":"956_CR12","doi-asserted-by":"publisher","unstructured":"Kim J, Li ML, Candan K, Sapino M (2017) Personalized PageRank in uncertain graphs with mutually exclusive edges. In: Proceedings of the 40th international ACM SIGIR conference on research and development in information retrieval, SIGIR\u201917. ACM, New York, NY, USA, pp 525\u2013534. https:\/\/doi.org\/10.1145\/3077136.3080794","DOI":"10.1145\/3077136.3080794"},{"key":"956_CR13","doi-asserted-by":"publisher","DOI":"10.1017\/9781316216002","volume-title":"Complex networks: principles, methods and applications","author":"V Latora","year":"2017","unstructured":"Latora V, Nicosia V, Russo G (2017) Complex networks: principles, methods and applications, 1st edn. Cambridge University Press, Cambridge","edition":"1"},{"key":"956_CR14","unstructured":"Leskovec J, Krevl A (2014) SNAP datasets: stanford large network dataset collection http:\/\/snap.stanford.edu\/data"},{"issue":"12","key":"956_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pone.0050093","volume":"7","author":"X Li","year":"2012","unstructured":"Li X, Stones RJ, Wang H, Deng H, Liu X, Wang G (2012) Netmode: network motif detection without nauty. PLoS ONE 7(12):1\u20139. https:\/\/doi.org\/10.1371\/journal.pone.0050093","journal-title":"PLoS ONE"},{"key":"956_CR16","doi-asserted-by":"crossref","unstructured":"Liu L, Jin R, Aggarwal C, Shen Y (2012) Reliable clustering on uncertain graphs. In: 2012 IEEE 12th international conference on data mining, pp 459\u2013468","DOI":"10.1109\/ICDM.2012.11"},{"key":"956_CR17","doi-asserted-by":"publisher","unstructured":"Liu P, Benson AR, Charikar M (2019) Sampling methods for counting temporal motifs. In: Proceedings of the twelfth ACM international conference on web search and data mining, WSDM\u201919. Association for Computing Machinery, New York, NY, USA, pp 294\u2013302. https:\/\/doi.org\/10.1145\/3289600.3290988","DOI":"10.1145\/3289600.3290988"},{"key":"956_CR18","doi-asserted-by":"crossref","unstructured":"Ma C, Cheng R, Lakshmanan LVS, Grubenmann T, Fang Y, Li X (2019) Linc: a motif counting algorithm for uncertain graphs. Proc VLDB Endow 13(2), 155\u2013168. https:\/\/doi.org\/10.14778\/3364324.3364330","DOI":"10.14778\/3364324.3364330"},{"issue":"2","key":"956_CR19","doi-asserted-by":"publisher","first-page":"810","DOI":"10.1016\/j.comnet.2011.08.019","volume":"56","author":"D Marcus","year":"2012","unstructured":"Marcus D, Shavitt Y (2012) Rage\u2014a rapid graphlet enumerator for large networks. Comput Netw 56(2):810\u2013819. https:\/\/doi.org\/10.1016\/j.comnet.2011.08.019","journal-title":"Comput Netw"},{"key":"956_CR20","unstructured":"Marinka Zitnik Rok Sosic SM, Leskovec J (2018) BioSNAP datasets: stanford biomedical network dataset collection. http:\/\/snap.stanford.edu\/biodata"},{"issue":"5569","key":"956_CR21","doi-asserted-by":"publisher","first-page":"910","DOI":"10.1126\/science.1065103","volume":"296","author":"S Maslov","year":"2002","unstructured":"Maslov S, Sneppen K (2002) Specificity and stability in topology of protein networks. Science 296(5569):910\u2013913. https:\/\/doi.org\/10.1126\/science.1065103","journal-title":"Science"},{"issue":"5594","key":"956_CR22","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1126\/science.298.5594.824","volume":"298","author":"R Milo","year":"2002","unstructured":"Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U (2002) Network motifs: simple building blocks of complex networks. Science (New York, NY) 298(5594):824\u2013827. https:\/\/doi.org\/10.1126\/science.298.5594.824","journal-title":"Science (New York, NY)"},{"key":"956_CR23","doi-asserted-by":"publisher","unstructured":"Mukherjee AP, Xu P, Tirthapura S (2015) Mining maximal cliques from an uncertain graph. In: 2015 IEEE 31st international conference on data engineering, pp 243\u2013254. https:\/\/doi.org\/10.1109\/ICDE.2015.7113288","DOI":"10.1109\/ICDE.2015.7113288"},{"key":"956_CR24","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1137\/S003614450342480","volume":"45","author":"MEJ Newman","year":"2003","unstructured":"Newman MEJ (2003) The structure and function of complex networks. SIAM Rev 45:167\u2013256","journal-title":"SIAM Rev"},{"key":"956_CR25","doi-asserted-by":"crossref","unstructured":"Pfeiffer JJ, Neville J (2011) Methods to determine node centrality and clustering in graphs with uncertain structure. In: Proceedings of the fifth international conference on weblogs and social media. The AAAI Press, pp 590\u2013593","DOI":"10.1609\/icwsm.v5i1.14187"},{"key":"956_CR26","doi-asserted-by":"publisher","unstructured":"Pinar A, Seshadhri C, Vishal V (2017) Escape: efficiently counting all 5-vertex subgraphs. In: Proceedings of the 26th international conference on world wide web, WWW \u201917, 1431\u20131440. International world wide web conferences steering committee, Republic and Canton of Geneva, CHE. https:\/\/doi.org\/10.1145\/3038912.3052597","DOI":"10.1145\/3038912.3052597"},{"issue":"1\u20132","key":"956_CR27","doi-asserted-by":"publisher","first-page":"997","DOI":"10.14778\/1920841.1920967","volume":"3","author":"M Potamias","year":"2010","unstructured":"Potamias M, Bonchi F, Gionis A, Kollios G (2010) K-nearest neighbors in uncertain graphs. Proc VLDB Endow 3(1\u20132):997\u20131008","journal-title":"Proc VLDB Endow"},{"key":"956_CR28","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-018-2236-9","author":"Y Ren","year":"2018","unstructured":"Ren Y, Sarkar A, Kahveci T (2018) Promote: an efficient algorithm for counting independent motifs in uncertain network topologies. BMC Bioinform. https:\/\/doi.org\/10.1186\/s12859-018-2236-9","journal-title":"BMC Bioinform"},{"key":"956_CR29","doi-asserted-by":"publisher","unstructured":"Ribeiro P, Silva F (2010) G-tries: an efficient data structure for discovering network motifs. SAC\u201910, 1559\u20131566. Association for Computing Machinery, New York, NY, USA. https:\/\/doi.org\/10.1145\/1774088.1774422","DOI":"10.1145\/1774088.1774422"},{"key":"956_CR30","doi-asserted-by":"publisher","unstructured":"Sarpe I, Vandin F (2021) OdeN: simultaneous approximation of multiple motif counts in large temporal networks, pp 1568\u20131577. Association for Computing Machinery, New York, NY, USA. https:\/\/doi.org\/10.1145\/3459637.3482459","DOI":"10.1145\/3459637.3482459"},{"key":"956_CR31","doi-asserted-by":"publisher","unstructured":"Todor A, Dobra A, Kahveci T (2015) Counting motifs in probabilistic biological networks. In: Proceedings of the 6th ACM conference on bioinformatics, computational biology and health informatics, BCB\u201915, 116\u2013125. Association for Computing Machinery, New York, NY, USA. https:\/\/doi.org\/10.1145\/2808719.2808731","DOI":"10.1145\/2808719.2808731"},{"key":"956_CR32","doi-asserted-by":"publisher","first-page":"2241","DOI":"10.1038\/ncomms3241","volume":"4","author":"N Tran","year":"2013","unstructured":"Tran N, Choi KP, Zhang L (2013) Counting motifs in the human interactome. Nat Commun 4:2241. https:\/\/doi.org\/10.1038\/ncomms3241","journal-title":"Nat Commun"},{"key":"956_CR33","doi-asserted-by":"publisher","unstructured":"Wernicke S (2005) A faster algorithm for detecting network motifs. In: Proceedings of the 5th international conference on algorithms in bioinformatics, WABI\u201905. Springer, Berlin, Heidelberg, pp 165\u2013177. https:\/\/doi.org\/10.1007\/11557067_14","DOI":"10.1007\/11557067_14"},{"issue":"9","key":"956_CR34","doi-asserted-by":"publisher","first-page":"1203","DOI":"10.1109\/TKDE.2010.80","volume":"22","author":"Z Zou","year":"2010","unstructured":"Zou Z, Li J, Gao H, Zhang S (2010) Mining frequent subgraph patterns from uncertain graph data. IEEE Trans Knowl Data Eng 22(9):1203\u20131218. https:\/\/doi.org\/10.1109\/TKDE.2010.80","journal-title":"IEEE Trans Knowl Data Eng"}],"container-title":["Social Network Analysis and Mining"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-022-00956-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13278-022-00956-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13278-022-00956-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T13:22:26Z","timestamp":1672665746000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s13278-022-00956-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,3]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["956"],"URL":"https:\/\/doi.org\/10.1007\/s13278-022-00956-y","relation":{},"ISSN":["1869-5450","1869-5469"],"issn-type":[{"value":"1869-5450","type":"print"},{"value":"1869-5469","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,3]]},"assertion":[{"value":"18 March 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 August 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 September 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors declare no financial and non-financial competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"126"}}