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

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