基于Ncut准则的图分割的新算法.pdfVIP

第 30卷第 12期 计算机应用 Vol. 30 No. 12 2010年 12月 Jour al of ComputerApp licatio s Dec. 2010 : 1001- 9081( 2010) 12- 3262- 03 Ncut 周德新, 王兴旺, 刘 涛 ( , 300300) (xww a g_0102@ yahoo. c ) : 针对有权图分割时不能很好解决子图内部耦合度不高的问 , 使用可以同时优化子图内部顶点耦合度 和子图之间顶点耦合度的 Ncut准则, 提出了一种新的基于迭代改善策略的 RNK分割算法算法通过不断交换可以 改善 Ncu t值的顶点对优化现有分割与传统分割算法相比, 可以同时保证子图内最大耦合度和子图间最小的耦合 度并提出一种散列技术, 提高查找最优交换顶点对的效率当图为稠密矩阵时, 改善效果尤为明显通过对随机图 分割的实验结果表明, 该算法较传统的 KL算法可以得到更理想的分割结果 : 图分割; 耦合度; Ncut准则; 散列 : TN47 : A N ew algorithm for partition ing graph based on N cut criterion ZHOU Dexi, WANG X i gw a g, LIU Tao (AeronauticalAutomation College, CivilAviation University of China, Tianj in 300300, China) A bstract: Co cer i g the prob lem of low s mi ilarityw ithi the same group i the u directed weighted graph partitio i g, the authors used o e m ore reaso able a d ew global partitio i g criterio , Ncut, to m easure both the total d issmi ilarity bewt ee the differe t groups as well as the total s mi ilarity w ith i the groups for partitio i g the graph. A d a ew algorithm called RNK w hich used the basic iterative mi provem e t strategy was proposed, a d the the existi g partitio of G w as brought forward by sw appi g pairs of odes that ca mi prove the Ncut. A lso the paper prese ted a hash strategy wh ich developed the efficie cy for ob tai i g the best ode pair to sw ap i the RNK algorithm, especially whe the graph w as de se. At last the au thors mi plem e ted KL, RNK algorithm. The resu lts obtai ed from usi g two algorithm s to partitio a um ber of ra dom graphs show that RNK is more reaso ab le a d efficie t. K ey w ords: graph partitio i g; coupled factor; Ncut criteri