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.

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 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.

To identify and analyze the frequently used shortest communication paths of information transfer in the thresholded FBNs stored in GD, 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.

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.

Fig. 2.

(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.

Fig. 3.

(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.

Table 1 All possible shortest paths from each node to every other node in 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.

Fig. 4.

(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.

Fig. 5.

(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.

Fig. 6.

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 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.

Fig. 7.

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.

Fig. 8.

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.

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%.

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.

Fig. 10.

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.