Cours/Séminaire
Notice
Lieu de réalisation
Paris
Langue :
Anglais
Crédits
François Baccelli (Publication), Payam Delgosha (Intervention)
Détenteur des droits
Inria
Conditions d'utilisation
Droit commun de la propriété intellectuelle
Citer cette ressource :
Payam Delgosha. Inria. (2022, 14 novembre). A Notion of Entropy for Sparse Marked Graphs and its Applications in Graphical Data Compression , in DYOGENE/ERC NEMO 2022 : Seminar series. [Vidéo]. Canal-U. https://www.canal-u.tv/147582. (Consultée le 16 juin 2024)

A Notion of Entropy for Sparse Marked Graphs and its Applications in Graphical Data Compression

Réalisation : 14 novembre 2022 - Mise en ligne : 14 novembre 2022
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
Descriptif

Many modern data sources arising from social networks, biological data, etc. are best viewed as being represented by combinatorial structures such as graphs, rather than time series. The local weak limit theory for sparse graphs, also known as the objective method, provides a framework which enables one to make sense of a stationary stochastic process for sparse graphs. The theory of time series is the engine driving an enormous range of applications in areas such as control theory, communications, information theory and signal processing. It is to be expected that a theory of stationary stochastic processes for combinatorial structures, in particular graphs, would eventually have a similarly wide-ranging impact. Employing the above framework, we introduce a notion of entropy for probability distributions on rooted graphs. This is a generalization of the notion of entropy introduced by Bordenave and Caputo to graphs which carry marks on their vertices and edges. The above notion of entropy can be considered as a natural counterpart for the Shannon entropy rate in the world of graphical data. We illustrate this by introducing a universal compression scheme for marked graphical data. We also discuss a low complexity universal compression algorithm for marked graphical data. Furthermore, we will discuss an extension of this approach to a more general sparsity regime that also takes into account heavy-tailed sparse graphs in which the number of edges in the graph scales super linearly with the number of vertices. In order to do this, we employ the sparse graphon framework as well as an appropriate notion of entropy for this framework. Using this, we introduce a universal lossless compression method which is simultaneously applicable to both sparsity regimes, namely the local weak convergence regime and the sparse graphon regime.

Intervention

Dans la même collection

Sur le même thème