基于協(xié)同邊推導的動態(tài)流式圖并行抽樣算法.pdf

1、隨著應用不斷深入，在社交網(wǎng)絡服務、科學計算仿真等場景中，圖數(shù)據(jù)持續(xù)、大量產(chǎn)生，對其進行快速、有效分析具有十分重要的意義。在某些對精確度要求不是很高或者只要求反映部分關鍵圖特性的應用中，采取從原圖中抽取具有代表性的子圖進行分析的方法，能節(jié)省計算資源和提高處理效率。對動態(tài)圖抽樣時，原圖的持續(xù)變化導致抽樣過程中無法獲取全圖靜態(tài)數(shù)據(jù)，故通常采用流式的抽樣算法。不過流式抽樣算法由于累計迭代特性，抽樣過程必須串行，因此當抽樣子圖規(guī)模較大時，抽樣過程

2、減速嚴重，難以保證實時性，而若抽樣子圖偏小，則難以保證其與原圖相似?，F(xiàn)有并行抽樣算法針對的都是靜態(tài)圖，不適用于動態(tài)圖，因此需要提出一種并行的流式抽樣算法。
　　研究分析典型的流式圖抽樣算法PIES(Partial-Induce Edge Sampling)及其改進算法 PIES-INV，分析 PIES并行化方案存在的問題，提出了一種基于協(xié)同邊推導的動態(tài)流式圖并行抽樣算法PaStS(Parallel Streaming Sampli

3、ng)。PaStS與PIES-INV采取相同的暫存點替換策略，在并行抽樣時，利用全局點信息同步的機制實現(xiàn)動態(tài)調整各抽樣器的抽樣目標大小，以及實現(xiàn)基于全局點集的協(xié)同邊推導，從而解決流式抽樣算法并行化時點和邊大量減少的問題。
　　經(jīng)過在真實動態(tài)圖數(shù)據(jù)集和生成圖數(shù)據(jù)集上的測試，PaStS算法相比PIES，在并行度為8時抽樣效率能提高15到49倍。PaStS抽樣得到的子圖在四種圖特性的代表性上與PIES-INV比較接近，在多數(shù)情況下都比P