| Résumé | Le problème de l'intégration de graphes préservant la distance consiste à intégrer les sommets d'un graphe pondéré donné dans des points d'un espace euclidien à d dimensions, d étant une constante, de sorte que pour chaque arête, la distance entre les extrémités correspondantes soit la proche possible du poids de l'arête. Si le graphe donné est complet, c'est-à-dire si les poids sont fournis en tant que matrice complète, alors l'analyse multidimensionnelle [13] peut minimiser la somme des carrés des erreurs d'intégration en temps quadratique. Un inconvénient notable de cette approche est son exigence d'espace quadratique. Dans cet article, nous développons un algorithme en espace linéaire pour résoudre ce problème, lorsque le poids d'une arête quelconque peut être calculé en temps constant. Une idée clé consiste à partitionner un ensemble de n objets en O(?n) sous-ensembles disjoints (grappes) de taille O(?n), de sorte que la distance minimum entre les grappes soit maximisée parmi toutes les partitions possibles. Nous présentons des résultats expérimentaux pour comparer la performance de la nouvelle méthode et celle de l'analyse multidimensionnelle classique à moindres carrés [13] en nous servant de trois applications différentes. Bien que l'analyse multidimensionnelle donne des résultats un peu plus précis que la nouvelle méthode, elle fait plafonner la capacité de mémoire pour les ensembles de données comprenant plus de 15 000 sommets. |
|---|
