Partitionnement de graphe : optimisation et applications

Contributeur(s)
- Siarry, Patrick (1952-....). Éditeur scientifique
- Bichot, Charles-Edmond. Éditeur scientifique
Éditeur(s)
- Hermès science publications-Lavoisier
Date
- impr. 2010
Notes
- Notes bibliogr. Glossaire. Index
Langues
- Français
Description matérielle
- 1 vol. (440 p.) : ill. ; 24 cm
Collections
- IC2
Sujet(s)
ISBN
- 978-2-7462-3005-7
Indice
- 518 Calcul et analyse numériques
Quatrième de couverture
- L'informatique, omniprésente dans notre vie, est multiforme. A la fois profondément unitaire quant à ses principes d'écriture et ceux qui sont à la base des machines, l'informatique est infiniment variée par ses applications.
  Informatique et Systèmes d'Information couvre l'ensemble des domaines suivants :
  Apprentissage
  Arithmétique des ordinateurs
  Bases de données
  Bioinformatique
  Représentation des connaissances
  Informatique parallèle et répartie
  Logique et programmation
  Recherche d'information et web
  Recherche opérationnelle
  Chaque ouvrage décrit aussi bien les aspects fondamentaux qu'expérimentaux. Une classification des différents chapitres contenus dans chacun, une bibliographie et un index détaillé orientent le lecteur vers ses points d'intérêt immédiats : celui-ci dispose ainsi d'un guide pour ses réflexions et ses choix.
  Sur chaque aspect, le traité s'efforce de marier chapitres de synthèse et connaissances les plus récentes pour donner au lecteur le panorama complet d'un sujet.
Tables des matières
- - Partitionnement de graphe
  - Optimisation et applications
  - Lavoisier
  - Introduction 19
  - Charles-Edmond Bichot, Patrick Siarry
  - Chapitre 1. Introduction générale au partitionnement de graphe 23
  - Charles-Edmond Bichot
  - 1.1. Le partitionnement23
  - 1.2. Notions mathématiques25
  - 1.3. Graphes27
  - 1.4. Description formelle du problème du partitionnement de graphe31
  - 1.5. Fonctions objectifs pour le partitionnement de graphe33
  - 1.6. Le partitionnement contraint35
  - 1.7. Le partitionnement non contraint37
  - 1.8. Différences entre partitionnement contraint et non contraint39
  - 1.9. De la bissection au k-partitionnement : la bissection récursive39
  - 1.9.1. Créer une partition avec pour nombre de partie une puissance de 240
  - 1.9.2. Créer une k-partition en utilisant la balance de partitionnement42
  - 1.10. NP-difficulté des problèmes de partitionnement42
  - 1.10.1. Le cas du partitionnement contraint42
  - 1.10.2. Le cas du partitionnement non contraint43
  - 1.10.2.1. NP-difficulté de la coupe normalisée43
  - 1.10.2.2. NP-difficulté du ratio de coupe44
  - 1.11. Conclusion45
  - 1.12. Bibliographie46
  - Première partie. Approche pour le calcul numérique 49
  - Chapitre 2. La méthode multi-niveaux 51
  - Charles-Edmond Bichot
  - 2.1. Introduction51
  - 2.2. Principes de la méthode multi-niveaux52
  - 2.3. Contraction du graphe55
  - 2.3.1. Introduction55
  - 2.3.2. Appariement d'un graphe56
  - 2.3.3. L'algorithme de contraction d'Hendrickson-Leland57
  - 2.3.4. Algorithme de contraction de la plus lourde arête (HEM)57
  - 2.4. Partitionnement du graphe réduit59
  - 2.4.1. Des méthodes de partitionnement éprouvées59
  - 2.4.2. Les méthodes d'expansion de région60
  - 2.4.2.1. Description générale60
  - 2.4.2.2. Graph Growing Partitioning algorithm (GGP)61
  - 2.4.2.3. Greedy Graph Growing Partitioning algorithm (GGGP)62
  - 2.5. Affinage et expansion du graphe63
  - 2.5.1. Présentation de la phase d'affinage et d'expansion du graphe63
  - 2.5.2. L'algorithme de Kernighan-Lin64
  - 2.5.2.1. Principe général64
  - 2.5.2.2. L'algorithme65
  - 2.5.2.3. Améliorations proposées par B. Kernighan et S. Lin67
  - 2.5.2.4. Complexité67
  - 2.5.2.5. Parties de tailles différentes68
  - 2.5.2.6. Sommets de poids différents68
  - 2.5.2.7. Autres améliorations de l'algorithme de Kernighan-Lin68
  - 2.5.3. L'implémentation de Fiduccia-Mattheyses69
  - 2.5.4. Adaptation au k-partitionnement direct71
  - 2.5.5. Global Kernighan-Lin refinement71
  - 2.5.6. Algorithme d'affinage de Walshaw-Cross73
  - 2.6. La méthode spectrale75
  - 2.6.1. Présentation75
  - 2.6.2. Quelques résultats d'analyse numérique76
  - 2.6.3. Trouver les valeurs propres de la matrice Laplacienne du graphe78
  - 2.6.4. Borne inférieure pour le partitionnement de graphe contraint79
  - 2.6.5. Méthodes spectrales pour le partitionnement contraint80
  - 2.6.6. Méthodes spectrales pour le partitionnement non contraint81
  - 2.6.6.1. Le ratio de coupe82
  - 2.6.6.2. La coupe normalisée82
  - 2.6.7. Problèmes et améliorations82
  - 2.7. Conclusion83
  - 2.8. Bibliographie84
  - Chapitre 3. Le partitionnement d'hypergraphe 89
  - Cédric Chevalier
  - 3.1. Définitions et métriques89
  - 3.1.1. Hypergraphe et partitionnement89
  - 3.1.2. Métriques pour le partitionnement d'hypergraphe91
  - 3.2. Relations entre graphes, hypergraphes et matrices91
  - 3.3. Algorithmes pour le partitionnement d'hypergraphe93
  - 3.3.1. Contraction93
  - 3.3.2. Partitionnement initial et affinage96
  - 3.3.3. Affinage96
  - 3.4. Utilisations97
  - 3.4.1. Intérêts du partitionnement d'hypergraphe97
  - 3.4.2. Partitionnement de matrices98
  - 3.4.3. Quelques résultats pratiques100
  - 3.4.4. Re-partitionnement101
  - 3.4.5. Utilisation des hypergraphes dans le cadre de partitionnement de maillages101
  - 3.4.6. Quelques autres applications102
  - 3.5. Conclusion102
  - 3.6. Ressources logicielles103
  - 3.7. Bibliographie103
  - Chapitre 4. Parallélisation du partitionnement de graphes 107
  - François Pellegrini
  - 4.1. Introduction107
  - 4.1.1. Nécessité du parallélisme107
  - 4.1.2. Schéma multi-niveaux108
  - 4.1.2.1. Expansion avec raffinement108
  - 4.1.2.2. Contraction109
  - 4.1.2.3. Partitionnement initial110
  - 4.2. Structures de données distribuées111
  - 4.3. Parallélisation de la phase de contraction112
  - 4.3.1. Construction du graphe contracté114
  - 4.3.2. Algorithmes parallèles d'appariement114
  - 4.3.3. Réduction des collisions au niveau des processus115
  - 4.3.4. Réduction des collisions au niveau des sommets116
  - 4.3.4.1. Appariement par couleurs116
  - 4.3.4.2. Appariement restreint117
  - 4.3.4.3. Appariement probabiliste118
  - 4.4. Repliement120
  - 4.5. Centralisation122
  - 4.6. Parallélisation de la phase de raffinement123
  - 4.6.1. Parallélisation des méthodes locales de raffinement124
  - 4.6.1.1. Collision de mouvements124
  - 4.6.1.2. Exclusion des collisions au niveau des sommets125
  - 4.6.1.3. Exclusion des collisions au niveau des processus125
  - 4.6.2. Graphes bandes127
  - 4.6.3. Multi-centralisation129
  - 4.6.4. Parallélisation des méthodes globales de raffinement130
  - 4.6.4.1. Raffinement par algorithmes génétiques130
  - 4.6.4.2. Raffinement par méthodes de diffusion132
  - 4.7. Résultats expérimentaux136
  - 4.8. Conclusion138
  - 4.9. Bibliographie141
  - Chapitre 5. Placement statique de graphes de processus 145
  - François Pellegrini
  - 5.1. Introduction145
  - 5.2. Modèles de placement statique146
  - 5.2.1. Fonctions de coût147
  - 5.2.2. Hétérogénéité des architectures cibles150
  - 5.3. Algorithmes exacts152
  - 5.4. Algorithmes approchés154
  - 5.4.1. Méthodes globales154
  - 5.4.1.1. Méthodes directes155
  - 5.4.1.2. Méthodes par regroupement156
  - 5.4.1.3. Méthodes multi-niveaux157
  - 5.4.2. Méthodes récursives158
  - 5.4.2.1. Structure générale158
  - 5.4.2.2. Séquencement des tâches de bipartition162
  - 5.5. Conclusion165
  - 5.6. Bibliographie166
  - Chapitre 6. Résolution de systèmes linéaires creux 169
  - Laura Grigori
  - 6.1. Matrices et graphes173
  - 6.2. Prédiction de structure pour la factorisation LU creuse176
  - 6.2.1. Le graphe de fusion par lignes pour A = P₁L₁ ... P_n-1L_n-1U178
  - 6.2.2. Bornes supérieures exactes pour PA = LU181
  - 6.2.3. L'arbre d'élimination par colonnes et l'arbre de fusion par lignes182
  - 6.3. Renumérotation des inconnues pour minimiser le remplissage185
  - 6.4. Factorisation symbolique187
  - 6.4.1. Algorithme parallèle189
  - 6.5. Factorisation numérique192
  - 6.5.1. Résultats expérimentaux194
  - 6.6. Conclusions198
  - 6.7. Bibliographie198
  - Deuxième partie. Méthodes d'optimisation 203
  - Chapitre 7. Métaheuristiques locales et partitionnement de graphe 205
  - Charles-Edmond Bichot
  - 7.1. Introduction générale sur les métaheuristiques206
  - 7.2. Le recuit simulé207
  - 7.2.1. Description de l'algorithme du recuit simulé208
  - 7.2.2. Adaptation du recuit simulé à la bissection de graphe210
  - 7.2.3. Généralisation de cette adaptation au k-partitionnement213
  - 7.2.4. Bilan de l'adaptation du recuit simulé214
  - 7.3. Recherche itérative locale, ILS215
  - 7.3.1. Présentation de la recherche itérative locale215
  - 7.3.1.1. Recherche aléatoire216
  - 7.3.1.2. Recherche itérative locale217
  - 7.3.2. Adaptation naïve de la recherche itérative locale219
  - 7.3.2.1. Adaptation219
  - 7.3.2.2. Évaluation221
  - 7.3.3. Recherche itérative locale et méthode multi-niveaux223
  - 7.4. Autres métaheuristiques de recherche locale225
  - 7.4.1. Algorithmes gloutons225
  - 7.4.2. Recherche tabou226
  - 7.5. Conclusion226
  - 7.6. Bibliographie227
  - Chapitre 8. Métaheuristiques à population et fusion-fission 231
  - Charles-Edmond Bichot
  - 8.1. Les algorithmes de colonies de fourmis231
  - 8.2. Les algorithmes évolutionnaires233
  - 8.2.1. Principe des algorithmes génétiques234
  - 8.2.1.1. Algorithme234
  - 8.2.1.2. Opérateurs de diversification235
  - 8.2.1.3. Sélection des individus236
  - 8.2.1.4. Opérateurs de sélection236
  - 8.2.1.5. Opérateurs de remplacement237
  - 8.2.2. Processus classique de l'adaptation des algorithmes génétiques238
  - 8.2.2.1. Fonction d'adaptation (fitness)238
  - 8.2.2.2. Codage de la population238
  - 8.2.2.3. Opérateur de croisement pour le partitionnement de graphe238
  - 8.2.2.4. Opérateur de mutation pour le partitionnement de graphe240
  - 8.2.3. L'adaptation de Bui et Moon240
  - 8.2.3.1. Sélection des parents242
  - 8.2.3.2. Croisement, mutation et équilibrage242
  - 8.2.3.3. Affinage des individus243
  - 8.2.3.4. Pré-traitement du graphe244
  - 8.2.3.5. Évaluation244
  - 8.2.4. Algorithme évolutionnaire multi-niveaux de Soper-Walshaw-Cross245
  - 8.2.4.1. Codage de la population246
  - 8.2.4.2. Algorithme247
  - 8.2.4.3. Les opérateurs de croisement et de mutation248
  - 8.2.4.4. Évaluation249
  - 8.2.5. Autres adaptations des algorithmes évolutionnaires249
  - 8.3. La méthode de fusion-fission251
  - 8.3.1. Présentation251
  - 8.3.2. Principe de la fusion-fission252
  - 8.3.3. Algorithme254
  - 8.3.4. Choix de l'algorithme multi-niveaux256
  - 8.3.5. Création de la séquence des nombres de parties257
  - 8.3.6. Choix de l'algorithme d'affinage258
  - 8.3.6.1. Utilisation de l'algorithme d'affinage de Walshaw-Cross259
  - 8.3.7. Évaluation260
  - 8.3.7.1. Robustesse de la fusion-fission260
  - 8.3.7.2. Évaluation sur les bancs de test classiques262
  - 8.4. Conclusion263
  - 8.5. Remerciements264
  - 8.6. Bibliographie265
  - Chapitre 9. Partitionnement des réseaux mobiles en zones tarifaires 269
  - Mustapha Oughdi, Sid Lamrous, Alexandre Caminada
  - 9.1. Introduction269
  - 9.1.1. Modèle de tarification planifiée269
  - 9.1.1.1. Modèle de tarification pour une cellule270
  - 9.1.1.2. Fonction objectif du problème d'optimisation270
  - 9.1.1.3. Modèle de comportement des clients271
  - 9.1.2. Modèle de tarification pour un réseau272
  - 9.1.2.1. Adaptation du modèle272
  - 9.1.2.2. Difficultés techniques et contrainte cognitive272
  - 9.1.2.3. Résolution du problème d'extension du modèle275
  - 9.2. Découpage spatial du réseau276
  - 9.2.1. Définitions277
  - 9.2.1.1. Allure d'un profil de demande277
  - 9.2.1.2. Corrélation de Pearson277
  - 9.2.1.3. Similitude des profils de demande des cellules278
  - 9.2.1.4. Proximité géographique des cellules280
  - 9.2.2. Formalisation du problème de découpage spatial280
  - 9.2.2.1. Fonction objectif pour le partitionnement281
  - 9.2.2.2. Poids et coupe d'une zone281
  - 9.2.2.3. Normalisation de la matrice des similitudes283
  - 9.2.3. Résolution du découpage spatial par un algorithme génétique284
  - 9.2.3.1. L'algorithme génétique284
  - 9.2.3.2. Codage et évaluation des chromosomes285
  - 9.2.3.3. Génération des individus de la population initiale286
  - 9.2.3.4. Sélection des parents286
  - 9.2.3.5. Opérateurs de croisement et de mutation287
  - 9.3. Résultats expérimentaux288
  - 9.4. Conclusion290
  - 9.5. Bibliographie291
  - Chapitre 10. Application du partitionnement au découpage aérien 293
  - Charles-Edmond Bichot, Nicolas Durand
  - 10.1. Introduction293
  - 10.2. Le problème du découpage de l'espace aérien295
  - 10.2.1. La création de blocs d'espace aérien fonctionnels en Europe296
  - 10.2.2. La création d'un bloc fonctionnel en Europe centrale298
  - 10.3. Modélisation du problème299
  - 10.3.1. Charge de contrôle dans un secteur299
  - 10.3.2. Objectif : minimiser la charge de coordination300
  - 10.3.3. Deux contraintes, les tailles des zones et des centres301
  - 10.3.4. Analyse et traitement des données du trafic aérien européen302
  - 10.3.5. Graphe du trafic aérien européen et adaptation au partitionnement303
  - 10.4. Partition de l'espace : vers une nouvelle métaheuristique d'optimisation305
  - 10.5. Découpage de l'espace aérien d'Europe centrale309
  - 10.6. Conclusion313
  - 10.7. Remerciements315
  - 10.8. Bibliographie315
  - Troisième partie. Autres approches du partitionnement 317
  - Chapitre 11. Application à la segmentation d'images 319
  - Amir Nakib, Laurent Najman, Hugues Talbot, Patrick Siarry
  - 11.1. Introduction319
  - 11.2. L'image vue sous la forme d'un graphe319
  - 11.3. Principe de la segmentation d'images via les graphes322
  - 11.3.1. Choix des poids des arcs pour la segmentation323
  - 11.4. Segmentation d'images via les flots maximaux325
  - 11.4.1. Flots maximaux pour la minimisation d'énergie325
  - 11.4.2. Surfaces et géodésiques minimales328
  - 11.4.2.1. L'approche de la géométrie différentielle328
  - 11.4.3. Surfaces et géodésiques minimales via les flots maximaux331
  - 11.4.4. Flots maximaux continus333
  - 11.5. Unification de méthodes de segmentation via la théorie des graphes334
  - 11.6. Conclusions et perspectives338
  - 11.7. Bibliographie340
  - Chapitre 12. Distances pour le partitionnement de graphe 345
  - Alain Guénoche
  - 12.1. Introduction345
  - 12.2. La distance de Dice347
  - 12.2.1. Deux extensions aux graphes pondérés349
  - 12.2.1.1. Les pondérations sont des probabilités349
  - 12.2.1.2. Les pondérations sont des intensités351
  - 12.3. La distance de Pons-Latapy352
  - 12.4. Une méthode de partitionnement pour tableaux de distance354
  - 12.5. Un protocole de simulation357
  - 12.5.1. Un générateur de graphes aléatoires357
  - 12.5.2. Qualité de la partition obtenue358
  - 12.5.2.1. L'indice de Rand corrigé par Hubert & Arabie358
  - 12.5.2.2. Distance des transferts359
  - 12.5.2.3. La modularité de Newman361
  - 12.5.3. Résultats361
  - 12.5.3.1. Graphes non pondérés362
  - 12.5.3.2. Graphes pondérés363
  - 12.6. Conclusions364
  - 12.7. Remerciements364
  - 12.8. Bibliographie365
  - Chapitre 13. Détection de communautés, disjointes ou chevauchantes, dans les réseaux 369
  - Jean-Baptiste Angelelli, Alain Guénoche, Laurence Reboul
  - 13.1. Introduction370
  - 13.2. La modularité des partitions et des recouvrements372
  - 13.3. Méthode de partitionnement375
  - 13.3.1. Fusion et/ou fissions de classes375
  - 13.3.2. Complexité de l'algorithme376
  - 13.3.3. Simulations377
  - 13.3.3.1. Les graphes377
  - 13.3.3.2. Les critères377
  - 13.3.3.3. Résultats378
  - 13.4. Méthode de recouvrement380
  - 13.4.1. Algorithme de fusion381
  - 13.4.2. Simulations383
  - 13.5. Conclusion385
  - 13.6. Remerciements386
  - 13.7. Bibliographie386
  - Chapitre 14. Optimisation locale multi-niveaux de la modularité 389
  - Thomas Aynaud, Vincent Blondel, Jean-Loup Guillaume, Renaud Lambiotte
  - 14.1. Introduction389
  - 14.2. Préliminaires sur la modularité391
  - 14.3. Optimisation de la modularité393
  - 14.3.1. Méthodes existantes393
  - 14.3.2. Limitations connues394
  - 14.3.3. La méthode de Louvain396
  - 14.3.3.1. Première phase397
  - 14.3.3.2. Deuxième phase397
  - 14.3.4. Gain de modularité398
  - 14.3.4.1. Supprimer un sommet de sa communauté398
  - 14.3.4.2. Insérer un sommet dans une communauté399
  - 14.3.5. Convergence de l'algorithme400
  - 14.3.5.1. Complexité théorique400
  - 14.3.5.2. Modèles par copie401
  - 14.4. Validation sur des graphes artificiels et empiriques401
  - 14.4.1. Graphes artificiels403
  - 14.4.2. Graphes réels406
  - 14.5. Discussion408
  - 14.5.1. Influence de l'ordre de traitement des sommets409
  - 14.5.2. Communautés intermédiaires409
  - 14.5.2.1. Résolution limite410
  - 14.5.2.2. Redécomposition des communautés intermédiaires410
  - 14.5.2.3. Modèle de Sales-Pardo412
  - 14.5.3. Améliorations possibles414
  - 14.5.3.1. Optimisation partielle414
  - 14.5.3.2. Suppression des feuilles415
  - 14.5.3.3. Déplacement des sommets415
  - 14.5.3.4. Retour à des niveaux inférieurs415
  - 14.5.3.5. Recuit simulé417
  - 14.5.4. Utilisations connues417
  - 14.5.4.1. Analyse de grands graphes417
  - 14.5.4.2. Application à d'autres fonctions de coût418
  - 14.6. Conclusion418
  - 14.7. Remerciements419
  - 14.8. Bibliographie419
  - Annexes 423
  - A. Les principaux outils et bancs de test pour le partitionnement de graphe423
  - A.1. Les outils pour le partitionnement contraint424
  - A.1.1. Chaco424
  - A.1.2. Metis425
  - A.1.3. Scotch425
  - A.1.4. Jostle426
  - A.1.5. Party426
  - A.2. Les outils pour le partitionnement non contraint426
  - A.2.1. Graclus427
  - A.3. Bancs de test du partitionnement de graphe427
  - A.3.1. Archives du partitionnement de graphe de C. Walshaw427
  - A.3.2. Autres bancs de test429
  - A.4. Bibliographie430
  - Glossaire 433
  - Index 437
Origine de la notice:
- BNF