Cover -- Graph Partitioning -- Title Page -- Copyright Page -- Table of Contents -- Introduction -- Chapter 1. General Introduction to Graph Partitioning -- 1.1. Partitioning -- 1.2. Mathematical notions -- 1.3. Graphs -- 1.4. Formal description of the graph partitioning problem -- 1.5. Objective functions for graph partitioning -- 1.6. Constrained graph partitioning -- 1.7. Unconstrained graph partitioning -- 1.8. Differences between constrained and unconstrained partitioning -- 1.9. From bisection to k-partitioning: he recursive bisection method -- 1.9.1. Creating a partition with a number of parts a power of 2, from a graph bisection algorithm -- 1.9.2. Creating a k-partition from a graph bisection algorithm using the partitioning balance -- 1.10. NP-hardness of graph partitioning optimization problems -- 1.10.1. The case of constrained graph partitioning -- 1.10.2. The case of unconstrained graph partitioning -- 1.11. Conclusion -- 1.12. Bibliography -- PART 1: GRAPH PARTITIONING FOR NUMERICAL ANALYSIS -- Chapter 2. A Partitioning Requiring Rapidity and Quality: The Multilevel Method and Partitions Refinement Algorithms -- 2.1. Introduction -- 2.2. Principles of the multilevel method -- 2.3. Graph coarsening -- 2.3.1. Introduction -- 2.3.2. Graph matching -- 2.3.3. Hendrickson-Leland coarsening algorithm -- 2.3.4. The Heavy Edge Matching (HEM) algorithm -- 2.4. Partitioning of the coarsened graph -- 2.4.1. State-of-the-art partitioning methods -- 2.4.2. Region growing methods -- 2.5. Uncoarsening and partitions refinement -- 2.5.1. Presentation of the uncoarsening and refinement phase -- 2.5.2. The Kernighan-Lin algorithm -- 2.5.3. Fiduccia-Mattheyses implementation -- 2.5.4. Adaptation to direct k-partitioning -- 2.5.5. Global Kernighan-Lin Refinement -- 2.5.6. The Walshaw-Cross refinement algorithm -- 2.6. The spectral method.

2.6.1. Presentation -- 2.6.2. Some results of numerical system -- 2.6.3. Finding the eigenvalues of the Laplacian matrix of a graph -- 2.6.4. Lower bound for constrained graph partitioning -- 2.6.5. Spectral methods for contrained partitioning -- 2.6.6. Spectral methods for unconstrained graph partitioning -- 2.6.7. Problems and improvements -- 2.7. Conclusion -- 2.8. Bibliography -- Chapter 3. Hypergraph Partitioning -- 3.1. Definitions and metrics -- 3.1.1. Hypergraph and partitioning -- 3.1.2. Metrics for hypergraph partitioning -- 3.2. Connections between graphs, hypergraphs, and matrices -- 3.3. Algorithms for hypergraph partitioning -- 3.3.1. Coarsening -- 3.3.2. Initial partitioning and uncoarsening and refinement -- 3.3.3. Uncoarsening and refinement -- 3.4. Purpose -- 3.4.1. Hypergraph partitioning benefits -- 3.4.2. Matrix partitioning -- 3.4.3. Practical results -- 3.4.4. Repartitioning -- 3.4.5. Use of hypergraphs within a mesh partitioning context -- 3.4.6. Other applications -- 3.5. Conclusion -- 3.6. Software references -- 3.7. Bibliography -- Chapter 4. Parallelization of Graph Partitioning -- 4.1. Introduction -- 4.1.1. Need for parallelism -- 4.1.2. Multilevel framework -- 4.2. Distributed data structures -- 4.3. Parallelization of the coarsening phase -- 4.3.1. Construction of the coarse graph -- 4.3.2. Parallel matching algorithms -- 4.3.3. Collision reduction at process level -- 4.3.4. Collision reduction at vertex level -- 4.4. Folding -- 4.5. Centralization -- 4.6. Parallelization of the refinement phase -- 4.6.1. Parallelization of the local refinement methods -- 4.6.2. Band graphs -- 4.6.3. Multi-centralization -- 4.6.4. Parallelization of the global refinement methods -- 4.7. Experimental results -- 4.8. Conclusion -- 4.9. Bibliography -- Chapter 5. Static Mapping of Process Graphs -- 5.1. Introduction.

5.2. Static mapping models -- 5.2.1. Cost functions -- 5.2.2. Heterogeneity of target architectures -- 5.3. Exact algorithms -- 5.4. Approximation algorithms -- 5.4.1. Global methods -- 5.4.2. Recursive methods -- 5.5. Conclusion -- 5.6. Bibliography -- PART 2: OPTIMIZATION METHODS FOR GRAPH PARTITIONING -- Chapter 6. Local Metaheuristics and Graph Partitioning -- 6.1. General introduction to metaheuristics -- 6.2. Simulated annealing -- 6.2.1. Description of the simulated annealing algorithm -- 6.2.2. Adaptation of simulated annealing to the graph bisection problem -- 6.2.3. Generalizing this adaptation to k-partitioning -- 6.2.4. Assessment of simulated annealing adaptation to graph partitioning -- 6.3. Iterated local search -- 6.3.1. Presentation of iterated local search -- 6.3.2. Simple adaptation of iterated local search to graph partitioning -- 6.3.3. Iterated local search and multilevel method -- 6.4. Other local search metaheuristics -- 6.4.1. Greedy algorithms -- 6.4.2. Tabu search -- 6.5. Conclusion -- 6.6. Bibliography -- Chapter 7. Population-based Metaheuristics, Fusion-Fission and Graph Partitioning Optimization -- 7.1. Ant colony algorithms -- 7.2. Evolutionary algorithms -- 7.2.1. Genetic algorithms -- 7.2.2. Standard process of genetic algorithm adaptation to graph partitioning -- 7.2.3. The GA's adaptation to graph bisection optimization of BUI and MOON -- 7.2.4. Multilevel evolutionary algorithm of Soper-Walshaw-Cross -- 7.2.5. Other adaptations of evolutionary algorithms to graph partitioning optimization -- 7.3. The fusion-fission method -- 7.3.1. Introduction -- 7.3.2. Fusion-fission method principles -- 7.3.3. Algorithm -- 7.3.4. Selection of the multilevel algorithm -- 7.3.5. Creation of the sequence of number of parts -- 7.3.6. Selection of the refinement algorithm -- 7.3.7. Evaluation -- 7.4. Conclusion.

7.5. Acknowledgments -- 7.6. Bibliography -- Chapter 8. Partitioning Mobile Networks into Tariff Zones -- 8.1. Introduction -- 8.1.1. Scheduled rating model -- 8.1.2. Rating model for a network -- 8.2. Spatial division of the network -- 8.2.1. Definitions -- 8.2.2. Formalization of the space division problem -- 8.2.3. Resolution of the space division problem by a genetic algorithm -- 8.3. Experimental results -- 8.4. Conclusion -- 8.5. Bibliography -- Chapter 9. Air Traffic Control Graph Partitioning Application -- 9.1. Introduction -- 9.2. The problem of dividing up the airspace -- 9.2.1. Creation of functional airspace blocks in Europe -- 9.2.2. Creation of a functional block in central Europe -- 9.3. Modeling the problem -- 9.3.1. Control workload in a sector -- 9.3.2. Objective: minimizing the coordination workload -- 9.3.3. Two constraints, the size of the qualification areas and size of the control centers -- 9.3.4. Analysis and processing of European air traffic data -- 9.3.5. Graph of European air traffic and adaptation to partitioning -- 9.4. Airspace partitioning: towards a new optimization metaheuristic -- 9.5. Division of the central European airspace -- 9.6. Conclusion -- 9.7. Acknowledgments -- 9.8. Bibliography -- PART 3: OTHER APPROACHES TO GRAPH PARTITIONING -- Chapter 10. Application of Graph Partitioning to Image Segmentation -- 10.1. Introduction -- 10.2. The image viewed in graph form -- 10.3. Principle of image segmentation using graphs -- 10.3.1. Choice of arc weights for segmentation -- 10.4. Image segmentation via maximum flows -- 10.4.1. Maximum flows for energy minimization -- 10.4.2. Minimal geodesics and surfaces -- 10.4.3. Minimum geodesics and surfaces via maximum flows -- 10.4.4. Continuous maximum flows -- 10.5. Unification of segmentation methods via graph theory -- 10.6. Conclusions and perspectives.

10.7. Bibliography -- Chapter 11. Distances in Graph Partitioning -- 11.1. Introduction -- 11.2. The Dice distance -- 11.2.1. Two extensions to weighted graphs -- 11.3. Pons-Latapy distance -- 11.4. A partitioning method for distance arrays -- 11.5. A simulation protocol -- 11.5.1. A random graph generator -- 11.5.2. Quality of the computed partition -- 11.5.3. Results -- 11.6. Conclusions -- 11.7. Acknowledgments -- 11.8. Bibliography -- Chapter 12. Detection of Disjoint or Overlapping Communities in Networks -- 12.1. Introduction -- 12.2. Modularity of partitions and coverings -- 12.3. Partitioning method -- 12.3.1. Fusion and/or fission of clusters -- 12.3.2. Algorithm complexity -- 12.3.3. Simulations -- 12.4. Overlapping partitioning methods -- 12.4.1. Fusion of overlapping classes -- 12.4.2. Simulations -- 12.5. Conclusion -- 12.6. Acknowledgments -- 12.7. Bibliography -- Chapter 13. Multilevel Local Optimization of Modularity -- 13.1. Introduction -- 13.2. Basics of modularity -- 13.3. Modularity optimization -- 13.3.1. Existing methods -- 13.3.2. Known limitations -- 13.3.3. Louvain method -- 13.3.4. Modularity increase -- 13.3.5. Convergence of the algorithm -- 13.4. Validation on empirical and artificial graphs -- 13.4.1. Artificial graphs -- 13.4.2. Empirical graphs -- 13.5. Discussion -- 13.5.1. Influence of the processing order of vertices -- 13.5.2. Intermediate communities -- 13.5.3. Possible improvements -- 13.5.4. Known uses -- 13.6. Conclusion -- 13.7. Acknowledgments -- 13.8. Bibliography -- Appendix. The Main Tools and Test Benches for Graph Partitioning -- A.1. Tools for constrained graph partitioning optimization -- A.1.1. Chaco -- A.1.2. Metis -- A.1.3. Scotch -- A.1.4. Jostle -- A.1.5. Party -- A.2. Tools for unconstrained graph partitioning optimization -- A.2.1. Graclus -- A.3. Graph partitioning test benches.

A.3.1. Graph partitioning archives of Walshaw.