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

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

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

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