可擴展的面向關聯的流式圖數據劃分方法研究.pdf

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

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

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