Towards understanding the dynamics of complex networks: An entropic and Markovian view

How do complex networks evolve? Is there a mathematically rigorous approach to naturally capture the microscopic behaviors of network dynamics and yet it can still lead to tractable analysis of the marcoscopic behaviors in large-scale complex networks? Aiming to obtain a fundamental understanding of network dynamics, we study network evolution from an entropic and Markovian perspective. Specifically, we first take a network entropy maximization (NEM) view to examine network steady state characteristics, in terms of degree distributions, and explore the underlying rationale connecting network entropy and widely observed phenomena, such as power law degree distributions, exponential degree distributions and Weibull degree distributions. Next, to capture the microscopic behaviors of network dynamics, we develop a two timescale Markov model where link generation and deletion takes place on a smaller timescale and new node arrivals (i.e., the network size grows) occur on a larger timescale. This two timescale model provides a natural platform to study both microscopic and macroscopic behaviors of network dynamics. Indeed, the corresponding graph dynamics offers a general framework towards understanding many transient network characteristics, such as network densification, which remain not well understood.