{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T19:27:40Z","timestamp":1764962860679,"version":"3.46.0"},"reference-count":64,"publisher":"MDPI AG","issue":"12","license":[{"start":{"date-parts":[[2025,11,29]],"date-time":"2025-11-29T00:00:00Z","timestamp":1764374400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004329","name":"Slovenian Research and Innovation Agency ARIS","doi-asserted-by":"publisher","award":["P5-0168"],"award-info":[{"award-number":["P5-0168"]}],"id":[{"id":"10.13039\/501100004329","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>A spanning tree of a network or graph is a subgraph that connects all nodes with the minimum number or total weight of edges. Spanning trees are among the simplest yet most effective techniques for network simplification, sampling, and uncovering a network\u2019s backbone or skeleton. Prim\u2019s algorithm and Kruskal\u2019s algorithm are well-known algorithms for computing a spanning tree of a weighted network, and are therefore also the default procedure for unweighted networks in the most popular network libraries. In this paper, we empirically evaluate the performance of these algorithms on unweighted networks and compare them with priority-first search algorithms. We show that the distances between the nodes are better preserved by a simpler algorithm based on breadth-first search. The spanning trees are also more compact and well-balanced, as measured by classical graph indices. We support our findings with experiments on synthetic graphs and over a thousand real networks, and demonstrate the practical applications of the computed spanning trees. We conclude that for preserving the structure of an unweighted network, the breadth-first search algorithm should be the preferred choice.<\/jats:p>","DOI":"10.3390\/a18120760","type":"journal-article","created":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T18:42:02Z","timestamp":1764960122000},"page":"760","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Computing Well-Balanced Spanning Trees of Unweighted Networks"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4161-2260","authenticated-orcid":false,"given":"Lovro","family":"\u0160ubelj","sequence":"first","affiliation":[{"name":"Faculty of Computer and Information Science, University of Ljubljana, Ve\u010dna pot 113, 1000 Ljubljana, Slovenia"},{"name":"Faculty of Social Sciences, University of Ljubljana, Kardeljeva plo\u0161\u010dad 5, 1000 Ljubljana, Slovenia"}]}],"member":"1968","published-online":{"date-parts":[[2025,11,29]]},"reference":[{"key":"ref_1","unstructured":"Newman, M.E.J. (2018). Networks, Oxford University Press. [2nd ed.]."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Tizzoni, M., Bajardi, P., Poletto, C., Ramasco, J.J., Balcan, D., Gon\u00e7alves, B., Perra, N., Colizza, V., and Vespignani, A. (2012). Real-time numerical forecast of global epidemic spreading: Case study of 2009 A\/H1N1pdm. BMC Med., 10.","DOI":"10.1186\/1741-7015-10-165"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"4426","DOI":"10.1073\/pnas.1818013116","article-title":"Evolution of resilience in protein interactomes across the tree of life","volume":"116","author":"Zitnik","year":"2019","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"eaao0185","DOI":"10.1126\/science.aao0185","article-title":"Science of science","volume":"359","author":"Fortunato","year":"2018","journal-title":"Science"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Backstrom, L., Boldi, P., Rosa, M., Ugander, J., and Vigna, S. (2012, January 22\u201324). Four degrees of separation. Proceedings of the ACM International Conference on Web Science, Evanston, IL, USA.","DOI":"10.1145\/2380718.2380723"},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Leskovec, J., and Faloutsos, C. (2006, January 20\u201323). Sampling from large graphs. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Philadelphia, PA, USA.","DOI":"10.1145\/1150402.1150479"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1007\/s13278-016-0332-2","article-title":"Structure-preserving sparsification methods for social networks","volume":"6","author":"Hamann","year":"2016","journal-title":"Soc. Netw. Anal. Min."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1016\/j.physa.2017.02.048","article-title":"Empirical comparison of network sampling: How to choose the most appropriate method?","volume":"477","author":"Blagus","year":"2017","journal-title":"Phys. A Stat. Mech. Its Appl."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1038\/ncomms1847","article-title":"Robust classification of salient links in complex networks","volume":"3","author":"Grady","year":"2012","journal-title":"Nat. Commun."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Coscia, M., and Neffke, F. (2017, January 19\u201322). Network backboning with noisy data. Proceedings of the IEEE International Conference on Data Engineering, San Diego, CA, USA.","DOI":"10.1109\/ICDE.2017.100"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"20180422","DOI":"10.1098\/rsif.2018.0422","article-title":"Convex skeletons of complex networks","volume":"15","year":"2018","journal-title":"J. R. Soc. Interface"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"cnab021","DOI":"10.1093\/comnet\/cnab021","article-title":"The distance backbone of complex networks","volume":"9","author":"Simas","year":"2021","journal-title":"J. Complex Netw."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Bollob\u00e1s, B. (1998). Modern Graph Theory, Springer.","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2019.05.017","article-title":"The generalized minimum spanning tree problem: An overview of formulations, solution procedures and latest advances","volume":"283","author":"Pop","year":"2020","journal-title":"Eur. J. Oper. Res."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"024312","DOI":"10.1103\/PhysRevE.105.024312","article-title":"Spanning trees of recursive scale-free graphs","volume":"105","author":"Diggans","year":"2022","journal-title":"Phys. Rev. E"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/s41109-024-00613-7","article-title":"C-RST: A parallel algorithm for random spanning trees in network analytics","volume":"9","author":"Henke","year":"2024","journal-title":"Appl. Netw. Sci."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"100359","DOI":"10.1016\/j.rico.2023.100359","article-title":"Innovative method to solve the minimum spanning tree problem: The Dhouib-Matrix-MSTP (DM-MSTP)","volume":"14","author":"Dhouib","year":"2024","journal-title":"Results Control Optim."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1007\/s13278-024-01247-4","article-title":"A spanning tree approach to social network sampling with degree constraints","volume":"14","author":"Rezvanian","year":"2024","journal-title":"Soc. Netw. Anal. Min."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"100359","DOI":"10.1007\/s13278-025-01409-y","article-title":"A comparative evaluation of social network analysis tools: Performance and community engagement perspectives","volume":"15","author":"Amure","year":"2025","journal-title":"Soc. Netw. Anal. Min."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1007\/s13278-011-0018-8","article-title":"Generalizing unweighted network measures to capture the focus in interactions","volume":"1","author":"Abdallah","year":"2011","journal-title":"Soc. Netw. Anal. Min."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1007\/BF02776078","article-title":"On Lipschitz embedding of finite metric spaces in Hilbert space","volume":"52","author":"Bourgain","year":"1985","journal-title":"Isr. J. Math."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1038\/30918","article-title":"Collective dynamics of \u2019small-world\u2019 networks","volume":"393","author":"Watts","year":"1998","journal-title":"Nature"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1137\/S003614450342480","article-title":"The structure and function of complex networks","volume":"45","author":"Newman","year":"2003","journal-title":"SIAM Rev."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1021\/ja01193a005","article-title":"Structural determination of paraffin boiling points","volume":"69","author":"Wiener","year":"1947","journal-title":"J. Am. Chem. Soc."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1093\/sysbio\/21.2.225","article-title":"\u201cGood\u201d and \u201cbad\u201d phenograms","volume":"21","author":"Sackin","year":"1972","journal-title":"Syst. Biol."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/j.jmb.2004.04.047","article-title":"LGL: Creating a map of protein function with an algorithm for visualizing very large biological networks","volume":"340","author":"Adai","year":"2004","journal-title":"J. Mol. Biol."},{"key":"ref_27","unstructured":"Knuth, D.E. (2011). The Art of Computer Programming, Addison-Wesley Professional."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1017\/S1446788700004432","article-title":"On the height of trees","volume":"7","author":"Szekeres","year":"1967","journal-title":"J. Aust. Math. Soc."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0021-9800(70)80012-6","article-title":"The distance between points in random trees","volume":"8","author":"Meir","year":"1970","journal-title":"J. Comb. Theory"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Fischer, M., Herbst, L., Kersting, S.A., K\u00fchn, L., and Wicke, K. (2023). Tree Balance Indices: A Comprehensive Survey, Springer. [1st ed.].","DOI":"10.1007\/978-3-031-39800-1"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1210","DOI":"10.1093\/sysbio\/syac027","article-title":"Robust, universal tree balance indices","volume":"71","author":"Lemant","year":"2022","journal-title":"Syst. Biol."},{"key":"ref_32","first-page":"266","article-title":"Tree balance","volume":"39","author":"Shao","year":"1990","journal-title":"Syst. Zool."},{"key":"ref_33","unstructured":"American Physical Society (2025, October 01). APS Dataset. Available online: http:\/\/journals.aps.org\/datasets."},{"key":"ref_34","unstructured":"Institute of Information Science (2025, October 01). SICRIS Database. Available online: http:\/\/www.sicris.si."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1093\/nar\/gkj109","article-title":"BioGRID: A general repository for interaction datasets","volume":"34","author":"Stark","year":"2006","journal-title":"Nucleic Acids Res."},{"key":"ref_36","unstructured":"Biological General Repository for Interaction Datasets (2025, October 01). BioGRID Database. Available online: http:\/\/thebiogrid.org."},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Paranjape, A., Benson, A.R., and Leskovec, J. (2017, January 6\u201310). Motifs in temporal networks. Proceedings of the ACM International Conference on Web Search and Data Mining, Cambridge, UK.","DOI":"10.1145\/3018661.3018731"},{"key":"ref_38","unstructured":"Leskovec, J., and Krevl, A. (2025, October 01). SNAP Datasets. Available online: http:\/\/snap.stanford.edu\/data."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"4165","DOI":"10.1016\/j.physa.2011.12.021","article-title":"Social structure of Facebook networks","volume":"391","author":"Traud","year":"2012","journal-title":"Phys. A Stat. Mech. Its Appl."},{"key":"ref_40","unstructured":"Rossi, R.A., and Ahmed, N.K. (2025, October 01). Network Data Repository. Available online: http:\/\/networkrepository.com."},{"key":"ref_41","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Kleinberg, J., and Faloutsos, C. (2005, January 21\u201324). Graphs over time: Densification laws, shrinking diameters and possible explanations. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Chicago, IL, USA.","DOI":"10.1145\/1081870.1081893"},{"key":"ref_42","first-page":"290","article-title":"On random graphs I","volume":"6","year":"1959","journal-title":"Publ. Math. Debr."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1126\/science.286.5439.509","article-title":"Emergence of scaling in random networks","volume":"286","author":"Albert","year":"1999","journal-title":"Science"},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"058701","DOI":"10.1103\/PhysRevLett.90.058701","article-title":"Scale-free networks are ultrasmall","volume":"90","author":"Cohen","year":"2003","journal-title":"Phys. Rev. Lett."},{"key":"ref_45","unstructured":"Barab\u00e1si, A.L. (2016). Network Science, Cambridge University Press."},{"key":"ref_46","doi-asserted-by":"crossref","first-page":"328","DOI":"10.19139\/soic-2310-5070-855","article-title":"Globally optimal dense and sparse spanning trees, and their applications","volume":"8","author":"Ozen","year":"2020","journal-title":"Stat. Optim. Inf. Comput."},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1137\/070710111","article-title":"Power-law distributions in empirical data","volume":"51","author":"Clauset","year":"2009","journal-title":"SIAM Rev."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"1017","DOI":"10.1038\/s41467-019-08746-5","article-title":"Scale-free networks are rare","volume":"10","author":"Broido","year":"2019","journal-title":"Nat. Commun."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.physrep.2016.09.002","article-title":"Community detection in networks: A user guide","volume":"659","author":"Fortunato","year":"2016","journal-title":"Phys. Rep."},{"key":"ref_50","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1017\/S0956792516000401","article-title":"Re-conceptualizing centrality in social networks","volume":"27","author":"Schoch","year":"2016","journal-title":"Eur. J. Appl. Math."},{"key":"ref_51","doi-asserted-by":"crossref","first-page":"35","DOI":"10.2307\/3033543","article-title":"A set of measures of centrality based on betweenness","volume":"40","author":"Freeman","year":"1977","journal-title":"Sociometry"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0378-8733(78)90021-7","article-title":"Centrality in social networks: Conceptual clarification","volume":"1","author":"Freeman","year":"1979","journal-title":"Soc. Netw."},{"key":"ref_53","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1080\/0022250X.2001.9990249","article-title":"A faster algorithm for betweenness centrality","volume":"25","author":"Brandes","year":"2001","journal-title":"J. Math. Sociol."},{"key":"ref_54","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1109\/MC.2013.242","article-title":"Large-scale graph visualization and analytics","volume":"46","author":"Ma","year":"2013","journal-title":"Computer"},{"key":"ref_55","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1177\/1473871612455749","article-title":"A survey of two-dimensional graph layout techniques for information visualisation","volume":"12","author":"Gibson","year":"2013","journal-title":"Inf. Vis."},{"key":"ref_56","first-page":"149","article-title":"A heuristic for graph drawing","volume":"42","author":"Eades","year":"1984","journal-title":"Congr. Numer."},{"key":"ref_57","doi-asserted-by":"crossref","first-page":"1129","DOI":"10.1002\/spe.4380211102","article-title":"Graph drawing by force-directed placement","volume":"21","author":"Fruchterman","year":"1991","journal-title":"Softw. Pract. Exp."},{"key":"ref_58","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1016\/0020-0190(89)90102-6","article-title":"An algorithm for drawing general undirected graphs","volume":"31","author":"Kamada","year":"1989","journal-title":"Inf. Process. Lett."},{"key":"ref_59","first-page":"10","article-title":"Convexity in scientific collaboration networks","volume":"13","author":"Fiala","year":"2019","journal-title":"J. Inf."},{"key":"ref_60","doi-asserted-by":"crossref","unstructured":"Kalyagin, V.A., Pardalos, P.M., Prokopyev, O., and Utkina, I. (2017). Computational Aspects and Applications in Large-Scale Networks, Springer. [1st ed.].","DOI":"10.1007\/978-3-319-96247-4"},{"key":"ref_61","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1162\/netn_a_00245","article-title":"Minimum spanning tree analysis of brain networks: A systematic review of network size effects, sensitivity for neuropsychiatric pathology, and disorder specificity","volume":"6","author":"Blomsma","year":"2022","journal-title":"Netw. Neurosci."},{"key":"ref_62","doi-asserted-by":"crossref","unstructured":"Hosseini, A. (2024). Uncertainty modeling and stability assessment of minimum spanning trees in network design. Mathematics, 12.","DOI":"10.3390\/math12233812"},{"key":"ref_63","first-page":"535","article-title":"An approach to the analysis of critical elements of transport and logistics networks using graph theory","volume":"18","author":"Strzelczyk","year":"2024","journal-title":"Int. J. Mar. Navig. Saf. Sea Transp."},{"key":"ref_64","first-page":"1","article-title":"Latency, capacity, and distributed minimum spanning trees","volume":"126","author":"Augustine","year":"2022","journal-title":"J. Parallel Distrib. Comput."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/12\/760\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T18:59:11Z","timestamp":1764961151000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/12\/760"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,29]]},"references-count":64,"journal-issue":{"issue":"12","published-online":{"date-parts":[[2025,12]]}},"alternative-id":["a18120760"],"URL":"https:\/\/doi.org\/10.3390\/a18120760","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,11,29]]}}}