Partitionnement de graphe (traité IC2) , livre ebook

Hermès - Editions Lavoisier - Charles - Edmond Bichot , Patrick Siarry

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

443 pages

Français

Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

A propos
Informations
Extrait

Description

L'optimisation du partitionnement de graphe est un problème théorique qui a des applications multiples, mais souvent méconnues, entre autres en calcul numérique, calcul parallèle, dessin des composants informatiques, analyse d'image et de vidéo. Ces dernières années ont vu de nouveaux challenges apparaître. La taille des graphes à partitionner a explosé, passant de quelques milliers de sommets à plusieurs millions.
Partitionnement de graphe a pour ambition de présenter au lecteur néophyte, comme à l'expert en informatique ou en mathématiques appliquées, des méthodes et des outils pour résoudre le problème du partitionnement de graphe. À cette fin, nous avons réuni plusieurs chapitres méthodologiques détaillant différentes approches d'optimisation du partitionnement de graphe comme la méthode multi-niveaux, les métaheuristiques, la parallélisation ou le partitionnement d'hypergraphes.
Plusieurs applications viennent compléter cet ouvrage, sur des sujets aussi différents que les réseaux mobiles, la résolution de systèmes linéaires, la segmentation d'image, le trafic aérien, les réseaux sociaux, etc...
Introduction. Chapitre 1. Introduction générale au partitionnement de graphe. APPROCHE POUR LE CALCUL NUMÉRIQUE. Chapitre 2. La méthode multi-niveaux. Chapitre 3. Le partitionnement d'hypergraphe. Chapitre 4. Parallélisation du partitionnement de graphes. Chapitre 5. Placement statique de graphes de processus. Chapitre 6. Résolution de systèmes linéaires creux. MÉTHODES D'OPTIMISATION. Chapitre 7. Métaheuristiques locales et partitionnement de graphe. Chapitre 8. Métaheuristiques à population et fusion-fission. Chapitre 9. Partitionnement des réseaux mobiles en zones tarifaires. Chapitre 10. Application du partitionnement au découpage aérien. AUTRES APPROCHES DU PARTITIONNEMENT. Chapitre 11. Application à la segmentation d'images. Chapitre 12. Distances pour le partitionnement de graphe. Chapitre 13. Détection de communautés, disjointes ou chevauchantes, dans les réseaux. Chapitre 14. Optimisation locale multi-niveaux de la modularité. Annexes. Glossaire. Index.

Sujets

Informatique

Mathématiques

Informations

Publié par	Hermès - Editions Lavoisier
Date de parution	08 juillet 2010
Nombre de lectures	18
EAN13	9782746241367
Langue	Français
Poids de l'ouvrage	12 Mo

Informations légales : prix de location à la page 0,1200€. Cette information est donnée uniquement à titre indicatif conformément à la législation en vigueur.

Extrait

Partitionnement de graphe

© LAVOISIER, 2010
LAVOISIER
11, rue Lavoisier
75008 Paris

www.hermes-science.com
www.lavoisier.fr

ISBN 978-2-7462-3005-7

Le Code de la propriété intellectuelle n’autorisant, aux termes de l’article L. 122-5, d’une
part, que les "copies ou reproductions strictement réservées à l’usage privé du copiste et non
destinées à une utilisation collective" et, d’autre part, que les analyses et les courtes citations
dans un but d’exemple et d’illustration, "toute représentation ou reproduction intégrale, ou
partielle, faite sans le consentement de l’auteur ou de ses ayants droit ou ayants cause, est
illicite" (article L. 122-4). Cette représentation ou reproduction, par quelque procédé que ce
soit, constituerait donc une contrefaçon sanctionnée par les articles L. 335-2 et suivants du
Code de la propriété intellectuelle.
Tous les noms de sociétés ou de produits cités dans cet ouvrage sont utilisés à des fins
d’identification et sont des marques de leurs détenteurs respectifs.

Printed and bound in England by Antony Rowe Ltd, Chippenham, September 2010.

Partitionnement

de graphe

optimisation et applications

sous la direction de
Charles-Edmond Bichot

Patrick Siarry

Il a été tiré de cet ouvrage
35 exemplaires hors commerce réservés
aux membres du comité scientifique,
aux auteurs et à l’éditeur
numérotés de 1 à 35

Partitionnement de graphe
sous la direction de Charles-Edmond Bichot et Patrick Siarry
fait partie de la série INFORMATIQUE ET SYSTEMES D’INFORMATION
dirigée par Jean-Charles Pomerol
Directeur de collection Francis Sourd

Traités IC2, sous la direction scientifique de Bernard Dubuisson

IC2 – constitué par un ensemble de huit traités – répond au besoin de
disposer d’une somme complète des connaissances et des méthodes
nécessaires à la maîtrise des systèmes technologiques.
Conçu volontairement dans un esprit d’échange disciplinaire, IC2
représente l’état de l’art dans les domaines suivants retenus par le comité
scientifique :
Cognition et traitement de l’information
Informatique et systèmes d’information
Ingénierie pour la santé
Management et gestion des STIC
Réseaux et télécoms
Signal et Image
Systèmes automatisés
Technologies et développement durable
Chaque ouvrage décrit aussi bien les aspects fondamentaux
qu’expérimentaux. Une classification des différents articles 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 ou pour ses choix.
Les savoirs, théories et méthodes rassemblés dans chaque ouvrage ont
été choisis pour leur pertinence dans l’avancée des connaissances ou pour
la qualité des résultats obtenus dans le cas d’expérimentations réelles.

Liste des auteurs

Jean-Baptiste ANGELELLI Jean-Loup GUILLAUME
IML LIP6
Aix-Marseille Universités Université Pierre et Marie Curie
Marseille Paris

Thomas AYNAUD Laura GRIGORI
LIP6 INRIA Saclay-Ile de France
Université Pierre et Marie Curie LRI
Paris Université Paris-Sud 11
Orsay
Charles-Edmond BICHOT
LIRIS Renaud LAMBIOTTE
Ecole centrale de Lyon Institute for Mathematical Sciences
Université de Lyon Imperial College London
Angleterre
Vincent BLONDEL
Department of Mathematical Sid LAMROUS
Engineering SET
Université catholique de Louvain UTBM
Belgique Belfort-Montbéliard

Alexandre CAMINADA Laurent NAJMAN
SET LIGM
UTBM ESIEE
Belfort-Montbéliard Noisy le Grand

HEVALIER AKIB Cédric C Amir N
Sandia National Laboratories LiSSi
Albuquerque Université Paris-Est Créteil
New Mexico Créteil
Etats-Unis
Mustapha OUGHDI
URAND Nicolas D SET
POM UTBM
DSNA/DTI/R&D Belfort-Montbéliard
Toulouse
François PELLEGRINI
Alain GUÉNOCHE INRIA
IML Bordeaux Sud-Ouest - LaBRI
CNRS Institut polytechnique de Bordeaux
Marseille Talence Laurence REBOUL Hugues TALBOT
Laboratoir de Mathématiques et LIGM
Applications ESIEE
Université de Poitiers Noisy le Grand
Poitiers

Patrick SIARRY
LiSSi
Université Paris-Est Créteil
Créteil

Tabledesmatières
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
Charles-EdmondBICHOT, Patrick SIARRY
Chapitre1.Introductiongénéraleaupartitionnementdegraphe . . . . . . 23
Charles-EdmondBICHOT
1.1. Lepartitionnement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.2. Notionsmathématiques . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.3. Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
1.4. Descriptionformelleduproblèmedupartitionnementdegraphe . . . . 31
1.5. Fonctionsobjectifspourlepartitionnementdegraphe . . . . . . . . . . 33
1.6. Lepartitionnementcontraint . . . . . . . . . . . . . . . . . . . . . . . . 35
1.7. Lepartitionnementnoncontraint . . . . . . . . . . . . . . . . . . . . . . 37
1.8. Différencesentrepartitionnementcontraintetnoncontraint . . . . . . 39
1.9. Delabissectionauk-partitionnement:labissectionrécursive . . . . . 39
1.9.1. Créerunepartitionavecpournombredepartieunepuissancede2 40
1.9.2. Créerunek-partitionenutilisantlabalancedepartitionnement . 42
1.10. NP-difﬁcultédesproblèmesdepartitionnement . . . . . . . . . . . . . 42
1.10.1. Lecasdupartitionnementcontraint . . . . . . . . . . . . . . . . 42
1.10.2. Lecasdupartitionnementnoncontraint . . . . . . . . . . . . . . 43
1.10.2.1. NP-difﬁcultédelacoupenormalisée . . . . . . . . . . . . . 43
1.10.2.2. NP-difﬁcultéduratiodecoupe . . . . . . . . . . . . . . . . 44
1.11. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
1.12. Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
PREMIÈRE PARTIE. APPROCHE POUR LE CALCUL NUMÉRIQUE . . . . . 49
Chapitre2.Laméthodemulti-niveaux . . . . . . . . . . . . . . . . . . . . . . 51
Charles-EdmondBICHOT
2.1. Introduction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.2. Principesdelaméthodemulti-niveaux . . . . . . . . . . . . . . . . . . 5210 Partitionnementdegraphe
2.3. Contractiondugraphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.3.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.3.2. Appariementd’ungraphe . . . . . . . . . . . . . . . . . . . . . . . 56
2.3.3. L’algorithmedecontractiond’Hendrickson-Leland . . . . . . . . 57
2.3.4. Algorithmedecontractiondelapluslourdearête(HEM) . . . . . 57
2.4. Partitionnementdugrapheréduit . . . . . . . . . . . . . . . . . . . . . . 59
2.4.1. Desméthodesdepartitionnementéprouvées . . . . . . . . . . . . 59
2.4.2. Lesméthodesd’expansionderégion . . . . . . . . . . . . . . . . 60
2.4.2.1. Descriptiongénérale. . . . . . . . . . . . . . . . . . . . . . . 60
2.4.2.2. GraphGrowingPartitioningalgorithm(GGP) . . . . . . . . 61
2.4.2.3. GreedyGraphGrowingPartitioningalgorithm(GGGP). . . 62
2.5. Afﬁnageetexpansiondugraphe . . . . . . . . . . . . . . . . . . . . . . 63
2.5.1. Présentationdelaphased’afﬁnageetd’expansiondugraphe . . . 63
2.5.2. L’algorithmedeKernighan-Lin . . . . . . . . . . . . . . . . . . . 64
2.5.2.1. Principegénéral . . . . . . . . . . . . . . . . . . . . . . . . . 64
2.5.2.2. L’algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
2.5.2.3. AméliorationsproposéesparB.KernighanetS.Lin. . . . . 67
2.5.2.4. Complexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.5.2.5. Partiesdetaillesdifférentes. . . . . . . . . . . . . . . . . . . 68
2.5.2.6. Sommetsdepoidsdifférents . . . . . . . . . . . . . . . . . . 68
2.5.2.7. Autresaméliorationsdel’algorithmedeKernighan-Lin . . . 68
2.5.3. L’implémentationdeFiduccia-Mattheyses . . . . . . . . . . . . . 69
2.5.4. Adaptationauk-partitionnementdirect . . . . . . . . . . . . . . . 71
2.5.5. GlobalKernighan-Linreﬁnement . . . . . . . . . . . . . . . . . . 71
2.5.6. Algorithmed’afﬁnagedeWalshaw-Cross . . . . . . . . . . . . . . 73
2.6. Laméthodespectrale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
2.6.1. Présentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
2.6.2. Quelquesrésultatsd’analysenumérique. . . . . . . . . . . . . . . 76
2.6.3. TrouverlesvaleurspropresdelamatriceLaplaciennedugraphe . 78
2.6.4. Borneinférieurepourlepartitionnementdegraphecontraint . . . 79
2.6.5. Méthodesspectralespourlepartitionnementcontraint . . . . . . 80
2.6.6. Méthodesspectralespourlepartitionnementnoncontraint . . . . 81
2.6.6.1. Leratiodecoupe . . . . . . . . . . . . . . . . . . . . . . . . 82
2.6.6.2. Lacoupenormalisée . . . . . . . . . . . . . . . . . . . . . . 82
2.6.7. Problèmesetaméliorations . . . . . . . . . . . . . . . . . . . . . . 82
2.7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2.8. Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
Chapitre3.Lepartitionnementd’hypergraphe . . . . . . . . . . . . . . . . 89
Cédric CHEVALIER
3.1. Déﬁnitionsetmétriques . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
3.1.1. Hypergrapheetpartitionnement . . . . . . . . . . . . . . . . . . . 89Tabledesmatières 11
3.1.2. Métriquespourlepartitionnementd’hypergraphe . . . . . . . . . 91
3.2. Relationsentregraphes,hypergraphesetmatrices . . . . . . . . . . . . 91
3.3. Algorithmespourlepartitionnementd’hypergraphe . . . . . . . . . . . 93
3.3.1. Contraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
3.3.2. Partitionnementinitialetafﬁnage . . . . . . . . . . . . . . . . . . 96
3.3.3. Afﬁnage. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.4. Utilisations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
3.4.1. Intérêtsdupartitionnementd’hypergraphe . . . . .