دانلود کتاب Tree-based Graph Partitioning Constraint

فهرست مطالب :

Cover......Page 1
Graph Partitioning......Page 3
Title Page......Page 5
Copyright Page......Page 6
Table of Contents......Page 7
Introduction......Page 15
1.1. Partitioning......Page 19
1.2. Mathematical notions......Page 20
1.3. Graphs......Page 22
1.4. Formal description of the graph partitioning problem......Page 26
1.5. Objective functions for graph partitioning......Page 29
1.6. Constrained graph partitioning......Page 31
1.7. Unconstrained graph partitioning......Page 32
1.8. Differences between constrained and unconstrained partitioning......Page 34
1.9.2. Creating a k-partition from a graph bisection algorithm using the partitioning balance......Page 35
1.10.1. The case of constrained graph partitioning......Page 37
1.10.2. The case of unconstrained graph partitioning......Page 38
1.12. Bibliography......Page 40
PART 1: GRAPH PARTITIONING FOR NUMERICAL ANALYSIS......Page 45
2.1. Introduction......Page 47
2.2. Principles of the multilevel method......Page 48
2.3.1. Introduction......Page 51
2.3.3. Hendrickson-Leland coarsening algorithm......Page 52
2.3.4. The Heavy Edge Matching (HEM) algorithm......Page 53
2.4.1. State-of-the-art partitioning methods......Page 55
2.4.2. Region growing methods......Page 56
2.5.1. Presentation of the uncoarsening and refinement phase......Page 58
2.5.2. The Kernighan-Lin algorithm......Page 59
2.5.3. Fiduccia-Mattheyses implementation......Page 64
2.5.4. Adaptation to direct k-partitioning......Page 65
2.5.5. Global Kernighan-Lin Refinement......Page 66
2.5.6. The Walshaw-Cross refinement algorithm......Page 68
2.6.2. Some results of numerical system......Page 70
2.6.3. Finding the eigenvalues of the Laplacian matrix of a graph......Page 73
2.6.5. Spectral methods for contrained partitioning......Page 74
2.6.6. Spectral methods for unconstrained graph partitioning......Page 75
2.6.7. Problems and improvements......Page 76
2.7. Conclusion......Page 77
2.8. Bibliography......Page 78
3.1.1. Hypergraph and partitioning......Page 83
3.2. Connections between graphs, hypergraphs, and matrices......Page 85
3.3. Algorithms for hypergraph partitioning......Page 86
3.3.1. Coarsening......Page 87
3.3.3. Uncoarsening and refinement......Page 89
3.4.1. Hypergraph partitioning benefits......Page 90
3.4.2. Matrix partitioning......Page 91
3.4.3. Practical results......Page 93
3.4.6. Other applications......Page 94
3.5. Conclusion......Page 95
3.7. Bibliography......Page 96
4.1.1. Need for parallelism......Page 99
4.1.2. Multilevel framework......Page 100
4.2. Distributed data structures......Page 102
4.3.2. Parallel matching algorithms......Page 105
4.3.3. Collision reduction at process level......Page 106
4.3.4. Collision reduction at vertex level......Page 107
4.4. Folding......Page 111
4.5. Centralization......Page 113
4.6.1. Parallelization of the local refinement methods......Page 114
4.6.2. Band graphs......Page 117
4.6.3. Multi-centralization......Page 119
4.6.4. Parallelization of the global refinement methods......Page 120
4.7. Experimental results......Page 125
4.9. Bibliography......Page 129
5.1. Introduction......Page 133
5.2.1. Cost functions......Page 134
5.2.2. Heterogeneity of target architectures......Page 137
5.3. Exact algorithms......Page 139
5.4.1. Global methods......Page 141
5.4.2. Recursive methods......Page 144
5.5. Conclusion......Page 151
5.6. Bibliography......Page 152
PART 2: OPTIMIZATION METHODS FOR GRAPH PARTITIONING......Page 155
Chapter 6. Local Metaheuristics and Graph Partitioning......Page 157
6.1. General introduction to metaheuristics......Page 158
6.2. Simulated annealing......Page 159
6.2.1. Description of the simulated annealing algorithm......Page 160
6.2.2. Adaptation of simulated annealing to the graph bisection problem......Page 162
6.2.3. Generalizing this adaptation to k-partitioning......Page 165
6.2.4. Assessment of simulated annealing adaptation to graph partitioning......Page 166
6.3.1. Presentation of iterated local search......Page 167
6.3.2. Simple adaptation of iterated local search to graph partitioning......Page 170
6.3.3. Iterated local search and multilevel method......Page 174
6.4.1. Greedy algorithms......Page 176
6.6. Bibliography......Page 177
7.1. Ant colony algorithms......Page 181
7.2.1. Genetic algorithms......Page 183
7.2.2. Standard process of genetic algorithm adaptation to graph partitioning......Page 187
7.2.3. The GA’s adaptation to graph bisection optimization of BUI and MOON......Page 190
7.2.4. Multilevel evolutionary algorithm of Soper-Walshaw-Cross......Page 195
7.2.5. Other adaptations of evolutionary algorithms to graph partitioning optimization......Page 198
7.3.1. Introduction......Page 200
7.3.2. Fusion-fission method principles......Page 202
7.3.3. Algorithm......Page 203
7.3.4. Selection of the multilevel algorithm......Page 205
7.3.5. Creation of the sequence of number of parts......Page 206
7.3.6. Selection of the refinement algorithm......Page 207
7.3.7. Evaluation......Page 209
7.4. Conclusion......Page 213
7.6. Bibliography......Page 214
8.1.1. Scheduled rating model......Page 219
8.1.2. Rating model for a network......Page 222
8.2.1. Definitions......Page 226
8.2.2. Formalization of the space division problem......Page 230
8.2.3. Resolution of the space division problem by a genetic algorithm......Page 234
8.3. Experimental results......Page 238
8.4. Conclusion......Page 240
8.5. Bibliography......Page 241
9.1. Introduction......Page 243
9.2. The problem of dividing up the airspace......Page 245
9.2.1. Creation of functional airspace blocks in Europe......Page 246
9.2.2. Creation of a functional block in central Europe......Page 248
9.3.1. Control workload in a sector......Page 249
9.3.3. Two constraints, the size of the qualification areas and size of the control centers......Page 250
9.3.4. Analysis and processing of European air traffic data......Page 251
9.3.5. Graph of European air traffic and adaptation to partitioning......Page 252
9.4. Airspace partitioning: towards a new optimization metaheuristic......Page 255
9.5. Division of the central European airspace......Page 258
9.6. Conclusion......Page 264
9.8. Bibliography......Page 265
PART 3: OTHER APPROACHES TO GRAPH PARTITIONING......Page 267
10.2. The image viewed in graph form......Page 269
10.3. Principle of image segmentation using graphs......Page 272
10.3.1. Choice of arc weights for segmentation......Page 273
10.4.1. Maximum flows for energy minimization......Page 275
10.4.2. Minimal geodesics and surfaces......Page 277
10.4.3. Minimum geodesics and surfaces via maximum flows......Page 281
10.5. Unification of segmentation methods via graph theory......Page 283
10.6. Conclusions and perspectives......Page 287
10.7. Bibliography......Page 289
11.1. Introduction......Page 293
11.2. The Dice distance......Page 294
11.2.1. Two extensions to weighted graphs......Page 296
11.3. Pons-Latapy distance......Page 299
11.4. A partitioning method for distance arrays......Page 301
11.5.2. Quality of the computed partition......Page 304
11.5.3. Results......Page 308
11.6. Conclusions......Page 310
11.8. Bibliography......Page 311
12.1. Introduction......Page 315
12.2. Modularity of partitions and coverings......Page 317
12.3. Partitioning method......Page 319
12.3.1. Fusion and/or fission of clusters......Page 320
12.3.3. Simulations......Page 321
12.4. Overlapping partitioning methods......Page 325
12.4.1. Fusion of overlapping classes......Page 326
12.4.2. Simulations......Page 327
12.5. Conclusion......Page 329
12.7. Bibliography......Page 330
13.1. Introduction......Page 333
13.2. Basics of modularity......Page 335
13.3.1. Existing methods......Page 337
13.3.2. Known limitations......Page 338
13.3.3. Louvain method......Page 339
13.3.4. Modularity increase......Page 342
13.3.5. Convergence of the algorithm......Page 343
13.4. Validation on empirical and artificial graphs......Page 345
13.4.1. Artificial graphs......Page 346
13.4.2. Empirical graphs......Page 349
13.5.1. Influence of the processing order of vertices......Page 351
13.5.2. Intermediate communities......Page 352
13.5.3. Possible improvements......Page 355
13.5.4. Known uses......Page 358
13.6. Conclusion......Page 359
13.8. Bibliography......Page 360
Appendix. The Main Tools and Test Benches for Graph Partitioning......Page 365
A.1.1. Chaco......Page 366
A.1.3. Scotch......Page 367
A.2. Tools for unconstrained graph partitioning optimization......Page 368
A.3.1. Graph partitioning archives of Walshaw......Page 369
A.3.2. Other test benches......Page 371
A.4. Bibliography......Page 372
Glossary......Page 375
List of Authors......Page 379
Index......Page 383