基于ncut准则的图分割的新算法

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