Quantification of Graph Complexity Based on the Edge Weight Distribution Balance: Application to Brain Networks.

Graph theory; brain complexity; brain networks; entropy; Adult; Brain/physiology; Brain/physiopathology; Cognition/physiology; Computer Simulation; Female; Humans; Male; Neuropsychological Tests; Schizophrenia/diagnosis; Schizophrenia/physiopathology; Wavelet Analysis; Electroencephalography/methods; Models, Theoretical; Cognitive processing; Complexity measures; Electroencephalographic (EEG); Node degree distribution; Schizophrenia patients; Synthetic graphs; Weight distributions; Brain; Cognition; Electroencephalography; Schizophrenia; Computer Networks and Communications; General Medicine

Abstract :

[en] The aim of this study was to introduce a novel global measure of graph complexity: Shannon graph complexity (SGC). This measure was specifically developed for weighted graphs, but it can also be applied to binary graphs. The proposed complexity measure was designed to capture the interplay between two properties of a system: the 'information' (calculated by means of Shannon entropy) and the 'order' of the system (estimated by means of a disequilibrium measure). SGC is based on the concept that complex graphs should maintain an equilibrium between the aforementioned two properties, which can be measured by means of the edge weight distribution. In this study, SGC was assessed using four synthetic graph datasets and a real dataset, formed by electroencephalographic (EEG) recordings from controls and schizophrenia patients. SGC was compared with graph density (GD), a classical measure used to evaluate graph complexity. Our results showed that SGC is invariant with respect to GD and independent of node degree distribution. Furthermore, its variation with graph size [Formula: see text] is close to zero for [Formula: see text]. Results from the real dataset showed an increment in the weight distribution balance during the cognitive processing for both controls and schizophrenia patients, although these changes are more relevant for controls. Our findings revealed that SGC does not need a comparison with null-hypothesis networks constructed by a surrogate process. In addition, SGC results on the real dataset suggest that schizophrenia is associated with a deficit in the brain dynamic reorganization related to secondary pathways of the brain network.

Disciplines :

Neurology

Author, co-author :

Gomez-Pilar, Javier; * Biomedical Engineering Group, E.T.S. Ingenieros de Telecomunicación, Universidad de Valladolid, Paseo Belén, 15, 47011 Valladolid, Spain

Poza, Jesús; * Biomedical Engineering Group, E.T.S. Ingenieros de Telecomunicación, Universidad de Valladolid, Paseo Belén, 15, 47011 Valladolid, Spain ; † IMUVA, Instituto de Investigación en Matemáticas, Universidad de Valladolid, Valladolid, Spain ; ‡ INCYL, Instituto de Neurociencias de Castilla y León, Universidad de Salamanca, Salamanca, Spain

Bachiller, Alejandro; * Biomedical Engineering Group, E.T.S. Ingenieros de Telecomunicación, Universidad de Valladolid, Paseo Belén, 15, 47011 Valladolid, Spain

Gómez, Carlos; * Biomedical Engineering Group, E.T.S. Ingenieros de Telecomunicación, Universidad de Valladolid, Paseo Belén, 15, 47011 Valladolid, Spain

Nunez Novo, Pablo ; University of Valladolid > Biomedical Engineering Group

Lubeiro, Alba; § Psychiatry Department, Facultad de Medicina, Universidad de Valladolid, Valladolid, Spain

Molina, Vicente; ‡ INCYL, Instituto de Neurociencias de Castilla y León, Universidad de Salamanca, Salamanca, Spain ; § Psychiatry Department, Facultad de Medicina, Universidad de Valladolid, Valladolid, Spain ; ¶ Clinical University Hospital of Valladolid, Valladolid, Spain

Hornero, Roberto; * Biomedical Engineering Group, E.T.S. Ingenieros de Telecomunicación, Universidad de Valladolid, Paseo Belén, 15, 47011 Valladolid, Spain ; † IMUVA, Instituto de Investigación en Matemáticas, Universidad de Valladolid, Valladolid, Spain ; ‡ INCYL, Instituto de Neurociencias de Castilla y León, Universidad de Salamanca, Salamanca, Spain

Language :

English

Title :

Quantification of Graph Complexity Based on the Edge Weight Distribution Balance: Application to Brain Networks.

Publication date :

February 2018

Journal title :

International Journal of Neural Systems

ISSN :

0129-0657

Publisher :

World Scientific Publishing Co. Pte Ltd, Singapore

Volume :

Issue :

Pages :

1750032

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://www.worldscientific.com/doi/pdf/10.1142/S0129065717500320

Available on ORBi :

since 17 May 2023

Statistics

Number of views

9 (0 by ULiège)

Number of downloads

0 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

C. J. Stam et al. Graph theoretical analysis of magnetoencephalographic functional connectivity in Alzheimer's disease, Brain 132 (2009) 213-224.
D. S. Bassett, B. G. Nelson, B. A. Mueller, J. Camchong and K. O. Lim, Altered resting state complexity in schizophrenia, Neuroimage 59 (2012) 2196-2207.
J. Gomez-Pilar et al. Neural network reorganization analysis during an auditory oddball task in schizophrenia using wavelet entropy, Entropy 17 (2015) 5241-5256.
A. Bachiller et al. a comparative study of eventrelated coupling patterns during an auditory oddball task in schizophrenia, J. Neural Eng. 12 (2015) 16007-1-16007-13.
M. Shim, D. W. Kim, S. H. Lee and C. H. Im, Disruptions in small-world cortical functional connectivity network during an auditory oddball paradigm task in patients with schizophrenia, Schizophr. Res. 156 (2014) 197-203.
G. Deco, G. Tononi, M. Boly and M. L. Kringelbach, Rethinking segregation and integration: Contributions of whole-brain modelling, Nat. Rev. Neurosci. 16 (2015) 430-439.
S. Boccaletti, V. Latora, Y. Moreno, M. Chavez and D. U. Hwang, Complex networks: Structure and dynamics, Phys. Rep. 424 (2006) 175-308.
E. T. Bullmore and D. S. Bassett, Brain graphs: Graphical models of the human brain connectome, Annu. Rev. Clin. Psychol. 7 (2011) 113-140.
G. Ansmann and K. Lehnertz, Surrogate-assisted analysis of weighted functional brain networks, J. Neurosci. Methods 208 (2012) 165-172.
L. D. F. Costa, F. A. Rodrigues, G. Travieso and P. R. V. Boas, Characterization of complex networks: A survey of measurements, Adv. Phys. 56 (2005) 167-242.
M. Rubinov and O. Sporns, Complex network measures of brain connectivity: Uses and interpretations, Neuroimage 52 (2010) 1059-1069.
D. Bonchev and G. A. Buck, in Complexity in Chemistry, Biology, and Ecology, ed. Media, S. S. & B. (Springer, USA, 2007), pp. 191-235. doi: 10. 1007/0-387-25871-X.
D. Watts and S. Strogatz, Collective dynamics of small-world networks, Nature 393 (1998) 440-442.
L. Astolfi et al. Assessing cortical functional connectivity by linear inverse estimation and directed transfer function: Simulations and application to real data, Clin. Neurophysiol. 116 (2005) 920-932.
F. D. V. Fallani et al. Extracting information from cortical connectivity patterns estimated from high resolution EEG recordings?: A theoretical graph approach, Brain Topogr. 19 (2007) 125-136.
M. Ahmadlou, H. Adeli and A. Adeli, Graph theoretical analysis of organization of functional brain networks in ADHD, Clin. EEG Neurosci. 43 (2012) 5-13.
O. Sporns and J. D. Zwi, The small world of the cerebral cortex, Neuroinformatics 2 (2004) 145-162.
M. Chiappalone, A. Vato, L. Berdondini, M. Koudelka-Hep and S. Martinoia, Network dynamics and synchronous activity in cultured cortical neurons, Int. J. Neural Syst. 17 (2007) 87-103.
F. Han, M. Wiercigroch, J.-A. Fang and Z. Wang, Excitement and synchronization of small-world neuronal networks with short-term synaptic plasticity, Int. J. Neural Syst. 21 (2011) 415-425.
P. J. Neefs, E. Steur and H. Nijmeijer, Network complexity and synchronous behavior-An experimental approach, Int. J. Neural Syst. 20 (2010) 233-247.
T. Yamanishi, J.-Q. Liu and H. Nishimura, Modeling fluctuations in default-mode brain network using a spiking neural network, Int. J. Neural Syst. 22 (2012) 1250016.
G. Tononi, G. M. Edelman and O. Sporns, Complexity and coherency: Integrating information in the brain, Trends Cogn. Sci. 2 (1998) 474-484.
M. Ahmadlou, H. Adeli and A. Adeli, New diagnostic EEG markers of the Alzheimer's disease using visibility graph, J. Neural Transm. 117 (2010) 1099-1109.
M. Ahmadlou and H. Adeli, Visibility graph similarity: A new measure of generalized synchronization in coupled dynamic systems, Phys. D Nonlinear Phenom. 241 (2012) 326-332.
B. Machta and J. Machta, Parallel dynamics and computational complexity of network growth models, Phys. Rev. E Stat. Nonlinear Soft Matter Phys. 71 (2005) 1-9.
H. Meyer-Ortmanns, Functional complexity measure for networks, Physica A 337 (2004) 679-690.
J. C. Claussen, Offdiagonal complexity: A computationally quick complexity measure for graphs and networks, Physica A 375 (2007) 365-373.
F. C. Morabito et al. a longitudinal EEG study of Alzheimer's disease progression based on a complex network approach, Int. J. Neural Syst. 25 (2015) 1550005.
K. J. Friston, The disconnection hypothesis, Schizophr. Res. 30 (1998) 115-125.
T. Nakamura, F. G. Hillary and B. B. Biswal, Resting network plasticity following brain injury, PLoS One 4 (2009) e8220.
B. C. M. van Wijk, C. J. Stam and A. Daffertshofer, Comparing brain networks of different size and connectivity density using graph theory, PLoS One 5 (2010) e13701.
J. Gomez-Pilar et al. Novel measure of the weigh distribution balance on the brain network: Graph complexity applied to schizophrenia, Proc. 35th Annual International Conference of the IEEE Engineering in Medicine and Biology Society Conference, IEEE, pp. 700-703 (2016).
C. E. Shannon, A mathematical theory of communication, Bell Syst. Tech. J. 27 (1948) 379-423.
M. T. Martin, A. Plastino and O. A. Rosso, Statistical complexity and disequilibrium, Phys. Lett. a 311 (2003) 126-132.
R. López-Ruiz, H. L. Mancini and X. Calbet, A statistical measure of complexity, Phys. Lett. a 209 (2002) 321-326.
American Psychiatric Association, Diagnostic and Statistical Manual of Mental Disorders, 5th Edition: DSM-5 (American Psychiatric Publishing, Arlington, 2013). doi: 10. 1176/appi. books. 9780890425596. 893619, 87-122.
S. R. Kay, L. A. Opler and J. P. Lindenmayer, The Positive and Negative Syndrome Scale (PANSS): Rationale and standardisation, Br. J. Psychiatry 155 (1989) 59-65.
B. J. Roach and D. H. Mathalon, Event-related EEG time-frequency analysis: An overview of measures and an analysis of early gamma band phase locking in schizophrenia, Schizophr. Bull. 34 (2008) 907-926.
K. Michalopoulos, M. Zervakis, M.-P. Deiber and N. Bourbakis, Classification of EEG single trial microstates using local global graphs and discrete hidden Markov models, Int. J. Neural Syst. 26 (2016) 1650036.
S, Mallat, A Wavelet Tour of Signal Processing, Academic Press, pp. 20-41 (1999). doi: 10. 1016/B978-012466606-1/50004-0
C. S. Herrmann, M. Grigutsch and N. Busch, EEG oscillations and wavelet analysis, in Event-related potentials: A methods Handbook, MIT Press, pp. 1-39 (1999).
C. Tallon-Baudry, O. Bertrand, C. Delpuech and J. Permier, Oscillatory gamma-band (30-70 Hz) activity induced by a visual search task in humans, J. Neurosci. 17 (1997) 722-734.
Z. Sankari, H. Adeli and A. Adeli, Wavelet coherence model for diagnosis of Alzheimer disease, Clin. EEG Neurosci. 43 (2016) 268-278.
E. van Diessen et al. Opportunities and methodological challenges in EEG and MEG resting state functional brain network research, Clin. Neurophysiol. 126 (2015) 1468-1481.
Z. Sankari and H. Adeli, Probabilistic neural networks for diagnosis of Alzheimer' s disease using conventional and wavelet coherence, J. Neurosci. Methods 197 (2011) 165-170.
P. Tewarie, E. van Dellen, A. Hillebrand and C. J. Stam, The minimum spanning tree: An unbiased method for brain network analysis, Neuroimage 104 (2015) 177-188.
J. M. Ford, B. J. Roach, W. O. Faustman and D. H. Mathalon, Synch before you speak: Auditory hallucinations in schizophrenia, Am. J. Psychiatry 164 (2007) 458-466.
E. Bramon, S. Rabe-Hesketh, P. Sham, R. M. Murray and S. Frangou, Meta-analysis of the P300 and P50 waveforms in schizophrenia, Schizophr. Res. 70 (2004) 315-329.
J. Polich, Updating P300: An integrative theory of P3a and P3b, Clin. Neurophysiol. 118 (2007) 2128-2148.
P. Sauseng et al. Theta coupling in the human electroencephalogram during a working memory task, Neurosci. Lett. 354 (2004) 123-126.
A. von Stein, C. Chiang and P. König, Top-down processing mediated by interareal synchronization, Proc. Natl Acad. Sci. USA 97 (2000) 14748-14753.
P. J. Uhlhaas, Dysconnectivity, large-scale networks and neuronal dynamics in schizophrenia. Curr. Opin. Neurobiol. 23 (2013) 283-290.
J. Gomez-Pilar et al. Association between electroencephalographic modulation, psychotic-like experiences and cognitive performance in the general population, Psychiatry Clin. Neurosci. 70 (2016) 286-294.
C. Schmiedt, A. Brand, H. Hildebrandt and C. Basar-Eroglu, Event-related theta oscillations during working memory tasks in patients with schizophrenia and healthy controls, Cogn. Brain Res. 25 (2005) 936-947.
S. Kapur, Psychosis as a state of aberrant salience: A framework linking biology, phenomenology, and pharmacology in schizophrenia, Am. J. Psychiatry 160 (2003) 13-23.
K. E. Stephan, K. J. Friston and C. D. Frith, Dysconnection in schizophrenia: From abnormal synaptic plasticity to failures of self-monitoring, Schizophr. Bull. 35 (2009) 509-527.
P. J. Uhlhaas and W. Singer, Abnormal neural oscillations and synchrony in schizophrenia, Nat. Rev. Neurosci. 11 (2010) 100-113.
P. J. Uhlhaas, C. Haenschel, D. Nikolíc and W. Singer, The role of oscillations and synchrony in cortical networks and their putative relevance for the pathophysiology of schizophrenia, Schizophr. Bull. 34 (2008) 927-943.
G. J. Ortega, R. G. Sola and J. Pastor, Complex network analysis of human ECoG data, Neurosci. Lett. 447 (2008) 129-133.
R. C. Prim, Shortest connection networks and some generalizations, Bell Syst. Tech. J. 36 (1957) 1389-1401.
A. Fortino, A. Zalesky and E. Bullmore, Fundamentals of Brain Network Analysis (Academic Press, 2016) 430.
E. Bullmore and O. Sporns, Complex brain networks: Graph theoretical analysis of structural and functional systems, Nat. Rev. Neurosci. 10 (2009) 186-198.
M. Rubinov et al. Small-world properties of nonlinear brain activity in schizophrenia, Hum. Brain Mapp. 30 (2009) 403-416.
E. Pachou et al. Working memory in schizophrenia: An EEG study using power spectrum and coherence analysis to estimate cortical activation and network behavior, Brain Topogr. 21 (2008) 128-137.
V. Molina and J. A. Blanco, A proposal for reframing schizophrenia research, J. Nervous Mental Illness 201 (2013) 744-752.
D. S. Bassett and E. Bullmore, Small-world brain networks, The Neuroscientist 12 (2006) 512-523.
M. Rubinov et al. Small-world properties of nonlinear brain activity in schizophrenia, Hum. Brain Mapp. 30 (2009) 403-416.
R. Bruña et al. Analysis of spontaneous MEG activity in mild cognitive impairment and Alzheimer's disease using spectral entropies and statistical complexity measures, J. Neural Eng. 9 (2012) 36007-1-36007-14.
P. L. Nunez et al. EEG coherency I: Statistics, reference electrode, volume conduction, Laplacians, cortical imaging, and interpretation at multiple scales, Electroencephalogr. Clin. Neurophysiol. 103 (1997) 499-515.