Brain Functional Network Based on Small-Worldness and Minimum Spanning Tree for Depression Analysis

Bingtao Zhang, Dan Wei, Yun Su, Zhonglin Zhang

Abstract: Since the outbreak and spread of corona virus disease 2019 (COVID-19), the prevalence of mental disorders, such as depression, has continued to increase.To explore the abnormal changes of brain functional connections in patients with depression, this paper proposes a depression analysis method based on brain function network (BFN).To avoid the volume conductor effect, BFN was constructed based on phase lag index (PLI).Then the indicators closely related to depression were selected from weighted BFN based on small-worldness (SW) characteristics and binarization BFN based on the minimum spanning tree (MST).Differences analysis between groups and correlation analysis between these indicators and diagnostic indicators were performed in turn.The resting state electroencephalogram (EEG) data of 24 patients with depression and 29 healthy controls(HC) was used to verify our proposed method.The results showed that compared with HC, the information processing of BFN in patients with depression decreased, and BFN showed a trend of randomization.

Keywords: depression; brain function network (BFN); small-worldness (SW); minimum spanning tree (MST)

1 Introduction

Depression is a mental disorder with persistent low mood and brain function damage as its typical clinical symptoms [1].According to the disclosure by World Health Organization (WHO),about 350 million people in the world are affected by depression in varying degrees [2].Compared with most physical diseases, the underlying neurological mechanism and pathological principles of depression are still unclear, so analyzing its brain function network (BFN) is an urgent need for effective recognition and intervention.

In recent decades, researchers have found that the brain functional connectivity is closely related to mental diseases, such as depression,epilepsy [3], and sleep disorders [4–6].For depression, researchers have conducted in-depth studies on morphological and physiological features.Cai et al.[7] achieved efficient depression detection based on multimodal fusion using electroencephalogram (EEG) features.To provide an effective detection method for mild depression, Li et al.[8] tried the combination of five feature selection methods and five classification algorithms, and it’s found that the combination of greedy stepwise based on correlation features selection and K-nearest neighbor (KNN) had the best performance.Zhang et al.[9] proposed a depression recognition framework based on feature-level fusion of spatial-temporal EEG, and the highest accuracy of 92.48% was obtained.

Human brain is one of the most complex systems in the world.It is difficult to reveal the alter rules of BFN in patients with depression that hidden deep in the brain if only the features is taken as a foothold.The development of complex networks provides a new perspective for the study of BFN and depression [10].Researchers use magnetic resonance imaging (MRI) and EEG data to construct various BFN, and then compare the differences of functional connectivity between patients with mental illness and healthy controls (HC), to explore the topological changes of their brain network [11].By the difference analysis of functional connectivity based on functional magnetic resonance imaging (FMRI), Shi et al.proposed a new method for identifying patients with Alzheimer’s disease (AD) from HC by using active voxels of the brain [12].EEG based BFN analysis of patients with schizophrenic showed that the regulatory effects of clustering coefficient and characteristic path length are disappeared significantly between baseline and response [13].Meanwhile, current studies have confirmed that mental diseases are closely related to abnormal topology changes of brain network [14].The purpose of this paper is to analyze and study the topological changes of functional connectivity in patients with depression from the brain network level, and then explore its potential markers and realize automatic recognition of depression.

As we all know, MRI has a high spatial resolution while EEG has a high temporal resolution[15, 16].Compared with MRI, EEG is more suitable for constructing functional connectivity related networks.In addition, it is considerable that EEG has the advantages of non-invasiveness, convenience to collect, and low cost.Therefore, this paper pays more attention to the research and analysis of BFN based on EEG.

To sum up, there are two key problems in this study need to be solved urgently.First of all how to construct the BFN based on EEG, and secondly how to analysis the BFN.Therefore,this paper proposes a BFN framework based on small-worldness (SW) and minimum spanning tree (MST) for depression analysis.EEG data are recorded by the acquisition equipment, and the weighted BFN and MST are constructed using the phase lag index (PLI) after preprocessing.On the basis of SW theory, the initial indicators of weighted BFN are extracted, and the initial indicators of significant difference for brain regions are extracted based on the adjacency matrix between MST groups.Finally, the patients with depression are recognized from HC based on the statistical analysis of the initial indicators.After condensing, the main contributions of this study can be summarized as the following aspects.

1) Through the correlation analysis between patient health questionnaire 9-items (PHQ-9)score and BFN indicators, we found that clustering coefficient, average characteristic path length,leaf fraction in left temporal region and diameter in right parietal-occipital region can be used as potential markers for depression recognition, and obtained the highest recognition accuracy of 95.76%.

2) Based on MST and difference matrix analysis, we found that the BFN connectivity of patients with depression is abnormal relative to HC.

3) PLI-based weighted BFN and non parametric permutation test found that a trend of randomization in BFN of depression patients.

2 Data and Preprocessing

EEG data used in this study are from a multimodal open dataset for mental disorder analysis(MODMA dataset) [17].The original MODMA dataset contains data of three types of depress patients and corresponding HC: event-related potentials data of 128-electrodes, pervasive 3-electrodes EEG data, resting state EEG data of 128-electrodes.

In this study, resting state EEG data of 128-electrodes were used, which contains 24 depression patients (male/female=13 : 11) and 29 HC(male/female=20 : 9).The subjects were between 18 and 52 years old, with a primary school education or above.EEG signal sampling rate was 250 Hz and the acquisition time was about 5 min.The reference electrode was Cz.For patients with depression, PHQ-9 scores ≥ 5, and for HC subjects PHQ-9 scores < 5.

In the process of recording EEG, noise is inevitable, to make the experimental data meet the research needs, it is necessary to perform preprocessing on the original data.First of all, on the basis of ensuring the electrodes uniform distribution and to reduce the calculation amount,only 64-channel resting state EEG data were selected in this study.The specific electrode distribution is shown in Fig.1, in which blue is left frontal (LF), dark green is right frontal (RF),olive green is left temporal (LT), grass green is right temporal (RT), orange is left central (LC),yellow is right central (RC), red is left parietaloccipital (LPO), brown is right parietal-occipital(RPO)

Fig.1 The distribution of 64 EEG electrodes

Studies have shown that EEG signal related to depression are distributed between 0.5 Hz and 50 Hz [18].In this paper, the EEGLAB toolbox is used to filter EEG signal.The signal is filtered by the band-pass filter with a high cut-off of 50 Hz and a low cut-off of 0.5 Hz to eliminate high-frequency noise and low-frequency drift.Electrooculogram (EOG) is the main noise doped in the EEG acquisition process, and even in the resting state, the amplitude of EOG is more than ten times that of EEG amplitude[19, 20].Usually EOG noise appears in the range of 0 Hz and 16 Hz, which overlap with the EEG signal in this frequency range.To this end, this paper uses a combination of discrete wavelet transform and adaptive noise cancellation proposed by Peng et al.[21] to remove EOG noise,thereby obtaining purer EEG data.

3 Methodology

3.1 BFN Construction

In this study, EEG electrode is defined as node,and the dependence relationship between nodes is defined as edge.EEG signals are recorded by placing electrodes on the scalp surface.Ideally,electrodes record signal sources that reflect neuronal activity.In fact, each tissue in the brain has certain electrical conductivity characteristics,so the brain is regarded as a volume conductor,and the activities of different neurons in the brain are conducted in different directions on the scalp, resulting to different neuron activities being recorded by electrodes, which leads to the volume conductor effect and affects the accuracy of EEG recording.PLI can effectively solve the problem of volume conductor effect by analyzing the synchronization difference of different signal sources.Therefore, to avoid the volume conductor effect, PLI is used to measure the synchronicity between nodes in the paper [22].For an arbitrary EEG signalx(t), its analytical signalψ(t)can be defined as the following complex function

whereA(t) is the instantaneous amplitude andφ(t)is the instantaneous phase.The phase difference between the signalsxa(t) andxb(t) is defined as

PLI is defined as an asymmetric measure of phase difference distribution

where sign is the symbolic function andNis the number of sampling points.

Previous studies have shown that there is a significant difference of EEG signal between depressed patients and HC in theta (4–8 Hz) frequency band [23].Therefore, theta band is used as the region of interest (ROI), and the PLI between EEG channels was calculated each 6 seconds to construct the adjacency matrix of BFN.The corresponding position values of the adjacency matrix is averaged to obtain the 64×64 adjacency matrix of depression group and HC group respectively, and then the BFN of the two groups is drawn.

3.2 BFN Indicators Based on SW and MST

The complex network theory clarifies that normal BFN has stable SW characteristics [24], that is, the network topology has high clustering coefficient and low average characteristic path length.However, The SW characteristics of psychiatric patients showed a trend of randomization [25].Therefore, the SW characteristic has been widely used in the related research fields of brain science and mental diseases.Based on the above reasons, the clustering coefficient and average characteristic path length were selected as the initial indicators for BFN study of depression patients in this paper.

The clustering coefficient represents the collectivization degree of the network.Node degree is the number of edges connected to the node.If the degree of nodeiisk, its clustering coefficient is defined as the ratio of the actual number of edges between theknodes to the total number of edges between theknodes.Similarly, the clustering coefficient of nodeiin the weighted network can be defined as

wherewijis the connection weight between nodesiandj, and the clustering coefficient of the weighted network is defined as

This index is used to describe the connection tightness between nodes.C=0, it means that all nodes in the network are isolated;C=1, it means that any two nodes in the network are directly connected.

The average characteristic path length is the average value of the distance between any two nodes, which is used to describe the global connection characteristics of the network.The shortest pathLijis the path with the least number of edges between any two nodesiandj.In the weighted network, the length of the connecting edge is defined as the reciprocal of the edge weight, that isLij=1/wij,wherewijis the element of rowiand columnjin the adjacency matrix.The average characteristic path length ofNnodes in the weighted network is defined as

Additionally to the above two initial indicators of BFN, to explore the difference between depression and HC, to improve the comparability between two groups, and to avoid the sparse sensitivity problem of traditional network, MST is introduced to realize binarization BFN based of the weighted brain network [26].MST is loopfree sub-network of the original network, which contains most of the strongest connections in the original network.The number of edges is the number of nodes minus 1.The network with the same number of nodes has the same number of edges, that is, the network scale is the same.Therefore, MST guarantees that the differences between groups of BFN are mainly caused by topological differences.This study adopts Kruskal’s algorithm to generate MST.Its core idea is to select the edge with the largest weight from the original network in turn without forming a loop and connect its corresponding nodes until all nodes of the network fall on a tree.

Fig.2 gives the corresponding adjacency matrix of two groups generated using Kruskal’s algorithm.However, Fig.2 doesn’t clearly show differences between groups, so we calculated the difference matrix between groups based on the adjacency matrix in Fig.2, and drew 3D graph of the corresponding difference matrix, as shown in Fig.3.The results showed that compared with the HC group, the connection density in the depression group was changed in the RF, LT,and RPO regions, and that is, the synchronous abnormality occurred.These results suggest that the differences of BFN between depression group and HC group mainly exist in these three regions.MST can provide the core topological information of the BFN [27].Therefore, the typical MST attributes in LT, RPO and RF brain regions were selected as the initial indicators for BFN study for depression.These indicators include degree, leaf fraction, diameter, betweenness centrality, tree hierarchy and eccentricity.Their specific descriptions are listed in Tab.1.

Fig.2 Adjacency matrix based on MST: (a) depression group;(b) HC group

Fig.3 Difference matrix between groups

Tab.1 MST related initial indicators

3.3 Differences Analysis of BFN Indicators Between Groups

Quantitative analysis of the BFN indicators for assess whether these were statistically significant between depression group and HC group.Nonparametric permutation test was used to calculate the average differences (t-value) of initial indicators between groups and as the observation value of test statistics.During this permutation process, all subjects were randomly assigned to depression group and HC group, remaining the number of subjects in each group unchanged, and the number ratio was still 24 : 29.Repeat calculation 2 000 times of the rearrangedt-value between groups, so as to obtain the zero distribution of the test statistics for the differences between groups.Finally, the sampling permutation proportion witht-value greater than the observation value of the test statistics was determined as the observedpvalue of group difference, in which the significant level was set asp<0.05.

3.4 Correlation Analysis of BFN Indicators with PHQ-9

In clinical practice, doctors use the PHQ-9 score as one of the main basis for clinical diagnosis of depression.Meanwhile, recently researchers often use the correlation between functional connectivity indicators and scale scores, such as PHQ-9 score, to determine whether the corresponding indicators can be used as potential markers for the diagnosis of related diseases [28].In this study, to determine whether the BFN indicators can be used as potential markers to distinguish depression patients from HC, the Pearson correlation coefficient was used to analyze the correlation between the BFN indicators and the diagnostic index PHQ-9 score between groups, and the significance level was set asp<0.05.

3.5 Performance Evaluation

In this study, the KNN classifier is adopted to evaluate the recognition performance.Previous studies have proved that KNN classifier was superior to other classifiers in depression recognition [29].To obtain unbiased results, the KNN classifier performs 10-fold cross validation, that is, the experimental data is divided into 10 folds,9 folds are training samples and remaining 1 fold is testing sample.Additionally, to get statistically meaningful results, classification tasks are performed 10 runs, which mean that 100 calls of KNN classifier with training samples and testing samples.In other words, this experiment consisted of 100 runs.Finally, the arithmetic average of 100 runs is used as the result for evaluation.

Accuracy, sensitivity, and specificity are used to evaluate classification performances [30, 31],which are calculated as

TP indicates the number of correctly classified patients with depression, FP indicates the number of incorrectly classified patients with depression, TN indicates the number of correctly classified HC, and FN indicates the number of incorrectly classified HC.

4 Results

4.1 Depression-Related BFN Indicators

Based on nonparametric permutation test, we evaluated the differences between groups for the clustering coefficients and average characteristic path length of weighted BFN and the indicators of binarized BFN.

Fig.4 shows the difference analysis results of clustering coefficients and average characteristic path length between depression group and HC group in full brain.Compared with HC group,the clustering coefficient is significantly decreased and the average characteristic path length is significantly increased of depression group.Generally, the HC have stable SW attributes, that is, a larger clustering coefficient and a smaller average characteristic path length.The results of Fig.4 indicate that these two attributes of patients with depression are abnormal, that is the clustering coefficient and average characteristic path length of the weighted network may be used to distinguish depression patients from HC.

Fig.4 Difference analysis results based on weighted BFN: (a)clustering coefficients; (b) average characteristic path length

Based on the location distribution of difference matrix 3D graph in Fig.3, the three brain regions of LT, RPO, and RF are further analyzed and the results are shown in Fig.5.The leaf fraction, tree hierarchy and eccentricity in LT region, the diameter in RPO region, and the leaf fraction in RF region are significantly different between groups.Due to space limitation,other brain regions without significant differences are not listed in Fig.5.The statistical significance of Fig.5 is indicate that these five indicators with significant differences may be used in the distinguish depression patients from HC.

4.2 Depression-Related Recognition Indicators

On the basis of the significant difference indicators between groups in Fig.4 and Fig.5, the correlation between these indicators and PHQ-9 score is further evaluated based on Pearson correlation coefficient.Fig.6 lists the indicators that are significantly correlated with the PHQ-9 score among these indicators, the clustering coefficient and average characteristic path length of weighted BFN are significantly correlated with PHQ-9 score (p<0.05), while the binarization BFN only has leaf fraction in LT region and the diameter in RPO region significantly correlated with PHQ-9 score (p<0.05).Therefore, the four indicators in Fig.6 can be used as potential markers for depression recognition.The indicators that have no significant correlation with PHQ-9 score are not listed in Fig.6.

Fig.5 Difference analysis results based on binarized BFN: (a) leaf fraction in LT region; (b) tree hierarchy in LT region; (c) eccentricity in LT region; (d) diameter in RPO region; (e) leaf fraction in RF region

4.3 Results of Depression Recognition

To verify the effectiveness and classification ability of BFN indicators that are significantly related to the PHQ-9 score as potential markers to distinguish depression from HC.Four indicators are input into KNN classifier (k=3, algorithm=“kd_tree”) using 10-fold cross validation,and the results are shown in Tab.2, which lists the average performance of four indicators individually and union as potential markers.It can be seen from Tab.2 that the four indicators are respectively used as KNN input, CC has the strongest recognition ability.The four indicators are union used as KNN input can be obtain the highest classification accuracy.

Fig.6 Significant indicators related with PHQ-9 score: (a) clustering coefficient of weighted BFN in full brain; (b) average characteristic path length of weighted BFN in full brain; (c) leaf fraction of binarized BFN in LT region; (d) diameter of binarized BFN in RPO region

Tab.2 Average performance of four indicators individually and union as potential marker

4.4 Results of MST and SW Analysis

In this study, MST and difference matrix are adopted to find that the synchronization change of BFN connections in depression patients relative to HC.The results show that synchronization significantly increased in LT and RPO regions, and synchronization significantly decreased in RF brain region.We speculate that this phenomenon is the external manifestation of functional connectivity synchronization imbalance caused by abnormal brain information processing in patients with depression.

Small world network represents an optimal network organization structure.BFN constructed by EEG data of healthy population has stable small-world network characteristics, while BFN constructed by patients with mental diseases using the same data usually shows a trend of randomization and partly loses SW characteristics [32].In this study, the PLI-based weighted BFN and non-parametric permutation test found that there were significant differences in the clustering coefficient and average characteristic path length between depression patients and HC.This finding means that the SW characteristics of patients with depression were at risk of randomization, and the BFN of depression patients has a trend of randomization.

4.5 Comparison and Analysis of Related Models

Considering that different models adopt different datasets or data usage strategies, the comparison of one or several indicators can’t fully reflect the advantages and disadvantages of each model.Based on this consideration, Tab.3 gives a comparison between several recent state-of-the-art models for analysis and recognition of depression in recent years and our proposed method, and from the advantages and disadvantages, accuracy and other aspects of these models were evaluated and analyzed.Although such comparative evaluation cannot fully explain which model is optimal, the comparison can enable readers to have a deeper understanding of the current research status in this field and provide certain support and help for relevant researchers.

Tab.3 Comparison between several recent state-of-the-art models for analysis and recognition of depression and our proposed method

5 Conclusions and Future Work

To address the problem of depression analysis and recognition, this paper proposes a BFN analysis framework based on SW and MST.Based on the nonparametric permutation test, we obtained several BFN indicators with significant differences between groups.Then, the correlation between these indicators and PHQ-9 score was further evaluated using Pearson correlation coefficient.It was found that CC, ACPL, LT-Lf and RPO-Dia can be used as potential markers for depression recognition.The highest recognition accuracy of 95.76% can be obtained using these indicators.

As we have shown, our proposed scheme is feasible and can be used for clinical analysis and auxiliary diagnosis of depression in the future work.In recent years, with the rapid aging of the world population, the number of patients with geriatric depression and Alzheimer’s disease has increased year by year.Although this study used data from depression patients aged 18 to 52 years and HC to achieve the analysis and clinical auxiliary diagnosis of depression.However, our proposed method can be extended to other research on analysis and recognition of mental disorders based on EEG data, such as geriatric depression,Alzheimer's disease and other typical geriatric diseases.In the foreseeable future work, our proposed analysis and auxiliary diagnosis method for depression will reduce the work burden of medical staff and benefit different populations such as young, middle-aged and old population.