Introduction

The minimum spanning tree (MST) method is a helpful tool that avoids some problems arising in brain network analysis [1, 2]. The MST analysis can provide insights into how the brain processes information and how different regions work together to support cognitive functions [3, 4]. By analyzing the MST of a functional brain network, researchers can identify the most efficient communication pathways between different brains [1, 3].

MST is insensitive to link strength or density changes and is equally sensitive to network topology changes as in conventional graph theory measurements. Therefore, it is convenient for comparative studies between brain networks [3].

In graph theory, a tree is defined as a connected graph without the formation of any loops. Employing MST is a solution to comparing network topologies under different conditions since there is no need to set thresholds and use a fixed number of nodes and edges. The MST method has the advantage that the MST of the weighted linkage metric is unique when the weights are unique [1]. Although many connections are removed due to the nature of this method, it is equally sensitive to the network topology as the existing graph theoretical measurement [2]. The potential of brain network properties to serve as neurological and psychopathological biomarkers is hampered by threshold problems. The MST is free from this problem, so it has increasingly been applied [1].

The MST metric is also robust against substantial noise in the data [5]. It is actively used in brain research related to brain diseases, and there are various MST-based research results related to this area.

In MST studies [5], MST leaf area significantly correlates with the network size, although MST analysis has not yet led to definitive neuropsychiatric symptoms or disease biomarkers.

Studies investigating Alzheimer’s disease (AD), a neurodegenerative disorder, using MST analysis by analyzing the functional connectivity, examined differences in brain networks between AD patients and healthy controls (HCs). The AD group showed a less integrated structural network with such MST metrics as a higher characteristic path length, but lower leaf fraction [6].

An abnormal MST structure is observed in patients with AD and mild cognitive impairment (MCI). In a study [7–9] using resting functional magnetic resonance imaging (fMRI) to examine functional brain connectivity changes in AD and MCI patients, AD and MCI patients showed abnormal MST characteristics in functional brain networks related to cognitive performance.

Over time, changes in MST properties in AD patients correlate with disease progression [7–9]. The MSTs for classifying Parkinson’s disease and essential tremor patients from diffusion magnetic resonance imaging (dMRI) data study use dMRI to investigate the brain’s structural connectivity. This result demonstrated differences in brain network connectivity between Parkinson’s disease and essential tremor patients [10].

MST analysis of the human connectome is employed to investigate the structural connectivity of the human brain. The study [11] examined various characteristics of the human brain’s connectivity (e.g., connection strength and type) using MST analysis and revealed that specific brain regions are more strongly connected to other brain regions.

MST methods are related to the severity of Parkinsonian cognitive impairment to neural connectivity changes [12]. Yan et al. (2019) used MST analysis to investigate changes in the global topology of functional brain networks and explore the relationship between these changes and cognitive function [13].

The study aims to investigate the difference in the global topology of brain networks in epilepsy patients via MST analysis. The epilepsy patients had an altered MST compared to HCs, with longer path lengths and decreased clustering coefficients. The degree of MST alteration was associated with the frequency and duration of seizures [14].

In this paper, individual and group-wise MST analyses are conducted for epilepsy patients and HCs. The main goal of this study is to examine whether there are any changes in the overall topology of brain networks among individuals and groups with epilepsy by employing MST analysis. Additionally, the aim to investigate the relationship between these alterations in network structure and specific epilepsy-related characteristics. The MST metrics are also computed for the resulting MSTs for group comparison.

Materials and methods

Data analysis pipeline

Individual subject MST

The following steps were applied for the analysis of epilepsy MEG data. In this study, epilepsy patients and HCs underwent MEG, neuropsychological assessment, and neurological examination. MST metrics were utilized for the analysis of variance (ANOVA) for group comparison.

The MEG data at the sensor level were projected onto an AAL atlas using beamforming, resulting in a 72-time series for each ROI (Figure 1A). The correlation coefficients between pairs of ROIs based on the entire time were calculated. A 72 × 72 adjacency matrix is constructed. This adjacency matrix is reconstructed based on the hierarchical clustering and shown in the image plot (Figure 1B). Considering the concept of distance with pairwise Pearson correlation r, calculate d = 1 – |r| for the adjacency matrix. Then the Prim algorithm was applied to obtain the MST matrix (Figure 1C). This distance was chosen as the simplest way to minimize bias in converting to the distance concept from correlation. The data is divided into three accumulated parts for the analysis according to three time-points. Optionally, three time-points at 10,000 (T1), 20,000 (T2), and 30,000 (T3) are chosen.

Display full size

Figure 1. 

Overview of the applied methods (lt020 patient for example). (A) MEG data; (B) connectivity image plot reordered with hierarchical clustering; (C) connectivity image plot reordered with MST analysis; (D) network graph with MST result; (E) tree graph with MST result on two first nsca axes

The MST analysis pipeline is illustrated in Figure 1. This MST is displayed as a graph on a brain image (Figure 1D). An example of a weighted MST tree graph is shown in Figure 1E. The overlapped nodes in Figure 1E are indicated as close to each other. The axes are the two first non-symmetric correspondence analyses (nsca, [18, 19]). The two dimensions of nsca are determined through principal component analysis (PCA) to maximize the variability in the original data along these two centered axes. The tree structure in Figure 1E is listed with the linked nodes as follows:

1-36, 2-22, 2-32, 2-42, 2-43, 2-59, 3-7, 3-11, 3-52, 4-34, 5-15, 5-32, 6-13, 6-32, 7-47, 8-31, 8-38, 8-44, 8-45, 8-57, 9-45, 10-14, 10-33, 10-71, 11-50, 12-46, 14-69, 16-21, 16-32, 17-35, 18-30, 18-32, 19-25, 20-24, 23-35, 23-60, 24-59, 25-26, 26-65, 27-29, 28-63, 29-61, 30-66, 31-33, 31-36, 31-41, 32-62, 33-39, 33-46, 34-70, 35-67, 35-71, 36-54, 36-63, 37-58, 40-48, 43-50, 48-50, 49-69, 51-53, 51-65, 51-66, 52-58, 55-57, 56-60, 61-72, 63-65, 64-65, 67-68, 67-70, 71-72.

Group-wise MST integration

Integrating individual data into one representative is a complicated problem, especially in combining the MEG data in each group. The researchers have yet to find the suggested way to combine MST from the previous research. Therefore, a new solution was tried in this article. Each MST was derived from the individual MEG network. Then an integrated MST was made by combining these MSTs with some weight matrices. The suggested steps are as follows. Here the connectivity measure should be converted to the distance measure.

First, the MST for each subject is obtained, followed by the application of the distance concept at a given time-point. Second, each subject MST matrix T_i is component-wise multiplied by each subject weight matrix w_i for MST T_i, resulting in integrated MST. Here N_g is the generative total number of group g. As a distance metric for MST. The following matrix computed as a distance metric for MST within each group.

Eqn. 2.6:

$${IT}_g=1-\sum T_i°w_i/N_g$$

Here ° is an element-wise product operator known as Hadamard product. Individual weight matrix w_i is defined as the degree of each node of an individual MST T_i.

Subtraction is made to make the distance for the MST. Finally, the resulting model is created by applying MST to IT_g such as

Eqn. 2.7:

$${Integrated}_{{MST}_g}=MST\left({IT}_g \right)$$

The integrated MST model can be a representative MST in each group at the corresponding time.

Results

Hub nodes in each subject MST were initially identified. In each group, the hub node was defined as a hub node when it was not only selected as the hub node from individual data but also as the hub node from more than five subjects. Then, the top three hub nodes were selected.

One important finding is that hub node 71 [posterior cingulate gyrus, limbic(right)] appears only in the patient LT and RT. Nodes 10 (superior frontal gyrus, orbital part) and 11 (superior frontal gyrus, medial orbital) in the orbital surface area were found as hub nodes at whole time-points of LT and HC. Node 33 (anterior cingulate and paracingulate gyri), corresponding to the limbic system, was selected as a hub node (an average of 12 times) throughout the whole time-points in HC. The hub nodes in each group by time-point are briefly summarized in Table 1.

Additionally, MST metrics were calculated and mean comparisons were performed using ANOVA and Kruskal-Wallis tests with nonnormality at each time-point. There was no significant difference between groups in a maximum BC but significant in means of BC. The average shortest path length in HC is also the lowest. Significant differences were observed at each time-points.

The eccentricity shows a significant difference only at time-point T2. Moreover, RT had the highest eccentricity. As a result of Tukey’s post-hoc analysis on eccentricity at time-point T2, one group (HC, LT) with RT was determined as one group.

The diameter was the largest in RT, but no statistically significant difference was found. The diameter and eccentricity of LT fluctuated between time-points. Further investigation is required in these measures.

The leaf fraction showed a significant difference at the T1 time-point. The leaf fraction was high in patients with epilepsy. Also, there was no significant difference between T2 and T3 time-points. In the whole time-points, RT has the most considerable eccentricity, diameter, and the average shortest path length. It tells that the RT patient network efficiency is the worst among the three groups.

Our data showed no significant difference between the tree hierarchy overlaps in seizure-free epileptic patients with an excellent postoperative prognosis. It supports the results of previous studies [16, 20]. The MST metrics summary and ANOVA results are shown in Table 2.

As discussed earlier, the MST method might be precious when comparing patients with controls. Because MST networks have a unique advantage that does not need a threshold, and MST networks from different groups contain the same number of nodes and connections. The MST metric results, which integrate individual data into one, were measured at 30,000 time-points.

What is noteworthy in this study is that node 71 was designated as a hub node only in the patient group in the integrated data as well as in the individual data analysis.

In addition, as a result of checking the centrality values of the 71st node, the LT group had 0.391, RT 0.389, and HC 0.028, which showed higher centrality of mediation in the patient group.

Similar to the individual data analysis, RT had the highest degree, and there was no significant difference between the control and patient groups in leaf fraction or tree hierarchy. On the other hand, in the integrated data, the LT group showed the highest BC and average shortest path length. However, the HC group still appears to have the best network efficiency with the smallest eccentricity, BC, average shortest path length, and diameter. The summarized results are presented in Table 3.

Integrated with weights was performed to draw an MST on the brain image in each group. In Figure 2, node 71 (the posterior cingulate gyrus) stands out in the LT and RT groups at the lower 2/3 part of the brain in the middle.

Display full size

Figure 2. 

Integrated MST at time-point = 30, 000 (T3) for LT (left), RT (middle), and HC (right)

Our results show that the results of the RT group in individual metrics are less likely to have a network effect. It is unknown whether these results are related to the surgical operation, and it is unlikely that this is a characteristic of patients who underwent surgery on the right side. However, it was found that HC had a shorter average shortest path length and average mediation centrality for both LT and RT groups.

The posterior cingulate gyrus in the patient group is known as the default network of the hippocampus in the limbic system. Our results show that only in the patient group, node 71, this default network is continuously active as the hub node, in contrast to the control group. It can hint that the default network is activated in the patient group. Our results suggest that, in the end, when one side of the hippocampus breaks down, it borrows from the default network to compensate for the weakened function. In addition, our patients had good prognosis because the surgery went well. Nevertheless, there were differences in topology and hub nodes between groups. At each time-point, our integrating method can be considered to combine and summarize the subject MSTs in each group.

Discussion

The MST with MEG data for epileptic patients and HC group was analyzed. The MST analysis is adopted to compare these groups because it facilitates topological information with fixed edges. There are few previous MST merging studies for brain imaging data. Our study suggests aggregating the individual MST results with node degree. Rather than applying MST to simple average connectivity, our method combines individual MSTs with node degree weights. This method can incorporate the individual MST information and degree information together. MST metrics can distinguish the patient and control groups. Our method can be used as topological features in individual and integrated ways.