Graph Partitioning: A Heuristic Procedure to Partition Network Graphs

Abstract

Graphs are mathematical structures used to model pair wise relationship between objects of a certain collection. It consists of collection of vertices or “nodes” and a collection of edges that connect these nodes. Graphs can be directed from one vertex to another or undirected. In our context, a graph denotes a network with computers distributed as nodes while the communication channel acting as the edges. These are directed graphs where each edge has a capacity which cannot be exceeded.
In real life applications, it becomes very essential that graphs are partitioned in some way so as to satisfy certain conditions. For example, while placing components of electronic circuit on circuit boards or substrates, components that are highly dependent on each other (exchanging maximum information) should be placed on the same board. Also an important factor is the number of connections between these boards should be minimized. Similar situation arises in a computer network where computer systems are distributed over a wide geographic location. This is the basis of graph partitioning problem.
The classical graph partitioning problem consists of dividing a graph into pieces, such that the pieces are of about same size and there exists very few connections between these pieces. The objective is to partition the nodes of a graph with costs on its edges into subsets so as to minimize the sum of the costs on all edges that are cut.
Let G be graph with n nodes, of sizes (weights) wi > 0, i = 1, 2, …., n. Let p be a positive number, such that 0 < wi < p for all i. Let C = (cij), i,j = 1, 2, ……, n be a weighted connectivity matrix describing the edges of G. Let k be a positive integer. A k-way partition of G is a set of disjoint subsets of G, v1, v2, …, vk such that

A partition is admissible if

for all i. The cost of partition is the summation of (cij), where i and j belong to different subsets.
A strictly exhaustive procedure for finding the optimal partition is out of question because the problem of graph partitioning is NP-Hard problem. For a graph with 40 nodes and 4 partitions, the possible number of partitioned cases will be of the order of 1036. Hence, any direct approach to find an optimal solution from these many cases is not a feasible option. As a result heuristic approaches are employed in these cases.
We use a heuristic partitioning algorithm that divides a network into 2 disjoint sets based on the distance between any two nodes. The network used is a real network termed ARPANET and is regarded as the origin of the Internet.