Affordable Access

Access to the full text

Stream graphs and link streams for the modeling of interactions over time

Authors
  • Latapy, Matthieu1
  • Viard, Tiphaine1
  • Magnien, Clémence1
  • 1 Sorbonne Universités, UPMC Univ Paris 06, CNRS UMR 7606, LIP6, Paris, 75005, France , Paris (France)
Type
Published Article
Journal
Social Network Analysis and Mining
Publisher
Springer Vienna
Publication Date
Oct 03, 2018
Volume
8
Issue
1
Identifiers
DOI: 10.1007/s13278-018-0537-7
Source
Springer Nature
Keywords
License
Yellow

Abstract

Graph theory provides a language for studying the structure of relations, and it is often used to study interactions over time too. However, it poorly captures the intrinsically temporal and structural nature of interactions, which calls for a dedicated formalism. In this paper, we generalize graph concepts to cope with both aspects in a consistent way. We start with elementary concepts like density, clusters, or paths, and derive from them more advanced concepts like cliques, degrees, clustering coefficients, or connected components. We obtain a language to directly deal with interactions over time, similar to the language provided by graphs to deal with relations. This formalism is self-consistent: usual relations between different concepts are preserved. It is also consistent with graph theory: graph concepts are special cases of the ones we introduce. This makes it easy to generalize higher level objects such as quotient graphs, line graphs, k-cores, and centralities. This paper also considers discrete versus continuous time assumptions, instantaneous links, and extensions to more complex cases.

Report this publication

Statistics

Seen <100 times