s12859-017-1677-x.pdf 1,56MB
1000 Titel
  • Clone temporal centrality measures for incomplete sequences of graph snapshots
1000 Autor/in
  1. Foraita, Ronja |
  2. Hanke, Moritz |
1000 Erscheinungsjahr 2017
1000 LeibnizOpen
1000 Publikationstyp
  1. Artikel |
1000 Online veröffentlicht
  • 2017-05-16
1000 Erschienen in
1000 Quellenangabe
  • 18: 261
1000 FRL-Sammlung
1000 Copyrightjahr
  • 2017
1000 Lizenz
1000 Verlagsversion
  • |
  • |
1000 Ergänzendes Material
  • |
1000 Publikationsstatus
1000 Begutachtungsstatus
1000 Sprache der Publikation
1000 Abstract/Summary
  • BACKGROUND: Different phenomena like the spread of a disease, social interactions or the biological relation between genes can be thought of as dynamic networks. These can be represented as a sequence of static graphs (so called graph snapshots). Based on this graph sequences, classical vertex centrality measures like closeness and betweenness centrality have been extended to quantify the importance of single vertices within a dynamic network. An implicit assumption for the calculation of temporal centrality measures is that the graph sequence contains all information about the network dynamics over time. This assumption is unlikely to be justified in many real world applications due to limited access to fully observed network data. Incompletely observed graph sequences lack important information about duration or existence of edges and may result in biased temporal centrality values. RESULTS: To account for this incompleteness, we introduce the idea of extending original temporal centrality metrics by cloning graphs of an incomplete graph sequence. Focusing on temporal betweenness centrality as an example, we show for different simulated scenarios of incomplete graph sequences that our approach improves the accuracy of detecting important vertices in dynamic networks compared to the original methods. An age-related gene expression data set from the human brain illustrates the new measures. Additional results for the temporal closeness centrality based on cloned snapshots support our findings. We further introduce a new algorithm called REN to calculate temporal centrality measures. Its computational effort is linear in the number of snapshots and benefits from sparse or very dense dynamic networks. CONCLUSIONS: We suggest to use clone temporal centrality measures in incomplete graph sequences settings. Compared to approaches that do not compensate for incompleteness our approach will improve the detection rate of important vertices. The proposed REN algorithm allows to calculate (clone) temporal centrality measures even for long snapshot sequences.
1000 Sacherschließung
lokal Shortest temporal path
lokal Centrality measures
lokal Closeness
lokal Betweenness
lokal Dynamic networks
lokal Dynamic graphs
lokal Time varying networks
1000 Fächerklassifikation (DDC)
1000 Liste der Beteiligten
1000 Label
1000 Förderer
  1. Leibniz Association |
1000 Fördernummer
  1. -
1000 Förderprogramm
  1. Open Access Fund
1000 Dateien
1000 Förderung
  1. 1000 joinedFunding-child
    1000 Förderer Leibniz Association |
    1000 Förderprogramm Open Access Fund
    1000 Fördernummer -
1000 Objektart article
1000 Beschrieben durch
1000 @id frl:6403880.rdf
1000 Erstellt am 2017-08-15T10:27:28.339+0200
1000 Erstellt von 25
1000 beschreibt frl:6403880
1000 Bearbeitet von 288
1000 Zuletzt bearbeitet Wed Mar 31 09:40:53 CEST 2021
1000 Objekt bearb. Wed Mar 31 09:40:52 CEST 2021
1000 Vgl. frl:6403880
1000 Oai Id
  1. |
1000 Sichtbarkeit Metadaten public
1000 Sichtbarkeit Daten public
1000 Gegenstand von

View source