Complexity of Weighted Graph

In recent years complexity of the brain structure in healthy and disordered subjects has been studied increasingly. But to the best of the authors’ knowledge, researchers so far have investigated the structural complexity only in the context of two restricted networks known as Small-World and Scale-free networks; whereas other aspects of the structural complexity of brain activities may be affected by aging and neurodegenerative disorders such as the Alzheimer’s disease and autism spectrum disorder. In this study, two general complexity metrics of graphs, Graph Index Complexity and Offdiagonal Complexity are proposed as general measures of complexity, not restricted to SWN only. They are adopted to measure the structural complexity of the weighted graphs instead of the common binary graphs. Fuzzy Synchronization Likelihood is applied to the EEGs and their sub-bands, as a functional connectivity metric of the brain, to construct the functional connectivity graphs. Two applications are used to evaluate the efficacy of the complexity measures: diagnosis of autism and aging, both based on EEG. It was discovered that the Graph Index Complexity of gamma band is discriminative in distinguishing autistic children from non-autistic children. Also, Offdiagonal Complexity of theta band in young subjects was observed to be significantly different than old subjects. This study shows that changes in the structure of functional connectivity of brain in disorders and different healthy states can be revealed by unrestricted metrics of graph complexity. While the applications presented in this paper are based on EEG, the approach is general and can be used with other modalities such as fMRI, MEG, etc. Further, it can be used to study every other neurological and psychiatric disorder.