{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T02:59:02Z","timestamp":1742957942636,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031215339"},{"type":"electronic","value":"9783031215346"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,1,18]],"date-time":"2023-01-18T00:00:00Z","timestamp":1674000000000},"content-version":"vor","delay-in-days":382,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Complex graphs are at the heart of today\u2019s big data challenges like recommendation systems, customer behavior modeling, or incident detection systems. One reoccurring task in these fields is the extraction of network motifs, which are subgraphs that are reoccurring and statistically significant. To assess the statistical significance of their occurrence, the observed values in the real network need to be compared to their expected value in a random graph model.<\/jats:p><jats:p>In this chapter, we focus on the so-called Link Assessment (LA) problem, in particular for bipartite networks. Lacking closed-form solutions, we require stochastic Monte Carlo approaches that raise the challenge of finding appropriate metrics for quantifying the quality of results (QoR) together with suitable heuristics that stop the computation process if no further increase in quality is expected. We provide investigation results for three quality metrics and show that observing the right metrics reveals so-called <jats:italic>phase transitions<\/jats:italic> that can be used as a reliable basis for such heuristics. Finally, we propose a heuristic that has been evaluated with real-word datasets, providing a speedup of <jats:inline-formula><jats:alternatives><jats:tex-math>$$15.4\\times $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>15.4<\/mml:mn>\n                    <mml:mo>\u00d7<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> over previous approaches.<\/jats:p>","DOI":"10.1007\/978-3-031-21534-6_3","type":"book-chapter","created":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T20:02:53Z","timestamp":1673985773000},"page":"39-56","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Increasing the Sampling Efficiency for the Link Assessment Problem"],"prefix":"10.1007","author":[{"given":"Andr\u00e9","family":"Chinazzo","sequence":"first","affiliation":[]},{"given":"Christian","family":"De Schryver","sequence":"additional","affiliation":[]},{"given":"Katharina","family":"Zweig","sequence":"additional","affiliation":[]},{"given":"Norbert","family":"Wehn","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,1,18]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","unstructured":"Barab\u00e1si, A.L., Albert, R., Jeong, H.: Mean-field theory for scale-free random networks. Physica A: Stat. Mech. Appl. 272(1), 173\u2013187 (1999). https:\/\/doi.org\/10.1016\/S0378-4371(99)00291-5","DOI":"10.1016\/S0378-4371(99)00291-5"},{"key":"3_CR2","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.knosys.2013.03.012","volume":"46","author":"J Bobadilla","year":"2013","unstructured":"Bobadilla, J., Ortega, F., Hernando, A., Guti\u00e9rrez, A.: Recommender systems survey. Knowl. Based Syst. 46, 109\u2013132 (2013). https:\/\/doi.org\/10.1016\/j.knosys.2013.03.012","journal-title":"Knowl. Based Syst."},{"issue":"1","key":"3_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s13278-016-0407-0","volume":"6","author":"C Brugger","year":"2016","unstructured":"Brugger, C., et al.: Increasing sampling efficiency for the fixed degree sequence model with phase transitions. Soc. Netw. Anal. Min. 6(1), 1\u201314 (2016). https:\/\/doi.org\/10.1007\/s13278-016-0407-0","journal-title":"Soc. Netw. Anal. Min."},{"key":"3_CR4","doi-asserted-by":"publisher","unstructured":"Brugger, C., et al.: Exploiting phase transitions for the efficient sampling of the fixed degree sequence model. In: ASONAM, pp. 308\u2013313. ACM (2015). https:\/\/doi.org\/10.1145\/2808797.2809388","DOI":"10.1145\/2808797.2809388"},{"key":"3_CR5","doi-asserted-by":"publisher","unstructured":"Carstens, C.J., Berger, A., Strona, G.: Curveball: a new generation of sampling algorithms for graphs with fixed degree sequence. CoRR abs\/1609.05137 (2016). https:\/\/doi.org\/10.1016\/j.mex.2018.06.018","DOI":"10.1016\/j.mex.2018.06.018"},{"key":"3_CR6","doi-asserted-by":"publisher","unstructured":"Carstens, C.J., Hamann, M., Meyer, U., Penschuck, M., Tran, H., Wagner, D.: Parallel and I\/O-efficient randomisation of massive networks using global curveball trades. In: ESA, pp. 11:1\u201311:15. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2018.11","DOI":"10.4230\/LIPIcs.ESA.2018.11"},{"key":"3_CR7","unstructured":"Duranton, M., et al.: HiPEAC vision 2019. In: European Network of Excellence on High Performance and Embedded Architecture and Compilation (HiPEAC) (2019)"},{"issue":"2","key":"3_CR8","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1137\/16M1087175","volume":"60","author":"BK Fosdick","year":"2018","unstructured":"Fosdick, B.K., Larremore, D.B., Nishimura, J., Ugander, J.: Configuring random graph models with fixed degree sequences. SIAM Rev. 60(2), 315\u2013355 (2018). https:\/\/doi.org\/10.1137\/16M1087175","journal-title":"SIAM Rev."},{"key":"3_CR9","unstructured":"Genio, C.I.D., Kim, H., Toroczkai, Z., Bassler, K.E.: Efficient and exact sampling of simple graphs with given arbitrary degree sequence. CoRR abs\/1002.2975 (2010)"},{"issue":"3","key":"3_CR10","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/1297332.1297338","volume":"1","author":"A Gionis","year":"2007","unstructured":"Gionis, A., Mannila, H., Mielik\u00e4inen, T., Tsaparas, P.: Assessing data mining results via swap randomization. ACM Trans. Knowl. Discov. Data 1(3), 14 (2007). https:\/\/doi.org\/10.1145\/1297332.1297338","journal-title":"ACM Trans. Knowl. Discov. Data"},{"issue":"21","key":"3_CR11","doi-asserted-by":"publisher","first-page":"8685","DOI":"10.1073\/pnas.0701361104","volume":"104","author":"KI Goh","year":"2007","unstructured":"Goh, K.I., Cusick, M.E., Valle, D., Childs, B., Vidal, M., Barab\u00e1si, A.L.: The human disease network. Proc. Natl. Acad. Sci. 104(21), 8685\u20138690 (2007). https:\/\/doi.org\/10.1073\/pnas.0701361104","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"8","key":"3_CR12","doi-asserted-by":"publisher","first-page":"4372","DOI":"10.1073\/pnas.0735871100","volume":"100","author":"DS Goldberg","year":"2003","unstructured":"Goldberg, D.S., Roth, F.P.: Assessing experimentally derived interactions in a small world. Proc. Natl. Acad. Sci. 100(8), 4372\u20134376 (2003). https:\/\/doi.org\/10.1073\/pnas.0735871100","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"9","key":"3_CR13","doi-asserted-by":"publisher","first-page":"2606","DOI":"10.1890\/0012-9658(2000)081[2606:NMAOSC]2.0.CO;2","volume":"81","author":"NJ Gotelli","year":"2000","unstructured":"Gotelli, N.J.: Null model analysis of species co-occurrence patterns. Ecology 81(9), 2606\u20132621 (2000). https:\/\/doi.org\/10.1890\/0012-9658(2000)081[2606:NMAOSC]2.0.CO;2","journal-title":"Ecology"},{"issue":"2","key":"3_CR14","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/s00442-009-1474-y","volume":"162","author":"NJ Gotelli","year":"2010","unstructured":"Gotelli, N.J., Ulrich, W.: The empirical Bayes approach as a tool to identify non-random species associations. Oecologia 162(2), 463\u2013477 (2010). https:\/\/doi.org\/10.1007\/s00442-009-1474-y","journal-title":"Oecologia"},{"issue":"3","key":"3_CR15","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/j.eij.2015.06.005","volume":"16","author":"F Isinkaye","year":"2015","unstructured":"Isinkaye, F., Folajimi, Y., Ojokoh, B.: Recommendation systems: principles, methods and evaluation. Egypt. Inform. J. 16(3), 261\u2013273 (2015). https:\/\/doi.org\/10.1016\/j.eij.2015.06.005","journal-title":"Egypt. Inform. J."},{"key":"3_CR16","doi-asserted-by":"publisher","first-page":"026120","DOI":"10.1103\/PhysRevE.73.026120","volume":"73","author":"EA Leicht","year":"2006","unstructured":"Leicht, E.A., Holme, P., Newman, M.E.J.: Vertex similarity in networks. Phys. Rev. E 73, 026120 (2006). https:\/\/doi.org\/10.1103\/PhysRevE.73.026120","journal-title":"Phys. Rev. E"},{"key":"3_CR17","doi-asserted-by":"publisher","unstructured":"L\u00fc, L., Zhou, T.: Link prediction in complex networks: a survey. Physica A: Stat. Mech. Appl. 390(6), 1150\u20131170 (2011). https:\/\/doi.org\/10.1016\/j.physa.2010.11.027","DOI":"10.1016\/j.physa.2010.11.027"},{"key":"3_CR18","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198805090.001.0001","volume-title":"Networks","author":"M Newman","year":"2018","unstructured":"Newman, M.: Networks. OUP, Oxford (2018)"},{"key":"3_CR19","doi-asserted-by":"publisher","unstructured":"Newman, M.E.J.: Networks: An Introduction. Oxford University Press, Oxford (2010). https:\/\/doi.org\/10.1093\/ACPROF:OSO\/9780199206650.001.0001","DOI":"10.1093\/ACPROF:OSO\/9780199206650.001.0001"},{"key":"3_CR20","doi-asserted-by":"publisher","unstructured":"Rapti, A., Tsolis, D., Sioutas, S., Tsakalidis, A.K.: A survey: mining linked cultural heritage data. In: EANN Workshops, pp. 24:1\u201324:6. ACM (2015). https:\/\/doi.org\/10.1145\/2797143.2797172","DOI":"10.1145\/2797143.2797172"},{"key":"3_CR21","doi-asserted-by":"publisher","unstructured":"Rechner, S., Berger, A.: Marathon: an open source software library for the analysis of Markov-chain Monte Carlo algorithms. CoRR abs\/1508.04740 (2015). https:\/\/doi.org\/10.1371\/journal.pone.0147935","DOI":"10.1371\/journal.pone.0147935"},{"issue":"1","key":"3_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s13278-015-0267-z","volume":"5","author":"WE Schlauch","year":"2015","unstructured":"Schlauch, W.E., Horv\u00e1t, E.\u00c1., Zweig, K.A.: Different flavors of randomness: comparing random graph models with fixed degree sequences. Soc. Netw. Anal. Min. 5(1), 1\u201314 (2015). https:\/\/doi.org\/10.1007\/s13278-015-0267-z","journal-title":"Soc. Netw. Anal. Min."},{"key":"3_CR23","doi-asserted-by":"publisher","unstructured":"Schlauch, W.E., Zweig, K.A.: Influence of the null-model on motif detection. In: ASONAM, pp. 514\u2013519. ACM (2015). https:\/\/doi.org\/10.1145\/2808797.2809400","DOI":"10.1145\/2808797.2809400"},{"issue":"4","key":"3_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pone.0152536","volume":"11","author":"A Spitz","year":"2016","unstructured":"Spitz, A., Gimmler, A., Stoeck, T., Zweig, K.A., Horv\u00e1t, E.: Assessing low-intensity relationships in complex networks. PLoS ONE 11(4), 1\u201317 (2016). https:\/\/doi.org\/10.1371\/journal.pone.0152536","journal-title":"PLoS ONE"},{"issue":"1","key":"3_CR25","doi-asserted-by":"publisher","first-page":"4114","DOI":"10.1038\/ncomms5114","volume":"5","author":"G Strona","year":"2014","unstructured":"Strona, G., Nappo, D., Boccacci, F., Fattorini, S., San-Miguel-Ayanz, J.: A fast and unbiased procedure to randomize ecological binary matrices with fixed row and column totals. Nat. Commun. 5(1), 4114 (2014). https:\/\/doi.org\/10.1038\/ncomms5114","journal-title":"Nat. Commun."},{"key":"3_CR26","doi-asserted-by":"publisher","unstructured":"Sun, C., Shrivastava, A., Singh, S., Gupta, A.: Revisiting unreasonable effectiveness of data in deep learning era. In: ICCV, pp. 843\u2013852. IEEE Computer Society (2017). https:\/\/doi.org\/10.1109\/ICCV.2017.97","DOI":"10.1109\/ICCV.2017.97"},{"issue":"3","key":"3_CR27","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/s13278-011-0021-0","volume":"1","author":"KA Zweig","year":"2011","unstructured":"Zweig, K.A., Kaufmann, M.: A systematic approach to the one-mode projection of bipartite graphs. Soc. Netw. Anal. Min. 1(3), 187\u2013218 (2011). https:\/\/doi.org\/10.1007\/s13278-011-0021-0","journal-title":"Soc. Netw. Anal. Min."}],"container-title":["Lecture Notes in Computer Science","Algorithms for Big Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-21534-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,17]],"date-time":"2023-01-17T20:03:32Z","timestamp":1673985812000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-21534-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031215339","9783031215346"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-21534-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"18 January 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}