Graph Partitioning

<p>Introduction xiii<br /> Charles–Edmond Bichot, Patrick Siarry</p>
<p>Chapter 1. General Introduction to Graph Partitioning 1<br /> Charles–Edmond Bichot</p>
<p>1.1. Partitioning 1</p>
<p>1.2. Mathematical notions 2</p>
<p>1.3. Graphs 4</p>
<p>1.4. Formal description of the graph partitioning problem 8</p>
<p>1.5. Objective functions for graph partitioning 11</p>
<p>1.6. Constrained graph partitioning 13</p>
<p>1.7. Unconstrained graph partitioning 14</p>
<p>1.8. Differences between constrained and unconstrained partitioning 16</p>
<p>1.9. From bisection to k–partitioning: the recursive bisection method 17</p>
<p>1.10. NP–hardness of graph partitioning optimization problems 19</p>
<p>1.11. Conclusion 22</p>
<p>1.12. Bibliography 22</p>
<p>Part 1: Graph Partitioning for Numerical Analysis 27</p>
<p>Chapter 2. A Partitioning Requiring Rapidity and Quality: The Multilevel Method and Partitions Refinement Algorithms 29<br /> Charles–Edmond Bichot</p>
<p>2.1. Introduction 29</p>
<p>2.2. Principles of the multilevel method 30</p>
<p>2.3. Graph coarsening 33</p>
<p>2.4. Partitioning of the coarsened graph 37</p>
<p>2.5. Uncoarsening and partitions refinement 40</p>
<p>2.6. The spectral method 52</p>
<p>2.7. Conclusion 59</p>
<p>2.8. Bibliography 60</p>
<p>Chapter 3. Hypergraph Partitioning 65<br /> C&eacute;dric Chevalier</p>
<p>3.1. Definitions and metrics 65</p>
<p>3.2. Connections between graphs, hypergraphs, and matrices 67</p>
<p>3.3. Algorithms for hypergraph partitioning 68</p>
<p>3.4. Purpose 72</p>
<p>3.5. Conclusion 77</p>
<p>3.6. Software references 78</p>
<p>3.7. Bibliography 78</p>
<p>Chapter 4. Parallelization of Graph Partitioning 81<br /> Fran&ccedil;ois Pellegrini</p>
<p>4.1. Introduction 81</p>
<p>4.2. Distributed data structures 84</p>
<p>4.3. Parallelization of the coarsening phase 87</p>
<p>4.4. Folding 93</p>
<p>4.5. Centralization 95</p>
<p>4.6. Parallelization of the refinement phase 96</p>
<p>4.7. Experimental results 107</p>
<p>4.8. Conclusion 111</p>
<p>4.9. Bibliography 111</p>
<p>Chapter 5. Static Mapping of Process Graphs 115<br /> Fran&ccedil;ois Pellegrini</p>
<p>5.1. Introduction 115</p>
<p>5.2. Static mapping models 116</p>
<p>5.3. Exact algorithms 121</p>
<p>5.4. Approximation algorithms 123</p>
<p>5.5. Conclusion 133</p>
<p>5.6. Bibliography 134</p>
<p>Part 2: Optimization Methods for Graph Partitioning 137</p>
<p>Chapter 6. Local Metaheuristics and Graph Partitioning 139<br /> Charles–Edmond Bichot</p>
<p>6.1. General introduction to metaheuristics 140</p>
<p>6.2. Simulated annealing 141</p>
<p>6.3. Iterated local search 149</p>
<p>6.4. Other local search metaheuristics 158</p>
<p>6.5. Conclusion 159</p>
<p>6.6. Bibliography 159</p>
<p>Chapter 7. Population–based Metaheuristics, Fusion–Fission and Graph Partitioning Optimization 163<br /> Charles–Edmond Bichot</p>
<p>7.1. Ant colony algorithms 163</p>
<p>7.2. Evolutionary algorithms 165</p>
<p>7.3. The fusion–fission method 182</p>
<p>7.4. Conclusion 195</p>
<p>7.5. Acknowledgments 196</p>
<p>7.6. Bibliography 196</p>
<p>Chapter 8. Partitioning Mobile Networks into Tariff Zones 201<br /> Mustapha Oughdi, Sid Lamrous, Alexandre Caminada</p>
<p>8.1. Introduction 201</p>
<p>8.2. Spatial division of the network 208</p>
<p>8.3. Experimental results 220</p>
<p>8.4. Conclusion 222</p>
<p>8.5. Bibliography 223</p>
<p>Chapter 9. Air Traffic Control Graph Partitioning Application 225<br /> Charles–Edmond Bichot, Nicolas Durand</p>
<p>9.1. Introduction 225</p>
<p>9.2. The problem of dividing up the airspace 227</p>
<p>9.3. Modeling the problem 231</p>
<p>9.4. Airspace partitioning: towards a new optimization metaheuristic 237</p>
<p>9.5. Division of the central European airspace 240</p>
<p>9.6. Conclusion 246</p>
<p>9.7. Acknowledgments 247</p>
<p>9.8. Bibliography 247</p>
<p>Part 3: Other Approaches to Graph Partitioning 249</p>
<p>Chapter 10. Application of Graph Partitioning to Image Segmentation 251<br /> Amir Nakib, Laurent Najman, Hugues Talbot, Patrick Siarry</p>
<p>10.1. Introduction 251</p>
<p>10.2. The image viewed in graph form 251</p>
<p>10.3. Principle of image segmentation using graphs 254</p>
<p>10.4. Image segmentation via maximum flows 257</p>
<p>10.5. Unification of segmentation methods via graph theory 265</p>
<p>10.6. Conclusions and perspectives 269</p>
<p>10.7. Bibliography 271</p>
<p>Chapter 11. Distances in Graph Partitioning 275<br /> Alain Gu&eacute;noche</p>
<p>11.1. Introduction 275</p>
<p>11.2. The Dice distance 276</p>
<p>11.3. Pons–Latapy distance 281</p>
<p>11.4. A partitioning method for distance arrays 283</p>
<p>11.5. A simulation protocol 286</p>
<p>11.6. Conclusions 292</p>
<p>11.7. Acknowledgments 293</p>
<p>11.8. Bibliography 293</p>
<p>Chapter 12. Detection of Disjoint or Overlapping Communities in Networks 297<br /> Jean–Baptiste Angelelli, Alain Gu&eacute;noche, Laurence Reboul</p>
<p>12.1. Introduction 297</p>
<p>12.2. Modularity of partitions and coverings 299</p>
<p>12.3. Partitioning method 301</p>
<p>12.4. Overlapping partitioning methods 307</p>
<p>12.5. Conclusion 311</p>
<p>12.6. Acknowledgments 312</p>
<p>12.7. Bibliography 312</p>
<p>Chapter 13. Multilevel Local Optimization of Modularity 315<br /> Thomas Aynaud, Vincent D. Blondel, Jean–Loup Guillaume and Renaud Lambiotte</p>
<p>13.1. Introduction 315</p>
<p>13.2. Basics of modularity 317</p>
<p>13.3. Modularity optimization 319</p>
<p>13.4. Validation on empirical and artificial graphs 327</p>
<p>13.5. Discussion 333</p>
<p>13.6. Conclusion 341</p>
<p>13.7. Acknowledgments 342</p>
<p>13.8. Bibliography 342</p>
<p>Appendix. The Main Tools and Test Benches for Graph Partitioning 347<br /> Charles–Edmond Bichot</p>
<p>A.1. Tools for constrained graph partitioning optimization 348</p>
<p>A.2. Tools for unconstrained graph partitioning optimization 350</p>
<p>A.3. Graph partitioning test benches 351</p>
<p>A.4. Bibliography 354</p>
<p>Glossary 357</p>
<p>List of Authors 361</p>
<p>Index 365</p>