Testing Graph Robustness Indexes for EEG Analysis in Alzheimer’s Disease Diagnosis

Abstract

Alzheimer’s Disease (AD) is an incurable neurodegenerative disorder which mainly affects older adults. An early diagnosis is essential because medical treatments can slow down the progression of the disease only if provided during the first stage, called Mild Cognitive Impairment (MCI). Starting from the study of electroencephalografic signals, brain functional connectivity analyses can be performed with the support of the graph theory. In particular, the purpose of this work is to verify the performances of three indexes, typically adopted to evaluate the graph robustness, in order to estimate the functional connectivity for three groups of subjects: healthy controls and people affected by dementia at two different stages (MCI and AD). The results obtained by the Connection Density Index, the Randić Index, and a normalized version of the Kirchhoff Index revealed a higher robustness in the brain networks of healthy people, followed by MCI and, finally, by AD patients, consistent with the hallmarks of Alzheimer’s disease. The statistical analysis showed that there is a significant difference between controls and AD for all three indexes. Finally, all three indexes were compared, revealing that the the Randić Index outperformed the other two indexes. These preliminary outcomes will be exploited to address further in-depth and time-expensive analyses for improving the diagnosis of Alzheimer’s disease.

1. Introduction

Alzheimer’s Disease (AD) is a neurodegenerative disorder which mainly affects older adults and represents the most common form of dementia (60–70% of cases). It is quite hard to be early diagnosed because the typical symptoms of the first stage, called Mild Cognitive Impairment (MCI), are often mistaken for consequences of normal aging. To date, there is no cure for AD, but proper medical treatments can slow the progression of the disease. As the therapy is more effective in the first stage of the disease, the need for an early diagnosis becomes essential.

Over the years, several brain imaging techniques have been employed by neuroscientists for collecting information about structure and functions of the brain, including positron emission tomography (PET), functional near infrared spectroscopy (fNIRS), magnetoencephalogram (MEG), electroencephalography (EEG), and functional magnetic resonance imaging (fMRI) [1,2].

In particular, many researchers have based their studies on the EEG analysis for investigating AD [3,4]. EEG is a widely employed diagnostic tool since it is not invasive, easy-to-use, and inexpensive. EEG signals are recorded by means of electrodes placed on the head surface. They represent a measurement of the potentials deriving from synchronous activity of populations of cortical neurons. Because of the conductivity of the scalp and the underlying tissues, each electrode detects the contribution of all active sources, superposed according to their distance and orientation. Hence, a realistic head model is required for an accurate interpretation of the EEG signal [5].

Brain functional connectivity concerns the functionally integrated relationship between spatially separated brain regions and is described in terms of statistical dependencies in the time domain (correlation) and in the frequency domain (coherence) among neurophysiological measurements. Over the years, several methods have been exploited for evaluating neuronal interactions [6].

Among the different techniques proposed in the literature, researchers verified that a valid support in the study of the dependencies between spatially separated brain regions may come from the graph theory. Indeed, graphs are able to represent a large variety of systems in many branches of Science and Engineering. Therefore, graphs have been largely investigated and a great number of techniques and indexes have been proposed in the literature to identify and measure different graphs’ properties. In this respect, graph theory is considered to be a valid tool to represent brain relationships [7,8]. As a consequence, functional brain dependencies can be conveniently represented and studied through the use of graphs, thus allowing to benefit from the analysis techniques developed with the graph theory.

In particular, in the early diagnosis of Alzheimer’s disease based on the EEG analysis scenario described above, to roughly represent the connectivity properties of brain regions associated with specific functionalities, not-oriented graphs can be conveniently exploited by considering connections, weighted or not. To this aim, we can consider some indexes adopted by graph theory to measure the robustness degree of a graph in order to obtain a quick estimation about some brain’s aspects of interest.

Usually, such indexes are particularly useful in the presence of large graphs, where, as already denoted in the literature [9], they represent good specimens of robust graphs—in other words of the graph resilience with respect to the loss of connections among the graph vertexes. However, also in the presence of little graphs, as in our case, such indexes could be conveniently exploited to provide a synthetic single measure potentially able to denote the possible onset of Alzheimer’s disease.

Given the premises above, our contribution consists of investigating the performances of some indexes in order to evaluate the functional connectivity in Alzheimer’s disease. To this aim, we have focused our research activity on comparing the results obtained by the Connection Density Index, commonly used, with those of the Randić Index and a normalized version of the Kirchhoff Index, in order to discover the most promising index for future studies about the evaluation of the functional connectivity in Alzheimer’s disease. The novelty is that both the Randić Index and Kirchhoff Index have not been compared for brain functional connectivity analysis before. The expected outcome is that the robustness of the graph decreases as the disease progresses, as a result of a reduction in EEG synchronize and functional connections between regions for AD patients [10,11,12].

Then, before testing the resilience indexes, it was necessary to localize the brain active sources. To this aim, the LORETA (Low Resolution Electromagnetic Tomography) framework that is one of the most adopted tools for brain source localization was exploited to reconstruct the sources of brain activity [13]. More precisely, we used the eLORETA (exact LORETA) algorithm and functional connectivity measurements were quantified by the Lagged Linear Connectivity (LLC) parameter (see Section 3.1), implemented in a toolbox recently introduced in the LORETA-KEY software [14,15].

Finally, in order to compare the results of the tested indexes, we introduced a synthetic index for making the results easily comparable (see Section 4). The results we obtained showed that all three indexes detected a higher robustness in the brain networks of healthy subjects compared to both MCI and AD patients. However, a statistical difference was found just between control subjects (CNT) and AD, for all three indexes. In addition, overall, the Randić index revealed a better ability to discriminate between healthy people and MCI/AD patients than the other two indexes. This preliminary study will represent a starting point for further in-depth and time-expensive brain connectivity analyses, in order to improve the diagnosis of Alzheimer’s disease.

The rest of the paper is organized as follows: Section 2 gives an overview of the related literature. In Section 3.1, eLORETA is briefly presented. Section 3.2 describes the tested robustness indexes. Section 4 contains the results of the experimental tests, and, finally, in Section 5, results are discussed and some conclusions are drawn.

2. Related Works

Brain functional connectivity has been widely investigated during the last two decades. Different approaches and techniques have been used, including coherence, phase synchronization, phase-slope index, phase lag index, and Granger causality, reviewed in [6,16].

In particular, graphs are considered an excellent tool for representing different topological properties of brain networks. Several studies proved that healthy human brain networks have a small-world architecture, characterized by local and global efficient information processing with low wiring cost [17]. The small-worldness of brain networks has been analyzed for exploring both pathological and non-pathological conditions [18,19,20]. As for Alzheimer’s Disease, brain networks are characterized by a weakening of the small-world properties as compared with healthy subjects [21,22,23]. Moreover, studies which compared healthy people, MCI, and AD patients have shown that MCI topological properties are intermediate [24,25,26]. Extensive reviews about graph theory applied to functional connectivity analysis in AD are provided in [27,28,29].

The robustness, otherwise called resilience, of a system can be defined as its ability to maintain its characteristics unchanged after a damage, regardless of the exogenous or endogenous damage origin with respect to the system [30,31,32]. The same definition can be associated with the graph by which such a system can be usually represented.

The techniques for determining the robustness of graphs are commonly differentiated in (i) based on the graph topology and in (ii) based on the eigenvalues of suitable matrices obtained starting from the graph under analysis.

In the study reported in [33], which belongs to the first approach, the resilience of graphs in which the distribution of node degrees follows a power law, i.e., those graphs associated with scale-free networks, are investigated. In more detail, two modalities of attack (i.e., damage) were considered. The first one aimed at randomly removing nodes (along with the arcs that affect them), while the second one is focused on removing nodes starting with the most relevant ones (i.e., high degree). The results of this study highlighted that scale-free networks are resilient with respect to the first modality of attack, but not so much when the nodes removed are the highest in degree.

Another proposal is presented in [34] on the basis of the theory of structural holes [35], and assumes the modification of the network topology by appropriately adding new links (link-addition strategy) without knowing the global topology of the graph, but relying only on local information. However, in analyzing the resilience of graphs, the topological approach has been applied in many contexts such as, for instance, mobile communication infrastructures [36], air traffic networks [37], P2P networks [38], and many others.

The approaches based on the eigenvalues exploits the adjacency matrix or the Laplacian matrix [39] of a graph to determine its robustness. With respect to the adjacency matrix of a graph, we define as a spectral radius its largest eigenvalue. The spectral radius is an index of expansion, i.e., of the speed at which a dynamic process propagates on a network, and it has been used to estimate the robustness of a graph in [40,41,42]. Another measure of expansion is the spectral gap, defined as the difference between the two largest eigenvalues of the adjacency matrix. Graphs characterized by high values of this index are good expanders [43] and, consequently, the index itself is also a measure of robustness [44]. Another metric is based on the number of alternative paths between any pair of nodes in a graph. In fact, the larger the number of alternative paths between nodes in the graph, the greater the resilience of the graph since the probability of ensuring connection between nodes in the graph [45,46] is greater.

Finally, some other measures are derived from the Laplacian $\mathbf{L}$ of a graph G, defined as $\mathbf{L}=\mathbf{D}-\mathbf{A}$, where $\mathbf{D}$ is a diagonal matrix and $\mathbf{A}$ is the adjacency matrix of G. A Laplacian-based robustness measure is, for instance, the algebraic connectivity [47] defined as the value of the first non-zero eigenvalue of the Laplacian. This measure is an indicator of the difficulty of breaking a graph into disconnected components and, therefore, the larger the algebraic connectivity, the greater the robustness of the graph [48].

Recently, connectivity indexes have successfully been employed for studying brain functional connectivity [7,8]. In a newly released study [49], the network resilience of controls, MCI and AD, was investigated. The results showed that, compared to controls, the network of both MCI and AD is less resilient in theta and alpha band, respectively.

Unlike the Connection Density Index, commonly used in this field, the Kirchhoff Index has never been employed for complex brain network analysis, whereas the Randić Index has been used for this purpose just once, but in relation to the structural connectivity [50].

As for the Lagged Linear Connectivity, it has already been used in studies about Alzheimer’s disease, revealing a decrease in lagged phase synchronization between most cortical regions in AD patients as compared with healthy subjects and a lower brain functional connectivity in MCI patients in comparison to healthy elderly subjects [51,52,53].

3. Methods

This section is organized as follows:

• Section 3.1 aims to present a brief overview on the LORETA (Low Resolution Electromagnetic Tomography) family algorithms and the Lagged Linear Connectivity parameter.
• Section 3.2 is focused on presenting some selected indicators potentially able to describe the robustness degree (i.e., resilience) of graphs.

The following diagram summarizes the experimental arrangement (Figure 1):

3.1. eLORETA Lagged Linear Connectivity Overview

LORETA was introduced in 1994 and, nowadays, it has become one of the most accurate and common methods for brain source reconstruction [54]. Its latest version was used in this work.

In more detail, LORETA produces a linear solution to the EEG inverse problem, providing a three-dimensional reconstruction of the brain electrical activity. The brain volume, including the grey matter and hippocampus, is discretized into volumetric points (voxels). Each source, placed on a specific voxel, is described by a current density vector with unknown moment components. As for eLORETA, the algorithm used in our data processing, the brain volume is made up of 6239 cortical voxels at 5 mm resolution. Differently from the previous LORETA family algorithms, eLORETA is characterized by zero error localization in the presence of measurement and structured biological noise and takes the deeper sources into account more adequately [14].

The estimated current density is given by:

$$\widehat{\mathbf{J}}=\mathbf{T}\mathsf{\Phi }$$

(1)

where $\mathbf{T}$ is the pseudoinverse and $\mathsf{\Phi }\in R^{N_{E}x1}$ is the vector of the electric potential differences measured at $N_E$ electrodes with respect to a single common reference electrode.

The pseudocode of the Algorithm 1 is the following:

Algorithm 1 eLORETA algorithm.

Input: $\mathbf{K}$; $\mathbf{H}$; $\alpha$; $ϵ$.

1: Set $error$ > $ϵ$

2: $Initialize\_Weight\_Matrix\left(\mathbf{W}\right)$

3: while $error$ > $ϵ$ do

4:     $\mathbf{M}={(\mathbf{K}{\mathbf{W}}^{-1}{\mathbf{K}}^T+\alpha \mathbf{H})}^{+}$

5:     for $j=1\cdots N_V$ do

6:         $W_j={\left[K_j^T\mathbf{M}{K}_j\right]}^{SySqrt}$

7:     end for

8: end while

9: $\mathbf{T}={\mathbf{W}}^{-1}{\mathbf{K}}^T{(\mathbf{K}{\mathbf{W}}^{-1}{\mathbf{K}}^T+\alpha \mathbf{H})}^{+}$

The eLORETA algorithm receives as input the average reference lead field $\mathbf{K}$ and the average reference operator $\mathbf{H}$, the regularization parameter $\alpha >0$, and the parameter $ϵ$ representing the maximum admissible error computed on the basis of changes occurring between two successive iterations in the weight matrix $\mathbf{W}$ (lines 3–8).

At first, a function initializes the weight matrix $\mathbf{W}$ (line 1) and then the matrix $\mathbf{M}$ is computed (line 2). Until the value of the parameter error is greater than $ϵ$ (lines 3–8), for each of the $N_V$ voxels, the corresponding value of W (lines 5–7) is computed. Note that, at line 2, the term ${\left[K_j^T\mathbf{M}{K}_j\right]}^{SySqrt}$ denotes the symmetric square root of the matrix $\left[K_j^T\mathbf{M}{K}_j\right]$. Finally, when the value of the parameter error is negligible (i.e., $error\le ϵ$), the matrix $\mathbf{T}$ is computed and the algorithm ends.

In addition to this, the authors of LORETA introduced a new parameter useful for the functional connectivity analysis [15,55]. They considered the total connectivity as deriving from an instantaneous and a lagged contribution: the first one takes account of the potentials generated by distant cortical regions and conducted across head volume (the so-called “volume conduction”), while the lagged component includes almost pure physiological information.

The linear dependence between time series X and Y at frequency $\omega$ is defined as:

$$F_{X,Y}\left(\omega \right)=ln\frac{\left|\begin{array}{c}\left(\begin{array}{cc}{\mathbf{S}}_{Y,Y}\left(\omega \right)& \mathbf{0}\\ {\mathbf{0}}^T& {\mathbf{S}}_{X,X}\left(\omega \right)\end{array}\right)\end{array}\right|}{\left|\begin{array}{c}\left(\begin{array}{cc}{\mathbf{S}}_{Y,Y}\left(\omega \right)& {\mathbf{S}}_{Y,X}\left(\omega \right)\\ {\mathbf{S}}_{X,Y}\left(\omega \right)& {\mathbf{S}}_{X,X}\left(\omega \right)\end{array}\right)\end{array}\right|}$$

(2)

where ${\mathbf{S}}_{X,X}$, ${\mathbf{S}}_{Y,Y}$, ${\mathbf{S}}_{X,Y}$, and ${\mathbf{S}}_{Y,X}$ denote the complex valued covariance matrices, and $\left|\mathbf{M}\right|$ is the determinant of M:

$$F_{X,Y}\left(\omega \right)=F_{X\rightleftarrows Y}\left(\omega \right)+F_{X·Y}\left(\omega \right)$$

(3)

The instantaneous linear dependence is defined as:

$$F_{X·Y}\left(\omega \right)=ln\frac{\left|\begin{array}{c}Re\left(\begin{array}{cc}{\mathbf{S}}_{Y,Y}\left(\omega \right)& \mathbf{0}\\ {\mathbf{0}}^T& {\mathbf{S}}_{X,X}\left(\omega \right)\end{array}\right)\end{array}\right|}{\left|\begin{array}{c}Re\left(\begin{array}{cc}{\mathbf{S}}_{Y,Y}\left(\omega \right)& {\mathbf{S}}_{Y,X}\left(\omega \right)\\ {\mathbf{S}}_{X,Y}\left(\omega \right)& {\mathbf{S}}_{X,X}\left(\omega \right)\end{array}\right)\end{array}\right|}$$

(4)

where Re(M) denotes the real part of M.

Finally, the measure of lagged linear dependence is:

$$F_{X\rightleftarrows Y}\left(\omega \right)=F_{X,Y}\left(\omega \right)-F_{X·Y}\left(\omega \right)=ln\frac{\left\{\begin{array}{c}\left|\begin{array}{c}Re\left(\begin{array}{cc}{\mathbf{S}}_{Y,Y}\left(\omega \right)& {\mathbf{S}}_{Y,X}\left(\omega \right)\\ {\mathbf{S}}_{X,Y}\left(\omega \right)& {\mathbf{S}}_{X,X}\left(\omega \right)\end{array}\right)\end{array}\right|/\left|\begin{array}{c}Re\left(\begin{array}{cc}{\mathbf{S}}_{Y,Y}\left(\omega \right)& \mathbf{0}\\ {\mathbf{0}}^T& {\mathbf{S}}_{X,X}\left(\omega \right)\end{array}\right)\end{array}\right|\end{array}\right\}}{\left\{\begin{array}{c}\left|\begin{array}{c}\left(\begin{array}{cc}{\mathbf{S}}_{Y,Y}\left(\omega \right)& {\mathbf{S}}_{Y,X}\left(\omega \right)\\ {\mathbf{S}}_{X,Y}\left(\omega \right)& {\mathbf{S}}_{X,X}\left(\omega \right)\end{array}\right)\end{array}\right|/\left|\begin{array}{c}\left(\begin{array}{cc}{\mathbf{S}}_{Y,Y}\left(\omega \right)& \mathbf{0}\\ {\mathbf{0}}^T& {\mathbf{S}}_{X,X}\left(\omega \right)\end{array}\right)\end{array}\right|\end{array}\right\}}$$

(5)

The above-mentioned measures are non-negative. They equal zero only when there is independence (lagged, instantaneous, or both). They can also be transformed into a “squared coherence”, with values in the [0 …1] range.

In this work, the active source localization and the brain connectivity measurements were computed by means of the eLORETA algorithm and the Connectivity toolbox (available online: https://sites.google.com/site/bctnet/, accessed on 7 June 2021), respectively, both implemented in the LORETA-KEY software v20201109 (available online: https://www.uzh.ch/keyinst/loreta.htm, accessed on 7 June 2021). Specifically, we computed the LLC by Equation (5). LLC provides a measurement of the statistical dependence among active sources, estimated by eLORETA, for each pair of cortical ROIs, at a given frequency range. In particular, we evaluated LLC for the all 84 possible ROIs defined by LORETA-KEY software, for the frequency range 1–40 Hz. The ROIs correspond to distinct Brodmann areas, 42 for each hemisphere. EEG were decomposed into artifact-free non-overlapping epochs of 250 samples (1 s) [56]. LLC was estimated for windows of three epochs, resulting in 40 connection matrices for each subject. Therefore, we obtained 40 values of each connectivity index for each subject.

3.2. The Examined Robustness Indexes

For sake of clarity, in the following, we will refer to a graph $G=\langle N,E\rangle$, where $N=\{1,\dots ,n\}$ is the set of nodes belonging to G and $E\subseteq N\times N$ is the set of edges connecting two nodes $u,v\in N$ with $\langle u,v\rangle \in E$. Edges can be oriented or not (i.e., directed or undirected), as well as weighted, to provide a measure of the connection strength between nodes, or not. The graph G is also characterized by its order and size; more specifically, a graph G will be said of order n if $\left|N\right|=n$ and of size m if $\left|E\right|=m$. If in G every pair of nodes is connected by at least one path, then G is said to be connected. In addition, if also every node of G is directly a connected to all other nodes in the graph, then G is also called complete. A complete graph of order n, denoted by $K_n$, has $\frac{n\left(n-1\right)}{2}$ edges, and the degree d of every node of G is $d=n-1$.

From graph theory [39], with respect to connected graphs, we selected three well-known robustness indexes that, in our opinion, appear as the mostly promising in an EEG context, namely: (li) the Connection Density Index [7]; (ii) the Randić Index [57,58,59]; (iii) the Kirchhoff Index [60,61]. Each of the investigated indexes tries to provide a measure of the robustness of a graph based on a different approach. All of the indexes were computed with MATLAB (R2018a, MathWorks Inc., Natick, MA, USA). In the following, the above selected indexes will be shortly presented in order of increasing computational complexity.

3.2.1. Connection Density Index

The Connection Density Index (D) of a graph (G) is the ratio of its current number of edges (i.e., E) to the maximum number of edges that would be present if G were a complete graph (i.e., $E_c$) [7]. More formally, D is computed as:

$$D=\frac{E}{E_c}=\frac{E}{\frac{{\displaystyle n·(n-1)}}{{\displaystyle 2}}}=\frac{2·E_c}{n·(n-1)}$$

(6)

This is the simpler connectivity index and has a computational complexity constant with respect to the number of nodes and edges of G, and, consequently, it can be easily computed also for large graphs and easily updated when edge and/or nodes increase or decrease in G. The value of D ranges into the domain [0.0;1.0] and, differently from the other indexes presented below, more D is greater and more G is connected. In fact, the logic behind this measure is quite simple and consists of assuming that the greater the number of edges in the graph, the greater its ability to connect different nodes.

3.2.2. Randić Index

The Randić Index of a graph has been introduced in 1976 by Milan Randić [57] to study molecular structures of organic chemistry compounds. Even though it is behind the aims of our investigation, from a mathematical viewpoint we highlight, as this index is still widely investigated for its properties as, for instance, in [62,63,64].

Formally, let u be a node belonging to G (i.e., $u\in G$) and let $d_u$ be the degree of u defined as the number of edges incident onto u. The Randić Index $R\left(G\right)$ associated with G is defined as:

$$R\left(G\right)=\sum _{\langle u,v\rangle \in E}\frac{1}{d_u{d}_v}.$$

(7)

The computation of $R\left(G\right)$, for a graph G of size m, increases linearly with m or, in other words, it has a computational complexity $O\left(m\right)$. Therefore, the Randić Index will be computed in a linear time with respect to the number of edges into G and easily re-computed (in an incremental way) when the graph topology changes in terms of added/deleted edges (or nodes). For large graphs, the computation of the Randić Index is also not particularly critical.

The Randić Index will be a minimum value for a complete graph so that the lower the $R\left(G\right)$, the more connected (i.e., robust) the G.

In our analysis, we used a different formulation of the Randić Index, already proposed in [50]. It is defined as:

$$R\left(G\right)=\sum _{\langle u,v\rangle \in E}{d}_u{d}_v$$

(8)

On the basis of Equation (8), the higher the $R\left(G\right)$, the more connected (i.e., robust) the G.

3.2.3. Kirchhoff Index

The Kirchhoff Index [60,61], identified by $Kf\left(G\right)$, is calculated on an electric circuit (i.e., $\Delta$) derived by the graph G, where nodes and edges of G correspond to points and resistors (of 1 $\Omega$) in $\Delta$, respectively. If we plug this electrical circuit into a potential electrical difference, the value of resistance measured between two of its points (i.e., nodes) u and v represents a measure of the resistance that the current has to flow from u to v. The Kirchhoff’s law allows us to compute the effective resistance $k_{u,v}$ existing between u and v.

The Kirchhoff Index $Kf\left(G\right)$ is computed as the pairwise sum of these k resistances and can be written as:

$$Kf\left(G\right)=\sum _{\forall u\in \Delta }\sum _{\forall v\in \Delta }{k}_{u,v}$$

(9)

and the smaller the $Kf\left(G\right)$, the more connected the G [65,66]. In more detail, the calculation of $Kf\left(G\right)$ has a computational complexity $O\left(n^2\right)$, for a graph G of order n. Therefore, from a computation complexity viewpoint, this index is the most expansive among those we considered here, as well as its updating when nodes or edges are added or deleted from G. This latter problem has been widely investigated in the literature as, for instance, in [67,68].

Here, we proposed a normalized version of the Kirchhoff Index, defined as [69]:

$${Kf\left(G\right)}_{norm}=\frac{n-1}{Kf\left(G\right).}$$

(10)

In this case, the higher the ${Kf\left(G\right)}_{norm}$, the more connected (i.e., robust) the G. Obviously, the values of ${Kf\left(G\right)}_{norm}$ belong to the interval $[0.0;1.0]$.

Note that, in this work, we adopted a version of the Kirchhoff index where resistances are not unitary but reflect the normalized strength of each edge connecting two vertexes.

4. Experiments

In the last few decades, great advancements in the knowledge of Alzheimer’s disease have been realized, but, unfortunately, fundamental aspects and mechanisms at different levels are still unknown. In such a knowledge framework, the use of robustness graph indexes try to empirically correlate existing dependencies between spatially separated brain regions. Given these premises, each of such indexes cannot represent a single reliable indicator of Alzheimer’s disease, but each of them may contribute to establish a well defined diagnosis together with other instrumental measures and an objective patient history conducted by specialists in the field.

Therefore, the purpose of these experiments is to conveniently address future studies aimed at identifying the most promising robustness graph index that, together with other information, can be used as one of the indicators of a potential early Alzheimer’s disease. To this aim, we exploited the EEG dataset collected at “IRCCS—Centro Neurolesi Bonino-Pulejo” of Messina (Italy), described in Section 1, consisting of the EEGs of three groups of subjects, namely: 10 control subjects (CNT), 21 Mild Cognitive Impairment patients (MCI), and 9 Alzheimer’s Disease patients (AD) (The research followed a protocol approved by the local Ethics Committee (Approved N. 003/17) and all the included subjects or their caregivers signed an informed consent form).

EEG recordings were obtained by a HD-EEG acquisition system that is the 256-channel HydroCel Geodesic Sensor Net, belonging to the Geodesic EEG System (the high-density electrode montage is shown in Figure 2). The electrode impedance was kept <50 k$\Omega$, according to EGI guidelines, and the reference electrode was Cz, placed in the middle of the head surface. EEGs were acquired in eyes-closed resting state with a sampling rate of 250 Hz and processed by a band-pass filter between 1 Hz and 40 Hz. After filtering, a visual inspection has been carried out to identify and delete artifacts. However, only 173 channels out of the starting 256 were considered in our study because the signals deriving from electrodes placed on the face and the neck included too many artifacts [70]. Finally, two minutes of cleaned EEGs were analyzed for each subject and transformed to a common average reference montage. The data preprocessing was conducted by means of the programming and numeric computing platform MATLAB (R2018a) of Mathworks. The main dataset parameters are summarized in

Table 1. Schematic of the main dataset parameters.

No. of CNT	10
No. of MCI	21
No. of AD	9
HD-EEG acquisition system (256-channel)	HydroCel Geodesic Sensor Net
Electrode impedance	<50 k$\Omega$
Sampling rate	250 Hz
Band-pass filter process	1–40 Hz
Channels excluded for too many artifacts	83 of 256
Analyzed EEG signal	2 min
Brain regions	84

.

From an operative viewpoint, preliminarily, we computed the normalized connection matrices and then, in order to correlate the value of the robustness indexes with the number of edge in the graph, we applied high-pass filters at increasing threshold levels for verifying the number of remaining edges. The results of this rough analysis, presented in

Table 2. Number of connected nodes for each group of subjects as a function of the threshold applied to the connection matrices of size m = $84\times 83$ = 6972 (self-loops are not taken into account).

Threshold	Connected Nodes
	CNT	MCI	AD
0	6972	6972	6972
0.05	6857	6848	6837
0.10	6342	6300	6255
0.15	5384	5315	5233
0.20	4264	4176	4084
0.25	3203	3112	3028
0.30	2309	2228	2162
0.35	1612	1548	1502
0.40	1098	1049	1020
0.45	730	697	680
0.50	476	454	445
0.55	304	292	288
0.60	189	184	183
0.65	117	115	113
0.70	71	70	69
0.75	42	42	42
0.80	24	24	25
0.85	13	14	14
0.90	7	8	8
0.95	4	4	4
1	0	0	0

and depicted in Figure 3, highlight that there is a drastic decrease of edges in the graph already at low thresholds (see below), which must be taken into account when interpreting the robustness indexes scores. Note that the differences between the different examined populations are not relevant.

4.1. Robustness Indexes’ Results

The methods described in Section 3.1 and Section 3.2 were applied to the HD-EEG dataset, and the selected indexes were computed as functions of the filtering threshold applied to the weighted connection matrix. Note that the graph will be fully connected when the filtering threshold is set to 0, and, conversely, disconnected when the filtering threshold is set to 1. In the following, Figure 4, Figure 5 and Figure 6 compare the results obtained with the mean value of D, $R\left(G\right)$, and $Kf{\left(G\right)}_{norm}$, respectively, for each group of subjects previously introduced. Moreover, numerical results are shown in

Table 3. Mean Connection Density Index, mean Randić Index, and mean Normalized Kirchhoff Index for CNT, MCI, and AD, for each filtering threshold value.

Threshold	$\mathit{D}\left(\mathit{G}\right)$			$\mathit{R}\left(\mathit{G}\right)\left({10}^6\right)$			$\mathit{Kf}{\left(\mathit{G}\right)}_{\mathit{norm}}$
	CNT	MCI	AD	CNT	MCI	AD	CNT	MCI	AD
0	1.000	1.000	1.000	0.504	0.483	0.472	0.248	0.245	0.241
0.05	0.984	0.982	0.981	0.502	0.482	0.470	0.247	0.244	0.240
0.1	0.910	0.904	0.897	0.481	0.461	0.448	0.239	0.235	0.230
0.15	0.772	0.762	0.751	0.418	0.398	0.387	0.213	0.209	0.202
0.2	0.612	0.599	0.586	0.324	0.305	0.297	0.170	0.167	0.157
0.25	0.459	0.446	0.434	0.224	0.210	0.205	0.118	0.117	0.107
0.30	0.331	0.320	0.310	0.141	0.131	0.128	0.068	0.069	0.063
0.35	0.231	0.222	0.215	0.082	0.076	0.075	0.029	0.032	0.029
0.40	0.157	0.151	0.146	0.045	0.041	0.041	0.010	0.010	0.011
0.45	0.105	0.100	0.097	0.023	0.021	0.021	0.001	0.002	0.002
0.50	0.068	0.065	0.064	0.011	0.010	0.010	0.000	0.000	0.000
0.55	0.044	0.042	0.041	0.005	0.005	0.005	0.000	0.000	0.000
0.60	0.027	0.026	0.026	0.002	0.002	0.002	0.000	0.000	0.000
0.65	0.017	0.016	0.016	0.001	0.001	0.001	0.000	-	0.000
0.70	0.010	0.010	0.010	0.000	0.000	0.000	-	-	-
0.80	0.003	0.003	0.004	0.000	0.000	0.000	-	-	-
0.85	0.002	0.002	0.002	0.000	0.000	0.000	-	-	-
0.90	0.001	0.001	0.001	0.000	0.000	0.000	-	-	-
0.95	0.001	0.001	0.001	0.000	0.000	0.000	-	-	-
1.00	0.000	0.000	0.000	0.000	0.000	0.000	-	-	-

.

4.2. Analysis

As expected, the values of the three indexes follow the same logistic trend found in the number of edges described in Table 2 and Figure 3. In fact, the most consistent part of the edge cutoff occurs for thresholds between $10\%$ and $35\%$: in particular, for the latter value, about $80\%$ of the links are removed, and, with them, the majority of the information existing in the dataset.

Therefore, by comparing the number of edges (see Table 2) and the corresponding values of the three robustness indexes D, $R\left(G\right)$ and $Kf{\left(G\right)}_{norm}$ (see Table 3) computed by thresholding the connection matrix of CNT, MCI, and AD at step of $5\%$, it is possible to observe that reliable results cannot be obtained outside the filtering threshold range $[0\%,25\%]$. Indeed, beyond such boundaries, the effects of the increasing level of edge cutting do not allow any of the tested indexes’ adequate reliability with respect to our purposes.

Figure 4, Figure 5 and Figure 6 display the mean value of each connectivity index for each group and show that all three connectivity indexes denote a greater network robustness of CNT, followed by MCI and finally by AD. This trend is typical of Alzheimer’s disease. Note that the mean connectivity indexes of each group of subjects were obtained by averaging the connectivity indexes of all subjects belonging to the given group.

A statistical analysis was carried out for each connectivity index in order to support the results. In particular, the Wilcoxon rank sum test [71] was performed under the null hypothesis that the data from two different populations are samples from continuous distributions with equal medians, against the alternative that they are not. In this case, the test was conducted for each connectivity index for evaluating if there is a significant difference between groups of subjects. The significance level was set at 5%, so that the differences between groups are statistically significant when $p<0.05$. The resulting p-values are reported in

Table 4. p-values resulting from the Wilcoxon rank sum test.

Threshold	$\mathit{D}\left(\mathit{G}\right)$ p-Value		$\mathit{R}\left(\mathit{G}\right)$ p-Value		$\mathit{Kf}{\left(\mathit{G}\right)}_{\mathit{norm}}$ p-Value
	CNT-MCI	CNT-AD	CNT-MCI	CNT-AD	CNT-MCI	CNT-AD
0	-	-	0.1084	0.0181 *	0.2542	0.0237 *
0.05	0.7203	0.0141 *	0.1083	0.0179 *	0.2616	0.0242 *
0.1	0.2999	0.0248 *	0.1086	0.0184 *	0.2925	0.0263 *
0.15	0.2474	0.0205 *	0.1029	0.0177 *	0.4139	0.0260 *
0.2	0.1693	0.150 *	0.0832	0.0168 *	0.6168	0.0288 *
0.25	0.1254	0.0129 *	0.0686	0.0156 *	0.8268	0.0382 *

* indicates p < 0.05, which denotes statistically significant differences between groups.

. All three indexes show a significant difference between CNT and AD groups, for all relevant threshold values. Note that, for $D\left(G\right)$, the p-value is not defined for the threshold set to zero because D(G) is equal to 1 for all groups.

In order to compare the performance of the three indexes in the specified range, we considered the ratio between the value of the index evaluated for the MCI and AD populations and the value of the same index calculated for the CNT population. The results are presented in

Table 5. Indexes’ performance comparison for the relevant threshold range.

Threshold	$\mathit{D}\left(\mathit{G}\right)$		$\mathit{R}\left(\mathit{G}\right)$		$\mathit{Kf}{\left(\mathit{G}\right)}_{\mathit{norm}}$
	MCI	AD	MCI	AD	MCI	AD
0	1.000	1.000	0.961	0.936	0.986	0.971
0.05	0.999	0.997	0.961	0.936	0.986	0.970
0.1	0.993	0.986	0.958	0.932	0.984	0.964
0.15	0.987	0.972	0.953	0.925	0.981	0.948
0.2	0.979	0.958	0.944	0.918	0.983	0.928
0.25	0.972	0.945	0.935	0.912	0.991	0.906

The lower is the value, the better is the performance of the corresponding index.

and Figure 7.

A lower ratio denotes a greater difference between groups of subjects, so the corresponding index will have a better ability to distinguish a group from another one.

As for AD, the best performance is given by the Randić index, followed by Kirchhoff index. This is valid for all threshold values except for 0.25, at which the Kirchhoff index outperforms the Randić index.

In relation to MCI, the Randić index provides a better discrimination as compared with the other two indexes for all thresholds’ values. The performance of the Kirchhoff index worsens starting from the threshold value of 0.2. This outcome could be due to the fact that the Kirchhoff index is the most affected by the addition or removal of nodes, which at 0.2 are reduced by about of 40%. In this case, the Kirchhoff index becomes less reliable. Note that, although the difference of the connectivity indexes between CNT and MCI is not statistically significant, the trend is consistent with the distinctive features of Alzheimer’s disease.

In conclusion, the Randić index showed a better ability to discriminate between healthy subjects and AD patients.

5. Discussion and Conclusions

Alzheimer’s disease is an incurable neurological disorder affecting, above all, the elderly. Over the years, many studies have been carried out in order to find biomarkers for an early diagnosis of AD.

In this respect, graph theory turned out to be a valid instrument for investigating several aspects of AD. Brain functional connectivity is deeply affected by AD, so the analysis of the so-called small-world properties of a brain network can provide an insightful contribution to the study of this pathology.

In particular, in our work, we conducted a preliminary study about the robustness of the graphs corresponding to the brain networks of healthy subjects and people affected by dementia at two different stages (MCI and AD). Specifically, we exploit the information deriving from three connectivity indexes for discriminating between the above-mentioned three groups. Starting from a dataset including HD-EEG recordings, the connection matrices were computed by means of the Lagged Linear Connectivity parameter, implemented in the LORETA-KEY software and already employed in literature [72,73,74,75,76].

Then, the connection matrices of each subject were thresholded at a step of 5%, and the robustness of the resulting graphs was investigated by computing the Connection Density Index, the Randić Index, and the Normalized Kirchhoff Index. It is noteworthy that, so far, the two latter indexes have never been compared for the brain functional connectivity analysis.

The results from our experiments suggest that all three above-mentioned indexes detected a higher robustness in the brain networks of healthy controls compared to both MCI and AD patients. Moreover, MCI shows intermediate values between CNT and AD. This trend is consistent with the hallmarks of Alzheimer’s disease, which produces a progressive weakening of the brain network connectivity.

In addition, we compared the performance of the three indexes. Overall, the Randić index outperformed the other two indexes for both MCI and AD groups. Only in the case of one threshold value (0.25) for the AD group, the Kirchhoff index showed a best performance. On the other hand, for MCI patients, the Kirchhoff index got worse when about 40% of the nodes of the graphs became disconnected, probably because of the Kirchhoff index sensitivity to the removal of the graph nodes. However, the statistical analysis showed a significant difference just between CNT and AD groups for all three indexes in the relevant threshold range. Future works could take into account other methods for classification tasks [77].

The main drawback of this work is represented by the database because the three groups are not balanced and consist of a limited number of subjects. In addition, this is a cross-sectional study, so our estimation is related to average values of the connectivity indexes. However, in despite of these concerns, this study must be considered in the broader context of the preparatory work needed to conduct a next in-depth, time-expansive research that will involve many patients and should provide more extensive results. One of the objectives of this forthcoming research will also be to confirm the results presented in this work by means of a longitudinal study, assessing the measures provided by these indexes with respect to the evolution of the disease of each patient monitored over time.

Furthermore, the use of directed graphs and multivariate methods could be exploited to study the effective connectivity, which refers to the causal relationship between brain regions. The advantage of multivariate methods is that they identify and suppress spurious connections, which can be produced by bivariate analysis (e.g., LLC) [6,7,16].

Moreover, the study of brain network robustness has to be considered as a starting point for deeper analysis involving other indexes representing several topological properties of brain networks. In addition, the choice of the most appropriate threshold for the connection matrix is a crucial issue because information deriving from network not adequately connected will turn out to be meaningless. Wang and colleagues considered a threshold value corresponding to a moderately connected network (about 50% of edges) [23]. The information deriving from different network parameters can be exploited for the study of the small-world properties of brain networks, thus providing valuable elements for supporting the medical assessment of Alzheimer’s disease.

In conclusion, this work provides a preliminary study which produces an analysis of robustness of graphs representing the brain networks in Alzheimer’s disease. The novelty is represented by the introduction of the Randić index and the Kirchhoff index for the study of complex brain networks. These two indexes, above all the Randić index, turned out to be able to best discriminate the groups of subjects in comparison to the Connection Density index, widely employed in this field. These outcomes represent a first step for further analyses and, together with other networks’ properties, could provide valuable elements for improving the early diagnosis of Alzheimer’s disease.