Compact Summaries of Rich Heterogeneous Graphs

Résumé : Les grands graphes de données, à structure potentiellement complexe et hétérogène, com- prenant parfois des noeuds typés et/ou une ontologie décrivant la sémantique d’un domaine d’application, sont utilisés largement de nos jours. Des nombreuses méthodes pour résumer de tels graphes ont été pro- posées; chacune aboutit à une structure compacte représentant l’essentiel de l’information sur la structure du graphe. Une famille de telles méthodes est basée sur la construction d’un graphe quotient, à partir d’une relation d’équivalence entre les noeuds du graphe d’origine. Dans ce travail, nous nous intéressons à la construction efficace de résumés compacts pour des graphes de données hétérogènes, en particulier des graphes RDF, qui peuvent comporter des données, des noeuds typés, et une ontologie. Nous proposons de nouvelles relations d’équivalence entre les noeuds d’un graphes, relations particulièrement adaptées à la hétérogénéité souvent rencontrée dans des graphes RDF. Ces relations conduisent à des résumés quotients qui sont compacts, tout en préservant de l’information sur la structure du graphe. Nous montrons comment tout relation d’équivalence entre les noeuds d’un graphe (comprenant, mais ne se limitant pas aux relations que nous introduisons) peut être étendue aux noeuds comportant des types, ainsi qu’aux ontologies. Par la suite, nous présentons la première étude approfondie de l’interaction entre les résumés par quotient et la saturation d’un graphe RDF, qui définit sa sémantique en présence d’une ontologie. Nous identifions une condition suffisante sur une relation d’équivalence entre des noeuds du graphe, condition qui, lorsqu’elle est satisfaite, conduit à une méthode rapide, appellée shortcut (raccourci) pour la construction du résumé d’un graphe RDF. Nous présentons des nouveaux algorithmes efficace, en particulier des algorithmes incrémentaux, pour résumer des graphes par nos nouvelles relations d’équivalence. Enfin, nous présentons des expériences qui valide la performance de nos algorithmes et l’intérêt des résumés étudiés.
Type de document :
Rapport
[Research Report] RR-8920, INRIA Saclay; Université Rennes 1. 2017
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01325900
Contributeur : Ioana Manolescu <>
Soumis le : mercredi 4 juillet 2018 - 10:53:07
Dernière modification le : vendredi 6 juillet 2018 - 01:24:38

Fichier

RR-04072018.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01325900, version 6

Citation

Šejla Čebirić, François Goasdoué, Pawel Guzewicz, Ioana Manolescu. Compact Summaries of Rich Heterogeneous Graphs. [Research Report] RR-8920, INRIA Saclay; Université Rennes 1. 2017. 〈hal-01325900v6〉

Partager

Métriques

Consultations de la notice

130

Téléchargements de fichiers

27