# bi-partiate graph partitioning

hi,

I have a bipartiate graph (V,U,E) where |V|>|U| (could be |V|>>|U|).

I have converted it into a standard undirected graph problem.

I want to ensure that every partition has a similar number of Us in them. How do I do this?

In other words for a standard problem if I define a set S of verticies, and want to ensure that each partition has the a similar number of verticies from this set S, how would I set the weights for this balancing problem?

Thanks in advance for your help.

Submitted by rasingh on Sat, 2008-06-21 13:22

## RE: Actually, pmetis behaves as

Actually, pmetis behaves as expected with larger size problems (over a million edges :)

## RE: The way to solve this

The way to solve this problem is to formulate it as a two constraint partitioning as follows.

Each vertex will have a vector of two weights (w1, w2). All vertices will have w1=1 and only the vertices in U will have w2=1 (the vertices not in U will have w2=0). The multi-constraint partitioning algorithm in Metis will ensure that the sum of the weights of each vector component across the partitions is balanced, i.e., the sum of the w1 weights in each partition will be the same, and the sum of the w2 weights will be the same.

## RE: How should I change this if

How should I change this if the bipartite graph represents a highly unsymmetric sparse matrix, where V corresponds to the rows, U corresponds to the columns and edges describe nonzero matrix entries? I would like to partition the matrix such that I get two big diagonal blocks and a hopefully small border region, and setting up the weights as described causes pmetis to divide the matrix into an upper triangular and lower triangular half, separated by a thin region that is very sparse.

Should I be using more than two partitions to achieve the intended effect?

(The fact the matrix is unsymmetric means I can't use the column ordering version of Metis)