Predictability of temporal networks quantified by an entropy-rate-based framework

Network or graph is a mathematical description of the internal structure between components in a complex system, such as connections between neurons, interactions between proteins, contacts between individuals in a crowd, and interactions between users in online social platform. The links in most real networks change over time, and such networks are often called temporal networks. The temporality of links encodes the ordering and causality of interactions between nodes and has a profound effect on neural network function, disease propagation, information aggregation and recommendation, emergence of cooperative behavior, and network controllability. More and more researches have focuses on mining the patterns in a temporal network and predicting its future evolution, using machine learning techniques, especially graph neural networks. However, how to quantify the predictability limit of a temporal network, i.e. the limit that no algorithm can go beyond, is still an open question.

Recently, a research team led by Xianbin Cao with Beihang University, Beijing, and Gang Yan at Tongji University, Shanghai, published a paper entitled Predictability of real temporal networks in National Science Review and proposed a framework for quantifying the predictability of temporal networks based on the entropy rate of random fields.

The authors mapped any given network to a temporality-topology matrix, and then extended the classic entropy rate calculation (that is only applicable to square matrices) to arbitrary matrices through regression operators. The significant advantages of this temporal-topological predictability were validated in two typical models of temporal networks. Applying the method to calculate the predictability of 18 real networks, the authors found that in different types of real networks, the contributions of topology and temporality to network predictability are significantly variable; Although the theoretical baseline and difficulty of temporal-topological predictability are much higher than that of one-dimensional time series, the temporal-topological predictabilities of most real networks are still higher than that of time series.

The predictability limit calculated in this research is an intrinsic property of temporal networks, i.e. is independent of any predictive algorithm, hence it can also be used to measure the possible space of improving predictive algorithms. The authors examined three widely used predictive algorithms and found that the performance of these algorithms is significantly lower than the predictive limits in most real networks, suggesting the necessity of new predictive algorithms that take into account both temporal and topological features of networks.