Computing well-balanced spanning trees of unweighted networks

Šubelj, Lovro (avtor)

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’s backbone or skeleton. Prim’s algorithm and Kruskal’s 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.

• Jezik: Angleški jezik
• Ključne besede: unweighted networks, spanning tree, breadth-first search, Prim’s algorithm, Kruskal’s algorithm
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FRI - Fakulteta za računalništvo in informatiko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2025
• Št. strani: 18 str.
• Številčenje: Vol. 18, iss. 12, art. 760
• PID: 20.500.12556/RUL-176570
• UDK: 004.021
• ISSN pri članku: 1999-4893
• DOI: 10.3390/a18120760
• COBISS.SI-ID: 259877379
• Datum objave v RUL: 04.12.2025

Gradivo je del revije

• Naslov: Algorithms
• Skrajšan naslov: Algorithms
• Založnik: MDPI
• ISSN: 1999-4893
• COBISS.SI-ID: 517501977

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: neutežena omrežja, vpeto drevo, preiskovanje v širino, Primov algoritem, Kruskalov algoritem

Projekti

• Financer: ARIS - Javna agencija za znanstvenoraziskovalno in inovacijsko dejavnost Republike Slovenije
• Številka projekta: P5-0168-2022
• Naslov: Družboslovna metodologija, statistika in informatika