Transformation de graphes dynamiques en signaux non stationnaires

Ronan Hamon (1) , Pierre Borgnat (1) , Patrick Flandrin (1) , Céline Robardet (2)

1 Phys-ENS - Laboratoire de Physique de l'ENS Lyon
2 DM2L - Data Mining and Machine Learning

Many data associated to networks, whether physical, biological or social, can be described by graphs that can become dynamic if a time evolution is added. These graphs are difficult to study because there exist only a few tools to describe these objects. The objective here is to propose a new method to visualize synthetically their evolution over time. The originality of this work consists of study dynamic graphs using a signal theory approach, by computing spectral analysis on series representing the graphs. The method consists of transforming a graph to a collection of signals using multidimensional scaling then linking frequency patterns of these series with graph properties. The extension to dynamic graph enables us to follow the evolution of these patterns and then track the modification of the structure of the graph over time. A method to reconstruct the graph from the collection of signals is also proposed to reduce the graph by selecting the most significant links.

De nombreux réseaux, qu'ils soient physiques, biologiques ou sociaux, peuvent se représenter sous la forme d'un graphe qui, si la composante temporelle est prise en compte, devient dynamique. L'étude de ces graphes dynamiques est compliquée du fait qu'il existe peu d'outils pour ce type d'objet. L'objectif ici est de proposer une nouvelle méthode pour visualiser de façon synthétique au cours du temps leur évolution. L'originalité des travaux consiste à aborder l'étude des graphes dynamiques à l'aide d'outils de la théorie du signal, en effectuant des analyses fréquentielles sur des séries représentant les graphes. La méthode proposée permet de transformer un graphe quelconque en une collection de signaux en utilisant le positionnement multidimensionnel classique puis de relier des motifs fréquentiels sur ces séries à des propriétés du graphe. L'application à des graphes dynamiques permet un suivi de ces motifs dans le temps : l'évolution de la structure globale du graphe est ainsi visible. Une méthode de reconstruction du graphe à partir des signaux est également proposée et permet de réduire le graphe en ne gardant que les liens les plus significatifs.

Domaines: Traitement du signal et de l'image [eess.SP]; Traitement du signal et de l'image [eess.SP]

Ronan Hamon, Pierre Borgnat, Patrick Flandrin, Céline Robardet. Transformation de graphes dynamiques en signaux non stationnaires. Colloque GRETSI 2013, Sep 2013, Brest, France. pp.251. ⟨ensl-00875085⟩