如何求解最大團(tuán)問(wèn)題的并行多層圖劃分方法概述

　　在當(dāng)今大數(shù)據(jù)環(huán)境下，針對(duì)圖中節(jié)點(diǎn)的海量性和分析的復(fù)雜性對(duì)最大團(tuán)問(wèn)題的研究在速度和精度上都提出了更高要求的問(wèn)題，提出求解最大團(tuán)問(wèn)題的并行多層圖劃分方法（ PMGP_SMC）。首先，提出一種新的多層圖劃分（ MGP）方法，在保持原有圖的團(tuán)結(jié)構(gòu)不被破壞的情況下對(duì)大規(guī)模圖例劃分產(chǎn)生子圖，并對(duì)規(guī)模較大的子圖進(jìn)行多層圖劃分，進(jìn)一步縮小子圖規(guī)模，并且應(yīng)用GraphX圖計(jì)算框架實(shí)現(xiàn)MGP，形成并行MGP（ PMGP）方法；然后，依據(jù)劃分后的子圖規(guī)模，減少了懲罰值局部搜索算法（ PBLS）的迭代次數(shù)，提出基于速度優(yōu)化的PBLS（ SPBLS）來(lái)求解劃分后的各個(gè)子圖的最大團(tuán)；最后，將PMGP和SPBLS相結(jié)合形成PMGP_SMC。采用Stanford大規(guī)模數(shù)據(jù)集運(yùn)行測(cè)試，實(shí)驗(yàn)結(jié)果表明，PMGP相比并行單層圖劃分方法（PSGP），求得的最大子圖規(guī)模能縮小至原來(lái)的1/100，平均子圖規(guī)模能縮小至原來(lái)的1/2；PMGP_SMC相比求解最大團(tuán)問(wèn)題的PSGP（ PSGP_SMC），總體時(shí)間縮短至原來(lái)的1/100，并且PMGP SMC求解最大團(tuán)的精度和基于極大團(tuán)枚舉求解最大團(tuán)問(wèn)題的并行多層圖劃分方法（PMGP_MCE） -敵。PMGP SMC能夠快速精準(zhǔn)地求解大規(guī)模圖例的最大團(tuán)。