* 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.
Int J Neural Syst. 2018 Feb;28(1):1750032. doi: 10.1142/S0129065717500320. Epub 2017 May 23.
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.
Shannon 图复杂度（SGC）。该度量方法专门针对加权图开发，但也可应用于二值图。所提出的复杂度度量旨在捕捉系统的两个性质之间的相互作用：“信息”（通过香农熵计算得出）和系统的“有序性”（通过非平衡度量估计得出）。SGC 的基本思想是，复杂的图应该在上述两个性质之间保持平衡，这可以通过边缘权重分布来衡量。在本研究中，使用了四个合成图数据集和一个由对照组和精神分裂症患者的脑电图（EEG）记录组成的真实数据集来评估 SGC。将 SGC 与图密度（GD）进行了比较，GD 是用于评估图复杂度的经典度量方法。我们的结果表明，SGC 与 GD 不变，与节点度分布无关。此外，对于[Formula: see text]，其随图大小[Formula: see text]的变化接近零。真实数据集的结果表明，在认知处理过程中，对照组和精神分裂症患者的权重分布平衡都有所增加，尽管这些变化对对照组更为明显。我们的研究结果表明，SGC 不需要与通过替代过程构建的零假设网络进行比较。此外，真实数据集上的 SGC 结果表明，精神分裂症与大脑网络次级途径相关的大脑动态重新组织能力缺陷有关。
