Knowledge Discovery in Graphs Through Vertex Separation

Marc Sarfati 1, 2 Marc Queudot 1 Catherine Mancel 3 Marie-Jean Meurs 1
1 UQAM - Université du Québec à Montréal
2 X - École polytechnique
3 ENAC - Ecole Nationale de l'Aviation Civile
Abstract : This paper presents our ongoing work on the Vertex Separator Problem (VSP), and its application to knowledge discovery in graphs representing real data. The classic VSP is modeled as an integer linear program. We propose several variants to adapt this model to graphs with various properties. To evaluate the relevance of our approach on real data, we created two graphs of different size from the IMDb database. The model was applied to the separation of these graphs. The results demonstrate how the model is able to semantically separate graphs into clusters.
Keywords : Graph partitioning Knowledge discovery Vertex Separator Problem
Type de document :
Chapitre d'ouvrage
Canadian Conference on Artificial Intelligence AI 2017: Advances in Artificial Intelligence , 10233, Springer, pp 203-214, 2017, Lecture Notes in Computer Science, 978-3-319-57350-2. 〈10.1007/978-3-319-57351-9_25〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger
https://hal-enac.archives-ouvertes.fr/hal-01521890
Contributeur : Laurence Porte <>
Soumis le : jeudi 18 mai 2017 - 11:53:23
Dernière modification le : vendredi 13 avril 2018 - 01:32:14

Fichier

vsp-cai2017.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

ENAC | OPTIM | X | UNIV-PARIS-SACLAY | PARISTECH

Citation

Marc Sarfati, Marc Queudot, Catherine Mancel, Marie-Jean Meurs. Knowledge Discovery in Graphs Through Vertex Separation. Canadian Conference on Artificial Intelligence AI 2017: Advances in Artificial Intelligence , 10233, Springer, pp 203-214, 2017, Lecture Notes in Computer Science, 978-3-319-57350-2. 〈10.1007/978-3-319-57351-9_25〉. 〈hal-01521890〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

75

Téléchargements de fichiers

34

Picto

Contact  : publications@enac.fr