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

Predictability of temporal networks quantified by an entropy-rate-based framework
Quantifying the predictability of a temporal network. Credit: Science China Press

Networks or graphs are mathematical descriptions 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 platforms. 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. Increasing research has focused 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 titled "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 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 limit calculated in this research is an intrinsic property of temporal networks, i.e. is independent of any predictive , 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.

More information: Disheng Tang et al, Predictability of real temporal networks, National Science Review (2020). DOI: 10.1093/nsr/nwaa015

Citation: Predictability of temporal networks quantified by an entropy-rate-based framework (2020, April 15) retrieved 26 May 2024 from
This document is subject to copyright. Apart from any fair dealing for the purpose of private study or research, no part may be reproduced without the written permission. The content is provided for information purposes only.

Explore further

Study reveals a delicate dance of dynamic changes in the conscious brain


Feedback to editors