2
$\begingroup$

I want to know why the distances between nodes in a minimum spanning tree seems to be rooted to the node with highest degree.

A bit of context here:

I have spatial explicit weighted network that describes the physical growth pattern of a fungal colony. Most of the nodes in this network have either degree = 1 or degree =3 (degree=2 is not possible because of biological reasons). Degree >4 are not possible except for only one (and only one) case: the center of the colony, where all edges orginally radiate.

Using the observed network, I obtained the MST (taking into account edge weights. BTW I using the mst function in igraph for R). I did this because I wanted to know how much the fungal colony differs from a MST pattern. However, I noticed that the resulting MST is essentially made up of the shortests paths between the center of the colony (that is, the only node with degree > 4) and any other node in the network. I am a biologist diving into network science, so I am now curious why is that so? why I do not get a shorthest path that does not include the node with hightest degree in the MST?

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ An MST will contain all nodes in the graph, but not necessarily all edges. To be an MST the weights of the edges used to connect all of the nodes should be the minimum. $\endgroup$
    – DenverCoder1
    Feb 25, 2021 at 10:17
  • $\begingroup$ That´s right! It includes all nodes. Thanks! I am now digesting why, then, the edges kept by the MST are exactly the same ones as if I calculate the shortest path (resistance based) from the center to any other node. $\endgroup$
    – carlos_ArT
    Feb 25, 2021 at 10:46
  • 1
    $\begingroup$ It's possible there are many equal-weight MSTs, and the algorithm just happened to pick this one. It's easy to construct an edge-weighted graph in which no MST uses more than a single edge incident on the highest-degree node (you can do this with just 5 vertices). $\endgroup$
    – j_random_hacker
    Feb 25, 2021 at 11:23
  • $\begingroup$ Thanks! I will play around with some simple networks to check what the possible MST result. I found this curious because for the MST, I use the Prim algorithm while for calculating shortest paths I use the Dijkstra algorithm. $\endgroup$
    – carlos_ArT
    Feb 26, 2021 at 6:23

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.