License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SAND.2023.8
URN: urn:nbn:de:0030-drops-179443
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17944/
Go to the corresponding LIPIcs Volume Portal

Bridonneau, Vincent ; Guinand, Frédéric ; Pigné, Yoann

Dynamic Graphs Generators Analysis: An Illustrative Case Study

pdf-format:
LIPIcs-SAND-2023-8.pdf (0.9 MB)

Abstract

In this work, we investigate the analysis of generators for dynamic graphs, which are defined as graphs whose topology changes over time. We focus on generated graphs whose orders are neither growing nor constant along time. We introduce a novel concept, called "sustainability," to qualify the long-term evolution of dynamic graphs. A dynamic graph is considered sustainable if its evolution does not result in a static, empty, or periodic graph. To measure the dynamics of the sets of vertices and edges, we propose a metric, named "Nervousness," which is derived from the Jaccard distance. As an illustration of how the analysis can be conducted, we design a parametrized generator, named D3G3 (Degree-Driven Dynamic Geometric Graphs Generator), that generates dynamic graph instances from an initial geometric graph. The evolution of these instances is driven by two rules that operate on the vertices based on their degree. By varying the parameters of the generator, different properties of the dynamic graphs can be produced. Our results show that in order to ascertain the sustainability of the generated dynamic graphs, it is necessary to study both the evolution of the order and the Nervousness for a given set of parameters.

BibTeX - Entry

@InProceedings{bridonneau_et_al:LIPIcs.SAND.2023.8,
  author =	{Bridonneau, Vincent and Guinand, Fr\'{e}d\'{e}ric and Pign\'{e}, Yoann},
  title =	{{Dynamic Graphs Generators Analysis: An Illustrative Case Study}},
  booktitle =	{2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)},
  pages =	{8:1--8:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-275-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{257},
  editor =	{Doty, David and Spirakis, Paul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17944},
  URN =		{urn:nbn:de:0030-drops-179443},
  doi =		{10.4230/LIPIcs.SAND.2023.8},
  annote =	{Keywords: Dynamic Graphs, Graph Generation, Graph Properties, Evolutionary models}
}

Keywords: Dynamic Graphs, Graph Generation, Graph Properties, Evolutionary models
Collection: 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)
Issue Date: 2023
Date of publication: 12.06.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI