Understanding and analyzing the dynamic interactions among the 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 functioning. 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 using multi-channel EEG data. A special weighted network called Shortest Path Network is constructed from the 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 the 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 the novel graph theoretic approach in identifying, quantifying, and comparing the significant shortest pathways of information exchange during mild and heavy cognitive load conditions. The experimental analysis also provides an element of future research to consider the biological inferences of the ability of the human brain to use reduced material and metabolic cost during instantaneous transmission of information.
BarrettA., MurphyM., BrunoM., NoirhommeQ., BolyM., LaureysS. and SethA.K., Granger causality analysis of steady-state electroencephalographic signals during propofol-induced anaesthesia, PLoS One7(1) (2012), e29072. doi:10.1371/journal.pone.0029072.
2.
BassettD.S. and BullmoreE.T., Small world brain networks, Neuroscientist12(6) (2006), 512–523. doi:10.1177/1073858406293182.
3.
BassettD.S. and BullmoreE.T., Small-World Brain Networks Revisited, The Neuroscientist (2016), 1–13. doi:10.1177/1073858416667720.
4.
BassettD.S., BullmoreE.T., Meyer-LindenbergA., ApudJ.A., WeinbergerD.R. and CoppolaR., Cognitive fitness of cost-efficient brain functional networks, Proc. Natl Acad Sci.106 (2009), 11747–11752. doi:10.1073/pnas.0903641106.
5.
BastH., FunkeS., SandersP. and SchultesD., Fast routing in road networks with transit nodes, Science316(5824) (2007), 566. doi:10.1126/science.1137521.
6.
BoersmaM., SmitD.J., BoomsmaD.I., De GeusE.J., Delemarre-van de WaalH.A. and StamC.J., Growing trees in child brains: Graph theoretical analysis of electroencephalography-derived minimum spanning tree in 5- and 7-year-old children reflects brain maturation, Brain Connect.3 (2013), 50–60. doi:10.1089/brain.2012.0106.
7.
BullmoreE. and SpornsO., Complex brain networks: Graph theoretical analysis of structural and functional systems, Nat. Rev. Neurosci.10(3) (2009), 186–198. doi:10.1038/nrn2575.
8.
BullmoreE. and SpornsO., The economy of brain network organization, Nat. Rev. Neurosci.13(5) (2012), 336–349. doi:10.1038/nrn3214.
9.
CocksB., NandagopalD., VijayalakshmiR., ThilagaM., DasariN. and DahalN., Breaking the camel's back: Can cognitive overload be quantified in the human brain?Procedia-Soc. and Behav.97(6) (2013), 21–29.
10.
DasariN., NandagopalD., VijayalaxmiR., CocksB., ThomasB.H., DahalN. and GaertnerP., Moment to moment variability in functional brain networks during cognitive activity in EEG data, J. Integr. Neurosci.14(3) (2015), 383–402. doi:10.1142/S0219635215500168.
11.
De VicoFallaniF., RichiardiJ., ChavezM. and AchardS., Graph analysis of functional brain networks: Practical issues in translational neuroscience, Philos. Trans. R. Soc. Lond. B Biol. Sci.369(1653) (2014), 20130521. doi:10.1098/rstb.2013.0521.
12.
DemuruM., FaraF. and FraschiniM., Brain network analysis of EEG functional connectivity during imagery hand movements, J. Integr. Neurosci.12 (2013), 441–447.
13.
DijkstraE.W., A note on two problems in connexion with graphs, Numerische Mathematik1 (1959), 269–271.
14.
EstevezP.A., TesmerM., PerezC.A. and ZuradaJ.M., Normalized mutual information feature selection, IEEE Trans. Neural Netw.20(2) (2009), 189–201. doi:10.1109/TNN.2008.2005601.
15.
FornitoA., ZaleskyA. and BullmoreE.T., Fundamentals of Brain Network Analysis, Academic Press, 2015.
16.
FreemanL.C., Centrality in social networks: Conceptual clarification, Soc. Networks1 (1978), 215–239. doi:10.1016/0378-8733(78)90021-7.
17.
GoniJ., van den HeuvelM.P., Avena-KoenigsbergerA., de MendizabalN.V., BetzelR.F., GriffaA., HagmannP., Corominas-MurtraB., ThiranJ.P. and SpornsO., Resting-brain functional connectivity predicted by analytic measures of network communication, Proc. NatlAcad Sci.111(2) (2014), 833–838. doi:10.1073/pnas.1315529111.
18.
HilfikerP. and EgliM., Detection and evolution of rhythmic components in ictal EEG using short segment spectra and discriminant analysis, Electroencephaograpgy and Clinical Neurophysiology82(4) (1992), 255–265. doi:10.1016/0013-4694(92)90106-R.
19.
JaliliM. and KnyazevaM.G., Constructing brain functional networks from EEG: Partial and unpartial correlations, J. Integr. Neurosci.10(213) (2011). doi:10.1142/S0219635211002725.
20.
KamelN. and MalikA.S., EEG/ERP Analysis: Methods and Applications, CRC Press, 2017. ISBN 9781138077089-CAT#K34271.
21.
KaplanA.Y., FingelkurtsA.A., FingelkurtsA.A., BorisovS.V. and DarkhovskyB.S., Nonstationary nature of the brain activity as revealed by EEG/MEG: Methodological, practical and conceptual challenges, Signal processing85 (2015), 2190–2212. doi:10.1016/j.sigpro.2005.07.010.
22.
KaplanA.Y. and ShishkinS.L., Application of the change-point analysis to the investigation of the brain's electrical activity, in: Nonparametric Statistcal Diagnosis: Problems and Methods, BrodskyB.E. and DarkhovskyB.S., eds, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2000, pp. 333–388.
23.
KempeD., KleinbergJ. and TardosV., Maximizing the spread of influence through a social network, in: KDD, 2003, pp. 137–146. doi:10.1145/956750.956769.
24.
KornbrotD., Pearson Product Moment Correlation, Encyclopedia of Statistics in Behavioral Science, Wiley, 2005.
25.
ManagbanagJ.R., WittenT.M., BonchevD., FoxL.A., TsuchiyaM., KennedyB.K. and KaeberleinM., Shortest-path network analysis is a useful approach toward identifying genetic determinants of longevity, PLoS One3(11) (2008), e3802. doi:10.1371/journal.pone.0003802.
26.
MeierJ., TewarieP. and Van MieghemP., The union of shortest path trees of functional brain networks, Brain Connect.5(9) (2015), 575–581. doi:10.1089/brain.2014.0330.
27.
NandagopalD., VijayalakshmiR., CocksB., DahalN., DasariN. and ThilagaM., Computational neuroengineering approaches to characterise cognitive activity in EEG data, in: Knowledge Based Information Systems in Practice, Smart Innovation, Knowledge, Systems and Technologies, Vol. 30, Springer International Publishing, Switzerland, 2015, pp. 115–137. doi:10.1007/978-3-319-13545-8.
28.
NolteG., BaiO., WheatonL., MariZ., VorbachS. and HalletM., Identifying true brain interaction from EEG data using the imaginary part of coherency, Clin. Neurophysiol.115(10) (2004), 2292–2307. doi:10.1016/j.clinph.2004.04.029.
29.
NunezP.L., Electroencephalography (EEG), in: Encyclopaedia of the Human Brain, RamachandranV.S., ed., 2002, pp. 169–179. doi:10.1016/B0-12-227210-2/00128-X.
30.
OlbrichE., AchermannP. and MeierP., Dynamics of human sleep EEG, Neurocomputing52–54 (2003), 857–862. doi:10.1016/S0925-2312(02)00816-0.
31.
PardeyJ., RobertsS., TarassenkoL. and StradlingJ., A new approach to the analysis of the human sleep/wakefulness continuum, J Sleep Res5 (1996), 201–210. doi:10.1111/j.1365-2869.1996.00201.x.
32.
Pastor-SatorrasR. and VespignaniA., Evolution and Structure of the Internet: A Statistical Physics Approach, Cambridge University Press, 2004.
33.
RahmanS.A. and SchomburgD., Observing local and global properties of metabolic pathways: ‘load points’ and ‘choke points’ in the metabolic networks, Bioinformatics22(14) (2006), 1767–1774. doi:10.1093/bioinformatics/btl181.
34.
RezvanianA. and MeybodiM.R., Sampling social networks using shortest paths, Physica A: Statistical Mechanics and its Applications424 (2015), 254–268. doi:10.1016/j.physa.2015.01.030.
35.
RubinovM. and SpornsO., Complex network measures of brain connectivity: Uses and interpretations, Neuroimage52(3) (2010), 1059–1069. doi:10.1016/j.neuroimage.2009.10.003.
36.
SaneiS. and ChambersJ.A., EEG Signal Processing, Wiley, England, 2007.
37.
SimpsonS.L., BowmanF.D. and LaurientiP.J., Analyzing complex functional brain networks: Fusing statistics and network science to understand the brain, Stat. Surv.7 (2013), 1–36. doi:10.1214/13-SS103.
38.
SpornsO., The human brain network, in: Handbook on Biological Networks, World Scientific Lecture Notes in Complex Systems, 2009, pp. 199–216.
39.
StamC.J. and ReijneveldJ.C., Graph theoretical analysis of complex networks in the brain, Nonlinear Biomedical Physics1(1) (2007), 3. doi:10.1186/1753-4631-1-3.
40.
SteuerR., KurthsJ., DaubC.O., WeiseJ. and SelbigJ., The mutual information: Detecting and evaluating dependencies between variables, Bioinformatics18(2) (2002), S231–S240. doi:10.1093/bioinformatics/18.suppl_2.S231.
41.
ThilagaM., VijayalakshmiR., NadarajanR. and NandagopalD., A novel pattern mining approach for identifying cognitive activity in EEG based functional brain networks, J. Integr. Neurosci.15(02) (2016), 223–245. doi:10.1142/S0219635216500151.
42.
ThilagaM., VijayalakshmiR., NadarajanR., NandagopalD., CocksB., ArchanaC. and DahalN., A heuristic branch-and-bound based thresholding algorithm for unveiling cognitive activity from EEG data, Neurocomputing170 (2015), 32–46. doi:10.1016/j.neucom.2015.03.095.
43.
Van DrongelenW., Signal Processing for Neuroscientists – An Introduction to the Analysis of Physiological Signals, Academic Press, Elsevier, Amsterdam, 2007.
44.
van WijkB.C., StamC.J. and DaffertshoferA., Comparing brain networks of different size and connectivity density using graph theory, PLoS One5(10) (2010), e13701. doi:10.1371/journal.pone.0013701.
45.
VijayalakshmiR., NandagopalD., DasariN., CocksB., DahalN. and ThilagaM., Minimum connected component – a novel approach to detection of cognitive load induced changes in functional brain networks, Neurocomputing170 (2015), 15–31. doi:10.1016/j.neucom.2015.03.092.
46.
VijayalakshmiR., NandagopalD., ThilagaM. and CocksB., Characterisation of cognitive activity using minimum connected component, Neural Information Processing9492 (2015), 531–539.
