基于通信負(fù)載均衡的社交網(wǎng)絡(luò)圖分割算法研究與實(shí)現(xiàn).pdf

1、海量社交網(wǎng)絡(luò)數(shù)據(jù)中蘊(yùn)含著豐富的信息，圖論是挖掘這些信息的重要方法之一。面對(duì)日益增多的圖數(shù)據(jù)，分布式計(jì)算成為處理大規(guī)模圖數(shù)據(jù)的有效手段。在分布式圖計(jì)算中，通信所消耗的時(shí)間占有很大的比例，通過(guò)圖分割算法的設(shè)計(jì)可以有效地降低通信量并實(shí)現(xiàn)負(fù)載均衡，從而提高分布式圖計(jì)算的效率，典型的例子包括Met is圖分割算法。但是，用現(xiàn)有的圖分割算法處理非均衡圖數(shù)據(jù)會(huì)造成各個(gè)子圖之間通信量不均衡，從而影響了計(jì)算效率。
　　本研究針對(duì)社交網(wǎng)絡(luò)圖數(shù)據(jù)特點(diǎn)進(jìn)

2、行了深入研究，并以傳統(tǒng)圖分割模型為基礎(chǔ)，建立了實(shí)現(xiàn)通信負(fù)載和存儲(chǔ)負(fù)載雙重平衡的圖分割模型。以通信負(fù)載均衡圖分割方法為理論依據(jù)，設(shè)計(jì)并實(shí)現(xiàn)了通信均衡標(biāo)簽交換算法(Communication Balanced Lable Exchanging method)，同時(shí)為進(jìn)一步減小貪婪算法模型帶來(lái)的局部?jī)?yōu)化影響，使用模擬退火算法對(duì)C BLE算法進(jìn)行深入優(yōu)化。使用Hash方法，Metis方法與CBLE算法進(jìn)行實(shí)驗(yàn)分析，分別在通信邊數(shù)量，頂點(diǎn)規(guī)模均衡