An Information-Theoretic Analysis on Temporal Graph Evolution

In this paper, we present a novel model termed Network Evolution Chains for simulating the temporal dynamics of networks. Our model's design is tailored to enable comprehensive analysis through information theory. We establish that this model creates a stationary and ergodic stochastic process, thus facilitating the application of the asymptotic equipartition property. This breakthrough paves the way for a thorough information-theoretic investigation into network behavior, encompassing the definition of typical sequences, future state prediction, and beyond.