Représentations compactes des graphes et contraintes pseudo booléennes

National audienceLes graphes représentent un outil efficace pour la modélisation des relations structurelles entre les objets. Cependant, l'exploitation de ces graphes de données est très coûteuse en raison de la taille. En effet, dans la plupart des applications réelles, la taille des graphes est largement grande, ce qui rend difficile à comprendre l'information et la structure codée dans ces graphes par une simple visualisation. La représentation compacte des grands graphes, appelée aussi compression des graphes, est une opération qui permet la diminution du nombre d'arêtes ou de noeuds du graphe pour faciliter leurs traitements. Dans cet article, nous proposons une nouvelle approche basée sur l'utilisation des contraintes pseudo booléennes pour une représentation condensée de larges graphes. L'avantage d'une telle représentation est qu'au lieu de représenter un graphe (e.g., clique) par un nombre quadratique d'arêtes, on peut l'exprimer sous forme d'une inéquation linéaire dont les modèles correspondent exactement aux arêtes du graphe initial. Notre approche permet le passage à l'échelle tout en garantissant la décompression de graphes par une simple résolution des inéquations linéaires correspondantes. Les expérimentation sur plusieurs graphes réels montrent que notre approche offre de meilleures performances comparée à plusieurs approches de l'état de l'art