Graph Partitioning

Charles-Edmond Bichot, Institution école Centrale de Lyon.Patrick Siarry, University Paris-Est Créteil (UPEC).

• Introduction xiiiCharles-Edmond Bichot, Patrick SiarryChapter 1. General Introduction to Graph Partitioning 1Charles-Edmond Bichot1.1. Partitioning 11.2. Mathematical notions 21.3. Graphs 41.4. Formal description of the graph partitioning problem 81.5. Objective functions for graph partitioning 111.6. Constrained graph partitioning 131.7. Unconstrained graph partitioning 141.8. Differences between constrained and unconstrained partitioning 161.9. From bisection to k-partitioning: the recursive bisection method 171.10. NP-hardness of graph partitioning optimization problems 191.11. Conclusion 221.12. Bibliography 22Part 1: Graph Partitioning for Numerical Analysis 27Chapter 2. A Partitioning Requiring Rapidity and Quality: The Multilevel Method and Partitions Refinement Algorithms 29Charles-Edmond Bichot2.1. Introduction 292.2. Principles of the multilevel method 302.3. Graph coarsening 332.4. Partitioning of the coarsened graph 372.5. Uncoarsening and partitions refinement 402.6. The spectral method 522.7. Conclusion 592.8. Bibliography 60Chapter 3. Hypergraph Partitioning 65Cédric Chevalier3.1. Definitions and metrics 653.2. Connections between graphs, hypergraphs, and matrices 673.3. Algorithms for hypergraph partitioning 683.4. Purpose 723.5. Conclusion 773.6. Software references 783.7. Bibliography 78Chapter 4. Parallelization of Graph Partitioning 81François Pellegrini4.1. Introduction 814.2. Distributed data structures 844.3. Parallelization of the coarsening phase 874.4. Folding 934.5. Centralization 954.6. Parallelization of the refinement phase 964.7. Experimental results 1074.8. Conclusion 1114.9. Bibliography 111Chapter 5. Static Mapping of Process Graphs 115François Pellegrini5.1. Introduction 1155.2. Static mapping models 1165.3. Exact algorithms 1215.4. Approximation algorithms 1235.5. Conclusion 1335.6. Bibliography 134Part 2: Optimization Methods for Graph Partitioning 137Chapter 6. Local Metaheuristics and Graph Partitioning 139Charles-Edmond Bichot6.1. General introduction to metaheuristics 1406.2. Simulated annealing 1416.3. Iterated local search 1496.4. Other local search metaheuristics 1586.5. Conclusion 1596.6. Bibliography 159Chapter 7. Population-based Metaheuristics, Fusion-Fission and Graph Partitioning Optimization 163Charles-Edmond Bichot7.1. Ant colony algorithms 1637.2. Evolutionary algorithms 1657.3. The fusion-fission method 1827.4. Conclusion 1957.5. Acknowledgments 1967.6. Bibliography 196Chapter 8. Partitioning Mobile Networks into Tariff Zones 201Mustapha Oughdi, Sid Lamrous, Alexandre Caminada8.1. Introduction 2018.2. Spatial division of the network 2088.3. Experimental results 2208.4. Conclusion 2228.5. Bibliography 223Chapter 9. Air Traffic Control Graph Partitioning Application 225Charles-Edmond Bichot, Nicolas Durand9.1. Introduction 2259.2. The problem of dividing up the airspace 2279.3. Modeling the problem 2319.4. Airspace partitioning: towards a new optimization metaheuristic 2379.5. Division of the central European airspace 2409.6. Conclusion 2469.7. Acknowledgments 2479.8. Bibliography 247Part 3: Other Approaches to Graph Partitioning 249Chapter 10. Application of Graph Partitioning to Image Segmentation 251Amir Nakib, Laurent Najman, Hugues Talbot, Patrick Siarry10.1. Introduction 25110.2. The image viewed in graph form 25110.3. Principle of image segmentation using graphs 25410.4. Image segmentation via maximum flows 25710.5. Unification of segmentation methods via graph theory 26510.6. Conclusions and perspectives 26910.7. Bibliography 271Chapter 11. Distances in Graph Partitioning 275Alain Guénoche11.1. Introduction 27511.2. The Dice distance 27611.3. Pons-Latapy distance 28111.4. A partitioning method for distance arrays 28311.5. A simulation protocol 28611.6. Conclusions 29211.7. Acknowledgments 29311.8. Bibliography 293Chapter 12. Detection of Disjoint or Overlapping Communities in Networks 297Jean-Baptiste Angelelli, Alain Guénoche, Laurence Reboul12.1. Introduction 29712.2. Modularity of partitions and coverings 29912.3. Partitioning method 30112.4. Overlapping partitioning methods 30712.5. Conclusion 31112.6. Acknowledgments 31212.7. Bibliography 312Chapter 13. Multilevel Local Optimization of Modularity 315Thomas Aynaud, Vincent D. Blondel, Jean-Loup Guillaume and Renaud Lambiotte13.1. Introduction 31513.2. Basics of modularity 31713.3. Modularity optimization 31913.4. Validation on empirical and artificial graphs 32713.5. Discussion 33313.6. Conclusion 34113.7. Acknowledgments 34213.8. Bibliography 342Appendix. The Main Tools and Test Benches for Graph Partitioning 347Charles-Edmond BichotA.1. Tools for constrained graph partitioning optimization 348A.2. Tools for unconstrained graph partitioning optimization 350A.3. Graph partitioning test benches 351A.4. Bibliography 354Glossary 357List of Authors 361Index 365