Graph Partitioning E-Book

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 651

Veröffentlichungsjahr: 2013

Beschreibung

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.

Leseprobe

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: the recursive bisection method

1.10. NP-hardness of graph partitioning optimization problems

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.4. Partitioning of the coarsened graph

2.5. Uncoarsening and partitions refinement

2.6. The spectral method

2.7. Conclusion

2.8. Bibliography

Chapter 3: Hypergraph Partitioning

3.1. Definitions and metrics

3.2. Connections between graphs, hypergraphs, and matrices

3.3. Algorithms for hypergraph partitioning

3.4. Purpose

3.5. Conclusion

3.6. Software references

3.7. Bibliography

Chapter 4: Parallelization of Graph Partitioning

4.1. Introduction

4.2. Distributed data structures

4.3. Parallelization of the coarsening phase

4.4. Folding

4.5. Centralization

4.6. Parallelization of the refinement phase

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.3. Exact algorithms

5.4. Approximation algorithms

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.3. Iterated local search

6.4. Other local search metaheuristics

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.3. The fusion-fission method

7.4. Conclusion

7.5. Acknowledgments

7.6. Bibliography

Chapter 8: Partitioning Mobile Networks into Tariff Zones

8.1. Introduction

8.2. Spatial division of the network

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.3. Modeling the problem

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.4. Image segmentation via 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.3. Pons-Latapy distance

11.4. A partitioning method for distance arrays

11.5. A simulation protocol

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.4. Overlapping partitioning methods

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.4. Validation on empirical and artificial graphs

13.5. Discussion

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.2. Tools for unconstrained graph partitioning optimization

A.3. Graph partitioning test benches

A.4. Bibliography

Glossary

List of Authors

Index

First published 2011 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd27-37 St George’s RoadLondon SW19 4EUUK

John Wiley & Sons, Inc.111 River StreetHoboken, NJ 07030USA

www.iste.co.uk

www.wiley.com

© ISTE Ltd 2011

The rights of Charles-Edmond Bichot and Patrick Siarry to be identified as the authors of this work have been asserted by them in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

Graph partitioning / edited by Charles-Edmond Bichot, Patrick Siarry.

p. cm.

Includes bibliographical references and index.

ISBN 978-1-84821-233-6

1. Partitions (Mathematics) 2. Graph theory. I. Bichot, Charles-Edmond. II. Siarry, Patrick.

QA76.165.G73 2011

512.7'3--dc23

2011028388

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN 978-1-84821-233-6

Introduction

Since the early 1970s, graph partitioning has been a widely researched topic. After 40 years of development, it is now time to evaluate the situation of the work done in this area.

Graph partitioning is a problem transverse to several fields in engineering, as well as research. The diversity of backgrounds of people working on this subject may explain why no real international community exists, despite the fact that some workshops have been organized on this subject over different periods of time. However, the number of people who work or have worked on this topic is quite significant, as shown by the abundant literature cited throughout the chapters of this book. Confronted with this profusion and diversity, it is interesting to gather the knowledge accumulated over so many years in order to synthesize it and draw the common theoretical fundamentals of this field.

This book intends to present to the neophyte reader, as well as the expert in applied mathematics or the computer science researcher, tools and methods to solve graph partitioning optimization problems. For this purpose, we have collected several methodological chapters detailing different graph partitioning optimization approaches such as the multilevel method, metaheuristics, partitioning parallelization, and hypergraph partitioning. In order to complete this theoretical part, several graph partitioning applications have been described on subjects as diverse as mobile networks, image segmentation, air traffic control, social networks, etc.

Despite the large number of studies in the domain of graph partitioning, it is clear that a lot of work remains to be done to solve this problem more efficiently. Recent years have seen the sizes of graphs to be partitioned soaring from a few thousand vertices to several million, or even billions of vertices. We hope that by reading this book the reader will feel inspired not only to take an interest in this problem, but also try to solve it more efficiently, both in terms of quality of partitions found and computation time required.

This book has three parts: Part 1 is dedicated to the most common application of graph partitioning, numerical analysis; Part 2 describes and implements several combinatorial optimization methods for graph partitioning; Part 3 presents other uses of graph partitioning.

Chapter 1 provides a general introduction to this book and is therefore independent of any part. It analyzes graph partitioning in order to identify the different problems associated with it.

A large number of studies on graph partitioning have been undertaken within the domain of numerical analysis. Part 1 of this book is dedicated to their presentation. Thus, Chapter 2 describes the methods and algorithms commonly used in numerical analysis to solve graph partitioning problems: the multilevel method, refinement algorithms like the Kernighan-Lin or Fiduccia-Mattheyses algorithms, and the spectral method. Chapter 3 introduces the particular case of hypergraph partitioning, which often occurs in numerical analysis. Chapter 4 presents several parallel algorithms to partition a graph. Finally, Chapter 5 presents the problem of static mapping which occurs in parallel computing.

Graph partitioning is often studied through a combinatorial optimization point of view. This is the theme of Part 2 of this book, which is dedicated to the study of combinatorial optimization methods, and more particularly metaheuristics, for graph partitioning. This part consists of two theoretical chapters followed by two application chapters. Chapter 6 focuses on the use of several local metaheuristics, like simulated annealing or iterated local search. Chapter 7 provides details on the use of population-based metaheuristics to optimize partitioning. This chapter explains the work done on Ant Colony algorithms and describes several adaptations of Genetic Algorithms to graph partitioning. It also introduces a recent method for graph partitioning optimization, fusion-fission, which works as a meta-method that overlooks a multilevel algorithm. The last 2 chapters of this part provide application examples for this part. Chapter 8 applies a Genetic Algorithm to the problem of mobile network partitioning in tariff zones. Chapter 9 describes an Air Traffic Control problem and solves it using the fusion-fission method.

Part 3 of this book develops other approaches of graph partitioning. In this part, we have chosen to focus on graph partitioning optimization, and thus we limited the scope of this part, even if many other works on graph partitioning could have been added, like constraint programming for graph partitioning or graph decomposition. Chapter 10 outlines the image segmentation problem and offers several methods to solve this problem, based on graph partitioning. Chapter 11 compares several distances between vertices, in order to build communities, using classification methods. Chapter 12 proposes to partition networks into unconnected or overlapping communities. Finally, Chapter 13 concludes by describing how to partition very large networks into communities.

Further information that could not be included in this book is available at the book’s Web address1. In particular, as this book is being printed in black and white, some figures will have lost their clarity when compared to their original color version. This is especially true for images in Chapters 9 and 10, respectively, about airspace partitioning and image segmentation. To overcome this problem, the original color versions of the figures concerned are also available at the book’s Web address. You will also find at this Web address different graphs used in this book, as well as links to several softwares for graph partitioning.

Charles-Edmond BICHOT and Patrick SIARRY August 2011

1 The book’s Website, “Graph partitioning: optimization and applications”, is available at: perso.ec-lyon.fr/charles-edmond.bichot/.

Chapter 1

General Introduction to Graph Partitioning1

1.1. Partitioning

The word partitioning represents the action of creating a partition by segmenting a set into several parts. In mathematics, a partition of a set X is a family of pairwise disjoint parts of X whose union is the set X . Therefore, each element of X belongs to one, and only one of the parts of the partition.

Partitioning is used to solve a large number of engineering problems. There are many examples of partitioning applications: data mining, VLSI design, load balancing, parallel computing, matrix computation, fluid dynamics, image analysis, air traffic control, etc.

Creating a partition consists of distributing a set of objects into several subsets. In order to distribute the objects in these different subsets, it may be useful to compare them. Thus, each object will be associated with a few other objects. When each object is associated with all other objects, then the grouping is known as clustering, and not partitioning. The resulting associations would be quantified. If the set of all these objects is finite, then all the conditions would be met to create a graph from these objects, in other words to materialize the associations between objects. The next step will be to build a partition of this graph. Partitioning a set of objects generally aims to distribute these objects into parts having strong internal links and weak links between parts. That is known as the objective of partitioning or objective function. This objective function varies according to the specific problem which is to be solved. We emphasize the fact that in this book we mainly focus on the optimization problem of minimizing an objective function. Thus, we will generally seek to minimize the links between parts rather than maximize them.

The problem of graph partitioning optimization is common to several disciplines:

it is part of graph theory problems and therefore discrete mathematics. Discrete mathematics relates to discrete structures, i.e. finite or countable sets;

it is also part of the combinatorial optimization problems. A combinatorial optimization problem tries to find out the best solution within a set of discrete solutions;

it is solved using computing.

Graph partitioning is, therefore, a discipline situated between computer science and applied mathematics.

Because of the diversity of its applications, the graph partitioning optimization problem evolves in a multitude of problems. However, we can group them into two large categories. The nature of a graph partitioning problem is very different according to whether we seek to obtain parts of very similar sizes or without any size constraint. This observation leads us to distinguish between two different graph partitioning problems:

constrained partitioning, when the parts of the partition are of similar sizes;

unconstrained partitioning, when the parts can be of (very) different sizes.

Before giving a precise definition of these two problems, this introductory chapter presents a few reminders on mathematics in section 1.2 and graph theory in section 1.3. These will be followed by a formal description of the graph partitioning optimization problem in section 1.4 and its different objectives in section 1.5. Then the two main categories of graph partitioning problems will be presented: first the constrained partitioning problem in section 1.6, and then the unconstrained partitioning problem in section 1.7. Finally, section 1.10 will study the NP-hardness of several graph partitioning problems.

1.2. Mathematical notions

In mathematics, the partition of a set V of objects is defined as follows:

DEFINITION 1.2. (PARTITION) Let V be an ordinary set. A set P of subsets of V is called a partition of V if:

no element of P is empty;

the elements of P are pairwise disjoint;

the union of the elements of P is equal to V.

The elements of P are called the parts of the partition P. The cardinality of the partition P is therefore the number of parts of P. In graph partitioning, the number of parts of P is often denoted k.

It is a bad habit to use the word partition instead of part, which creates ambiguity. Thus, instead of saying the partition P1 of P, it is better to say the part P1 of the partition P.

As previously mentioned, the graph partitioning problem is a combinatorial optimization problem, which is a branch of discrete mathematics. Discrete mathematics represent the study of mathematical structures, where the notion of continuity doesnt exist. Thus, sets studied in discrete mathematics are countable, and therefore countable sets are sometimes called discrete sets.