基于度特征的部分推導邊抽樣算法研究.pdf

1、大規(guī)模圖數(shù)據(jù)的抽樣在社交網(wǎng)絡、信息網(wǎng)絡和生物網(wǎng)絡等圖式數(shù)據(jù)的分析中有著重要的作用。很多現(xiàn)實的網(wǎng)絡有的規(guī)模非常巨大，有的在持續(xù)變化。在測試和研究中，為了合理折衷性能與精確性，往往需要在原圖基礎上抽樣得到較小的有代表性的子圖。傳統(tǒng)的圖抽樣方法是針對靜態(tài)圖，并且需要保證對全圖的可訪問性。然而，當原圖的規(guī)模大到全圖結構無法一次性加載到主存中，或者圖本身是動態(tài)變化時，傳統(tǒng)的圖抽樣算法就無法適用。
　　利用流式的抽樣算法，可消除靜態(tài)抽樣算法對

2、全圖結構的依賴性，從而實現(xiàn)大規(guī)模圖和動態(tài)圖流式抽樣。本項研究分析最新的流式圖抽樣算法PIES及其改進算法PIES-MIN，以此為基礎找出兩者在抽樣時暫存點替換策略存在的問題，提出了新的替換策略。新的替換策略參考PIES-MIN的思路，選取度的特征為替換標準，以暫存點的度的倒數(shù)為比例，為不同度的點分配不同的替換概率，在一定程度上防止了度高的點被頻繁地刪除，同時也不會像PIES-MIN算法一樣造成度高的點的大量集聚。
　　經(jīng)過分析和推

3、導，PIES-INV算法在單次邊處理時的時間開銷與PIES-MIN算法相同，空間開銷比PIES-MIN算法稍大，但在可接受的范圍之內。經(jīng)過在不同實際圖數(shù)據(jù)集上的測試，PIES-INV算法得到的子圖在四種圖特性的代表性上幾乎都超越了PIES算法。在低度點比例較大的圖中PIES-INV算法在度分布、k-core分布和有效路徑這三個特性上的表現(xiàn)比PIES-MIN要好，在平均集聚系數(shù)較小的圖中PIES-INV算法在集聚特性上的表現(xiàn)比PIES-M