Recent developments in quantitative graph theory: information inequalities for networks

In this article, we tackle a challenging problem in quantitative graph theory. We establish relations between graph entropy measures representing the structural information content of networks. In particular, we prove formal relations between quantitative network measures based on Shannon's entropy to study the relatedness of those measures. In order to establish such information inequalities for graphs, we focus on graph entropy measures based on information functionals. To prove such relations, we use known graph classes whose instances have been proven useful in various scientific areas. Our results extend the foregoing work on information inequalities for graphs.     

Towards a unifying approach to diversity measures: bridging the gap between the Shannon entropy and Rao's quadratic index

The diversity of a species assemblage has been studied extensively for many decades in relation to its possible connection with ecosystem functioning and organization. In this view most diversity measures, such as Shannon's entropy, rely upon information theory as a basis for the quantification of diversity. Also, traditional diversity measures are computed using species relative abundances and cannot account for the ecological differences between species. Rao first proposed a diversity index, termed quadratic diversity (Q) that incorporates both species relative abundances and pairwise distances between species. Quadratic diversity is traditionally defined as the expected distance between two randomly selected individuals. In this paper, we show that quadratic diversity can be interpreted as the expected conflict among the species of a given assemblage. From this unusual interpretation, it naturally follows that Rao's Q can be related to the Shannon entropy through a generalized version of the Tsallis parametric entropy.     

Some measures of information arising in statistical games

This paper discusses some measures of information which naturally arise in the context of statistical games (games against nature). Some useful inequalities are proven relating the entropy to the value of information provided by experiments. Two other measures, based on the notion of a metric as informational distance and that of a diameter value are also discussed.     

A comparative study of pattern synchronization detection between neural signals using different cross-entropy measures

Cross-approximate entropy (X-ApEn) and cross-sample entropy (X-SampEn) have been employed as bivariate pattern synchronization measures for characterizing interdependencies between neural signals. In this study, we proposed a new measure, cross-fuzzy entropy (X-FuzzyEn), to describe the synchronicity of patterns. The performances of three statistics were first quantitatively tested using five different coupled systems including both deterministic and stochastic models, i.e., coupled broadband noises, Lorenz–Lorenz, Rossler–Rossler, Rossler–Lorenz, and neural mass model. All the measures were compared with each other with respect to their ability to distinguish between different levels of coupling and their robustness against noise. The three measures were then applied to a real-life problem, pattern synchronization analysis of left and right hemisphere rat electroencephalographic (EEG) signals. Both simulated and real EEG data analysis results showed that the X-FuzzyEn provided an improved evaluation of bivariate series pattern synchronization and could be more conveniently and powerfully applied to different neural dynamical systems contaminated by noise.     

Interrelations of Graph Distance Measures Based on Topological Indices

In this paper, we derive interrelations of graph distance measures by means of inequalities. For this investigation we are using graph distance measures based on topological indices that have not been studied in this context. Specifically, we are using the well-known Wiener index, Randić index, eigenvalue-based quantities and graph entropies. In addition to this analysis, we present results from numerical studies exploring various properties of the measures and aspects of their quality. Our results could find application in chemoinformatics and computational biology where the structural investigation of chemical components and gene networks is currently of great interest.     

Prediction of catalytic residues based on an overlapping amino acid classification

Protein sequence conservation is a powerful and widely used indicator for predicting catalytic residues from enzyme sequences. In order to incorporate amino acid similarity into conservation measures, one attempt is to group amino acids into disjoint sets. In this paper, based on the overlapping amino acids classification proposed by Taylor, we define the relative entropy of Venn diagram (RVD) and RVD2. In large-scale testing, we demonstrate that RVD and RVD2 perform better than many existing conservation measures in identifying catalytic residues, especially than the commonly used relative entropy (RE) and Jensen–Shannon divergence (JSD). To further improve RVD and RVD2, two new conservation measures are obtained by combining them with the classical JSD. Experimental results suggest that these combination measures have excellent performances in identifying catalytic residues.     

Reliability difference between spectral and entropic measures of erector spinae muscle fatigability

This study investigated back muscle fatigability of the erector spinae (ES) muscles during submaximal contractions with the use of surface electromyography (sEMG). It was important to confirm the reliability of measurements for characterizing neuromuscular alterations by establishing the difference between the Shannon (information) entropy and the power spectrum analysis in subjects with low back pain (LBP). The data was collected on two different days, one week apart, and the between-days reliability of these measures was examined. Thirty-two gender-matched subjects completed the modified Sorenson test; 16 of the subjects were female while 16 were male. The entropy of the sEMG signal was more reliable than either the median frequency (MF) or the slope of the MF. The intraclass correlation coefficient (ICC) was higher for the entropy than for the MF slope. The ICC values of entropy for between-day measurements were higher (0.82–0.85) than MF (0.54–0.64) and MF slope (0.26–0.30). The standard errors of measurement (SEM) values for entropy were lower (0.04–0.05) than MF (3.10–3.60) and MF slope (0.03–0.04). The Pearson correlation coefficients of the entropy were significantly higher (0.75–0.77) than those of the MF (0.38–0.47) and the MF slope (0.15–0.18). Therefore, the results of this study indicated that the entropy analysis could provide a reliable measure of muscle fatigability.     

Noise and complexity in human postural control: interpreting the different estimations of entropy

Background

Over the last two decades, various measures of entropy have been used to examine the complexity of human postural control. In general, entropy measures provide information regarding the health, stability and adaptability of the postural system that is not captured when using more traditional analytical techniques. The purpose of this study was to examine how noise, sampling frequency and time series length influence various measures of entropy when applied to human center of pressure (CoP) data, as well as in synthetic signals with known properties. Such a comparison is necessary to interpret data between and within studies that use different entropy measures, equipment, sampling frequencies or data collection durations.

Methods and Findings

The complexity of synthetic signals with known properties and standing CoP data was calculated using Approximate Entropy (ApEn), Sample Entropy (SampEn) and Recurrence Quantification Analysis Entropy (RQAEn). All signals were examined at varying sampling frequencies and with varying amounts of added noise. Additionally, an increment time series of the original CoP data was examined to remove long-range correlations. Of the three measures examined, ApEn was the least robust to sampling frequency and noise manipulations. Additionally, increased noise led to an increase in SampEn, but a decrease in RQAEn. Thus, noise can yield inconsistent results between the various entropy measures. Finally, the differences between the entropy measures were minimized in the increment CoP data, suggesting that long-range correlations should be removed from CoP data prior to calculating entropy.

Conclusions

The various algorithms typically used to quantify the complexity (entropy) of CoP may yield very different results, particularly when sampling frequency and noise are different. The results of this study are discussed within the context of the neural noise and loss of complexity hypotheses.     

Dynamic Approximate Entropy Electroanatomic Maps Detect Rotors in a Simulated Atrial Fibrillation Model

There is evidence that rotors could be drivers that maintain atrial fibrillation. Complex fractionated atrial electrograms have been located in rotor tip areas. However, the concept of electrogram fractionation, defined using time intervals, is still controversial as a tool for locating target sites for ablation. We hypothesize that the fractionation phenomenon is better described using non-linear dynamic measures, such as approximate entropy, and that this tool could be used for locating the rotor tip. The aim of this work has been to determine the relationship between approximate entropy and fractionated electrograms, and to develop a new tool for rotor mapping based on fractionation levels. Two episodes of chronic atrial fibrillation were simulated in a 3D human atrial model, in which rotors were observed. Dynamic approximate entropy maps were calculated using unipolar electrogram signals generated over the whole surface of the 3D atrial model. In addition, we optimized the approximate entropy calculation using two real multi-center databases of fractionated electrogram signals, labeled in 4 levels of fractionation. We found that the values of approximate entropy and the levels of fractionation are positively correlated. This allows the dynamic approximate entropy maps to localize the tips from stable and meandering rotors. Furthermore, we assessed the optimized approximate entropy using bipolar electrograms generated over a vicinity enclosing a rotor, achieving rotor detection. Our results suggest that high approximate entropy values are able to detect a high level of fractionation and to locate rotor tips in simulated atrial fibrillation episodes. We suggest that dynamic approximate entropy maps could become a tool for atrial fibrillation rotor mapping.     

基于替代数据思想的复杂度归一化方法及其在心电信号分析中的应用

基于替代数据(Surrogate)思想的复杂度归一化方法,克服了一般复杂度对信号采样长度与采样频率的敏感性。文章对在生物医学信号复杂度分析中最有潜在应用价值的近似熵和C0复杂度进行了归一化。应用该方法可以有效地反映人体心脏某些病理状态之间的差别。同时,通过比较各种复杂度指标发现,C0复杂度和近似熵对采样长度的敏感性最弱,适用于短数据量的信号分析。     

Complexity of Multi-Dimensional Spontaneous EEG Decreases during Propofol Induced General Anaesthesia

Emerging neural theories of consciousness suggest a correlation between a specific type of neural dynamical complexity and the level of consciousness: When awake and aware, causal interactions between brain regions are both integrated (all regions are to a certain extent connected) and differentiated (there is inhomogeneity and variety in the interactions). In support of this, recent work by Casali et al (2013) has shown that Lempel-Ziv complexity correlates strongly with conscious level, when computed on the EEG response to transcranial magnetic stimulation. Here we investigated complexity of spontaneous high-density EEG data during propofol-induced general anaesthesia. We consider three distinct measures: (i) Lempel-Ziv complexity, which is derived from how compressible the data are; (ii) amplitude coalition entropy, which measures the variability in the constitution of the set of active channels; and (iii) the novel synchrony coalition entropy (SCE), which measures the variability in the constitution of the set of synchronous channels. After some simulations on Kuramoto oscillator models which demonstrate that these measures capture distinct ‘flavours’ of complexity, we show that there is a robustly measurable decrease in the complexity of spontaneous EEG during general anaesthesia.     

Empirical assessment of the relation between ecological connectivity and land complexity based on information-theoretic metrics

Habitat fragmentation and connectivity loss pose significant threats to biodiversity at both local and landscape levels. Strategies to increase ecological connectivity and preserve strong connectivity are important for dealing with the potential threat of habitat degradation. Various metrics have been used to measure (i.e., quantify) landscape composition and configuration in landscape ecology. However, their relationship with ecological connectivity must be understood to interpret landscape patterns comprehensively. In the present study, correlations between ecological connectivity and land complexity are examined based on information-theory metrics. Two primary questions are explored: (1) to what extent are landscape mosaic measures of entropy correlated with ecological connectivity, with landscape gradient-based measures, and with each other? (2) are landscape gradient-based entropy measures correlated with ecological connectivity more than discrete entropy measures? Results show that all information theoretic metrics are statistically significant (p < 0.05) for modelling ecological connectivity. Among categorically-based indices, the relationship between ECI and joint entropy was the most significant, while a generalized additive model indicated that Boltzmann entropy could predict the ecological connectivity index, explaining ∼60% of the variance. Therefore, configurational entropy can be used for improving ecological connectivity models.     

Connections between classical and parametric network entropies

This paper explores relationships between classical and parametric measures of graph (or network) complexity. Classical measures are based on vertex decompositions induced by equivalence relations. Parametric measures, on the other hand, are constructed by using information functions to assign probabilities to the vertices. The inequalities established in this paper relating classical and parametric measures lay a foundation for systematic classification of entropy-based measures of graph complexity.     

Neural net classification of REM sleep based on spectral measures as compared to nonlinear measures

 In various studies the implementation of nonlinear and nonconventional measures has significantly improved EEG (electroencephalogram) analyses as compared to using conventional parameters alone. A neural network algorithm well approved in our laboratory for the automatic recognition of rapid eye movement (REM) sleep was investigated in this regard. Originally based on a broad range of spectral power inputs, we additionally supplied the nonlinear measures of the largest Lyapunov exponent and correlation dimension as well as the nonconventional stochastic measures of spectral entropy and entropy of amplitudes. No improvement in the detection of REM sleep could be achieved by the inclusion of the new measures. The accuracy of the classification was significantly worse, however, when supplied with these variables alone. In view of results demonstrating the efficiency of nonconventional measures in EEG analysis, the benefit appears to depend on the nature of the problem. Received: 10 October 2000 / Accepted in revised form: 26 April 2001     

An information-theoretical measure of taxonomic diversity

Traditional diversity indices are computed from the abundances of species present and are insensitive to taxonomic differences between species. However, a community in which most species belong to the same genus is intuitively less diverse than another community with a similar number of species distributed more evenly between genera. In this paper, we propose an information-theoretical measure of taxonomic diversity that reflects both the abundances and taxonomic distinctness of the species. Unlike previous measures of taxonomic diversity, such as Rao's quadratic entropy, in this new measure the analyzed taxonomic properties are associated with the single species instead of species pairs.     

Reproductive numbers, epidemic spread and control in a community of households

Many of the studies on emerging epidemics (such as SARS and pandemic flu) use mass action models to estimate reproductive numbers and the needed control measures. In reality, transmission patterns are more complex due to the presence of various social networks. One level of complexity can be accommodated by considering a community of households. Our study of transmission dynamics in a community of households emphasizes five types of reproductive numbers for the epidemic spread: household-to-household reproductive number, leaky vaccine-associated reproductive numbers, perfect vaccine reproductive number, growth rate reproductive number, and the individual reproductive number. Each of those carries different information about the transmission dynamics and the required control measures, and often some of those can be estimated from the data while others cannot. Simulations have shown that under certain scenarios there is an ordering for those reproductive numbers. We have proven a number of ordering inequalities under general assumptions about the individual infectiousness profiles. Those inequalities allow, for instance, to estimate the needed vaccine coverage and other control measures without knowing the various transmission parameters in the models. Along the way, we have also shown that in choosing between increasing vaccine efficacy and increasing coverage levels by the same factor, preference should go to efficacy.     

一个基于熵的指数精细定位人类复杂性状位点

近来,一个基于熵的指数被提出用来对人类复杂性状位点进行连锁不平衡定位．这个熵指数比较了患病个体与正常个体或极端样本之间标记基因频率的熵和条件熵．本文基于熵理论,提出了另一个备选指数．这个新的指数比较患病个体与正常个体之间标记基因型频率的熵和条件熵．计算机模拟结果表明本文提出的新指数平行于之前的熵指数．而基于遗传性血色病（hereditary haemochromatosis,HH）数据的分析表明了这个新指数能有效对人类复杂性状位点进行精细定位．     

Expected Shannon Entropy and Shannon Differentiation between Subpopulations for Neutral Genes under the Finite Island Model

Shannon entropy H and related measures are increasingly used in molecular ecology and population genetics because (1) unlike measures based on heterozygosity or allele number, these measures weigh alleles in proportion to their population fraction, thus capturing a previously-ignored aspect of allele frequency distributions that may be important in many applications; (2) these measures connect directly to the rich predictive mathematics of information theory; (3) Shannon entropy is completely additive and has an explicitly hierarchical nature; and (4) Shannon entropy-based differentiation measures obey strong monotonicity properties that heterozygosity-based measures lack. We derive simple new expressions for the expected values of the Shannon entropy of the equilibrium allele distribution at a neutral locus in a single isolated population under two models of mutation: the infinite allele model and the stepwise mutation model. Surprisingly, this complex stochastic system for each model has an entropy expressable as a simple combination of well-known mathematical functions. Moreover, entropy- and heterozygosity-based measures for each model are linked by simple relationships that are shown by simulations to be approximately valid even far from equilibrium. We also identify a bridge between the two models of mutation. We apply our approach to subdivided populations which follow the finite island model, obtaining the Shannon entropy of the equilibrium allele distributions of the subpopulations and of the total population. We also derive the expected mutual information and normalized mutual information (“Shannon differentiation”) between subpopulations at equilibrium, and identify the model parameters that determine them. We apply our measures to data from the common starling (Sturnus vulgaris) in Australia. Our measures provide a test for neutrality that is robust to violations of equilibrium assumptions, as verified on real world data from starlings.     

Compression entropy contributes to risk stratification in patients with cardiomyopathy.

Sudden cardiac death (SCD) is a leading cause of mortality with an incidence of 3 million cases per year worldwide. Therapies for patients who have survived an SCD episode or have a high risk of developing lethal ventricular arrhythmia are well established and depend mainly on risk stratification. In this study we investigated the suitability of the non-linear measure compression entropy (Hc) for improved risk prediction in cardiac patients. We recorded 24-h Holter ECG for 300 patients with congestive heart failure (CHF). During a mean follow-up period of 12 months, 32 patients died due to a cardiac event. Hc depends on the compression parameters window length w and buffer length b, which were optimised by analysing a subgroup of patients. Compression entropies based on the beat-to-beat interval (BBI) were subsequently calculated and compared with standard heartrate variability parameters. Statistical analysis revealed significant differences between high- and low-risk CHF patients in standard HRV measures, as well as compression entropy based on the BBI (cardiac death, p = 0.005; SCD, p = 0.02). In conclusion, the implementation of non-linear compression entropy analysis in multivariate analysis seems to be useful for enhanced risk stratification of cardiac death, especially SCD, in ischaemic cardiomyopathy patients.     

Power-law inter-spike interval distributions infer a conditional maximization of entropy in cortical neurons

The brain is considered to use a relatively small amount of energy for its efficient information processing. Under a severe restriction on the energy consumption, the maximization of mutual information (MMI), which is adequate for designing artificial processing machines, may not suit for the brain. The MMI attempts to send information as accurate as possible and this usually requires a sufficient energy supply for establishing clearly discretized communication bands. Here, we derive an alternative hypothesis for neural code from the neuronal activities recorded juxtacellularly in the sensorimotor cortex of behaving rats. Our hypothesis states that in vivo cortical neurons maximize the entropy of neuronal firing under two constraints, one limiting the energy consumption (as assumed previously) and one restricting the uncertainty in output spike sequences at given firing rate. Thus, the conditional maximization of firing-rate entropy (CMFE) solves a tradeoff between the energy cost and noise in neuronal response. In short, the CMFE sends a rich variety of information through broader communication bands (i.e., widely distributed firing rates) at the cost of accuracy. We demonstrate that the CMFE is reflected in the long-tailed, typically power law, distributions of inter-spike intervals obtained for the majority of recorded neurons. In other words, the power-law tails are more consistent with the CMFE rather than the MMI. Thus, we propose the mathematical principle by which cortical neurons may represent information about synaptic input into their output spike trains.