This paper presents a taxonomy and overview of approaches to the measurement of graph and network complexity. The taxonomy distinguishes between deterministic (e.g., Kolmogorov complexity) and probabilistic approaches with a view to placing entropy-based probabilistic measurement in context. Entropy-based measurement is the main focus of the paper. Relationships between the different entropy functions used to measure complexity are examined; and intrinsic (e.g., classical measures) and extrinsic (e.g., Körner entropy) variants of entropy-based models are discussed in some detail.

Accurate detection of anomalies in multivariate time series data has attracted much attention due to its importance in a wide range of applications. Since it is difficult to obtain accurately labeled data, many unsupervised anomaly detection algorithms for multivariate time series data have been developed. However, building such a system is challenging since it requires capturing temporal dependencies in each time series and must also encode the inter-correlations between different pairs of time series. To meet this challenge, we propose a Multi Scale Convolutional Variational Autoencoder (MSCVAE) to detect anomalies in multivariate time series data. Firstly, multi scale attribute matrices are constructed from multivariate time series to characterize multiple levels of the system states at different time steps. Then, given the attribute matrices, a convolutional variational autoencoder is employed to generate reconstructed attribute matrices, and also an attention-based ConvLSTM network is used to capture the temporal patterns. In addition, a new ERR-based threshold setting strategy is developed to optimize anomaly detection performance instead of relying on the traditional ROC-based threshold setting strategy with an imbalanced dataset. Finally, the proposed framework is assessed by means of experiments on four datasets. The experimental results show that our proposed framework is superior to competing algorithms in terms of model performance and robustness, demonstrating that our model is effective in detecting anomalies in multivariate time series.

Research on the structural complexity of networks has produced many useful results in graph theory and applied disciplines such as engineering and data analysis. This paper is intended as a further contribution to this area of research. Here we focus on measures designed to compare graphs with respect to symmetry. We do this by means of a novel characteristic of a graph G, namely an “orbit polynomial." A typical term of this univariate polynomial is of the form czn, where c is the number of orbits of size n of the automorphism group of G. Subtracting the orbit polynomial from 1 results in another polynomial that has a unique positive root, which can serve as a relative measure of the symmetry of a graph. The magnitude of this root is indicative of symmetry and can thus be used to compare graphs with respect to that property. In what follows, we will prove several inequalities on the unique positive roots of orbit polynomials corresponding to different graphs, thus showing differences in symmetry. In addition, we present numerical results relating to several classes of graphs for the purpose of comparing the new symmetry measure with existing ones. Finally, it is applied to a set of isomers of the chemical compound adamantane C10H16. We believe that the measure can be quite useful for tackling applications in chemistry, bioinformatics, and structure-oriented drug design.

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}_{\sigma }(G)$ , the Hosoya entropy $H(G)$ and, finally, the radial centric information entropy $H_{ecc}$ . We compare these measures on two infinite classes of fullerene graphs denoted by $A_{12n+4}$ and $B_{12n+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.

This paper demonstrates properties of Hosoya entropy, a quantitative measure of graph complexity based on a decomposition of the vertices linked to partial Hosoya polynomials. Connections between the information content of a graph and Hosoya entropy are established, and the special case of Hosoya entropy of trees is investigated.