Abstract: Concerning the problem of low similarity within the same group in the undirected weighted graph partitioning, the authors used one more reasonable and new global partitioning criterion, Ncut, to measure both the total dissimilarity between the different groups as well as the total similarity within the groups for partitioning the graph. And a new algorithm called RNK which used the basic iterative improvement strategy was proposed, and then the existing partition of G was brought forward by swapping pairs of nodes that can improve the Ncut. Also the paper presented a hash strategy which developed the efficiency for obtaining the best node pair to swap in the RNK algorithm, especially when the graph was dense. At last the authors implemented KL, RNK algorithm. The results obtained from using two algorithms to partition a number of random graphs show that RNK is more reasonable and efficient.

Key words: graph partitioning, coupled factor, Ncut criterion, hashing

摘要： 针对有权图分割时不能很好解决子图内部耦合度不高的问题，使用可以同时优化子图内部顶点耦合度和子图之间顶点耦合度的Ncut准则，提出了一种新的基于迭代改善策略的RNK分割算法。算法通过不断交换可以改善Ncut值的顶点对优化现有分割。与传统分割算法相比，可以同时保证子图内最大耦合度和子图间最小的耦合度。并提出一种散列技术，提高查找最优交换顶点对的效率。当图为稠密矩阵时，改善效果尤为明显。通过对随机图分割的实验结果表明，该算法较传统的KL算法可以得到更理想的分割结果。

关键词: 图分割, 耦合度, Ncut准则, 散列