%0 Generic %1 Casteigts2010 %A Casteigts, Arnaud %A Flocchini, Paola %A Quattrociocchi, Walter %A Santoro, Nicola %D 2010 %K dynamic evolving interaction network structures %T Time-Varying Graphs and Dynamic Networks %U http://arxiv.org/abs/1012.0009 %X 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, 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 can be viewed as fragments of a larger formal description of this universe. The main contribution of this paper is to integrate the existing partial models proposed in the literature into a unified framework, which we call TVG (for time-varying graphs). 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. As part of the framework definition, we identify a hierarchy of classes of TVGs, defined with respects to basic properties to which correspond necessary conditions and impossibility results for basic computations; thus the inclusion relationship between classes implies the transfer of feasibility results to an included class and of impossibility results to an including class. This paper is a first step towards the development and analysis of the TVG framework, and its use in the exploration of the universe of dynamic networks.

@misc{Casteigts2010, abstract = { 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, 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 can be viewed as fragments of a larger formal description of this universe. The main contribution of this paper is to integrate the existing partial models proposed in the literature into a unified framework, which we call TVG (for time-varying graphs). 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. As part of the framework definition, we identify a hierarchy of classes of TVGs, defined with respects to basic properties to which correspond necessary conditions and impossibility results for basic computations; thus the inclusion relationship between classes implies the transfer of feasibility results to an included class and of impossibility results to an including class. This paper is a first step towards the development and analysis of the TVG framework, and its use in the exploration of the universe of dynamic networks. }, added-at = {2010-12-19T11:43:03.000+0100}, author = {Casteigts, Arnaud and Flocchini, Paola and Quattrociocchi, Walter and Santoro, Nicola}, biburl = {https://www.bibsonomy.org/bibtex/2e4fc27313c8e0ebf11d3abd7768de023/demiurgo}, description = {Time-Varying Graphs and Dynamic Networks}, interhash = {a0583edcb76873a7c3283dc87ee8a9c6}, intrahash = {e4fc27313c8e0ebf11d3abd7768de023}, keywords = {dynamic evolving interaction network structures}, note = {cite arxiv:1012.0009 Comment: 10 pages two-columns, 8 figures}, timestamp = {2010-12-19T11:43:03.000+0100}, title = {Time-Varying Graphs and Dynamic Networks}, url = {http://arxiv.org/abs/1012.0009}, year = 2010 }