Graph Theoretical Measures for Alzheimer’s,MCI,and Normal Controls: A Comparative Study Using MRI Data

Abstract

Background

The Graph theory provides the platform that could be used to model complex brain networks mathematically, and it could play a significant role in the diagnosis of various neurodegenerative diseases such as Alzheimer’s.

Purpose

The main aim of our study is to perform a comparative analysis in terms of various graph theoretic measures of structural brain networks. In particular, the paper evaluates graph theoretical measures by first forming graphs using magnetic resonance imaging (MRI) data.

Method

In this paper, we study and evaluate graph theoretical measures using MRI data, namely characteristic path length, global efficiency, strength, and clustering coefficient, in a cohort of normal controls (N = 30), a cohort of mild cognitive impairment (MCI) (N = 30), and a cohort of Alzheimer’s disease (AD) (N = 30). In our work, MRI data is preprocessed and cortical thickness is extracted for each brain region. The connectivity matrix is obtained, and thus a graph is formed. We have also performed receiver operating characteristic (ROC) and area under the ROC analyses of all graph theoretical measures to better elucidate and validate the results.

Results

It is observed that these measures may be used to differentiate Alzheimer’s from normal. In our study, we observed that a very random and disrupted network is obtained in the case of Alzheimer’s in comparison with the normal and MCI cases. The other observations in terms of graph theoretic measures are an increase in characteristic path length, a decrease in global efficiency, a decrease in strength, and a reduction in values of the clustering coefficient in the case of Alzheimer’s.

Conclusion

The findings suggest that graph theoretical measures and alterations in network topology could be used as quantitative biomarkers of AD.

Keywords

MRI mild cognitive impairment (MCI)brain connectivity Alzheimer

Introduction

The brain is the most fascinating and least understood organ in the human body. Researchers have for a long time pondered the relationship between behavior, emotion, memory, thought, consciousness, and the physical body.¹ The role played by medical imaging in the field of neuroscience is significant. The neuroimaging or brain mapping² is the use of various techniques to image the structure and functions of the nervous system. Various imaging modalities,³ such as X-ray, computed tomography, and magnetic resonance imaging (MRI), allow better understanding and characterization of tissues at the structural, hemodynamic, and functional levels.

MRI is a neuroimaging technique¹ that provides structural information about the brain. One of the major advantages of MRI⁴ is the ability to image the soft tissue in the human body and its metabolic processes. It is a powerful imaging modality because of its flexibility and non-invasive nature.⁵ It offers great promise for understanding the human body at the structural, functional, and hemodynamic levels. The MRI stems from the application of nuclear magnetic resonance (NMR) to radiology imaging.⁴ MRI, based on the phenomenon of NMR,⁵ produces images of the human body with excellent soft tissue contrast, distinguishing between gray and white matter of the brain and brain defects such as tumors. It provides excellent characterization between the gray matter,³ white matter, and cerebral spinal fluid. MRI is a non-ionizing technique⁵ with full three-dimensional capability and high spatial resolution.⁴ It is well known that neurodegenerative diseases⁶ severely affect the structural connectivity of the brain. Since graph theoretic measures⁷ are best suited to capture such information, we employed them in our study. Hence, in our study, we have carried out a graph theoretical analysis of MRI data comprising 30 normal controls, 30 mild cognitive impairment (MCI), and 30 Alzheimer’s patients, acquired from the Alzheimer’s Disease Neuroimaging Initiative (ADNI) database.

In the literature, most of the papers investigate network alterations in Alzheimer’s disease (AD) by using electroencephalogram,⁸ functional MRI,⁹ diffusion tensor imaging¹⁰ data, but there are very few studies focusing on network alterations in the continuum of AD using MRI data. In our work, we have performed a comparative analysis in terms of various graph theoretic measures of structural brain networks in normal controls, MCI, and Alzheimer’s patients using MRI data. To perform a structural whole-brain connectivity analysis,¹¹ it is necessary to define the brain Atlas. In our analysis, we have used the Desikan Atlas,¹¹ which has 68 brain regions.

Methods

Subjects

In our study, we have used the MRI data obtained from the ADNI database,¹² available at adni.loni.usc.edu. For our analysis, we have taken the MRI data of 90 subjects, out of which 30 were normal controls, 30 were MCI, and 30 were Alzheimer patients. Table 1 provides relevant details about the database¹² used in our study.

Table 1.

Demographics of Studied Cohort.¹²

Variables	Normal Controls	Mild Cognitive Impairment	Alzheimer’s
Number of subjects	30	30	30
Age	72.9 ± 5.6	73 ± 4.5	74 ± 6.9
Gender	Male	Male	Male
Mini mental state exam²⁶	29.4 ± 1.1	25 ± 2.7	22.3 ± 3.8
Clinical dementia rate²⁶	0 ± 0	0.7 ± 0.2	0.9 ± 0.5

MRI Acquisition

The data were obtained from the ADNI database¹² where all the participants have gone through an MRI scan of 1.5T using a T1-weighted magnetization prepared rapid gradient echo¹³ sequence having repetition time (TR) = 9−14 ms, echo time (TE) = 3.2−4 ms, inversion time (IT) = 900 ms, flip angle = 7 degrees, and voxel size = 1 × 1 × 1.2 mm³.

Image Processing

All MRI data were preprocessed using the Free-surfer tool,¹⁴ which is freely available at http://surfer.nmr.mgh.harvard.edu/. The preprocessing includes correction of motion artifacts¹⁵ and spatial distortion due to gradient non-linearity and B1 field homogeneity; removal of non-brain tissue using the surface deformation procedure;¹⁶ automated translation into the Talairach standard space by normalizing onto the Montreal Neurological Institute template;⁴ and segmentation of gray matter and white matter structures. This was followed by the parcellation¹⁵ of the cerebral cortex into 68 cortical regions using the atlas by Desikan et al.¹¹ In our work, we have extracted the cortical thickness¹⁷ of 68 brain regions from the Desikan atlas.

Graphical Analysis

The graph theoretical analysis means obtaining brain graphs from human MRI data^{18, 19} (simply image data). The whole analysis comprises three main steps.

Network Construction

Network construction implies building the structural connectivity matrix⁷ from MRI data. To obtain the connectivity matrix,²⁰ first of all, the raw MRI data was preprocessed. This preprocessing²¹ involves several steps such as realignment, magnetic field homogeneity correction, registration, and segmentation. After carrying out preprocessing steps, the cortical thickness²² was extracted for each brain region for each of the subjects listed in Table 1, so the nodes²³ in the connectivity matrix correspond to brain regions of the atlas¹¹ employed in the analysis. The edges were calculated as the correlation coefficient⁹ of the value of cortical thickness extracted earlier (for each of the three cases separately, namely normal controls, MCI, and Alzheimer’s) between pairs of brain regions across the group of subjects. Therefore, the structural connectivity matrix was obtained for each group of subjects, 30 in each category.²⁴ So the connectivity matrix was built such that rows and columns represent brain regions, and entries represent correlation coefficients between cortical thicknesses for each pair of brain regions.²⁵

Network Analysis

Once we have the structural connectivity matrix at our disposal, we can calculate various graph theoretic measures, or brain measures²⁶ that assess the topology of the whole brain network. These brain measures are degree,⁷ which is the average number of connections a node has with the rest of the network or the total number of edges connected to a node; characteristic path length⁷ is the average distance from a node to all other nodes; clustering coefficient⁷ is a fraction of triangles present around a node; global efficiency⁷ is the average of the inverse shortest path length from a node to all other nodes; and strength⁷ is the sum of weights of all the edges connected to a node.

Network Implications

The network implication implies the pattern of brain graphs that depict early changes within individuals over time, depicting the alterations²⁷ in network topology.

Results and Discussion

As mentioned earlier, after preprocessing the MRI data for all three cases, namely normal controls, MCI, and Alzheimer’s, connectivity matrices are computed. The connectivity matrices are used to compute various graph theoretic measures, mentioned in subsection “Network Analysis” and tabulated in Table 2. These graph theoretic measures were computed using the brain connectivity toolbox²⁸ (brain-connectivity-toolbox.net), which is a MATLAB-based toolbox. The results so obtained suggest that these measures could act as biomarkers of AD. In Alzheimer’s, the observable brain measures are increased in characteristic path length and reduced in global efficiency, strength, and clustering coefficient, which differentiates Alzheimer’s from normal controls. It is also interesting to note that values for MCI (Table 2) fall in between, suggesting continuity in the degradation process, which may be exploited to quantify the measure of degradation.

Table 2.

Brain Measures in Normal, Mild Cognitive Impairment, and Alzheimer’s.

Normal	Mild Cognitive Impairment	Alzheimer’s
Characteristic path length = 4.5	Characteristic path length = 4.7	Characteristic path length = 4.8
Global efficiency = 0.26	Global efficiency = 0.23	Global efficiency = 0.19
Strength = 12.40	Strength = 10.94	Strength = 7.56
Clustering coefficient = 0.17	Clustering coefficient = 0.14	Clustering coefficient = 0.11

The brain graphs were obtained as presented in Figure 1a–c, which represents the structural connectivity pattern in the cases of normal controls, MCI, and Alzheimer’s, respectively, describing the degradation process in terms of strength of connection and number of connections connecting various brain regions (Table 2). In normal controls, a much more organized and consistent network is obtained, depicting high connectivity strength; on the other hand, in MCI, the connectivity strength declines, and in the case of Alzheimer’s, a more random and disconnected network is obtained. In particular, the connections are disconnected between

Interhemispheric frontal poles

Interhemispheric lateral occipital lobes

Intrahemispheric frontal poles and pars orbitalis

Intrahemispheric lateral occipital lobes and superior temporal sulcus.

Figure 1.

(a) Brain Graph of Normal controls. (b) Brain Graph of Mild Cognitive Impairment. (c) Brain Graph of Alzheimer’s.

Receiver Operating Characteristic and Area Under the Receiver Operating Characteristic Analysis

ROC and AUROC analysis of (normal and Alzheimer’s) and (normal and mild) considering characteristic path length (Figures 2 and 3).

ROC and AUROC analysis of (normal and Alzheimer’s) and (normal and mild) considering global efficiency (Figures 4 and 5).

ROC and AUROC analysis of (normal and Alzheimer’s) and (normal and mild) considering strength (Figures 6 and 7).

ROC and AUROC analysis of (normal and Alzheimer’s) and (normal and mild) considering clustering coefficient (Figures 8 and 9).

Figure 2.

ROC Curve of Normal and Alzheimer’s having AUC = 0.94.

Figure 3.

ROC Curve of Normal and Mild Having AUC = 0.62.

Figure 4.

ROC Curve of Normal and Alzheimer’s Having AUC = 0.96.

Figure 5.

ROC Curve of Normal and Mild Having AUC = 0.73.

Figure 6.

ROC curve of Normal and Alzheimer’s having AUC=0.88.

Figure 7.

ROC Curve of Normal and Mild Having AUC = 0.75.

Figure 8.

ROC Curve of Normal and Alzheimer’s Having AUC = 0.91.

Figure 9.

ROC Curve of Normal and Mild Having AUC = 0.64.

Logistic Analysis

In the logistic analysis, we have calculated the diagnostic test indices⁷ as depicted in Table 3 for each graph theoretic measure for Alzheimer’s versus normal which are:

Sensitivity

Specificity

Accuracy.

Table 3.

Depicting Logistic Indices.

	Characteristic Path Length	Global Efficiency	Strength	Clustering Coefficient
Sensitivity (%)	92.4	97	86.4	88.6
Specificity (%)	97	87.9	81.8	86.2
Accuracy (%)	93.9	94.7	86.9	87.9

The logistic analysis can be best explained by the following example depicting the sensitivity and specificity at various values of one of the graphic theoretical measures, that is, the characteristic path length for the detection of Alzheimer’s (Table 4).

Table 4.

An Example Depicting the Sensitivity and Specificity at Various Values of One of the Graphical Measure, that is, Characteristic Path Length for Detection of Alzheimer’s.

Characteristic Path Length	Alzheimer’s (n = 30)	Alzheimer’s (n = 30)	Normal (n = 30)	Normal (n = 30)	Sensitivity	Specificity
Characteristic Path Length	True Positive (TP)	False Negative (FN)	False Positive (FP)	True Negative (TN)	Sensitivity	Specificity
4.42	30	0	30	0	1	0
4.44	30	0	29	1	1	0.03
4.45	27	3	28	2	0.9	0.06
4.47	27	3	26	4	0.9	0.13
4.50	20	10	25	5	0.66	0.17
4.55	18	12	24	6	0.60	0.2
4.56	13	17	22	8	0.43	0.27
4.61	12	18	17	13	0.40	0.43
4.65	10	20	15	15	0.33	0.5
4.72	9	21	8	22	0.30	0.73
4.75	7	23	6	24	0.23	0.8
4.78	5	25	4	26	0.17	0.87
4.80	3	27	2	28	0.10	0.93
4.82	2	28	1	29	0.06	0.97
4.85	1	29	1	29	0.03	0.97

Sensitivity = TP/(TP+FN)

Specificity= TN/(TN+FP)

Accuracy = (TN+TP)/(TN+TP+FN+FP).

So calculated the diagnostic test indices for each graph theoretic measure for Alzheimer’s versus normal, which are: sensitivity, specificity and accuracy are depicted in Table 3.

Conclusion

The analysis presented shows that the amalgamation of structural MRI with graph theory may help in the early diagnosis of AD. It is observed that the calculated brain measures (characteristic path length, global efficiency, strength, and clustering coefficient) and the brain graphs clearly distinguish Alzheimer’s from normal controls. All these findings suggest that alterations in network topology and various brain measures may act as quantitative biomarkers of AD. Also, since the values of graph measures for MCI fall in between, we conjecture that the continuous variations in these measures could be exploited to quantify the degree of degradation.

Further studies with a large patient cohort should evaluate and validate the diagnostic certainty of these brain measures. Also, further implementation could be done to analyze the structural connectivity of the brain and alterations in network topology by focusing on specific brain regions such as sub-cortical regions and the hippocampus.

Appendix A

Mathematical formulation and explanation of calculated brain measures:

The characteristic path length (L)²⁹ is the average of the path lengths of all the nodes and is computed as

L = \frac{1}{n (n - 1)} \sum_{i \neq j} d_{i j}

(1)

where n = total number of nodes and d_ij is the shortest distance between node i and node j computed using Dijkstra’s algorithm.

The global efficiency (E)²⁹ is defined as the inverse of characteristic path length and can be calculated as:

E = \frac{1}{n (n - 1)} \sum_{i \neq j} d_{i j}^{- 1}

(2)

The clustering coefficient (C) is a measure of degree to which the nodes in the graph tend to cluster together³⁰ and is computed as

C = \frac{1}{n} \sum_{i} \frac{2 t_{i}}{k_{i} (k_{i} - 1)}

(3)

here k_i = degree of node i, t_i = number of triangles around node i and $t_{i} = \frac{1}{2} \sum_{i} {(w_{i j} w_{i h} w_{j h})}^{1 / 3}$ and $w_{i j} w_{i h} w_{j h}$ = corresponding weights.

The strength (S) is calculated by taking the sum of weights of all the edges connected to a node.³⁰ For weighted undirected graphs, strength is calculated by taking sum either over rows or columns of weighted connectivity matrix and is calculated as:

S = \sum_{i \neq j} a_{i j}

(4)

where a_ij are corresponding weights.

Footnotes

Data Availability

The data used in preparation of this article were obtained from the ADNI and is available with permission to all researchers.

Acknowledgements

This work is supported by Ministry of Education (MoE), formerly the Ministry of Human Resource Development (1985–2020), Government of India. And a sincere thanks to ADNI for providing us the access of their valuable database.

Authors’ Contribution

Rakhi Sharma: conceptualization, methodology, software, and writing-original draft. Shiv Dutt Joshi: conceptualization, methodology, and supervision.

Statement of Ethics

All the data were obtained from ADNI database,¹² available at (adni.loni.usc.edu). Informed consent from the patients is obtained before assessment is carried out by ADNI study team and this study is secondary data analysis of the ADNI data collection. The data access and usage are within the ADNI data use agreements.

Declaration of Conflicting Interests

The authors declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The authors received no financial support for the research, authorship and/or publication of this article.

ORCID iD

Rakhi Sharma

References

Webb

Introduction to Biomedical Imaging . John Wiley and Sons, 2003.

Morris

PG.

Nuclear magnetic resonance imaging in medicine and biology . Oxford University Press, Oxford, 1990.

Cappabianco

FAM

, Shida

, Ide

JS.

Introduction to Research in Magnetic Resonance Imaging . 29th SIBGRAPI Conference on Graphics, Patterns and Images Tutorials. 2016.

Smith

SM.

Overview of MRI analysis. Br J Radiol 2004; 77(2): S167–S175.

Liang

and Lauterbur

PC.

Principles of magnetic resonance imaging: A signal perspective . IEEE Press, New York, 2000.

Tijms

, Wink

, de Haan

, . Alzheimer’s disease: Connecting findings from graph theoretical studies of brain networks. Neurobiol Aging 2013; 34(8): 2023–2036.

Fornito

, Zalesky

, Bullmore

Fundamentals of Brain Network Analysis . 2016.

de Haan

, AL Pijnenburg

, LM Strijers

, . Functional neural network analysis in frontotemporal dementia and Alzheimer’s disease using EEG and graph theory. BMC Neurosci 2009; 10: 101.

Sanz-Arigita

, Schoonheim

, Damoiseaux

, . Loss of small world networks in Alzheimers disease: Graph analysis of fMRI resting state functional connectivity. PLoS ONE 2010; 5(11): e13788.

10.

C-Y

, Wang

P-N

, Chou

K-H

, . Diffusion tensor tractography reveals abnormal topological organization in structural cortical networks in Alzheimer’s disease. J Neurosci 2010; 30(50): 16876–16885.

11.

Desikan

, Ségonne

, Fischl

, . An automated labelling system for subdividing the human cerebral cortex on MRI scans into gyral based regions of interest. Neuroimage 2006; 31(3): 968–980.

12.

ADNI (Alzheimer disease neuroimaging initiative) database (adni.loni.usc.edu).

13.

Jack

Jr , Bernstein

, Fox

, . The Alzheimer disease neuroimaging initiative (ADNI): MRI methods. J Magn Reson Imaging 2008; 27: 685–691.

14.

Free-surfer tool, freely available at http://surfer.nmr.mgh.harvard.edu/

15.

Fornito

, Zalesky

, Breakspear

Graph analysis of the human connectome: Promise, progress and pitfalls. Neuroimage 2013; 80: 426–444.

16.

Dimitriadis

, Drakesmith

, Bells

, . Improving the reliability of network metrics in structural brain networks by integrating different network weighting strategies into a single graph. Front Neurosci 2017; 11: 1–17.

17.

Lehmann

, Crutch

, Ridgway

, . Cortical thickness and voxel-based morphometry in posterior cortical atrophy and typical Alzheimer’s disease. Neurobiol Aging 2011; 32(8): 1466–1476.

18.

Bullmore

and Sporns

Complex brain networks: Graph theoretical analysis of structural and functional systems. Nat Rev Neurosci 2009; 10: 186–198.

19.

Falahati

, . The effect of age correction on multivariate classification in Alzheimer’s disease, with a focus on the characteristics of incorrectly and correctly classified subjects. Brain Topogr 2016; 29(2): 296–307.

20.

Alexander-Bloch

, Giedd

, Bullmore

Imaging structural co-variance between human brain regions. Nat Rev Neurosci 2013; 14(5): 322–336.

21.

Tijms

, Möller

, Vrenken

, . Single-subject matter graphs in Alzheimer’s disease. PLoS ONE 2013; 8(3): e58921.

22.

Schwarz

, Gunter

, Wiste

, . A large-scale comparison of cortical thickness and volume methods for measuring Alzheimer’s disease severity. Neuroimage Clin 2016; 11, 802–812.

23.

Liu

, Li

, Pan

, . Complex brain network analysis and its applications to brain disorders: A survey. Complexity 2017; 2017: 1–27.

24.

Bassett

and Bullmore

ET.

Human brain networks in health and disease. Curr Opin Neurol 2009; 22: 340–347.

25.

Zalesky

, Fornito

, Bullmore

On the use of correlation as a measure of network connectivity. NeuroImage 2012; 60: 2096–2106.

26.

Rubinov

and Sporns

Complex network measures of brain connectivity: Uses and interpretations. Neuroimage 2010; 52(3): 1059–1069.

27.

Frisoni

, Fox

, Jack

Jr , . The clinical use of structural MRI in Alzheimer disease. Nat Rev Neurol 2010; 6(2): 67–77.

28.

Brain connectivity toolbox (brain-connectivity-toolbox.net).

29.

DelEtoile

and Adeli

Graph theory and brain connectivity in Alzheimer’s disease. Neuroscientist 2017; 23(6): 616–626.

30.

Mårtensson

, Pereira

, Mecocci

, . Stability of graph theoretical measures in structural brain networks in Alzheimer’s disease. Sci Rep 2018; 8: 11592.

Graph Theoretical Measures for Alzheimer’s,MCI,and Normal Controls: A Comparative Study Using MRI Data

Abstract

Background

Purpose

Method

Results

Conclusion

Keywords

Introduction

Methods

Subjects

Demographics of Studied Cohort. 12

MRI Acquisition

Image Processing

Graphical Analysis

Network Construction

Network Analysis

Network Implications

Results and Discussion

Brain Measures in Normal, Mild Cognitive Impairment, and Alzheimer’s.

(a) Brain Graph of Normal controls. (b) Brain Graph of Mild Cognitive Impairment. (c) Brain Graph of Alzheimer’s.

Receiver Operating Characteristic and Area Under the Receiver Operating Characteristic Analysis

ROC Curve of Normal and Alzheimer’s having AUC = 0.94.

ROC Curve of Normal and Mild Having AUC = 0.62.

ROC Curve of Normal and Alzheimer’s Having AUC = 0.96.

ROC Curve of Normal and Mild Having AUC = 0.73.

ROC curve of Normal and Alzheimer’s having AUC=0.88.

ROC Curve of Normal and Mild Having AUC = 0.75.

ROC Curve of Normal and Alzheimer’s Having AUC = 0.91.

ROC Curve of Normal and Mild Having AUC = 0.64.

Logistic Analysis

Depicting Logistic Indices.

An Example Depicting the Sensitivity and Specificity at Various Values of One of the Graphical Measure, that is, Characteristic Path Length for Detection of Alzheimer’s.

Conclusion

Appendix A

Footnotes

Data Availability

Acknowledgements

Authors’ Contribution

Statement of Ethics

Declaration of Conflicting Interests

Funding

ORCID iD

References

Demographics of Studied Cohort.¹²