Format: PDF / Kindle (mobi) / ePub
Graph partitioning is a theoretical subject with applications in many areas, principally: numerical analysis, programs mapping onto parallel architectures, image segmentation, VLSI design. During the last 40 years, the literature has strongly increased and big improvements have been made.
This book brings together the knowledge accumulated during many years to extract both theoretical foundations of graph partitioning and its main applications.
Example of precise multi-label segmentation obtained by the power watersheds method (for q = 2). These images are in color on the Website of this book: perso.ec-lyon.fr/charles-edmond.bichot/livre_partitionnement more general and efficient. We can, therefore, estimate that in the near future, a unified approach of these problems will be proposed. We estimate that the discrete methods introduced in this chapter, or those that will be inspired by them, will play a crucial role in their
information, see [BRU 07]. Except for pyramids [DID 86], related to the existence of a total order on the vertex set, the application of these models to the real data has not been used as hierarchical or partitioning methods. In this chapter, we develop a unified approach for the construction of the class systems which aims at maximizing the modularity. In the second section, we show how Newman’s modularity, defined on strict partitions, can be extended to the class systems. By the way, we
density clusters in graphs structured this way. We have introduced the modularity optimization algorithms for the detection of disjoint or overlapping communities in a graph. Rather than sticking to the value of this criterion on public graphs, we have established the simulation protocols in order to measure the efficiency of our algorithms and to compare the results in the average. For that task, we have selected several partitioning quality criteria. Comparisons made on the randomly generated
method only uses the latter to simplify the computation required by the spectral method [BAR 93, BAR 94]. Subsequently, the balance of power was reversed, and the spectral method emerged as one of the tools used in the multilevel methods [HEN 95b]. Many chapters introduce the use of the spectral method to graph partitioning, for both constrained [HEN 95b, BAR 94, HEN 93, POT 90] and unconstrained graph partitioning problems [HAG 92a, DIN 01, DHI 04a, DHI 04b]. The theoritical results linked to
6 Local Metaheuristics and Graph Partitioning 1 This chapter and the following chapter are dedicated to the application of metaheuristics to the graph partitioning optimization problems. State-of-the-art methods are introduced, as well as those which currently appear to be the most efficient and/or promising. Since numerous adaptations of metaheuristics to graph optimization problems have been proposed in the last 20 years, it has not been possible to condense all of them into a single