分布式環(huán)境下大規(guī)模單圖的頻繁子圖挖掘.pdf

1、隨著科學(xué)技術(shù)的快速發(fā)展，各類(lèi)數(shù)據(jù)的存儲(chǔ)量與日俱增，對(duì)于這些海量數(shù)據(jù)的挖掘需求越來(lái)越強(qiáng)烈，因此大規(guī)模單圖下的頻繁子圖挖掘也隨之成為研究熱點(diǎn)。頻繁子圖的目標(biāo)是從圖集或者單圖中找出支持度大于某個(gè)閾值的所有子圖，結(jié)果可運(yùn)用于分類(lèi)、聚類(lèi)和索引的建立，并且單圖下的頻繁子圖挖掘?qū)τ谏缃痪W(wǎng)絡(luò)和萬(wàn)維網(wǎng)的研究意義尤為顯著。在已有研究工作中，基于單機(jī)的頻繁子圖挖掘算法對(duì)于閾值較低的支持度挖掘難以支撐，也不適合較大規(guī)模圖的挖掘；現(xiàn)有分布式下的單圖挖掘算法僅支持

2、指定頂點(diǎn)數(shù)量 k的挖掘，多數(shù)基于Hadoop實(shí)現(xiàn)，對(duì)于迭代類(lèi)算法的實(shí)現(xiàn)產(chǎn)生額外開(kāi)銷(xiāo)。本文在對(duì)現(xiàn)有的頻繁子圖工作和分布式框架進(jìn)行充分研究的基礎(chǔ)上，借助 Spark平臺(tái)，提出了大規(guī)模單圖下的分布式頻繁子圖挖掘算法-FSMBUS和基于頻繁邊的圖采樣算法-DFES。
　　FSMBUS算法以頻繁邊為起點(diǎn)，利用次優(yōu)樹(shù)生成候選子圖，對(duì)候選子圖進(jìn)行搜索數(shù)據(jù)域構(gòu)建之后并行計(jì)算其支持度，在支持度計(jì)算階段使用非頻繁檢測(cè)和搜索順序進(jìn)行優(yōu)化，還設(shè)計(jì)了一種基

3、于貪心的數(shù)據(jù)劃分策略實(shí)現(xiàn)負(fù)載均衡。FSMBUS借助次優(yōu)樹(shù)可進(jìn)行子圖模式增長(zhǎng)的挖掘，所使用的優(yōu)化方式以及負(fù)載均衡策略可以有效提升算法運(yùn)行速度，基于 Spark進(jìn)行分布式運(yùn)行，也避免了迭代時(shí)數(shù)據(jù)交換的開(kāi)銷(xiāo)。最后實(shí)驗(yàn)表示 FSMBUS算法的效率比最新的單機(jī)算法快一個(gè)數(shù)量級(jí)，同時(shí)還比該算法的Hadoop移植版本快2~4倍。
　　頻繁子圖挖掘是一個(gè) NP難題，隨著圖數(shù)據(jù)的規(guī)模日益擴(kuò)大,其運(yùn)行開(kāi)銷(xiāo)也隨之成倍增加。由于大規(guī)模圖數(shù)據(jù)的頻繁子圖挖掘