Stream graphs and link streams for the modeling of interactions over time
Stream graphs and link streams for the modeling of interactions over time
复制标题
DOI：
10.1007/s13278-018-0537-7
复制
发表时间：
2018-10-03
影响因子：
2.8
通讯作者：
Magnien, Clemence
中科院分区：
文献类型：
--
作者：
Latapy, Matthieu;Viard, Tiphaine;Magnien, Clemence
图论提供了一种用于研究关系结构的语言，它也经常用于研究随时间变化的交互作用。然而，它很难捕捉到交互的内在时间和结构性质，这需要专门的形式主义。在本文中，我们概括了图概念，以一致的方式处理这两个方面。我们从密度、簇或路径等基本概念开始，并从中推导出更高级的概念，如派系、度、聚类系数或连通分量。我们获得了一种直接处理随时间变化的交互的语言，类似于图形提供的处理关系的语言。这种形式主义是自洽的：不同概念之间的通常关系得以保留。它也与图论一致：图概念是我们引入的概念的特例。这使得推广更高级别的对象变得容易，例如商图、折线图、k 核和中心性。本文还考虑了离散与连续时间假设、瞬时链接以及对更复杂情况的扩展。
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.