{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:13:13Z","timestamp":1755997993249},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,10,13]],"date-time":"2023-10-13T00:00:00Z","timestamp":1697155200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,13]],"date-time":"2023-10-13T00:00:00Z","timestamp":1697155200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Hungarian National Research, Development and Innovation Office \u2013 NKFIH","award":["SNN-13564"],"award-info":[{"award-number":["SNN-13564"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Appl Netw Sci"],"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In their previous work, the authors considered the concept of random spanning tree intersection of complex networks (London and Pluh\u00e1r, in: Cherifi, Mantegna, Rocha, Cherifi, Micciche (eds) Complex networks and their applications XI, Springer, Cham, 2023). A simple formula was derived for the size of the minimum expected intersection of two spanning trees chosen uniformly at random. Monte Carlo experiments were run for real networks. In this paper, we provide a broader context and motivations for the concept, discussing its game theoretic origins, examples, its applications to network optimization problems, and its potential use in quantifying the resilience and modular structure of complex networks.<\/jats:p>","DOI":"10.1007\/s41109-023-00600-4","type":"journal-article","created":{"date-parts":[[2023,10,13]],"date-time":"2023-10-13T13:02:15Z","timestamp":1697202135000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Intersection of random spanning trees in complex networks"],"prefix":"10.1007","volume":"8","author":[{"given":"Andr\u00e1s","family":"London","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andr\u00e1s","family":"Pluh\u00e1r","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,10,13]]},"reference":[{"issue":"5","key":"600_CR1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2020.112282","volume":"344","author":"N Albin","year":"2021","unstructured":"Albin N, Clemens J, Hoare D, Poggi-Corradini P, Sit B, Tymochko S (2021) Fairest edge usage and minimum expected overlap for random spanning trees. Discrete Math 344(5):112282","journal-title":"Discrete Math"},{"issue":"1","key":"600_CR2","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1137\/S0097539792224474","volume":"24","author":"N Alon","year":"1995","unstructured":"Alon N, Karp RM, Peleg D, West D (1995) A graph-theoretic game and its application to the k-server problem. SIAM J Comput 24(1):78\u2013100","journal-title":"SIAM J Comput"},{"issue":"5439","key":"600_CR3","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1126\/science.286.5439.509","volume":"286","author":"A-L Barab\u00e1si","year":"1999","unstructured":"Barab\u00e1si A-L, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509\u2013512","journal-title":"Science"},{"key":"600_CR4","doi-asserted-by":"crossref","unstructured":"Bartal Y (1996) Probabilistic approximation of metric spaces and its algorithmic applications. In: Proceedings of 37th conference on foundations of computer science. IEEE, pp 184\u2013193","DOI":"10.1109\/SFCS.1996.548477"},{"issue":"10","key":"600_CR5","doi-asserted-by":"publisher","first-page":"10008","DOI":"10.1088\/1742-5468\/2008\/10\/P10008","volume":"2008","author":"VD Blondel","year":"2008","unstructured":"Blondel VD, Guillaume J-L, Lambiotte R, Lefebvre E (2008) Fast unfolding of communities in large networks. J Stat Mech Theory Exp 2008(10):10008","journal-title":"J Stat Mech Theory Exp"},{"key":"600_CR6","first-page":"442","volume":"89","author":"AZ Broder","year":"1989","unstructured":"Broder AZ (1989) Generating random spanning trees. FOCS 89:442\u2013447","journal-title":"FOCS"},{"key":"600_CR7","doi-asserted-by":"crossref","unstructured":"Chen C, Morris S (2003) Visualizing evolving networks: minimum spanning trees versus pathfinder networks. In: IEEE symposium on information visualization 2003 (IEEE Cat. No. 03TH8714). IEEE, pp 67\u201374","DOI":"10.1109\/INFVIS.2003.1249010"},{"key":"600_CR8","volume-title":"Linear programming","author":"V Chvatal","year":"1983","unstructured":"Chvatal V (1983) Linear programming. Macmillan, New York"},{"issue":"10","key":"600_CR9","doi-asserted-by":"publisher","first-page":"2491","DOI":"10.1016\/j.laa.2011.02.024","volume":"435","author":"W Ellens","year":"2011","unstructured":"Ellens W, Spieksma FM, Van Mieghem P, Jamakovic A, Kooij RE (2011) Effective graph resistance. Linear Algebra Appl 435(10):2491\u20132506","journal-title":"Linear Algebra Appl"},{"issue":"1","key":"600_CR10","first-page":"17","volume":"5","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s P, R\u00e9nyi A et al (1960) On the evolution of random graphs. Publ Math Inst Hung Acad Sci 5(1):17\u201360","journal-title":"Publ Math Inst Hung Acad Sci"},{"issue":"3","key":"600_CR11","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/0097-3165(73)90005-8","volume":"14","author":"P Erd\u00f6s","year":"1973","unstructured":"Erd\u00f6s P, Selfridge JL (1973) On a combinatorial game. J Comb Theory Ser A 14(3):298\u2013301","journal-title":"J Comb Theory Ser A"},{"key":"600_CR12","doi-asserted-by":"crossref","unstructured":"Fakcharoenphol J, Rao S, Talwar K (2003) A tight bound on approximating arbitrary metrics by tree metrics. In: Proceedings of the thirty-fifth annual ACM symposium on theory of computing, pp 448\u2013455","DOI":"10.1145\/780542.780608"},{"key":"600_CR13","first-page":"180","volume":"20","author":"G Gautier","year":"2019","unstructured":"Gautier G, Polito G, Bardenet R, Valko M (2019) DPPy: DPP sampling with python. J Mach Learn Res 20:180\u20131","journal-title":"J Mach Learn Res"},{"issue":"4","key":"600_CR14","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.81.046106","volume":"81","author":"BH Good","year":"2010","unstructured":"Good BH, De Montjoye Y-A, Clauset A (2010) Performance of modularity maximization in practical contexts. Phys Rev E 81(4):046106","journal-title":"Phys Rev E"},{"issue":"6","key":"600_CR15","doi-asserted-by":"publisher","first-page":"1360","DOI":"10.1086\/225469","volume":"78","author":"MS Granovetter","year":"1973","unstructured":"Granovetter MS (1973) The strength of weak ties. Am J Sociol 78(6):1360\u20131380","journal-title":"Am J Sociol"},{"key":"600_CR16","doi-asserted-by":"crossref","unstructured":"Gueye A, Walrand JC, Anantharam V (2010) Design of network topology in an adversarial environment. In: International conference on decision and game theory for security. Springer, pp 1\u201320","DOI":"10.1007\/978-3-642-17197-0_1"},{"issue":"4","key":"600_CR17","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.70.046126","volume":"70","author":"D-H Kim","year":"2004","unstructured":"Kim D-H, Noh JD, Jeong H (2004) Scale-free trees: the skeletons of complex networks. Phys Rev E 70(4):046126","journal-title":"Phys Rev E"},{"key":"600_CR18","volume-title":"Spanning tree modulus and secure broadcast games","author":"K Kottegoda","year":"2020","unstructured":"Kottegoda K (2020) Spanning tree modulus and secure broadcast games. Kansas State University, Manhattan, Kansas"},{"key":"600_CR19","doi-asserted-by":"crossref","unstructured":"Kunegis J (2013) KONECT\u2014the Koblenz network collection. In: Proceedings of the international conference on world wide web companion, pp 1343\u20131350. http:\/\/dl.acm.org\/citation.cfm?id=2488173","DOI":"10.1145\/2487788.2488173"},{"issue":"4","key":"600_CR20","doi-asserted-by":"publisher","first-page":"687","DOI":"10.1137\/0112059","volume":"12","author":"A Lehman","year":"1964","unstructured":"Lehman A (1964) A solution of the Shannon switching game. J Soc Ind Appl Math 12(4):687\u2013725","journal-title":"J Soc Ind Appl Math"},{"key":"600_CR21","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-031-21131-7_26","volume-title":"Complex networks and their applications XI","author":"A London","year":"2023","unstructured":"London A, Pluh\u00e1r A (2023) Intersection of random spanning trees in small-world networks. In: Cherifi H, Mantegna RN, Rocha LM, Cherifi C, Micciche S (eds) Complex networks and their applications XI. Springer, Cham, pp 337\u2013345"},{"key":"600_CR22","doi-asserted-by":"crossref","unstructured":"Ma B, Hero A, Gorman J, Michel O (2000) Image registration with minimum spanning tree algorithm. In: Proceedings 2000 international conference on image processing (Cat. No. 00CH37101), vol 1. IEEE, pp 481\u2013484","DOI":"10.1109\/ICIP.2000.901000"},{"issue":"1","key":"600_CR23","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s100510050929","volume":"11","author":"RN Mantegna","year":"1999","unstructured":"Mantegna RN (1999) Hierarchical structure in financial markets. Eur Phys J B Condens Matter Complex Syst 11(1):193\u2013197","journal-title":"Eur Phys J B Condens Matter Complex Syst"},{"key":"600_CR24","unstructured":"Mark Newman\u2019s network data. http:\/\/www-personal.umich.edu\/$$\\sim$$mejn\/netdata\/. Accessed 02 Feb 2023"},{"key":"600_CR25","unstructured":"Network Repository. https:\/\/networkrepository.com\/. Accessed 02 Feb 2023"},{"key":"600_CR26","unstructured":"Stanford Large Network Dataset Collection. https:\/\/snap.stanford.edu\/data\/. Accessed 02 Feb 2023"},{"issue":"1","key":"600_CR27","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1016\/j.jedc.2007.01.034","volume":"32","author":"V Tola","year":"2008","unstructured":"Tola V, Lillo F, Gallegati M, Mantegna RN (2008) Cluster analysis for portfolio optimization. J Econ Dyn Control 32(1):235\u2013258","journal-title":"J Econ Dyn Control"},{"issue":"6684","key":"600_CR28","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1038\/30918","volume":"393","author":"DJ Watts","year":"1998","unstructured":"Watts DJ, Strogatz SH (1998) Collective dynamics of \u2018small-world\u2019 networks. Nature 393(6684):440\u2013442","journal-title":"Nature"},{"key":"600_CR29","doi-asserted-by":"crossref","unstructured":"Wilson DB (1996) Generating random spanning trees more quickly than the cover time. In: Proceedings of the twenty-eighth annual ACM symposium on theory of computing, pp 296\u2013303","DOI":"10.1145\/237814.237880"},{"key":"600_CR30","doi-asserted-by":"publisher","DOI":"10.1201\/9780203497289","volume-title":"Spanning trees and optimization problems","author":"BY Wu","year":"2004","unstructured":"Wu BY, Chao K-M (2004) Spanning trees and optimization problems. Chapman and Hall, New York"},{"issue":"1","key":"600_CR31","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/S0262-8856(96)01105-5","volume":"15","author":"Y Xu","year":"1997","unstructured":"Xu Y, Uberbacher EC (1997) 2d image segmentation using minimum spanning trees. Image Vis Comput 15(1):47\u201357","journal-title":"Image Vis Comput"}],"container-title":["Applied Network Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-023-00600-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41109-023-00600-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41109-023-00600-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,18]],"date-time":"2023-11-18T15:05:33Z","timestamp":1700319933000},"score":1,"resource":{"primary":{"URL":"https:\/\/appliednetsci.springeropen.com\/articles\/10.1007\/s41109-023-00600-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,13]]},"references-count":31,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2023,12]]}},"alternative-id":["600"],"URL":"https:\/\/doi.org\/10.1007\/s41109-023-00600-4","relation":{},"ISSN":["2364-8228"],"issn-type":[{"value":"2364-8228","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,13]]},"assertion":[{"value":"21 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 September 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 October 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"72"}}