可擴展的面向關(guān)聯(lián)的流式圖數(shù)據(jù)劃分方法研究.pdf

1、當前社交網(wǎng)絡、生物網(wǎng)絡等構(gòu)成的圖的規(guī)模正迅速增長。許多應用場景都需要完整的圖信息，但介于普通機器已無能力單獨存儲整張圖，通過對完整的圖進行計算從而進行信息提取變得越來越具挑戰(zhàn)。為解決該問題，圖的合理劃分顯得非常必要?，F(xiàn)有圖劃分方法在處理大規(guī)模圖數(shù)據(jù)時，不僅有巨大的計算和通信開銷，同時也要求圖的完整信息。另一方面，以在線社交網(wǎng)絡Facebook為例，其用戶賬戶每天都在創(chuàng)建或刪除，朋友之間不斷地分享圖片、文字等信息；由此可見圖已經(jīng)不再是靜態(tài)

2、的，而是處于動態(tài)變化中。
　　能否高效地對動態(tài)圖進行計算處理，正被作為大數(shù)據(jù)處理領(lǐng)域的熱點問題進行研究。在動態(tài)環(huán)境下圖的平衡劃分問題被稱為流式圖數(shù)據(jù)的劃分問題。流式圖數(shù)據(jù)的處理在包括劃分聚類算法、分發(fā)策略等各個層面都面臨巨大挑戰(zhàn)。Assc是一種可擴展的面向關(guān)聯(lián)的流式圖數(shù)據(jù)劃分方法，旨在處理此類規(guī)模持續(xù)增長的大規(guī)模流式圖數(shù)據(jù)。該方法首先采用混合近似PageRank算法計算節(jié)點PageRank值并排名，然后根據(jù)節(jié)點的排名和關(guān)聯(lián)關(guān)系，采

3、用關(guān)聯(lián)聚類算法對其聚類。Assc采用的策略一方面能對節(jié)點的連接能力進行量化評估，并以節(jié)點PageRank值低到高排序作為處理順序，避免過早出現(xiàn)規(guī)模非常大的劃分集合，從而確保劃分的規(guī)模相似；另一方面充分挖掘節(jié)點間的關(guān)聯(lián)關(guān)系，在聚類的每一步中盡可能將關(guān)聯(lián)關(guān)系大的節(jié)點劃分至同一個劃分集合，提升劃分的相關(guān)性的同時也降低了通信開銷。
　　最后，對比評估Assc與Hash和METIS兩種算法。實驗結(jié)果表明，在大量收集的圖數(shù)據(jù)集上分別運行三種方