Measures on graphs : from similarity to density
(2014)
Files
Thesis_Final.pdf
Open Access - Adobe PDF
- 12.52 MB
Details
- Authors
- Supervisors
- Fouss, François
- Abstract
- (fr) Notre recherche doctorale s’intéresse principalement à deux problèmes étroitement liés, dans les domaines de l’analyse de données et de l’apprentissage automatique: (1) le développement de nouvelles mesures de similarité entre graphes et entre nœuds d’un graphe, et (2) le développement de nouvelles mesures de densité sur les nœuds d’un graphe. Dans la première partie de ce document, trois nouveaux noyaux sur graphes, pouvant être considérés comme des mesures de similarité entre graphes, sont introduits. Ces noyaux sont évalués sur une tâche de classification dont l’objectif est de classer des molécules d’origines diverses, modélisées sous forme de graphes, suivant une de leurs propriétés (mutagénicité,…). Dans notre recherche sur la quantification de la similarité entre nœuds d’un graphe, trois nouvelles mesures ont été définies en assignant aux forêts présentes dans le graphe une probabilité d’être choisies au hasard, favorisant les petites forêts (ayant un coût faible) au détriment des plus étendues. Ces mesures sont ensuite évaluées sur une tâche de classification semi-supervisée dont l’objectif est de prédire les étiquettes manquant sur certains nœuds à partir de celles attachées aux autres nœuds. De ces mesures de similarité, un indice de densité d’un nœud d’un graphe, appelé « Sum-over-Forests » (SoF), a été développé en supposant qu’un nœud présent sur beaucoup de forêts (de préférence petites – et donc avec une plus forte probabilité d’être choisies au hasard) devrait être situé dans une région dense du graphe. Cet indice de densité est ensuite testé de différentes manières, évaluant sa qualité en tant qu’estimateur de densité sur graphes. Enfin, deux méthodes de clustering de nœuds, basées sur l’indice de densité SoF, pouvant être appliquées directement sur des graphes et ne nécessitant pas a priori le nombre de clusters à obtenir, ont été mises au point.
- Affiliations
Citations
Senelle, M. (2014). Measures on graphs : from similarity to density. https://hdl.handle.net/2078.5/191247