{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T16:47:46Z","timestamp":1761324466033,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,8,12]],"date-time":"2022-08-12T00:00:00Z","timestamp":1660262400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,12]],"date-time":"2022-08-12T00:00:00Z","timestamp":1660262400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["22K12279","20K11940"],"award-info":[{"award-number":["22K12279","20K11940"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This study tackles the problem of extracting the node roles in uncertain graphs based on network motifs. Uncertain graphs are useful for modeling information diffusion phenomena because the presence or absence of edges is stochastically determined. In such an uncertain graph, the node role also changes stochastically according to the presence or absence of edges, so approximate calculation using a huge number of samplings is common. However, the calculation load is very large, even for a small graph. We propose a method to extract uncertain node roles with high accuracy and high speed by ensembling a large number of sampled graphs and efficiently searching for all other transitionable roles. This method provides highly accurate results compared to simple sampling and ensembling methods that do not consider the transition to other roles. In our evaluation experiment, we use real-world graphs artificially assigned uniform and non-uniform edge existence probabilities. The results show that the proposed method outperforms an existing method previously reported by the authors, which is the basis of the proposed method, as well as another current method based on the state-of-the-art algorithm, in terms of efficiency and accuracy.<\/jats:p>","DOI":"10.1007\/s41109-022-00496-6","type":"journal-article","created":{"date-parts":[[2022,8,12]],"date-time":"2022-08-12T08:08:25Z","timestamp":1660291705000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Improving accuracy of expected frequency of uncertain roles based on efficient ensembling"],"prefix":"10.1007","volume":"7","author":[{"given":"Soshi","family":"Naito","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3448-8182","authenticated-orcid":false,"given":"Takayasu","family":"Fushimi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,8,12]]},"reference":[{"key":"496_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"},{"issue":"4","key":"496_CR2","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"},{"issue":"1","key":"496_CR3","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1080\/0022250X.1994.9990134","volume":"19","author":"M Everett","year":"1994","unstructured":"Everett M, Borgatti S (1994) Regular equivalence: general theory. J Math Sociol 19(1):29\u201352","journal-title":"J Math Sociol"},{"key":"496_CR4","doi-asserted-by":"crossref","unstructured":"Gilpin S, Eliassi-Rad T, Davidson I (2013) Guided learning for role discovery (glrd): Framework, algorithms, and applications. In: Proceedings of the 19th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, New York, pp 113\u2013121","DOI":"10.1145\/2487575.2487620"},{"key":"496_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":"36","key":"496_CR6","doi-asserted-by":"publisher","first-page":"13333","DOI":"10.1073\/pnas.0801870105","volume":"105","author":"C Guerrero","year":"2008","unstructured":"Guerrero C, Milenkovi\u0107 T, Pr\u017eulj N, Kaiser P, Huang L (2008) Characterization of the proteasome interaction network using a QTAX-based tag-team strategy and protein interaction network analysis. Proc Natl Acad Sci 105(36):13333\u201313338. https:\/\/doi.org\/10.1073\/pnas.0801870105","journal-title":"Proc Natl Acad Sci"},{"key":"496_CR7","doi-asserted-by":"crossref","unstructured":"Henderson K, Gallagher B, Eliassi-Rad T, Tong H, Basu S, Akoglu L, Koutra D, Faloutsos C, Li L (2012) Rolx: structural role extraction & mining in large graphs. In: Proceedings of the 18th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, pp 1231\u20131239","DOI":"10.1145\/2339530.2339723"},{"key":"496_CR8","doi-asserted-by":"crossref","unstructured":"Henderson K, Gallagher B, Li L, Akoglu L, Eliassi-Rad T, Tong H, Faloutsos C (2011) It\u2019s who you know: graph mining using recursive structural features. In: Proceedings of the 17th ACM SIGKDD international conference on knowledge discovery and data mining. ACM, New York, pp 663\u2013671","DOI":"10.1145\/2020408.2020512"},{"key":"496_CR9","doi-asserted-by":"crossref","unstructured":"Hu J, Cheng R, Huang Z, Fang Y, Luo S (2017) On embedding uncertain graphs. In: ACM on conference on information and knowledge management, vol 123, pp 157\u2013166","DOI":"10.1145\/3132847.3132885"},{"key":"496_CR10","unstructured":"https:\/\/github.com\/fuppo27\/graph_dataset"},{"key":"496_CR11","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. Phys A Stat Mech Appl 381:482\u2013490. https:\/\/doi.org\/10.1016\/j.physa.2007.02.102","journal-title":"Phys A Stat Mech Appl"},{"key":"496_CR12","doi-asserted-by":"crossref","unstructured":"Klimt B, Yang Y (2004) The enron corpus: a new dataset for email classification research. In: Boulicaut JF, Esposito F, Giannotti F, Pedreschi D (eds) Machine learning: ECML 2004. Springer, Berlin, pp 217\u2013226","DOI":"10.1007\/978-3-540-30115-8_22"},{"key":"496_CR13","doi-asserted-by":"publisher","DOI":"10.3390\/e19110631","author":"TO Kv\u00e5lseth","year":"2017","unstructured":"Kv\u00e5lseth TO (2017) On normalized mutual information: measure derivations and properties. Entropy. https:\/\/doi.org\/10.3390\/e19110631","journal-title":"Entropy"},{"key":"496_CR14","unstructured":"Leskovec J, Krevl A (2014) SNAP datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data"},{"issue":"1","key":"496_CR15","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1080\/0022250X.1971.9989788","volume":"1","author":"F Lorrain","year":"1971","unstructured":"Lorrain F, White H (1971) Structural equivalence of individuals in social networks. J Math Sociol 1(1):49\u201380","journal-title":"J Math Sociol"},{"issue":"2","key":"496_CR16","doi-asserted-by":"publisher","first-page":"155","DOI":"10.14778\/3364324.3364330","volume":"13","author":"C Ma","year":"2019","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","journal-title":"Proc VLDB Endow"},{"key":"496_CR17","unstructured":"Marinka Zitnik Rok Sosi\u010d SM, Leskovec J (2018) BioSNAP datasets: Stanford biomedical network dataset collection. http:\/\/snap.stanford.edu\/biodata"},{"issue":"12","key":"496_CR18","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pone.0114503","volume":"9","author":"MD McDonnell","year":"2014","unstructured":"McDonnell MD, Yaveroglu ON, Schmerl BA, Iannella N, Ward LM (2014) Motif-role-fingerprints: the building-blocks of motifs, clustering-coefficients and transitivities in directed networks. PLoS ONE 9(12):1\u201325. https:\/\/doi.org\/10.1371\/journal.pone.0114503","journal-title":"PLoS ONE"},{"issue":"5594","key":"496_CR19","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 298(5594):824\u2013827. https:\/\/doi.org\/10.1126\/science.298.5594.824","journal-title":"Science"},{"key":"496_CR20","doi-asserted-by":"crossref","unstructured":"Naito S, Fushimi T (2021) Motif-role extraction in uncertain graph based on efficient ensembles. In: Proceedings of the 10th international conference on complex networks and their applications, pp 501\u2013513","DOI":"10.1007\/978-3-030-93409-5_42"},{"key":"496_CR21","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser GL, Wolsey LA, Fisher ML (1978) An analysis of approximations for maximizing submodular set functions. Math Program 14:265\u2013294","journal-title":"Math Program"},{"issue":"2","key":"496_CR22","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/s11403-010-0066-6","volume":"5","author":"T Ohnishi","year":"2010","unstructured":"Ohnishi T, Takayasu H, Takayasu M (2010) Network motifs in an inter-firm network. J Econ Interact Coord 5(2):171\u2013180","journal-title":"J Econ Interact Coord"},{"key":"496_CR23","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"},{"key":"496_CR24","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. Republic and Canton of Geneva, CHE, pp 1431\u20131440. https:\/\/doi.org\/10.1145\/3038912.3052597","DOI":"10.1145\/3038912.3052597"},{"issue":"2","key":"496_CR25","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1093\/bioinformatics\/btl301","volume":"23","author":"N Pr\u017eulj","year":"2007","unstructured":"Pr\u017eulj N (2007) Biological network comparison using graphlet degree distribution. Bioinformatics 23(2):177\u2013183. https:\/\/doi.org\/10.1093\/bioinformatics\/btl301","journal-title":"Bioinformatics"},{"key":"496_CR26","doi-asserted-by":"crossref","unstructured":"Rossi RA, Gallagher B, Neville J, Henderson K (2012) Role-dynamics: fast mining of large dynamic networks. In: Proceedings of the 21st international conference companion on World Wide Webv, pp 997\u20131006","DOI":"10.1145\/2187980.2188234"},{"key":"496_CR27","doi-asserted-by":"crossref","unstructured":"Rossi RA, Gallagher B, Neville J, Henderson K (2013) Modeling dynamic behavior in large evolving graphs. In: Proceedings of the sixth ACM international conference on web search and data mining. ACM, pp 667\u2013676","DOI":"10.1145\/2433396.2433479"},{"issue":"4","key":"496_CR28","doi-asserted-by":"publisher","first-page":"1112","DOI":"10.1109\/TKDE.2014.2349913","volume":"27","author":"RA Rossi","year":"2015","unstructured":"Rossi RA, Ahmed NK (2015) Role discovery in networks. IEEE Trans Knowl Data Eng 27(4):1112\u20131131","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"496_CR29","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1038\/srep35098","volume":"123","author":"A Sarajli\u0107","year":"2016","unstructured":"Sarajli\u0107 A, Malod-Dognin N, Yavero\u01e7lu ON, Pr\u017eulj N (2016) Graphlet-based characterization of directed networks. Nature 123:89. https:\/\/doi.org\/10.1038\/srep35098","journal-title":"Nature"},{"key":"496_CR30","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. Association for Computing Machinery, New York, pp 116\u2013125. https:\/\/doi.org\/10.1145\/2808719.2808731","DOI":"10.1145\/2808719.2808731"},{"key":"496_CR31","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":"496_CR32","doi-asserted-by":"crossref","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, pp 165\u2013177","DOI":"10.1007\/11557067_14"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-022-00496-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-022-00496-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-022-00496-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,12]],"date-time":"2022-08-12T08:35:20Z","timestamp":1660293320000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-022-00496-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,12]]},"references-count":32,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2022,12]]}},"alternative-id":["496"],"URL":"https:\/\/doi.org\/10.1007\/s41109-022-00496-6","relation":{},"ISSN":["2364-8228"],"issn-type":[{"type":"electronic","value":"2364-8228"}],"subject":[],"published":{"date-parts":[[2022,8,12]]},"assertion":[{"value":"27 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"55"}}