Semi-Markov Graph Dynamics

In this paper, we outline a model of graph (or network) dynamics based on two ingredients. The first ingredient is a Markov chain on the space of possible graphs. The second ingredient is a semi-Markov counting process of renewal type. The model consists in subordinating the Markov chain to the semi-Markov counting process. In simple words, this means that the chain transitions occur at random time instants called epochs. The model is quite rich and its possible connections with algebraic geometry are briefly discussed. Moreover, for the sake of simplicity, we focus on the space of undirected graphs with a fixed number of nodes. However, in an example, we present an interbank market model where it is meaningful to use directed graphs or even weighted graphs.本文提出了一种基于两大核心要素的图（或称网络）动力学模型。第一大要素为定义于全体可能图构成的空间之上的马尔可夫链（Markov chain）；第二大要素为更新型半马尔可夫计数过程（semi-Markov counting process）。该模型通过将马尔可夫链从属至该半马尔可夫计数过程而构建。简言之，这意味着链的状态转移发生于被称为epochs的随机时间节点上。该模型具备丰富的理论内涵，本文还简要探讨了其与代数几何的潜在关联。此外，为简化论述，本文仅聚焦于节点数目固定的无向图空间。不过在示例章节中，本文将展示一款银行间市场模型，该场景下使用有向图乃至加权图均具备实际意义。