^{1}Computational Neuroscience Laboratory, Department of Applied Mathematics and Computational Sciences, PSG College of Technology, Coimbatore, Tamil Nadu, 641004, India

^{2}Department of Computer Science and Software Engineering, Miami University, Oxford, Ohio, 45056, USA

^{3}Cognitive Neuroengineering Laboratory, School of Information Technology and Mathematical Sciences, Division of IT, Engineering and the Environments, University of South Australia, Adelaide, 5005, South Australia

^{*}Correspondence: ramasav@miamioh.edu (Vijayalakshmi Ramasamy)

**Submitted: 30 March 2017 | Accepted: 18 September 2017 | Published: 15 May 2018**

Understanding and analyzing the dynamic interactions among millions of spatially distributed and functionally connected regions in the human brain constituting a massively parallel communication system is one of the major challenges in computational neuroscience. Many studies in the recent past have employed graph theory to efficiently model, quantitatively analyze, and understand the brain's electrical activity. Since, the human brain is believed to broadcast information with reduced material and metabolic costs, identifying various brain regions in the shortest pathways of information dissemination becomes essential to understand the intricacies of brain function. This paper proposes a graph theoretic approach using the concept of shortest communication paths between various brain regions (electrode sites) to identify the significant communication pathways of information exchange between various nodes in the functional brain networks constructed from multi-channel electroencephalograph data. A special weighted network called the Shortest Path Network is constructed from a functional brain network where the edge weight is computed as the sum of frequency of occurrence of that edge in all possible shortest paths between every pair of electrodes. The weighted Shortest Path Networks thus constructed portray information on the number of times the edges are used in information propagation during different cognitive states. This network is further analyzed by computing the influential communication paths to characterize the information dissemination among brain regions during different cognitive load conditions. The experimental results presented demonstrate the efficacy of this novel graph theoretic approach in identifying, quantifying, and comparing the significant shortest pathways of information exchange during mild and heavy cognitive load conditions. Analysis also suggests that future research should consider the biological inferences of the ability of the human brain to use reduced material and metabolic cost during the instantaneous transmission of information.

It has been one of the major themes of research in the field of computational neuroscience in the recent past to understand the complex functioning of the human brain during different cognitive load states. Cognition is a mental process of transforming sensed information into action. Besides an active research in unveiling the abnormality of brain functioning in the literature, understanding of normal brain functioning has gained significant attention in addressing various mental health issues [1,2,3,4,5,6]. Characterization of the neuronal interaction patterns of the brain during different activities is a challenging problem and many studies have used graph theory as a tool to model and analyze the organizational principles of the brain to thereby understand the complexity of cognitive function. Graph, a renowned data structure, models the relationships/interactions among entities as networks to facilitate better understanding of the functioning of complex systems [7,8,9,10,11].

There has been an increasing interest in human neuroscientific research not only due to advances both in various non-invasive data acquisition techniques such as neuroimaging (e.g., magnetic resonance imaging (*MRI*), functional magnetic resonance imaging (*fMRI*)) and neurophysiological recording (e.g., electroencephalography (*EEG*), magnetoenphalography (*MEG*)) that help to acquire the electrical activity of the human brain but also due to technological developments in methods of data analysis. Despite the advent of advanced neuroimaging technologies, for several decades the wide use of *EEG* in many areas of clinical work and research to investigate the brain's behavior has been promising due to its non-invasive nature, superior temporal resolution, and low hardware cost etc [12]. The electrical activity of the brain recorded using multi-channel *EEG* has enabled acquisition of dynamic and non-trivial information related to the patterns of interaction of various brain regions. Analysis of such massive spatiotemporal databases requires the use of extensive and efficient computational knowledge acquired from many disciplines, such as graph theory, inferential statistics, signal processing, and complex network theory, which help in the understanding of human brain behavior during various mental tasks.

Recent studies in neuroscience have revealed the notion of shortest paths for the transfer of information within the brain. The human brain exchanges information with reduced material and metabolic costs [13]. The fact that brain networks use the shortest paths to communicate information during different brain activities has been analyzed by investigators to understand functional connectivity with regard to structural connectivity [14]. Some of the network analysis measures used in Functional Brain Network (*FBN*) analysis such as average path length, diameter, and global efficiency are based on the concept of shortest paths, thus demonstrating the fact that the most effective information dissemination takes place through shorter paths. A short average path length and high clustering coefficient are the characteristics of small-world networks exhibited by the brain networks that allow segregated and cost-effective information processing with regard to wiring and metabolic cost [15]. Hence, analyzing the shortest information communication pathways between brain regions provides a better understanding of brain function during various cognitive activities in normal brain and when networks are alterated by brain diseases. Many investigators have used the concept of shortest path to study the topological properties of brain networks in the recent past. The current study emphasizes the analysis of the shortest path networks constructed for mild and heavy cognitive load states to characterize the information communication patterns among brain regions during these states. It uses the thresholded subnetwork of the *FBN* derived from a special thresholding algorithm (proposed by the authors) for studying the shortest paths between brain regions used for information dissemination.

This paper proposes a shortest path based network analysis approach to characterize mild and heavy cognitive load conditions of the human brain by computing the number of times data transmission occurs through the shortest paths in the FBNs. The *FBN* is constructed using a non-linear statistical metric on preprocessed *EEG* data results in a fully connected weighted *FBN*. To retain and analyze only those strong connections in *FBN*, a Branch-and-Bound based thresholding algorithm called Weighted Subgraph Extraction algorithm (WeSE) is used as a measure of data reduction [16]. A special weighted network called the Shortest Path Network (*SPN*) is constructed from the thresholded *FBN* by computing the weight of each edge as the number of times it occurs for all possible shortest paths of data transmission between all pairs of electrode sites. Thus, the weights of the edges in *SPN* contain the essential information about the number of times each edge lies in the shortest communication path between brain regions. The weighted *SPNs* constructed for mild and heavy cognitive load states are further analyzed using graph theoretical methods and statistical tests to characterize cognitive activity of the brain.

Neuroscience is one of the most predominant areas of research to study the human brain activity ranging from macro to micro scales. The massive volumes of data generated by various neuroimaging/neurophysiological techniques have posed many challenges to the computational neuroscience research community including modelling, storing, and mining of the data. To address these challenges, many investigators have analyzed the complex and dynamic behavior obtained from the human brain by use of advanced methods derived from graph theory, signal processing, statistics, and information theory. In particular, connectivity based methods derived from graph theory have played a significant role in characterizing the brain's behavior during different activities. Graph based analytical techniques model brain regions and the complex relationships that exist between them as nodes and edges, respectively. The intrinsic neuronal connectivity patterns attributed to various normal and disturbed brain functions are explored using neuroimaging/neurophysiological data that is modelled as a weighted graph/network. These networks are constructed by different brain regions (electrode sites) as nodes/vertices, the physical connections (synapses or axonal projections) or functional association among brain regions as edges (links) between them, and the connectivity strength (correlations between the nodes) as weights of the edges [8].

The magnitude of temporal dependency measured among *n* brain regions during a specific activity using linear/non-linear statistical measures results in an *$n \times n$* functional connectivity matrix that portrays the multivariate relationships between them. The temporal dependencies computed between all pairs of brain regions are represented as a network referred to as a Functional Brain Network where electrode sites and the statistical dependencies computed between them are considered as its nodes and edge weights, respectively [17]. A range of linear/non-linear measures such as Pearson's Correlation Coefficient (r), Magnitude Squared Coherence (MSC), Approximate Entropy (AE), Mutual Information (MI), and Synchronization Likelihood (SL) have been used by various researchers to construct *FBN* from neuroimaging/neurophysiological data [18,19,20,21,22]. While the linear measures capture only the linear dependency between two variables, many investigators have employed non-linear measures (such as MI, SL) to analyze underlying non-linear relationships, as such measures take into account both linear and non-linear associations between two variables. Here, MI is employed to construct *FBNs* as a quantative measure of the relation between pairs of random variables. The MI between two discrete random variables *X* and *Y* is computed as

where *p(x, y)* is the joint probability distribution function of *X* and *Y*. *p(x)* and *p(y)* are the marginal probability distribution functions of *X* and *Y*, respectively. The *MI* of *X and Y* is zero if they are independent and it is a symmetric measure. *MI* is the same as the entropy of *Y*(or *X*). Since the *MI* of *X* and *Y* lies in the range 0 to min *H(X)*, *H(Y)*, where *H(X)* and *H(Y)* are the entropies of *X* and *Y* respectively, it needs to be normalized before comparing the results across different activities. In analyses reported here, a minimum of the entropies of *X* and *Y* is used for normalization [20]. To facilitate analysis of a fully connected weighted *FBN*, a process called thresholding, that eliminates the noisy/ weak connections, is used thereby retaining only the relatively strong connections. Various thresholding methods such as fixed thresholding, fixed average degree, and fixed edge density are used to alyze *FBNs* [23,24,25]. To overcome a number of limitations in these techniques, a Branch-and-Bound based *WeSE* algorithm which does not use any arbitrarily chosen threshold value is used. The novelty of this algorithm is that, it dynamically selects only the strong connections from a fully connected weighted network while preserving the connectedness of the network [16].

Graph theory based complex network analysis techniques are extensively used to examine various topological properties of the functional connectivity of networks. Investigating the shortest paths between the network elements of the thresholded *FBN* opens a useful perspective on the influential communication pathways. Such an analysis provides a comprehensive understanding of the small-world properties of brain network organization, nodes that are hubs during a particular brain activity, community structures, and the local and global communication abilities [26].

*2.1 Role of shortest path analysis in complex networks*

Many topological properties of real-world complex networks such as biological, social, and technological networks are formalized based upon the assumption that the information flows in a network along the shortest (or geodesic) paths so as to optimize transportation cost. Given a weighted undirected graph G = (V, E) with positive weight function $ {w:E \to R} $, the weight w of a path $ p = (v_{0}, v_{1},\dots, v_{n}$) is computed as

where *w(p)* is the sum of the weights of the edges of the path *P*. For any two nodes s(source) and t (destination), the shortest path weight (represented as $\delta(s, t)$) is computed as

The shortest path between the nodes $s$ and $t$ is defined as any path $ p $ with weight $w(p) = \delta(s, t )$ [27]. In other words, the shortest path between two nodes $s$ and $t$ is defined as an ordered set of edges linking the nodes $s$ and $t$ where the sum of the weights of the edges of the path is minimal. A network may contain multiple shortest paths between a pair of nodes. The concept of shortest paths has been widely used in many application areas including social networks (to identify influential persons and communities), metabolic networks (to find the optimal pathways between compounds), transportation networks (to identify efficient routes between source and destination) and communication networks (to efficiently manage various resources) [28,29,30,31].

Shortest paths in FBNs have been considered the principal routes/functional pathways through which information propagates most of the time to various brain regions [27]. In particular, it has already been proved that the human brain exhibits small-world properties characterized by a high clustering coefficient (densely connected local clusters) and short path length between any pair of nodes. This property confirms both the segregated and distributed information processing abilities of the brain [15]. The small-worldliness further ensures that information is disseminated along the shortest paths thereby minimizing conduction delays and the energy required to propagate information between various brain regions. Shortest paths in *FBNs* have also demonstrated their role in the prediction of the cognitive abilities of individuals [32]. Moreover, the concept of shortest path has been used as an underlying metric in defining a number of popular network measures such as closeness, betweenness, characteristic path length, local and global efficiencies, eccentricity, and diameter [10,33].

Various investigators have studied and characterized different types of networks using shortest paths based on the assumption that information dissemination over shortest paths is faster and less noisy [8]. Shortest-path based network analysis has been used to identify the genes that modulate longevity by construction of a shortest path longevity network from a protein-protein interaction dataset. Analysis of this network enabled not only the identification of longevity-associated genes but also the genes that cause multiple age-associated diseases such as cancer, heart disease, and neurodegenerative disorders [34]. The shortest paths between the nodes in a network have also served as a sampling method for online social networks. Each edge occurring in the shortest paths between many pairs of selective nodes are ranked based on the number of times they appear in various shortest paths. The subnetwork (sampled network) that includes a specified percentage of the highly ranked edges is then extracted and used for further analysis [35].

The Union of Shortest Path Trees (*USPT*) rooted at each node in the network has been used as a sampling method to analyze *FBNs*. The *USPTs* of a *FBN* represent the most important connections. These are interpreted as the functional highways of brain networks. Analyzing these shortest paths facilitates both the identification of pathological network changes that result in certain brain diseases, such as multiple sclerosis, and the significant differences in network topology between patients with mental disorders and healthy controls [27]. Thus, the study of shortest paths in *FBNs* helps to identify frequently used communication paths and influential nodes that occur repeatedly in shortest paths and to characterize brain functions during different activities.

*2.2 Data collection and pre-processing*

The *EEG* data used in this study was collected in the Cognitive Neuroengineering & Computational Neuroscience Lab (*CNEL*) at the University of South Australia, HREC Approval (30855), from nine participants (P1 through P9). Participants were asked to drive a US standard Simuride driving simulator. A 30 channel Nuamps *EEG* amplifier is used to acquire the *EEG* data using Curry V7 software. *EEG* data is collected for two distinct cognitive load conditions: a simple driving along a curved track maintaining constant speed (*Drive*) and driving with audio distraction (*DriveAdo*). Detailed description about cognitive load experiments given to participants during data collection and the data preprocessing methods used are given in Thilaga *et al*. [16].

The proposed Shortest Path based Network Analysis Framework (*SPNA Framework*) is shown in Fig.1 with the following four-fold objectives.

(i) Construct Graph Database (*GD*) containing *FBNs* for the two cognitive load conditions mentioned earlier from *EEG* data pre-processed using *NMI*.

(ii) Extract the thresholded (influential) subnetworks from the fully connected *FBNs* using a dynamic Branch-and-Bound based Weighted Subgraph Extraction (*WeSE*) thresholding algorithm.

(iii)Construct Shortest Path Networks from thresholded *FBNs* using Dijikstra's shortest path algorithm, and

(iv)Characterize the brain functioning during mild and heavy cognitive activities using* SPNs*.

Shortest Path based Network Analysis Framework.

The following subsections describe the steps involved in modelling and analyzing *FBNs* to characterize brain function during the various cognitive activities.

*3.1 Construction of FBNs*

The preprocessed *EEG* data (time domain-amplitude) of mild (*Drive*) and heavy (*DriveAdo*) cognitive load states are partitioned into a number of chunks (each of length two seconds). It is well known that the human brain is a complex non-linear system showing emergent properties. The *EEG* signal produced by the brain is non-stationary as its statistical properties are time variant [36]. However, in time and frequency domain analysis, an *EEG* signal is considered stationary over a short time interval for efficient estimation of different average statistical functions [37,38]. Non-stationarity in EEG signals and methods to overcome this through segmentation, including 2 second segmentation, has been described well in literature [39,40,41,42,43]. Any choice of *EEG* time segment (epoch length) for analysis is always associated with a compromise between time and frequency resolution. It is not possible to choose a segment length which will give both high temporal and frequency resolution [44]. Here, two second *EEG* segments are used, following previously reported literature. Each chunk of data is modelled as a *FBN* by considering the *n* electrode sites (in this study, *n* = 30) as nodes and the pair-wise associations of these sites measured using a non-linear statistical measure *NMI* as weights on the edges. These *NMI* graphs computed for forty chunks of *EEG* data are averaged into a single graph. The fully connected weighted undirected *NMI* graphs (*FBNs*) of different cognitive load states are stored into *GD*. To retain only the influential/strong connectivity patterns that contribute to the study of cognitive activities, the weak/false positive connections are eliminated from the undirected complete *FBNs*. To achieve this, a dynamic Branch-and-Bound based *WeSE* algorithm is used to obtain the thresholded subnetworks. The significance of the *WeSE* is that it dynamically extracts the influential connections from the fully connected *FBNs* without any user specified threshold value while simultaneously ensuring network connectivity [16]. These weighted undirected thresholded graphs/networks are used to study the shortest communication paths of information exchange in the *FBNs* during mild and heavy cognitive load states.

*3.2 Construction of Shortest Path Networks*

To identify and analyze the frequently used shortest communication paths of information transfer in the thresholded *FBNs* stored in *G*D, all the shortest paths between all pairs of nodes are computed using Dijikstra's algorithm [45]. A special network called Shortest Path Network (*SPN*) is constructed using Algorithm 1.

The *SPN* is defined as a weighted undirected network/graph *G = (V, E, w)*, where *V* and *E* are sets of vertices (electrode sites) and edges (links between the electrode sites) respectively and *w* represents the weights on the edges *E* computed as the frequencies of occurrences of the edges in all possible shortest paths between all pairs of nodes. Algorithm 1 computes all the shortest paths between all pairs of nodes in the thresholded *FBNs*. For each edge *(u, v)* in the shortest paths, it computes the number of times (frequency) it lies in all possible shortest paths (steps 5 to 9) between all pairs of nodes. The frequency values computed for all the edges are then updated as edge weights in the *SPN*(step 10). For an edge *(u, v)* in *SPN*, the high edge weight indicates that this edge is used many times in the shortest path of information transfer and hence, it is influential and dominant. Therefore, by analyzing the *SPNs* of different cognitive load states, it is possible to identify the influential functional pathways that are used for information dissemination most of the times during a specific brain activity.

Algorithm 1 Construction of SPN |
---|

Input: Thresholded FBN in GD_{s} |

Output: SPN_{s} |

1. frequency(u;v) ←0, Paths = {φ}, SPN←{φ}, (u;v) is the edge |

between the nodes u and v |

2. for each FBN, FBN, 1 ≤ i ≤ _{i}N, N = number of FBN in _{s}GD |

3. for each node, Node in _{j}FBN, 1 ≤ _{i}j ≤ n |

4. Paths←Set of all possible shortest paths from Node to _{j}Node,_{k} |

1 ≤ k ≤n; j ≠ k |

5. for each PathP in Paths_{a} |

6. for each edge (u) in _{j} ,v_{k}P_{a} |

7. frequency (u_{j} , v_{k}) ←frequency (u_{j} , v_{k}) + 1; |

8. end for |

9. end for |

10. Update SPN with all the edges in _{i}P with weight(_{a}u_{j} , v_{k}) = |

weight(u) + frequency(_{j} , v_{k}u)_{j} , v_{k} |

11. frequency(u_{j} , v_{k}) ←0, 1 ≤ j;k ≤ n |

12. end for |

13. Append SPN into _{i}GD |

14. end for |

*3.3 Analysis of SPNs*

Analyzing the topological characteristics of *SPN* using efficient computational methods helps in the study of information communication patterns in the brain. The edge weights in the *SPN* of a specific brain activity contain significant information about how many times a particular edge has been used in the shortest path of information exchange to other brain regions. Hence, by comparing the edge weights of *SPNs* of mild and heavy cognitive load states, the Dominant neuronal Connections (*DCs*) due to specific cognitive activity can be identified. The *DCs* in the *SPN* of mild cognitive load state (*SPN${} _{DCmild}$*) are defined as those connections with high edge weights when compared to heavy cognitive load state and are computed as

Similarly, the *DCs* of heavy cognitive load state (*SPN${} _{DCHeavy}$*) are computed by including only those edges with high edge weights during this state and is given as:

This connectivity analysis provides useful information at the macro level based on the number of dominant connections present in *SPNs* of mild and heavy cognitive load states. A two-tailed $ t $-test is carried out by comparing the number of *DCs* in each brain region (electrode sites) in the *SPN${} _{DCmild}$* and *SPN${} _{DCHeavy}$* networks to ensure that the group means of these networks are significantly different. To further investigate only those high weighted edges that contribute more to the study of frequently used shortest communication paths among the brain regions, the highly dominant connectivity patterns in the *SPNs* are extracted using a graph theoretic approach called Minimum Connected Component (*MCC*) [3]. *MCC* is a spanning subgraph of the original graph which extracts significant connected components of a given weighted graph without using any specified parameter. The *MCCs* of *SPNs* constructed for mild and heavy cognitive load states are further analysed to uncover the brain regions that are involved in transmitting information through the shortest paths most of the time.

The construction of a *SPN* is illustrated using an undirected fully connected weighted graph G(*FBN*) with seven nodes (edge weights represent the statistical dependencies between the nodes) and its adjacency matrix as shown in Fig.2a and 2b.

(a) Undirected fully connected weighted Graph $G$; (b) Adjacency Matrix of $G$.

To reduce the computational complexity involved in analyzing the *FBNs*, the weak/insignificant connections are removed from $G$ using a *WeSE* thresholding algorithm. The thresholded subnetwork of $G$ ($G'$) constructed using the *WeSE* algorithm is shown in Fig.3a.

(a) Thresholded subnetwork $G'$; (b) $G'$ after remapping the edge weights.

Fornito et al. [46] have stated that the edges with high weights in a functional connectivity matrix are the strongest and the most reliable connections among brain regions. Performing a shortest path analysis using the weighted *FBN* is anomalous because the shortest path between any two nodes $ s $ and $ t $ is computed as the sum of weights of the edges between them in the paths that are minimal. As a consequence, such an analysis includes less influential edges and avoids the most important communication routes of information transfer (i.e., high weighted edges). To overcome this problem, a monotonic remapping of the edge weights is performed before computing the shortest paths. This remapping converts the largest weights into smallest weights and vice versa. If the edge weights ${w} _{ij}$, $ 1\leq i, j \leq n $, are between 0 and 1, either ${w} _{ij}$ $ \leftarrow $ - log ${w} _{ij}$ or ${w} _{ij}$ $ \leftarrow $ 1 - ${w} _{ij}$ can be considered as remapping functions [14]. Since the weights of the edges in the *FBN* are positive values in the range 0 to 1, the edge weights are remapped by subtracting them from 1. This enables the shortest path algorithm to choose high weighted edge at each step. In the current study, Dijkstra's shortest path algorithm [45] is used to compute all possible shortest paths between all pairs of nodes from the given *FBN*. Graph $G'$ after remapping of edge weights is shown in Fig.3b. All possible shortest paths computed between all pairs of nodes in $G'$ (Fig.3b) are shown in Table 1.

*G'*after remapping the edge weights

From the shortest paths list, the frequency of occurrence of each edge is calculated by counting its presence in all possible shortest paths. This gives useful information about which edges are prominent in propagating information through the shortest paths. For instance, in the illustrated example, the edge (3, 4) occurs in six different shortest paths (2-3-4, 3-4-1, 3-4, 5-3-4, 6-7-3-4 and 7-3-4) and hence the edge weight of this edge in *SPN* is 6. The frequencies of occurrence of all the edges in $G'$ are computed to represent the edge weights of the *SPN*. The *SPN* of $G'$ (assuming that this network represents the heavy cognitive load state) constructed using Algorithm 1 and its adjacency matrix are shown in Fig.4a and 4b respectively.

(a) *SPNHeavy* constructed from $G'$; (b) Adjacency Matrix of *SPNHeavy*.

Using the *SPNs* of mild and heavy cognitive load states, the *DCs* in each of these states are extracted using equations (4) and (5). The extraction of *DCs* from the *SPNs* of these cognitive load states is illustrated using the two networks shown in Fig.5a and 5b as *SPN${} _{Mild}$* and *SPN${} _{Heavy}$*cognitive load networks, respectively.

(a) *SPN _{Mild}*; (b)

*SPN*.

_{Heavy}To accomplish the objective of characterizing the information communication patterns among various brain regions during mild and heavy cognitive load conditions using a shortest path based network analysis approach, the following heuristic is employed. If an edge weight (representing the frequency of occurrence of that edge in all possible shortest paths between all pairs of nodes) is more, for instance, during heavy cognitive load state than that of mild cognitive load state, it is retained only in the *SPN* of the heavy cognitive load state. In case of equal frequencies, the contribution of that edge in disseminating information during different cognitive load states is equal. Hence, such an edge will neither help expose the differences nor a change in the communication patterns of information exchange during mild and heavy cognitive load states.The heuristic used to compare the *SPN* networks highlights the most significant shortest functional pathways of information transmission during a specific cognitive activity. For instance, the edge weight of the edge (1, 2) in *SPN${} _{Mild}$* and *SPN${} _{Heavy}$* are two and three, respectively, as shown in Fig.5a and 5b. So, this *DC* is retained in *SPN${} _{Heavy}$* but removed from *SPN${} _{Mild}$*. Similarly, the edge (2, 3) has edge weight three in both the *SPN${} _{Mild}$* and *SPN${} _{Heavy}$* networks and hence it is removed from both these networks. This process is repeated for all the edges present in the *SPNs* of mild and heavy cognitive load states. The resulting *SPN${} _{DCmild}$* and *SPN${} _{DCHeavy}$* networks are shown in Fig.6a and 6b, respectively. The *DCs* in the *SPN${} _{DCmild}$* and *SPN${} _{DCHeavy}$* networks show the influential and frequently used connectivity patterns employed for dissemination of information to various other brain regions during mild and heavy cognitive load conditions respectively.

*SPNs* with Dominant Connections (a) *SPNDC _{Mild}*; (b)

*SPNDC*.

_{Heavy}Further analyzing these edges with efficient computational techniques, such as graph theory based methods and statistical tests, would facilitate detection of the shortest communication patterns of brain networks during different brain states.

The *SPNs* constructed from the thresholded states of the *FBNs* of *Drive* and *DriveAdo* for participants were analyzed using graph theoretic concepts and the results are statistically validated using a two-tailed statistical $ t $-test. The results and discussion of various analyses of *SPNs* are included in the following subsections.

*4.1 Analysis of connectivity patterns of SPN*

The connectivity patterns (edges) between the electrode sites of *SPNs* of *Drive* and *DriveAdo* states of all participants are shown in Fig.7a and 7b, respectively.

*SPNs* of all the participants (a) *Drive* state; (b)* DriveAdo* State.

It is important to note that the edges in the *SPNs* of *Drive* and *DriveAdo* states are computed from the thresholded *FBNs* of the respective states. The thresholded *FBN* (obtained using the *WeSE* thresholding algorithm) includes only the influential edges (edges with high edge weights) which are determined by the topology of the fully connected *FBN* and associated edge weights. Hence, the shortest paths computed using the thresholded *FBN* provides only high-probability paths, such that information is disseminated over them to various other brain regions. These shortest paths (computed using Dijkstra's algorithm) are used to construct the *SPNs* of *Drive* and *DriveAdo* states as shown in Fig.7a and 7b, respectively. Since, the *SPNs* of these states are dense, it is very difficult to identify the connections employed by the shortest paths most of the time for information exchange during a particular brain activity. To understand only the relatively strong (dominant) connectivity patterns among the electrode sites which might characterize the *Drive* and *DriveAdo* states, the edge weights in the *SPNs* of these states are compared using the heuristic as discussed in Section 4.3. Fig.8a and 8b illustrate the *DCs* of *Drive* (*SPN${} _{DCDrive}$*) and *DriveAdo* (*SPN${} _{DCDriveAdo}$*) states, respectively, for all participants. These dominant connections are used in information transfer many times during the respective cognitive load state.

Dominant Connections of all the participants (a) *SPNDCDrive*; (b) *SPNDCDriveAdo*.

The *DCs* present in the *SPNs* of *Drive* and *DriveAdo* states are analyzed using an edge density measure. From Fig.8a and 8b, it is interesting to note that the number of *DCs* (edge density) during the *DriveAdo* state is relatively high when compared to the *Drive* state for all participants. The high edge density during *SPN${} _{DCDriveAdo}$* indicates that many edges are utilized in information exchange using shortest paths. Moreover, the high edge density results of the short average path length of the network enable effective communication among the various regions active during the *DriveAdo* state.

The presence of many *DCs* between brain regions during the *DriveAdo* state further indicates that information flow to other brain regions takes place over many shortest paths enabling higher functional integration during heavy cognitive load states. To statistically validate that the number of *DCs* of electrode sites between the *SPN${} _{DCDrive}$* and *SPN${} _{DCDriveAdo}$* networks are significantly different, group means are computed using a post-hoc $ t $-test (two-tailed) at *$\alpha$* 0. 05 with Bonferroni adjustment. Results for all participants are shown in Fig.9.

Statistical $ t $-test results of all the participants.

The results of the $ t $-tests reveal that the group means of the number of *DCs* of electrode sites computed for *Drive* and *DriveAdo* states are significantly different for all participants and that the number of *DCs* of electrode sites in the *SPN* of *DriveAdo* state is relatively high. This indicates that with an increasing cognitive load, the number of *DCs* connections employed to transfer information between brain regions also increases. Experimental results further illustrate that the number of *DCs* present in the *SPN${} _{DCDriveAdo}$* network is greater when compared to the *SPN${} _{DCDrive}$* state for all participants.

To quantitatively compare differences in the number of *DCs* between the electrode sites of the *SPN${} _{DCDrive}$* and *SPN${} _{DCDriveAdo}$* networks, the mean differences between the number of *DCs* of these states are computed using post-hoc $ t $-tests (two-tailed) at *$\alpha$* 0.05 with Bonferroni adjustment and the results are presented in Table 2. After Bonferroni adjustment, *p* (new *$\alpha$*-*values*) less than 0.05 are considered statistically significant. It is can be seen that *p values* for all the participants are less than 0.05, hence the group means of all participants are significantly different. Therefore, the null hypothesis that the mean difference of the number of *DCs* of the electrode sites in the *SPN${} _{DCDrive}$* and *SPN${} _{DCDriveAdo}$* networks is not significantly different is rejected for a signficance level of 5%.

*DCs*of electrode sites in

*SPN*and

_{DCDrive}*SPN*networks of all the participants

_{DCDrive}Participant | Mean Difference of DCs |
>95% CI | >p-value |
---|---|---|---|

P2 | -4.4667* | [-7.8314, -1.1020] | 0.0102 |

P3 | -5.5333* | [-8.9584, -2.1083] | 0.002 |

P4 | -3.6333* | [-7.2408, -0.0259] | 0.0447 |

P5 | -4.4000* | [-7.3391, -1.4609] | 0.038 |

P6 | -7.2667* | [-10.9129, -3.6205] | 0.00061 |

P7 | -6.3333* | [-9.6891, -2.9776] | 0.00573 |

P8 | -7.5333* | [-10.8562, -4.2105] | 0.0003145 |

P9 | -4.9000* | [-8.2348, -1.5652] | 0.01356 |

*Mean difference is significant at *a <* 0.05 level.

The results shown in Fig.8a and 8b give only limited information about the number of *DCs* present in the *SPNs* of *Drive* and *DriveAdo* states. To further investigate and extract the highly dominant connections which occurred most of the time in the shortest paths of information exchange, the graph theoretic concept of *MCC* was used. It extracted only the highly dominant connections (i.e., the edges with higher weights) from the *SPN${} _{DCDrive}$* and *SPN${} _{DCDriveAdo}$* networks. Using the *MCC* networks of mild and heavy cognitive load states, the average number of connections of all the electrode sites normalized in the range of values 0 to 1 (low to high), represented using the color bar (blue: low to red: high), is plotted in the 3D headplot as shown in Fig.10 to visualize and identify the electrode sites which are many times found within the shortest paths of information exchange between other electrode sites.

Average number of highly *DCs* in *MCC* networks of *Drive* and *DriveAdo* states of all the Participants.

The empirical results of headplots show that only a few electrode sites in the frontal, central, and central-parietal regions during the *Drive* state used many shortest paths for exchanging information. On the other hand, during *DriveAdo*, transmission of information occurred through many of the frontal electrode sites using highly dominant shortest path connections. This can be interpreted to mean that the frontal region is much involved in faster information propagation to various other brain regions during the *DriveAdo*, which assists in promoting various significant cognitive skills such as problem solving, reasoning, creativity, and judgment.

The shortest path based network analysis approach is employed in this study to identify information communication patterns in the brain during mild and heavy cognitive load states. The uniqueness of this study is that the shortest paths are computed using a thresholded network of fully connected *FBN* that includes only influential connections (connections over which the amount of information exchange is high). Using these influential connections, all possible shortest paths between all pairs of nodes were computed and the number of occurrences of each edge was calculated to construct a *SPN* network. The *SPNs* of mild and heavy cognitive load states are analyzed using a heuristic that highlights the *DCs* (i.e., edges occurring in the shortest paths many times) of the respective state. The connection density of the networks of different brain states informs the spread of information to various brain regions. The empirical analysis performed using the *DCs* revealed that the number of *DCs* (connection density) during *DriveAdo* is relatively higher than that of the *Drive* state. This implies that an increase in the number of *DCs* is due to increased cognitive load. The statistical $ t $-test performed using the *DCs* of electrode sites ensures that the number of *DCs* are significantly different between the mild and heavy cognitive load states. Moreover, the experimental analysis performed using highly dominant connections extracted using the *MCC* showed that many of the electrode sites in the frontal regions have a greater number of *DCs*. This highlights the fact that the frontal electrode sites contributed more effective information integration during a heavy cognitive load state, which is essential for cognitive activities. Overall, the *SPN* based *FBN* analytic technique demonstrated its efficacy in detecting cognitive load changes in brain activity. The techniques described here have potential for the clinical diagnosis of cognitive impairments. Such research could be further extended to identify connected components (community structures) for the analysis and understand of the topology of *SPN* networks of different cognitive load states.

This work has been carried out in collaboration with the Cognitive Neuro Engineering & Computational Neuroscience Laboratory (CNeL), University of South Australia, Australia.

All authors declare no conflicts of interest.