The brain is one of the largest and most complex organs in the human body and EEG is a noninvasive electrophysiological monitoring method that is used to record the electrical activity of the brain. Lately, the functional connectivity in human brain has been regarded and studied as a complex network using EEG signals. This means that the brain is studied as a connected system where nodes, or units, represent different specialized brain regions and links, or connections, represent communication pathways between the nodes. Graph theory and theory of complex networks provide a variety of measures, methods, and tools that can be useful to efficiently model, analyze, and study EEG networks. This article is addressed to computer scientists who wish to be acquainted and deal with the study of EEG data and also to neuroscientists who would like to become familiar with graph theoretic approaches and tools to analyze EEG data.
Get full access to this article
View all access options for this article.
References
1.
Abou-KhalilB, MisulisK. 2006. Atlas of EEG & Seizure Semiology. Amsterdam, The Netherlands: Butterworth-Heinemann, Elsevier.
2.
AurlienH, GjerdeI, AarsethJ, EldoenG, KarlsenB, SkeidsvollH, GilhusN. 2004. EEG background activity described by a large computerized database. Clin Neurophysiol, 115:665–673.
3.
BarratA, BarthelemyM, Pastor-SatorrasR, VespignaniA. 2004. The architecture of complex weighted networks. Proc Natl Acad Sci U S A, 101:3747–3752.
4.
BassettD, Meyer-LindenbergA, AchardS, DukeT, BullmoreE. 2006. Adaptive reconfiguration of fractal small-world human brain functional networks. Proc Natl Acad Sci U S A, 103:19518–19523.
5.
BassettDS, WymbsNF, PorterMA, MuchaPJ, CarlsonJM, GraftonST. 2011. Dynamic reconfiguration of human brain networks during learning. Proc Natl Acad Sci U S A, 108:7641–7646.
6.
BatoolK, NiaziM. 2014. Towards a methodology for validation of centrality measures in complex networks. PLoS One, 9:e98379.
7.
BaurM, BenkertM, BrandesU, CornelsenS, GaertlerM, KopfB, et al.Visone—Software for Visual Social Network Analysis. In Proceedings of the 9th International Symposium on Graph Drawing, vol. 2265, London, United Kingdom, 2002, p. 463.
8.
BlumA, RutkoveS. 2007. Clinical Neurophysiology Primer. New York: Humana Press, Springer.
9.
BrandesU. 2001. A faster algorithm for betweenness centrality. J Math Sociol, 25:163–177.
BullmoreE, SpornsO. 2009. Complex brain networks: graph theoretical analysis of structural and functional systems. Nat Rev Neurosci, 10:186–198.
14.
BuzsakiG. 2007. Rhythms of the Brain. Oxford, UK: Oxford University Press.
15.
CahnB, PolichJ. 2006. Meditation states and traits: EEG, ERP, and neuroimaging studies. Psychol Bull, 132:180–211.
16.
CardilloA, PetriG, NicosiaV, SinatraR, Gomez-GardenesJ, LatoraV. 2014. Evolutionary dynamics of time-resolved social interactions. Phys Rev E Stat Nonlin Soft Matter Phys, 90:052825.
17.
ChristodoulakisM, AnastasiadouM, PapacostasS, PapathanasiouE, MitsisG. Investigation of Network Brain Dynamics from EEG Measurements in Patients with Epilepsy Using Graph-Theoretic Approaches. In Proceedings of the 12th IEEE International Conference on Bioinformatics and Bioengineering (BIBE), Larnaca, Cyprus, 2012, p. 303.
18.
ChristodoulakisM, HadjipapasA, PapathanasiouE, AnastasiadouM, PapacostasS, MitsisG. 2015. On the effect of volume conduction on graph theoretic measures of brain networks in epilepsy. In: SakkalisV (ed.) Modern Electroencephalographic Assessment Techniques, vol. 91; p. 103. New York, NY: Springer.
19.
CohenR, HavlinS. 2010. Complex Networks: Structure, Robustness and Function. Cambridge, UK: Cambridge University Press.
20.
CormenT, LeisersonC, RivestR, SteinC. 2009. Introduction to Algorithms, 3rd ed. Cambridge, MA: MIT Press.
21.
CraddockR, TungarazaR, MilhamM. 2015. Connectomics and new approaches for analyzing human brain functional connectivity. Gigascience, 4:13.
22.
De NooyW, MrvarA, BatageljV. 2011. Exploratory Social Network Analysis with Pajek. Cambridge, UK: Cambridge University Press.
23.
De PasqualeF, Della PennaS, SpornsO, RomaniG, CorbettaM. 2015. A dynamic core network and global efficiency in the resting human brain. Cereb Cortex, 25:1–19.
24.
De Vico FallaniF, AstolfiL, CincottiF, MattiaD, MarcianiMG, TocciA, et al.2008a. Cortical network dynamics during foot movements. Neuroinformatics, 6:23–34.
25.
De Vico FallaniF, da Fontoura CostaL, RodriguezF, AstolfiL, VecchiatoG, ToppiJ, et al.2010. A graph-theoretical approach in brain functional networks. Possible implications in EEG studies. Nonlinear Biomed Phys, 4(Suppl 1):S8.
26.
De Vico FallaniF, RichiardiJ, ChavezM, AchardS. 2014. Graph analysis of functional brain networks: practical issues in translational neuroscience. Philos Trans R Soc Lond B Biol Sci, 369:20130521.
27.
De Vico FallaniV, AstolfiL, CincottiF, MattiaD, MarcianiM, SalinariS, et al.2007. Cortical functional connectivity networks in normal and spinal cord injured patients: evaluation by graph analysis. Hum Brain Mapp, 28:1334–1346.
28.
De Vico FallaniV, LatoraV, AstolfiL, CincottiF, MattiaD, MarcianiM, et al.2008b. Persistent patterns of interconnection in time-varying cortical networks estimated from high-resolution EEG recordings in humans during a simple motor act. J Phys A Math Theor, 41:224014.
29.
Del MondoG, RodrguezM, ClaramuntC, BravoL, ThibaudR. 2013. Modeling consistency of spatio-temporal graphs. Data Knowl Eng, 84:59–80.
30.
DijkstraE. 1959. A note on two problems in connection with graphs. Numer Math, 1:269–271.
31.
DimitriadisS, LaskarisN, TsirkaV, VourkasM, MicheloyannisS. 2012. An EEG study of brain connectivity dynamics at the resting state. Nonlinear Dynamics Psychol Life Sci, 16:5–22.
EngelsM, StamC, van der FlierW, ScheltensP, de WaalH, van StraatenE. 2015. Declining functional connectivity and changing hub locations in Alzheimer's disease: an EEG study. BMC Neurol, 15:145–152.
35.
EstradaE, Rodriguez-VelazquezJ. 2005. Subgraph centrality in complex networks. Phys Rev E Stat Nonlin Soft Matter Phys, 71:e98379.
FraschiniM, HillebrandA, DemuruM, DidaciL, MarcialisG. 2015. An EEG-based biometric system using eigenvector centrality in resting state brain networks. IEEE Signal Proc Lett, 22:186–195.
38.
FreemanL. 1979. Centrality in social networks conceptual clarification. Soc Netw, 1:215–239.
39.
FristonKJ. 1994. Functional and effective connectivity in neuroimaging: a synthesis. Hum Brain Mapp, 2:56–78.
40.
GareyM, JohnsonD. 1979. Computers and Intractibility: A Guide to the Theory of NP-Completeness. New York, NY: W. H. Freeman.
41.
GoldI. 1999. Does 40-hz oscillation play a role in visual consciousness?. Conscious Cogn, 8:186–195.
42.
GreenfieldL, GeyerJ, CarneyP. 2010. Reading EEGs: A Practical Approach. Baltimore, MD: Lippincorr Williams & Wilkins.
43.
GribkovD, GribkovaV. 2000. Learning dynamics from non-stationary time series: analysis of electroencephalograms. Phys Rev E Stat Phys Plasmas Fluids Relat Interdiscip Topics, 61:6538–6545.
44.
GuevaraR, LuisJ, VelazquezP, NenadovicV, WennbergR, SenjanoviG, et al.2005. Phase synchronization measurements using electroencephalographic recordings: what can we really say about neuronal synchrony?. Neuroinformatics, 3:301–314.
45.
HughesJ. 2008. Gamma, fast, and ultrafast waves of the brain: their relationships with epilepsy and behavior. Epilepsy Behav, 13:25–31.
46.
HumphriesM, GurneyK. 2008. Network small-world-ness': a quantitative method for determining canonical network equivalence. PLoS One, 3:e0002051.
IakovidouN, ChristodoulakisM, PapathanasiouE, PapacostasS, MitsisG. Introducing Weighted Approaches to Study Network Brain Dynamics from EEG Epilepsy Measurements: The EigenBrain Algorithm. In Proceedings of the 15th IEEE International Conference on Bioinformatics and Bioengineering (BIBE), Belgrade, Serbia, 2015, p. 1.
49.
IakovidouN, DimitriadisS, LaskarisN, TsichlasK. Querying Functional Brain Connectomics to Discover Consistent Subgraph Patterns. In Proceedings of the 13th IEEE International Conference on Bioinformatics and Bioengineering (BIBE), Chania, Greece, 2013a, p. 1.
50.
IakovidouN, DimitriadisS, LaskarisN, TsichlasK, ManolopoulosY. 2013b. On the discovery of group-consistent graph substructure patterns from brain networks. J Neurosci Methods, 213:204–213.
51.
IasemidisL. 2011. Seizure prediction and its applications. Neurosurg Clin N Am, 22:489–506.
52.
JiangC, CoenenF, ZitoM. Frequent Sub-graph Mining on Edge Weighted Graphs. In Proceedings of the 12th International Conference on Data Warehousing and Knowledge Discovery, Bilbao, Spain, 2010, p. 77.
53.
JiangC, CoenenF, ZitoM. 2013. A survey of frequent subgraph mining algorithms. Knowl Eng Rev, 28:75–105.
54.
JoudakiA, SalehiN, JaliliM, KnyazevaMG. 2012. EEG-based functional brain networks: does the network size matter?. PLoS One, 7:e35673.
55.
JoyceK, LaurientiP, BurdetteJ, HayasakaS. 2010. A new measure of centrality for brain networks. PLoS One,, 5:e12200.
56.
JurcakV, TsuzukiD, DanI. 2007. 10/20, 10/10, and 10/5 systems revisited: their validity as relative head-surface-based positioning systems. Neuroimage, 34:1600–1611.
57.
KashaniR, AhrabianZ, ElahiH, Nowzari-DaliniE, SaberiA, AsadiE, et al.2009. Kavosh: a new algorithm for finding network motifs. BMC Bioinformatics, 10:318.
58.
KintaliS. 2008. Betweenness centrality: algorithms and lower bounds. arXiv:0809.1906 [cs.DS].
59.
KramarenkoA, TanU. 2003. Effects of high-frequency electromagnetic fields on human EEG: a brain mapping study. Int J Neurosci, 113:1007–1019.
60.
KruskalJ. 1956. On the shortest spanning subtree of a graph and the traveling salesman problem. Proc Am Math Soc, 7:48–50.
61.
LagerlundaT. 2000. Manipulating the magic of digital EEG: montage reformatting and filtering. Am J Electroneurodiagn Technol, 40:121–136.
62.
LatoraV, MarchioriM. 2001. Efficient behavior of small-world networks. Phys Rev Lett, 87:198701.
63.
LeeU, OhG, KimS, NohG, ChoiB, MashourG. 2010. Brain networks maintain a scale-free organization across consciousness, anesthesia, and recovery: evidence for adaptive reconfiguration. Anesthesiology, 113:1081–1091.
64.
MiloR, Shen-OrrS, ItzkovitzS, KashtanN, ChklovskiiD, AlonU. 2002. Network motifs: simple building blocks of complex networks. Science, 298:824–827.
65.
NevadoA, HadjipapasA, KinseyK, MorattiS, BarnesG, HollidayI, GreenG. 2012. Estimation of functional connectivity from electromagnetic signals and the amount of empirical data required. Neurosci Lett, 513:57–61.
66.
NewmanM. 2003. The structure and function of complex networks. SIAM Rev, 45:167256.
67.
NiedermeyerE. 1997. Alpha rhythms as physiological and abnormal phenomena. Int J Psychophysiol, 26:31–49.
68.
NiedermeyerE, Lopes da SilvaF. 2012. Electroencephalography: Basic Principles, Clinical Applications, and Related Fields, 5th ed. Baltimore, MD: Lippincott Williams & Wilkins.
NolteG, BaiO, WheatonL, MariZ, VorbachS, HallettM. 2004. Identifying true brain interaction from EEG data using the imaginary part of coherency. Clin Neurophysiol, 115:2292–2307.
71.
NunezP, PilgreenK. 1991. The spline-laplacian in clinical neurophysiology: a method to improve EEG spatial resolution. Clin Neurophysiol, 8:397–413.
72.
NunezP, SilbersteinR, ShiZ, CarpenterM, SrinivasanR, TuckerD, et al.1999. EEG coherency II: experimental comparisons of multiple measures. Clin Neurophysiol, 110:469–483.
73.
NunezP, SrinivasanR. 2006a. Electric Fields of the Brain: The Neurophysics of EEG. Oxford, UK: Oxford University Press.
74.
NunezP, SrinivasanR. 2006b. A theoretical basis for standing and traveling brain waves measured with human EEG with implications for an integrated consciousness. Clin Neurophysiol, 117:2424–2435.
75.
PerazaL, AsgharA, GreenG, HallidayD. 2012. Phase synchronization measurements using electroencephalographic recordings: what can we really say about neuronal synchrony?. J Neurosci Methods, 207:189–199.
PfurtschellerG, Lopes Da SilvaF. 1999. Event-related EEG/MEG synchronization and desynchronization: basic principles. Clin Neurophysiol, 110:1842–1857.
78.
PrimR. 1957. Shortest connection networks and some generalizations. Bell Syst Tech J, 36:1389–1401.
79.
PritchardW, DukeD. 1995. Measuring “chaos” in the brain: a tutorial review of EEG dimension estimation. Brain Cogn, 27:353–397.
80.
RabinovichM, VaronaP, SelverstonA, AbarbanelH. 2006. Dynamical principles in neuroscience. Rev Mod Phys, 78:1213–1265.
81.
RubinovM, SpornsO. 2010. Complex network measures of brain connectivity: uses and interpretations. Neuroimage, 52:1059–1069.
82.
SaramakiJ, KivelaM, OnnelaJ, KaskiK, KerteszJ. 2007. Generalizations of the clustering coefficient to weighted complex networks. Phys Rev E Stat Nonlin Soft Matter Phys, 75:027105.
83.
SchmidtC, WeissT, KomusiewiczC, WitteH, LeistritzL. 2012. An analytical approach to network motif detection in samples of networks with pairwise different vertex labels. Comput Math Methods Med, 2012:910380.
84.
SimpsonS, MoussaM, LaurientiP. 2012. An exponential random graph modeling approach to creating group-based representative whole-brain connectivity networks. Neuroimage, 60:1117–1126.
85.
SpornsO. 2013. Making sense of brain network data. Nat Methods, 10:491–493.
86.
SpornsO, HoneyC. 2006. Small worlds inside big brains. Proc Natl Acad Sci U S A, 51:19219–19220.
87.
SpornsO, KotterR. 2004. Motifs in brain networks. PLoS Biol, 2:e369.
88.
StamC. 2005. Nonlinear dynamical analysis of EEG and MEG: review of an emerging field. Clin Neurophysiol, 116:2266–2301.
89.
StamC, de BruinE. 2004. Scale-free dynamics of global functional connectivity in the human brain. Hum Brain Mapp, 22:97–109.
90.
StamC, NolteG, DaffertshoferA. 2011. Phase lag index: assessment of functional connectivity from multi channel EEG and MEG with diminished bias from common sources. Hum Brain Mapp, 28:1548–1565.
91.
StamC, ReijneveldJ. 2007. Graph theoretical analysis of complex networks in the brain. Nonlinear Biomed Phys, 1:3.
92.
StumpE. 2008. The seizures no one wants to talk about. Neurol Now, 4:23–26.
93.
TangJ, ScellatoS, MusolesiM, MascoloC, LatoraV. 2010. Small-world behavior in time-varying graphs. Phys Rev E Stat Nonlin Soft Matter Phys 81(Pt, 2):055101.
94.
TeplanM. 2002. Fundamentals of EEG measurement. Meas Sci Rev, 2:1–11.
95.
TewarieP, HillebrandA, SchoonheimM, van DijkB, GeurtsJ, BarkhofF, et al.2014. Functional brain network analysis using minimum spanning trees in multiple sclerosis: an MEG source-space study. Neuroimage, 88:308–318.
96.
TewarieP, van DellenE, HillebrandA, StamC. 2015. The minimum spanning tree: an unbiased method for brain network analysis. Neuroimage, 104:177–188.
97.
ThatcherR. 2012. Coherence, phase differences, phase shift and phase lock in EEG/ERP analyses. Dev Neuropsychol, 37:476–496.
98.
ThomaM, ChengH, GrettonA, HanJ, KriegelH, SmolaA, et al.2010. Discriminative frequent subgraph mining with optimality guarantees. Stat Anal Data Min, 3:10084.
99.
Van de VilleD, BritzJ, MichelC. 2010. EEG microstate sequences in healthy humans at rest reveal scale-free dynamics. Proc Natl Acad Sci U S A, 107:18179–18184.
100.
van den HeuvelM, SpornsO. 2013. Network hubs in the human brain. Trends Cogn Sci, 17:683–696.
101.
van StraatenE, StamC. 2013. Structure out of chaos: functional brain network analysis with EEG, MEG, and functional MRI. Eur Neuropsychopharmacol, 23:7–18.
102.
VertesP, Alexander-BlochA, GogtayN, GieddJN, RapoportJL, BullmoreE. 2012. Simple models of human brain functional networks. Proc Natl Acad Sci U S A, 109:5868–5873.
103.
VijayalakshmiR, NandagopalD, DasariN, CocksB, DahalN, ThilagaM. 2015a. Minimum connected component—a novel approach to detection of cognitive load induced changes in functional brain networks. Neurocomputing, 170:15–31.
104.
VijayalakshmiR, NandagopalD, ThilagaM, CocksB. 2015b. Characterisation of cognitive activity using minimum connected component. Neural Inf Process, 9492:531–539.
105.
VinckM, OostenveldR, van WingerdenM, BattagliaF, PennartzC. 2011. An improved index of phase-synchronization for electrophysiological data in the presence of volume-conduction, noise and sample-size bias. Neuroimage, 55:1548–1565.
106.
WangZ, LiuJ, ZhongN, QinY, ZhouH, YangJ, LiK. 2012. A naive hypergraph model of brain networks. Brain Inform, 7670:119–129.
107.
WattsD, StrogatzS. 1998. Collective dynamics of ‘small-world’ networks. Nature, 393:440–442.
108.
YangJ, SuW, LiS, DalkilicM. WIGM: Discovery of Subgraph Patterns in a Large Weighted Graph. In Proceedings of the 12th SIAM International Conference on Data Mining, California, USA, 2012, p. 1083.
109.
ZhouF, MahlerS, ToivonenH. 2012. Simplification of networks by edge pruning. Lect Notes Comput Sci, 7250:179–198.
