A Time-Dependent Graph Model for Describing Evolving Networks

  • Take-Yuki Nagao Advanced Institute of Industrial Technology
  • Antoine Bossard Advanced Institute of Industrial Technology
Keywords: Dynamic graphs, load balancing, time-dependent graphs, time-evolution


A growing network like the Internet has a characteristic that the number of nodes is indefinite and may change with time. This characteristic makes it difficult to understand quantitatively and qualitatively how data are transferred among computers. In this article, we propose TFGM, which is a dynamic graph model to describe data transfer inside a network of indefinite size. The network is assumed to be time-dependent and allowed to change by discrete events. TFGM enables us to depict how data are sent from a server and to clients by using data densities, which depend continuously on time. As an application, fairness of load balancing is formulated and theorems are proven concerning an upper bound for the number of simultaneous clients for periodic polling.


G. B. Folland, Real Analysis, John Wiley & Sons, 1999.

C. Henke, C. Schmoll, and T. Zseby, “Empirical evaluation of hash functions for multipoint measurements,” SIGCOMM Computer Communication Review, ACM, 2008; doi:10.1145/1384609.1384614.

F. Harary and G. Gupta, “Dynamic graph models,” Mathematical and Computer Modelling, vol. 25, no. 7, 1997, pp. 79–87.

T. Nagao, “A method to estimate data volume of awareness information using a continuous time model,” Bulletin of Advanced Institute of Industrial Technology, vol. 3, 2010, pp. 183–188.

Technical Papers (Information and Communication Technology)