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

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

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

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