Predictability of real temporal networks

Disheng Tang; Wenbo Du; Louis Shekhtman; Yijie Wang; Shlomo Havlin; Xianbin Cao; Gang Yan

doi:10.1093/nsr/nwaa015

Predictability of real temporal networks

Natl Sci Rev. 2020 May;7(5):929-937. doi: 10.1093/nsr/nwaa015. Epub 2020 Feb 10.

Authors

Disheng Tang^{1

2

3}, Wenbo Du^{1

3}, Louis Shekhtman⁴, Yijie Wang^{1

3}, Shlomo Havlin⁵, Xianbin Cao^{1

3}, Gang Yan^{2

6

7}

Affiliations

¹ School of Electronic and Information Engineering, Beihang University, Beijing 100191, China.
² School of Physics Science and Engineering, Tongji University, Shanghai 200092, China.
³ National Engineering Laboratory of Big Data Application Technologies of Comprehensive Transportation, Beijing 100191, China.
⁴ Network Science Institute, Northeastern University, Boston, MA 02115, USA.
⁵ Department of Physics, Bar Ilan University, Ramat Gan 5290002, Israel.
⁶ Shanghai Institute of Intelligence Science and Technology, Tongji University, Shanghai 200092, China.
⁷ CAS Center for Excellence in Brain Science and Intelligence Technology, Chinese Academy of Sciences, Shanghai 200031, China.

Abstract

Links in most real networks often change over time. Such temporality of links encodes the ordering and causality of interactions between nodes and has a profound effect on network dynamics and function. Empirical evidence has shown that the temporal nature of links in many real-world networks is not random. Nonetheless, it is challenging to predict temporal link patterns while considering the entanglement between topological and temporal link patterns. Here, we propose an entropy-rate-based framework, based on combined topological-temporal regularities, for quantifying the predictability of any temporal network. We apply our framework on various model networks, demonstrating that it indeed captures the intrinsic topological-temporal regularities whereas previous methods considered only temporal aspects. We also apply our framework on 18 real networks of different types and determine their predictability. Interestingly, we find that, for most real temporal networks, despite the greater complexity of predictability brought by the increase in dimension, the combined topological-temporal predictability is higher than the temporal predictability. Our results demonstrate the necessity for incorporating both temporal and topological aspects of networks in order to improve predictions of dynamical processes.

Keywords: network entropy; predictability; predictive algorithm; temporal network.