Time-varying graphs and dynamic networks

By A. Casteigts, Paola Flocchini, Walter Quattrociocchi, Nicola Santoro. Int. J. Parallel Emergent Distributed Syst., 2010

859 citations recorded by the source corpus.

The past few years have seen intensive research efforts carried out in some apparently unrelated areas of dynamic systems – delay-tolerant networks, opportunistic-mobility networks and social networks – obtaining closely related insights. Indeed, the concepts discovered in these investigations can be viewed as parts of the same conceptual universe, and the formal models proposed so far to express some specific concepts are the components of a larger formal description of this universe. The main contribution of this paper is to integrate the vast collection of concepts, formalisms and results found in the literature into a unified framework, which we call time-varying graphs (TVGs). Using this framework, it is possible to express directly in the same formalism not only the concepts common to all those different areas, but also those specific to each. Based on this definitional work, employing both existing results and original observations, we present a hierarchical classification of TVGs; each class corresponds to a significant property examined in the distributed computing literature. We then examine how TVGs can be used to study the evolution of network properties, and propose different techniques, depending on whether the indicators for these properties are atemporal (as in the majority of existing studies) or temporal. Finally, we briefly discuss the introduction of randomness in TVGs.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/05c24763d5db30c56154080e0e49447fae459f73

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

Citations in the corpus

Foundations and Modeling of Dynamic Networks Using Dynamic Graph Neural Networks: A Survey (2020, background): “oblem [8]. Complex networks which change over time have been referred to, among others, as; dynamic networks [9], [10], temporal networks [2], [11], evolutionary networks [3] or time-varying networks [12]. With models often working only on speciﬁc types of networks, a clear and more detailed termino”
Path Problems in Temporal Graphs (2014, methodology): “Apart from that, there are surveys [1, 8] that cover most of the prior proposed concepts of temporal graphs.”
Modern temporal network theory: a colloquium (2015, background): “especting path between them. Another generalization of distances to temporal networks is to consider the number of contacts in a temporal path. Refs. [24,23] use only this denition, while e.g. Refs. [33,303,38,259] use both. Computing, generalized distances in time from one node to all others is rat”
Community Discovery in Dynamic Networks (2017, neutral): “al., 2013b). 1. Temporal Networks Several formalisms have been proposed to represent evolving networks without loss of information: Temporal Networks (Holme and Saramaki, 2012), Time-Varying Graphs (Casteigts et al., 2012), Interaction Networks (Rossetti et al., 2015), Link Streams and Stream graphs”