GraphPartitioning Graph Partitioning Edited by Charles-Edmond Bichot Patrick Siarry Firstpublished2011inGreatBritainandtheUnitedStatesbyISTELtdandJohnWiley&Sons,Inc. Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permittedundertheCopyright,DesignsandPatentsAct1988,thispublicationmayonlybereproduced, storedortransmitted,inanyformorbyanymeans,withthepriorpermissioninwritingofthepublishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentionedaddress: ISTELtd JohnWiley&Sons,Inc. 27-37StGeorge’sRoad 111RiverStreet LondonSW194EU Hoboken,NJ07030 UK USA www.iste.co.uk www.wiley.com ©ISTELtd2011 TherightsofCharles-EdmondBichotandPatrickSiarrytobeidentifiedastheauthorsofthisworkhave beenassertedbytheminaccordancewiththeCopyright,DesignsandPatentsAct1988. ____________________________________________________________________________________ LibraryofCongressCataloging-in-PublicationData Graphpartitioning/editedbyCharles-EdmondBichot,PatrickSiarry. p.cm. Includesbibliographicalreferencesandindex. ISBN978-1-84821-233-6 1. Partitions(Mathematics)2. Graphtheory. I.Bichot,Charles-Edmond.II.Siarry,Patrick. QA76.165.G732011 512.7'3--dc23 2011028388 BritishLibraryCataloguing-in-PublicationData ACIPrecordforthisbookisavailablefromtheBritishLibrary ISBN978-1-84821-233-6 PrintedandboundinGreatBritainbyCPIGroup(UK)Ltd.,Croydon,SurreyCR04YY Table of Contents Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii Charles-EdmondBichot,PatrickSiarry Chapter1.GeneralIntroductiontoGraphPartitioning . . . . . . . . . . . 1 Charles-EdmondBichot 1.1.Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2.Mathematicalnotions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.3.Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4.Formaldescriptionofthegraphpartitioningproblem. . . . . . . . . . . 8 1.5.Objectivefunctionsforgraphpartitioning . . . . . . . . . . . . . . . . . 11 1.6.Constrainedgraphpartitioning . . . . . . . . . . . . . . . . . . . . . . . 13 1.7.Unconstrainedgraphpartitioning . . . . . . . . . . . . . . . . . . . . . . 14 1.8.Differencesbetweenconstrainedandunconstrainedpartitioning . . . . 16 1.9.Frombisectiontok-partitioning:therecursivebisectionmethod . . . . 17 1.9.1.Creatingapartitionwithanumberofpartsapowerof2,froma graphbisectionalgorithm . . . . . . . . . . . . . . . . . . . . . . . 17 1.9.2.Creatingak-partitionfromagraphbisectionalgorithmusingthe partitioningbalance . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.10.NP-hardnessofgraphpartitioningoptimizationproblems . . . . . . . 19 1.10.1.Thecaseofconstrainedgraphpartitioning . . . . . . . . . . . . . 19 1.10.2.Thecaseofunconstrainedgraphpartitioning . . . . . . . . . . . 20 1.11.Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.12.Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 Part1:GraphPartitioningforNumericalAnalysis . . . . . . . . . 27 Chapter2.APartitioningRequiringRapidityandQuality:TheMultilevel MethodandPartitionsRefinementAlgorithms . . . . . . . . . . . . . . . . . 29 Charles-EdmondBichot 2.1.Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2.Principlesofthemultilevelmethod . . . . . . . . . . . . . . . . . . . . . 30 vi GraphPartitioning 2.3.Graphcoarsening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3.1.Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3.2.Graphmatching. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3.3.Hendrickson-Lelandcoarseningalgorithm. . . . . . . . . . . . . . 34 2.3.4.TheHeavyEdgeMatching(HEM)algorithm . . . . . . . . . . . . 35 2.4.Partitioningofthecoarsenedgraph . . . . . . . . . . . . . . . . . . . . . 37 2.4.1.State-of-the-artpartitioningmethods . . . . . . . . . . . . . . . . . 37 2.4.2.Regiongrowingmethods . . . . . . . . . . . . . . . . . . . . . . . 38 2.5.Uncoarseningandpartitionsrefinement . . . . . . . . . . . . . . . . . . 40 2.5.1.Presentationoftheuncoarseningandrefinement phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 2.5.2.TheKernighan-Linalgorithm . . . . . . . . . . . . . . . . . . . . . 41 2.5.3.Fiduccia-Mattheysesimplementation. . . . . . . . . . . . . . . . . 46 2.5.4.Adaptationtodirectk-partitioning . . . . . . . . . . . . . . . . . . 47 2.5.5.GlobalKernighan-LinRefinement . . . . . . . . . . . . . . . . . . 48 2.5.6.TheWalshaw-Crossrefinementalgorithm . . . . . . . . . . . . . . 50 2.6.Thespectralmethod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.6.1.Presentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.6.2.Someresultsofnumericalsystem . . . . . . . . . . . . . . . . . . 52 2.6.3.FindingtheeigenvaluesoftheLaplacianmatrixofa graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.6.4.Lowerboundforconstrainedgraphpartitioning . . . . . . . . . . 56 2.6.5.Spectralmethodsforcontrainedpartitioning . . . . . . . . . . . . 56 2.6.6.Spectralmethodsforunconstrainedgraphpartitioning . . . . . . . 57 2.6.7.Problemsandimprovements . . . . . . . . . . . . . . . . . . . . . 58 2.7.Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.8.Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 Chapter3.HypergraphPartitioning . . . . . . . . . . . . . . . . . . . . . . . 65 CédricChevalier 3.1.Definitionsandmetrics. . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.1.1.Hypergraphandpartitioning. . . . . . . . . . . . . . . . . . . . . . 65 3.1.2.Metricsforhypergraphpartitioning. . . . . . . . . . . . . . . . . . 67 3.2.Connectionsbetweengraphs,hypergraphs,andmatrices. . . . . . . . . 67 3.3.Algorithmsforhypergraphpartitioning . . . . . . . . . . . . . . . . . . 68 3.3.1.Coarsening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.3.2.Initialpartitioninganduncoarseningandrefinement . . . . . . . . 71 3.3.3.Uncoarseningandrefinement . . . . . . . . . . . . . . . . . . . . . 71 3.4.Purpose . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.4.1.Hypergraphpartitioningbenefits . . . . . . . . . . . . . . . . . . . 72 3.4.2.Matrixpartitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.4.3.Practicalresults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 TableofContents vii 3.4.4.Repartitioning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.4.5.Useofhypergraphswithinameshpartitioning context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.4.6.Otherapplications . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.5.Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.6.Softwarereferences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 3.7.Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 Chapter4.ParallelizationofGraphPartitioning . . . . . . . . . . . . . . . 81 FrançoisPellegrini 4.1.Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.1.1.Needforparallelism . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.1.2.Multilevelframework . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.2.Distributeddatastructures . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.3.Parallelizationofthecoarseningphase . . . . . . . . . . . . . . . . . . . 87 4.3.1.Constructionofthecoarsegraph . . . . . . . . . . . . . . . . . . . 87 4.3.2.Parallelmatchingalgorithms . . . . . . . . . . . . . . . . . . . . . 87 4.3.3.Collisionreductionatprocesslevel. . . . . . . . . . . . . . . . . . 88 4.3.4.Collisionreductionatvertexlevel . . . . . . . . . . . . . . . . . . 89 4.4.Folding. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 4.5.Centralization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 4.6.Parallelizationoftherefinementphase . . . . . . . . . . . . . . . . . . . 96 4.6.1.Parallelizationofthelocalrefinementmethods . . . . . . . . . . . 96 4.6.2.Bandgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 4.6.3.Multi-centralization . . . . . . . . . . . . . . . . . . . . . . . . . . 101 4.6.4.Parallelizationoftheglobalrefinementmethods . . . . . . . . . . 102 4.7.Experimentalresults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 4.8.Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 4.9.Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 Chapter5.StaticMappingofProcessGraphs . . . . . . . . . . . . . . . . . 115 FrançoisPellegrini 5.1.Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 5.2.Staticmappingmodels . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 5.2.1.Costfunctions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 5.2.2.Heterogeneityoftargetarchitectures . . . . . . . . . . . . . . . . . 119 5.3.Exactalgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 5.4.Approximationalgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.4.1.Globalmethods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.4.2.Recursivemethods . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 5.5.Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 5.6.Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 viii GraphPartitioning Part2:OptimizationMethodsforGraphPartitioning . . . . . . . . 137 Chapter6.LocalMetaheuristicsandGraphPartitioning . . . . . . . . . . 139 Charles-EdmondBichot 6.1.Generalintroductiontometaheuristics . . . . . . . . . . . . . . . . . . . 140 6.2.Simulatedannealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 6.2.1.Descriptionofthesimulatedannealingalgorithm . . . . . . . . . . 142 6.2.2.Adaptationofsimulatedannealingtothegraph bisectionproblem. . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 6.2.3.Generalizingthisadaptationtok-partitioning . . . . . . . . . . . . 147 6.2.4.Assessmentofsimulatedannealingadaptation tographpartitioning . . . . . . . . . . . . . . . . . . . . . . . . . . 148 6.3.Iteratedlocalsearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 6.3.1.Presentationofiteratedlocalsearch . . . . . . . . . . . . . . . . . 149 6.3.2.Simpleadaptationofiteratedlocalsearch tographpartitioning . . . . . . . . . . . . . . . . . . . . . . . . . . 152 6.3.3.Iteratedlocalsearchandmultilevelmethod . . . . . . . . . . . . . 156 6.4.Otherlocalsearchmetaheuristics . . . . . . . . . . . . . . . . . . . . . . 158 6.4.1.Greedyalgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 6.4.2.Tabusearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 6.5.Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 6.6.Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 Chapter7.Population-basedMetaheuristics,Fusion-Fission andGraphPartitioningOptimization . . . . . . . . . . . . . . . . . . . . . . 163 Charles-EdmondBichot 7.1.Antcolonyalgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163 7.2.Evolutionaryalgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 7.2.1.Geneticalgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 7.2.2.Standardprocessofgeneticalgorithmadaptation tographpartitioning . . . . . . . . . . . . . . . . . . . . . . . . . . 169 7.2.3.TheGA’sadaptationtographbisectionoptimization ofBuiandMoon . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172 7.2.4.MultilevelevolutionaryalgorithmofSoper-Walshaw-Cross. . . . 177 7.2.5.Otheradaptationsofevolutionaryalgorithmstograph partitioningoptimization. . . . . . . . . . . . . . . . . . . . . . . . 180 7.3.Thefusion-fissionmethod . . . . . . . . . . . . . . . . . . . . . . . . . . 182 7.3.1.Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182 7.3.2.Fusion-fissionmethodprinciples . . . . . . . . . . . . . . . . . . . 184 7.3.3.Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 7.3.4.Selectionofthemultilevelalgorithm . . . . . . . . . . . . . . . . . 187 7.3.5.Creationofthesequenceofnumberofparts. . . . . . . . . . . . . 188 7.3.6.Selectionoftherefinementalgorithm . . . . . . . . . . . . . . . . 189 TableofContents ix 7.3.7.Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191 7.4.Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 7.5.Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 7.6.Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 Chapter8.PartitioningMobileNetworksintoTariffZones . . . . . . . . . 201 MustaphaOughdi,SidLamrous,AlexandreCaminada 8.1.Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 8.1.1.Scheduledratingmodel . . . . . . . . . . . . . . . . . . . . . . . . 201 8.1.2.Ratingmodelforanetwork . . . . . . . . . . . . . . . . . . . . . . 204 8.2.Spatialdivisionofthenetwork . . . . . . . . . . . . . . . . . . . . . . . 208 8.2.1.Definitions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 8.2.2.Formalizationofthespacedivisionproblem . . . . . . . . . . . . 212 8.2.3.Resolutionofspacedivisionbyageneticalgorithm . . . . . . . . 216 8.3.Experimentalresults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 8.4.Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 8.5.Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 Chapter9.AirTrafficControlGraphPartitioningApplication . . . . . . . 225 Charles-EdmondBichot,NicolasDurand 9.1.Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 9.2.Theproblemofdividinguptheairspace . . . . . . . . . . . . . . . . . . 227 9.2.1.CreationoffunctionalairspaceblocksinEurope . . . . . . . . . . 228 9.2.2.CreationofafunctionalblockincentralEurope . . . . . . . . . . 230 9.3.Modelingtheproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 9.3.1.Controlworkloadinasector . . . . . . . . . . . . . . . . . . . . . 231 9.3.2.Objective:minimizingthecoordinationworkload . . . . . . . . . 232 9.3.3.Twoconstraints,thesizeofthequalificationareas andsizecontrolcenters . . . . . . . . . . . . . . . . . . . . . . . . 232 9.3.4.AnalysisandprocessingofEuropeanairtrafficdata . . . . . . . . 233 9.3.5.GraphofEuropeanairtrafficandadaptationtopartitioning . . . . 234 9.4.Airspacepartitioning:towardsanewoptimizationmetaheuristic . . . . 237 9.5.DivisionofthecentralEuropeanairspace . . . . . . . . . . . . . . . . . 240 9.6.Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 9.7.Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 9.8.Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247 Part3:OtherApproachestoGraphPartitioning . . . . . . . . . . . 249 Chapter10.ApplicationofGraphPartitioning toImageSegmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 AmirNakib,LaurentNajman,HuguesTalbot,PatrickSiarry 10.1.Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 10.2.Theimageviewedingraphform . . . . . . . . . . . . . . . . . . . . . 251 x GraphPartitioning 10.3.Principleofimagesegmentationusinggraphs . . . . . . . . . . . . . . 254 10.3.1.Choiceofarcweightsforsegmentation. . . . . . . . . . . . . . . 255 10.4.Imagesegmentationviamaximumflows . . . . . . . . . . . . . . . . . 257 10.4.1.Maximumflowsforenergyminimization . . . . . . . . . . . . . 257 10.4.2.Minimalgeodesicsandsurfaces . . . . . . . . . . . . . . . . . . . 259 10.4.3.Minimumgeodesicsandsurfacesviamaximumflows . . . . . . 263 10.4.4.Continuousmaximumflows . . . . . . . . . . . . . . . . . . . . . 265 10.5.Unificationofsegmentationmethodsviagraphtheory . . . . . . . . . 265 10.6.Conclusionsandperspectives . . . . . . . . . . . . . . . . . . . . . . . 269 10.7.Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 Chapter11.DistancesinGraphPartitioning . . . . . . . . . . . . . . . . . . 275 AlainGuénoche 11.1.Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 11.2.TheDicedistance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 276 11.2.1.Twoextensionstoweightedgraphs . . . . . . . . . . . . . . . . . 278 11.3.Pons-Latapydistance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 11.4.Apartitioningmethodfordistancearrays . . . . . . . . . . . . . . . . . 283 11.5.Asimulationprotocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286 11.5.1.Arandomgraphgenerator . . . . . . . . . . . . . . . . . . . . . . 286 11.5.2.Qualityofthecomputedpartition . . . . . . . . . . . . . . . . . . 286 11.5.3.Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 11.6.Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292 11.7.Acknowledgments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 11.8.Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 Chapter12.DetectionofDisjointorOverlapping CommunitiesinNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 Jean-BaptisteAngelelli,AlainGuénoche,LaurenceReboul 12.1.Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 12.2.Modularityofpartitionsandcoverings . . . . . . . . . . . . . . . . . . 299 12.3.Partitioningmethod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 12.3.1.Fusionand/orfissionofclusters . . . . . . . . . . . . . . . . . . . 302 12.3.2.Algorithmcomplexity . . . . . . . . . . . . . . . . . . . . . . . . 303 12.3.3.Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 303 12.4.Overlappingpartitioningmethods . . . . . . . . . . . . . . . . . . . . . 307 12.4.1.Fusionofoverlappingclasses . . . . . . . . . . . . . . . . . . . . 308 12.4.2.Simulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309 12.5.Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 12.6.Acknowledgments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312 12.7.Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312 TableofContents xi Chapter13.MultilevelLocalOptimizationofModularity . . . . . . . . . . 315 ThomasAynaud,VincentD.Blondel,Jean-LoupGuillaume andRenaudLambiotte 13.1.Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315 13.2.Basicsofmodularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317 13.3.Modularityoptimization . . . . . . . . . . . . . . . . . . . . . . . . . . 319 13.3.1.Existingmethods . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 13.3.2.Knownlimitations . . . . . . . . . . . . . . . . . . . . . . . . . . 320 13.3.3.Louvainmethod . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321 13.3.4.Modularityincrease . . . . . . . . . . . . . . . . . . . . . . . . . . 324 13.3.5.Convergenceofthealgorithm . . . . . . . . . . . . . . . . . . . . 325 13.4.Validationonempiricalandartificialgraphs . . . . . . . . . . . . . . . 327 13.4.1.Artificialgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328 13.4.2.Empiricalgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 331 13.5.Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333 13.5.1.Influenceoftheprocessingorderofvertices . . . . . . . . . . . . 333 13.5.2.Intermediatecommunities . . . . . . . . . . . . . . . . . . . . . . 334 13.5.3.Possibleimprovements . . . . . . . . . . . . . . . . . . . . . . . . 337 13.5.4.Knownuses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 340 13.6.Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 13.7.Acknowledgments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 13.8.Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 Appendix.TheMainToolsandTestBenchesforGraphPartitioning . . . . 347 Charles-EdmondBichot A.1. Toolsforconstrainedgraphpartitioningoptimization . . . . . . . . 348 A.1.1.Chaco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 A.1.2.Metis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 A.1.3.Scotch. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 A.1.4.Jostle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 A.1.5.Party . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350 A.2. Toolsforunconstrainedgraphpartitioningoptimization. . . . . . . 350 A.2.1.Graclus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 A.3. Graphpartitioningtestbenches . . . . . . . . . . . . . . . . . . . . 351 A.3.1.GraphpartitioningarchivesofWalshaw . . . . . . . . . . . . 351 A.3.2.Othertestbenches . . . . . . . . . . . . . . . . . . . . . . . . . 353 A.4. Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354 Glossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 ListofAuthors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365