Charles-Edmond Bichot - Graph Partitioning

Table of Contents

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 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

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: presents other uses of graph partitioning.

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. 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 describes an Air Traffic Control problem and solves it using the fusion-fission method.

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 books Web address, respectively, about airspace partitioning and image segmentation. To overcome this problem, the original color versions of the figures concerned are also available at the books 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

.

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