Dynamic networks are a complex topic. Not only do they inherit the complexity of static networks (as a particular case) while making obsolete many techniques for these networks; they also happen to be deeply sensitive to specific definitional subtleties, such as strictness (can several consecutive edges be used at the same time instant?), properness (can adjacent edges be present at the same time?) and simpleness (can an edge be present more than once?). These features, it turns out, have a significant impact on the answers to various questions, which is a frequent source of confusion and incomparability among results. In this paper, we explore the impact of these notions, and of their interactions, in a systematic way. Our conclusions show that these aspects really matter. In particular, most of the combinations of the above properties lead to distinct levels of expressivity of a temporal graph in terms of reachability. Then, we advocate the study of an extremely simple model -- happy graphs -- where all these distinctions vanish. Happy graphs suffer from a loss of expressivity; yet, we show that they remain expressive enough to capture (and strengthen) interesting features of general temporal graphs. A number of questions are proposed to motivate the study of these objects further.
翻译:动态网络是一个复杂的主题。 这些特征不仅继承了静态网络的复杂性(作为一个特定案例),同时为这些网络创造了许多过时的技术;它们也碰巧对具体的定义微妙性非常敏感,例如严格性(能够同时使用几个连续边缘? ) 、适当性(能够同时存在相邻边缘? ) 和简单性(能够不止一次存在边缘? ) 。这些特征对各种问题的答案产生了重大影响,而这些问题经常是结果之间混乱和不相容的来源。在本文中,我们以系统的方式探讨这些概念及其相互作用的影响。我们的结论表明,这些方面确实很重要。特别是,上述特性的多数组合导致一个时间图在可及性方面的清晰度。然后,我们主张研究一个非常简单的模型 -- -- 快乐的图表 -- -- 所有的这些区别都消失了。快乐的图表受到表达性的损失;然而,我们表明,这些概念及其相互作用的影响仍然足以表达(和强化一般时间图的有趣特征) 。提出的问题数是用来进一步激励这些研究。