The minimum spanning tree: An unbiased method for brain network analysis

• DOI: 10.1016/j.neuroimage.2014.10.015
• Publication Date: 2014-10-16T02:21:58Z
• Authors: P. Tewarie; E. van Dellen; A. Hillebrand; C.J. Stam
• Keywords: Connectivity; Brain Mapping; Cognitive Neuroscience; Brain; Minimum spanning tree; General Medicine; Functional and structural networks; Graph theory; 03 medical and health sciences; 0302 clinical medicine; Complex brain networks; Neurology; Humans; Computer Simulation; Nerve Net; Algorithms

The brain is increasingly studied with graph theoretical approaches, which can be used to characterize network topology. However, studies on brain networks have reported contradictory findings, and do not easily converge to a clear concept of the structural and functional network organization of the brain. It has recently been suggested that the minimum spanning tree (MST) may help to increase comparability between studies. The MST is an acyclic sub-network that connects all nodes and may solve several methodological limitations of previous work, such as sensitivity to alterations in connection strength (for weighted networks) or link density (for unweighted networks), which may occur concomitantly with alterations in network topology under empirical conditions. If analysis of MSTs avoids these methodological limitations, understanding the relationship between MST characteristics and conventional network measures is crucial for interpreting MST brain network studies. Here, we firstly demonstrated that the MST is insensitive to alterations in connection strength or link density. We then explored the behavior of MST and conventional network-characteristics for simulated regular and scale-free networks that were gradually rewired to random networks. Surprisingly, although most connections are discarded during construction of the MST, MST characteristics were equally sensitive to alterations in network topology as the conventional graph theoretical measures. The MST characteristics diameter and leaf fraction were very strongly related to changes in the characteristic path length when the network changed from a regular to a random configuration. Similarly, MST degree, diameter, and leaf fraction were very strongly related to the degree of scale-free networks that were rewired to random networks. Analysis of the MST is especially suitable for the comparison of brain networks, as it avoids methodological biases. Even though the MST does not utilize all the connections in the network, it still provides a, mathematically defined and unbiased, sub-network with characteristics that can provide similar information about network topology as conventional graph measures.