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

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

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