基于并行計算的高效圖稀疏化處理算法-論文.pdf

《基于并行計算的高效圖稀疏化處理算法-論文.pdf》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第28卷第2期四川理工學(xué)院學(xué)報(自然科學(xué)版)Vo1．28No．2Q±旦生量!：!翌垡曼!!!!壘蘭竺!!豎!苧型!：!蘭!里2壘旦文章編號：1673-1549(2015)02-0045-07DOI：10．11863／j．suse．2015．02．11基于并行計算的高效圖稀疏化處理算法李融(溫州廣播電視大學(xué)，浙江溫州325000)摘要：針對目前的圖聚類分析方法存在的不足，在分析研究MapReduce架構(gòu)理論、最小哈希算法以及圖聚類分析中的數(shù)據(jù)抽樣和稀疏化處理機(jī)制的基礎(chǔ)上，提出了一種基于并行計算的高效的圖稀疏化處理算法。該方法以MapR

2、educe架構(gòu)理論為基礎(chǔ)，通過Minhash算法進(jìn)行并行化分析，利用MapRe—duce框架結(jié)構(gòu)對圖聚類分析稀疏化操作過程中的多個任務(wù)進(jìn)行了高效的推算分析與處理，并在Hadoop計算環(huán)境下，通過模擬實驗對提出的高效圖稀疏化處理算法的性能進(jìn)行了測試。測試結(jié)果表明：基于并行計算的高效圖稀疏化處理算法可行，能對圖聚類數(shù)據(jù)信息進(jìn)行快速稀疏化處理。關(guān)鍵詞：MapReduce；Minhash；圖聚類分析；數(shù)據(jù)抽樣；并行計算中圖分類號：TB115文獻(xiàn)標(biāo)志碼：A出現(xiàn)，如何高效地進(jìn)行圖聚類分析與處理，以此來挖掘引言圖數(shù)據(jù)中的潛在有效數(shù)據(jù)信息，已成為人

3、工智能、數(shù)據(jù)日益復(fù)雜的網(wǎng)絡(luò)交互體系可以通過建模以圖模型挖掘等領(lǐng)域的熱點研究方向之一。的形式表示，如社交網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、交通運輸網(wǎng)絡(luò)國內(nèi)外研究人員對圖聚類算法進(jìn)行了廣泛的研究，等]。在圖模型中，每個結(jié)點表示對象實體，每條邊表提出了很多的圖聚類算法，包括經(jīng)典聚類算法(如劃分示對象實體之間的關(guān)聯(lián)。例如，可以把社交網(wǎng)絡(luò)體系以式聚類算法)、層次式圖聚類算法、基于密度的圖聚類算一個無向圖模型的形式表示，圖模型中每個結(jié)點表示一法、最小生成圖樹聚類算法等。個社交群體或一個個體，每條邊表示兩個社交群體之間數(shù)據(jù)抽樣是圖聚類分析與處理機(jī)制中的一種高或兩個

4、個體之間的關(guān)聯(lián)，這種關(guān)聯(lián)可以是同事關(guān)系或朋效數(shù)據(jù)處理方式。數(shù)據(jù)抽樣首先從整體數(shù)據(jù)集合中抽友關(guān)系等J。近幾年，隨著網(wǎng)絡(luò)科學(xué)與信息化技術(shù)的不取局部樣本，然后對樣本數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘、處理與分?jǐn)喟l(fā)展以及新浪微博、微信等虛擬網(wǎng)絡(luò)應(yīng)用產(chǎn)品的不斷析。數(shù)據(jù)抽樣可以實現(xiàn)時間與挖掘處理結(jié)果的高性能推廣，圖數(shù)據(jù)信息的處理量呈逐年上升趨勢，給圖數(shù)據(jù)比以及提高圖聚類分析與處理的有效性。在圖聚類分的挖掘、分析及應(yīng)用帶來了極大的挑戰(zhàn)。析與處理過程中，首先對圖模型中的結(jié)點和邊分別進(jìn)行圖聚類是圖數(shù)據(jù)挖掘、分析及應(yīng)用過程中可能會用數(shù)據(jù)抽樣(圖稀疏化處理)，然后對圖稀疏

5、化處理的結(jié)果到的一個關(guān)鍵技術(shù)。圖聚類通過將圖模型中的每個結(jié)進(jìn)行圖聚類分析。點按照聚簇進(jìn)行分類，可以提高同類別聚簇圖結(jié)點對象作為圖聚類分析與處理機(jī)制中較為重要的一個環(huán)實體的關(guān)聯(lián)緊密性、降低不同類聚簇圖結(jié)點對象實體的節(jié)，圖稀疏化處理機(jī)制已被應(yīng)用于多個研究方向。針關(guān)聯(lián)緊密性。隨著超大規(guī)模圖數(shù)據(jù)信息與處理機(jī)制的對小規(guī)模、小區(qū)域范圍的圖模型數(shù)據(jù)信息，現(xiàn)有的圖稀收稿日期：2015．02—14作者簡介：李融(1977一)，男，浙江溫州人，講師，碩士，主要從事計算機(jī)應(yīng)用與教育技術(shù)方面的研究，(E—mail)1697986428@qq．corn四川理

6、工學(xué)院學(xué)報(自然科學(xué)版)2015年4月疏化處理機(jī)制主要包含L-spar9]、k-最近鄰圖n叫等幾種其中，Jaccard參數(shù)值是、兩個數(shù)據(jù)集合的對比數(shù)值。方法。這些方法在對小規(guī)模、小區(qū)域范圍的圖模型數(shù)據(jù)從式(1)中可知，兩個數(shù)據(jù)集合相似度越高，其Jaccard信息進(jìn)行處理時，能夠得到很好的處理效果，但是在對參數(shù)值就越大。然而在數(shù)據(jù)集合較大時，Jaccard參數(shù)值較大規(guī)模、較大區(qū)域范圍的圖模型數(shù)據(jù)信息進(jìn)行處理和會受到交并集合的規(guī)模大小影響，其效率無法得到提應(yīng)用于分布式集群計算環(huán)境時，處理效果比較差。升。隨著圖模型應(yīng)用產(chǎn)品的不斷發(fā)展和應(yīng)用

7、規(guī)模的不Minhash算法就是依據(jù)Jaccard參數(shù)值的相關(guān)知識，斷擴(kuò)大，圖模型的數(shù)據(jù)信息變得越來越復(fù)雜，依靠單一先利用Hash函數(shù)(以日表示)計算、數(shù)據(jù)集合的總的計算環(huán)境對圖數(shù)據(jù)進(jìn)行處理已不能滿足數(shù)據(jù)分析與體元素數(shù)量，然后獲取結(jié)果信息，即Minhash(A)與處理的需要。針對這種情況，能夠通過與大規(guī)模計算機(jī)Minhash(B)：服務(wù)終端相關(guān)聯(lián)來對大規(guī)模數(shù)據(jù)進(jìn)行分析與處理的P，[minh。s(A)=mnhnsh(8)3={—∈寶斗(2)MapReduce并行計算理論框架得到了廣泛應(yīng)用。所以，在此算法中，其相似度問題則巧妙地變換成多個

8、哈希算法，是根據(jù)設(shè)定的哈希函數(shù)H(key)和處理沖數(shù)據(jù)集合的等值概率數(shù)學(xué)問題，從而改進(jìn)了數(shù)據(jù)集合相突方法將一組關(guān)鍵字映像到一個有限的地址區(qū)間上，并似度計算效率。以關(guān)鍵字在地址區(qū)間中的像作為記錄在表中的存儲位1．2并行計算理論置，這種表