# Graph Partition Across Cluster - Minimize Largest Matrix Size

I am writing some code for modeling semi-biologically realistic neural networks, which is to be run/distributed across nodes in a computer cluster. I begin with a very large adjacency matrix (representing the neural connectivity), and I want to split the $n\times n$ matrix into $k$ smaller $n \times (n/k)$ matrices. From there each machine will do some expensive computations on it's assigned matrix. Additionally, I can remove empty rows from the $n \times (n/k)$ matrices before distributing to the machines (so that they are $\leq n \times (n/k)$). So my question is: how do I split the matrix into $k$ sub-matrices, so that I can minimize the size of the largest sub-matrix.

My graph theory knowledge is limited, and so any references or direction would be great in lieu of an explicit answer if there are already resources out there that are related to this kind of problem.

• Since the computational expense is element-wise, and the connectivity is bound to follow some sort of power-law, this would probably result in a couple less connected [wide] sub-matrices, and a couple of highly connected [thin] sub-matrices... – JoeC Dec 22 '14 at 0:31
• Maybe a sort of decision tree would work OK. I could sort the vertices by the number of edges, and take the first vertex as the seed for group 1. Then going down the list I could find the neuron which has the most connectivity not equal to the seed for group one. Then for the 3rd seed it would be the most not equal to both 1 and 2, etc. And in any case where there are an equal number of options, those represent branches in a decision tree. Once the seed vertices (or set of seed vertices) are found, the remaining vertices would be added to one of the groups. – JoeC Dec 22 '14 at 0:39
• According to minimizing the addition of any vertices that have incoming connections not already part of the group, with a preference for the later seed groups in case of a tie, since they have the fewest incoming connections already. – JoeC Dec 22 '14 at 0:41