Multi-Server Multi-Function Distributed Computation.

The work here studies the communication cost for a multi-server multi-task distributed computation framework, as well as for a broad class of functions and data statistics. Considering the framework where a user seeks the computation of multiple complex (conceivably non-linear) tasks from a set of distributed servers, we establish the communication cost upper bounds for a variety of data statistics, function classes, and data placements across the servers. To do so, we proceed to apply, for the first time here, Körner's characteristic graph approach-which is known to capture the structural properties of data and functions-to the promising framework of multi-server multi-task distributed computing. Going beyond the general expressions, and in order to offer clearer insight, we also consider the well-known scenario of cyclic dataset placement and linearly separable functions over the binary field, in which case, our approach exhibits considerable gains over the state of the art. Similar gains are identified for the case of multi-linear functions.

Graph Multi-Scale Permutation Entropy for Bearing Fault Diagnosis.

Bearing faults are one kind of primary failure in rotatory machines. To avoid economic loss and casualties, it is important to diagnose bearing faults accurately. Vibration-based monitoring technology is widely used to detect bearing faults. Graph signal processing methods promising for the extraction of the fault features of bearings. In this work, graph multi-scale permutation entropy (MPEG) is proposed for bearing fault diagnosis. In the proposed method, the vibration signal is first transformed into a visibility graph. Secondly, a graph coarsening method is used to generate coarse graphs with different reduced sizes. Thirdly, the graph's permutation entropy is calculated to obtain bearing fault features. Finally, a support vector machine (SVM) is applied for fault feature classification. To verify the effectiveness of the proposed method, open-source and laboratory data are used to compare conventional entropies and other graph entropies. Experimental results show that the proposed method has higher accuracy and better robustness and de-noising ability.

Explanatory Change Detection in Financial Markets by Graph-Based Entropy and Inter-Domain Linkage.

In this study, we analyzed structural changes in financial markets under COVID-19 to support investors' investment decisions. Because an explanation of these changes is necessary to respond appropriately to said changes and prepare for similar major changes in the future, we visualized the financial market as a graph. The hypothesis was based on expertise in the financial market, and the graph was analyzed from a detailed perspective by dividing the graph into domains. We also designed an original change-detection indicator based on the structure of the graph. The results showed that the original indicator was more effective than the comparison method in terms of both the speed of response and accuracy. Explanatory change detection of this method using graphs and domains allowed investors to consider specific strategies.

Entropy-Based Graph Clustering of PPI Networks for Predicting Overlapping Functional Modules of Proteins.

Functional modules can be predicted using genome-wide protein-protein interactions (PPIs) from a systematic perspective. Various graph clustering algorithms have been applied to PPI networks for this task. In particular, the detection of overlapping clusters is necessary because a protein is involved in multiple functions under different conditions. graph entropy (GE) is a novel metric to assess the quality of clusters in a large, complex network. In this study, the unweighted and weighted GE algorithm is evaluated to prove the validity of predicting function modules. To measure clustering accuracy, the clustering results are compared to protein complexes and Gene Ontology (GO) annotations as references. We demonstrate that the GE algorithm is more accurate in overlapping clusters than the other competitive methods. Moreover, we confirm the biological feasibility of the proteins that occur most frequently in the set of identified clusters. Finally, novel proteins for the additional annotation of GO terms are revealed.

Low Entropy Sub-Networks Prevent the Integration of Metabolomic and Transcriptomic Data.

The constantly and rapidly increasing amount of the biological data gained from many different high-throughput experiments opens up new possibilities for data- and model-driven inference. Yet, alongside, emerges a problem of risks related to data integration techniques. The latter are not so widely taken account of. Especially, the approaches based on the flux balance analysis (FBA) are sensitive to the structure of a metabolic network for which the low-entropy clusters can prevent the inference from the activity of the metabolic reactions. In the following article, we set forth problems that may arise during the integration of metabolomic data with gene expression datasets. We analyze common pitfalls, provide their possible solutions, and exemplify them by a case study of the renal cell carcinoma (RCC). Using the proposed approach we provide a metabolic description of the known morphological RCC subtypes and suggest a possible existence of the poor-prognosis cluster of patients, which are commonly characterized by the low activity of the drug transporting enzymes crucial in the chemotherapy. This discovery suits and extends the already known poor-prognosis characteristics of RCC. Finally, the goal of this work is also to point out the problem that arises from the integration of high-throughput data with the inherently nonuniform, manually curated low-throughput data. In such cases, the over-represented information may potentially overshadow the non-trivial discoveries.

On Properties of Distance-Based Entropies on Fullerene Graphs.

In this paper, we study several distance-based entropy measures on fullerene graphs. These include the topological information content of a graph I a ( G ) , a degree-based entropy measure, the eccentric-entropy I f σ ( G ) , the Hosoya entropy H ( G ) and, finally, the radial centric information entropy H e c c . We compare these measures on two infinite classes of fullerene graphs denoted by A 12 n + 4 and B 12 n + 6 . We have chosen these measures as they are easily computable and capture meaningful graph properties. To demonstrate the utility of these measures, we investigate the Pearson correlation between them on the fullerene graphs.

Relating Vertex and Global Graph Entropy in Randomly Generated Graphs.

Combinatoric measures of entropy capture the complexity of a graph but rely upon the calculation of its independent sets, or collections of non-adjacent vertices. This decomposition of the vertex set is a known NP-Complete problem and for most real world graphs is an inaccessible calculation. Recent work by Dehmer et al. and Tee et al. identified a number of vertex level measures that do not suffer from this pathological computational complexity, but that can be shown to be effective at quantifying graph complexity. In this paper, we consider whether these local measures are fundamentally equivalent to global entropy measures. Specifically, we investigate the existence of a correlation between vertex level and global measures of entropy for a narrow subset of random graphs. We use the greedy algorithm approximation for calculating the chromatic information and therefore Körner entropy. We are able to demonstrate strong correlation for this subset of graphs and outline how this may arise theoretically.

Calculation of the Connected Dominating Set Considering Vertex Importance Metrics.

The computation of a set constituted by few vertices to define a virtual backbone supporting information interchange is a problem that arises in many areas when analysing networks of different natures, like wireless, brain, or social networks. Recent papers propose obtaining such a set of vertices by computing the connected dominating set (CDS) of a graph. In recent works, the CDS has been obtained by considering that all vertices exhibit similar characteristics. However, that assumption is not valid for complex networks in which their vertices can play different roles. Therefore, we propose finding the CDS by taking into account several metrics which measure the importance of each network vertex e.g., error probability, entropy, or entropy variation (EV).

Virtual Network Embedding Based on Graph Entropy.

For embedding virtual networks into a large scale substrate network, a massive amount of time is needed to search the resource space even if the scale of the virtual network is small. The complexity of searching the candidate resource will be reduced if candidates in substrate network can be located in a group of particularly matched areas, in which the resource distribution and communication structure of the substrate network exhibit a maximal similarity with the objective virtual network. This work proposes to discover the optimally suitable resource in a substrate network corresponding to the objective virtual network through comparison of their graph entropies. Aiming for this, the substrate network is divided into substructures referring to the importance of nodes in it, and the entropies of these substructures are calculated. The virtual network will be embedded preferentially into the substructure with the closest entropy if the substrate resource satisfies the demand of the virtual network. The experimental results validate that the efficiency of virtual network embedding can be improved through our proposal. Simultaneously, the quality of embedding has been guaranteed without significant degradation.

Seizure detection from multi-channel EEG using entropy-based dynamic graph embedding.

An epileptic seizure is a chronic disease with sudden abnormal discharge of brain neurons, which leads to transient brain dysfunction. To detect epileptic seizures, we propose a novel idea based on a dynamic graph embedding model. The dynamic graph is built by identifying the correlation among the multi-channel EEG signals. Graph entropy measurement is exploited to calculate the similarity among the graph at each time interval and construct the graph embedding space. Since the abnormal electrical brain activity causes the epileptic seizure, the graph entropy during the seizure time interval is different from other time intervals. Therefore, we propose an entropy-based dynamic graph embedding model to cluster the graphs, and the graphs with epileptic seizures are discriminated. We applied the proposed approach to the Children Hospital Boston-Massachusetts Institute of Technology Scalp EEG database. The results have shown that the proposed approach outperformed the baselines by 1.4% with respect to accuracy.

Treatment Trajectories Graph Compression Algorithm Based on Cliques.

Learning treatment methods and disease progression is significant part of medicine. Graph representation of data provides wide area for visualization and optimization of structure. Present work is dedicated to suggest method of data processing for increasing information interpretability. Graph compression algorithm based on maximum clique search is applied to data set with acute coronary syndrome treatment trajectories. Results of compression are studied using graph entropy measures.

scGET: Predicting Cell Fate Transition During Early Embryonic Development by Single-cell Graph Entropy.

During early embryonic development, cell fate commitment represents a critical transition or "tipping point" of embryonic differentiation, at which there is a drastic and qualitative shift of the cell populations. In this study, we presented a computational approach, scGET, to explore the gene-gene associations based on single-cell RNA sequencing (scRNA-seq) data for critical transition prediction. Specifically, by transforming the gene expression data to the local network entropy, the single-cell graph entropy (SGE) value quantitatively characterizes the stability and criticality of gene regulatory networks among cell populations and thus can be employed to detect the critical signal of cell fate or lineage commitment at the single-cell level. Being applied to five scRNA-seq datasets of embryonic differentiation, scGET accurately predicts all the impending cell fate transitions. After identifying the "dark genes" that are non-differentially expressed genes but sensitive to the SGE value, the underlying signaling mechanisms were revealed, suggesting that the synergy of dark genes and their downstream targets may play a key role in various cell development processes.The application in all five datasets demonstrates the effectiveness of scGET in analyzing scRNA-seq data from a network perspective and its potential to track the dynamics of cell differentiation. The source code of scGET is accessible at https://github.com/zhongjiayuna/scGET_Project.

Sub-graph entropy based network approaches for classifying adolescent obsessive-compulsive disorder from resting-state functional MRI.

This paper presents a novel approach for classifying obsessive-compulsive disorder (OCD) in adolescents from resting-state fMRI data. Currently, the state-of-the-art for diagnosing OCD in youth involves interviews with adolescent patients and their parents by an experienced clinician, symptom rating scales based on Diagnostic and Statistical Manual of Mental Disorders (DSM), and behavioral observation. Discovering signal processing and network-based biomarkers from functional magnetic resonance imaging (fMRI) scans of patients has the potential to assist clinicians in their diagnostic assessments of adolescents suffering from OCD. This paper investigates the clinical diagnostic utility of a set of univariate, bivariate and multivariate features extracted from resting-state fMRI using an information-theoretic approach in 15 adolescents with OCD and 13 matched healthy controls. Results indicate that an information-theoretic approach based on sub-graph entropy is capable of classifying OCD vs. healthy subjects with high accuracy. Mean time-series were extracted from 85 brain regions and were used to calculate Shannon wavelet entropy, Pearson correlation matrix, network features and sub-graph entropy. In addition, two special cases of sub-graph entropy, namely node and edge entropy, were investigated to identify important brain regions and edges from OCD patients. A leave-one-out cross-validation method was used for the final predictor performance. The proposed methodology using differential sub-graph (edge) entropy achieved an accuracy of 0.89 with specificity 1 and sensitivity 0.80 using leave-one-out cross-validation with in-fold feature ranking and selection. The high classification accuracy indicates the predictive power of the sub-network as well as edge entropy metric.

On TD-WGcluster: Theoretical Foundations and Guidelines for the User.

We review the TD-WGcluster (time delayed weighted edge clustering) software integrating static interaction networks with time series data in order to detect modules of nodes between which the information flows at similar time delays and intensities. The software has represented an advancement of the state of the art in the software for the identification of connected components due to its peculiarity of dealing with direct and weighted graphs, where the attributes of the physical entities represented by nodes vary over time. This chapter aims to deepen those theoretical aspects of the clustering model implemented by TD-WGcluster that may be of greater interest to the user. We show the instructions necessary to run the software through some exploratory cases and comment on the results obtained.

An efficient strategy for identifying cancer-related key genes based on graph entropy.

Gene networks are beneficial to identify functional genes that are highly relevant to clinical outcomes. Most of the current methods require information about the interaction of genes or proteins to construct genetic network connection. However, the conclusion of these methods may be bias because of the current incompleteness of human interactome. In this paper, we propose an efficient strategy to use gene expression data and gene mutation data for identifying cancer-related key genes based on graph entropy (iKGGE). Firstly, we construct a gene network using only gene expression data based on the sparse inverse covariance matrix, then, cluster genes use the algorithm of parallel maximal cliques for quickly obtaining a series of subgraphs, and at last, we introduce a novel metric that combine graph entropy and the influence of upstream gene mutations information to measure the impact factors of genes. Testing of the three available cancer datasets shows that our strategy can effectively extract key genes that may play distinct roles in tumorigenesis, and the cancer patient risk groups are well predicted based on key genes.

Epileptic seizure detection in EEGs signals based on the weighted visibility graph entropy.

PURPOSE: Epileptic seizure detection has been a complex task for both researchers and specialist in that the assessment of epilepsy is difficult because, electroencephalogram (EEG) signals are chaotic and non-stationary. METHOD: This paper proposes a new method based on weighted visibility graph entropy (WVGE) to identify seizure from EEG signals. Single channel EEG signals are mapped onto the WVGs and WVGEs are calculated from these WVGs. Then some features are extracted of WVGEs and given to classifiers to investigate the performance of these features to classify the brain signals into three groups of normal (healthy), seizure free (interictal) and during a seizure (ictal) groups. Four popular classifiers namely Support Vector Machine (SVM), K-Nearest Neighbor (KNN), Decision tree (DT) and, Naïve Bayes (NB) are used in this work. RESULT: Experimental results show that the proposed method can classify normal, ictal and interictal groups with a high accuracy of 97%. CONCLUSIONS: This high accuracy index, which is obtained using just three features, is higher than those obtained by several previous works in which more nonlinear features were employed. Also, our method is fast and easy and may be helpful in different applications of automatic seizure detection such as online epileptic seizure detection.

Analysis of alcoholic EEG signals based on horizontal visibility graph entropy.

This paper proposes a novel horizontal visibility graph entropy (HVGE) approach to evaluate EEG signals from alcoholic subjects and controlled drinkers and compare with a sample entropy (SaE) method. Firstly, HVGEs and SaEs are extracted from 1,200 recordings of biomedical signals, respectively. A statistical analysis method is employed to choose the optimal channels to identify the abnormalities in alcoholics. Five group channels are selected and forwarded to a K-Nearest Neighbour (K-NN) and a support vector machine (SVM) to conduct classification, respectively. The experimental results show that the HVGEs associated with left hemisphere, [Formula: see text]1, [Formula: see text]3 and FC5 electrodes, of alcoholics are significantly abnormal. The accuracy of classification with 10-fold cross-validation is 87.5 [Formula: see text] with about three HVGE features. By using just optimal 13-dimension HVGE features, the accuracy is 95.8 [Formula: see text]. In contrast, SaE features associated cannot identify the left hemisphere disorder for alcoholism and the maximum classification ratio based on SaE is just 95.2 [Formula: see text] even using all channel signals. These results demonstrate that the HVGE method is a promising approach for alcoholism identification by EEG signals.