一種基于局部信息的分布式社區(qū)結構挖掘算法.pdf

1、復雜系統(tǒng)是現(xiàn)實世界的重要組成部分，復雜網(wǎng)絡是對復雜系統(tǒng)的抽象。研究并發(fā)掘復雜網(wǎng)絡的性質可以幫助人們更好的理解復雜系統(tǒng)。隨著社會的網(wǎng)絡化以及計算機技術的不斷發(fā)展，人們對現(xiàn)實世界的建模能力較過去有了長足的發(fā)展，這使得網(wǎng)絡科學的工作者所接觸的網(wǎng)絡模型越來越復雜，面對的任務也越來越重。而社區(qū)結構是人們認識復雜網(wǎng)絡的一個有力工具，從而使得解決復雜網(wǎng)絡中的社區(qū)結構挖掘問題成為一項積極有意義的工作?，F(xiàn)實世界中個人在生活工作中所產(chǎn)生的數(shù)據(jù)急劇增加，同樣

2、它們所需要的信息量也隨之增加。面對海量數(shù)據(jù)，如何在一個可接受的時間內(nèi)挖掘出特定人群所需要的信息是一個重要的挑戰(zhàn)，分布式成為人們處理海量數(shù)據(jù)的主要方式之一。
　　文中首先分析了復雜網(wǎng)絡的基本特征并以此引出復雜網(wǎng)絡的社區(qū)結構特征;然后分析了現(xiàn)有的社區(qū)結構挖掘算法，總結了算法的優(yōu)缺點?；谌中畔⒌纳鐓^(qū)結構挖掘算法需要利用網(wǎng)絡的全局信息，因此時空復雜度都較高，而且在復雜網(wǎng)絡中全局信息并不容易獲得。為此本文研究并實現(xiàn)了一種基于局部信息的社

3、區(qū)結構挖掘算法，同時將其推廣到分布式平臺上進行實現(xiàn)。利用分布式平臺的優(yōu)勢，達到時間與空間的良好平衡。文中在Clauset提出的局部模塊度概念的基礎上提出了一個新的衡量節(jié)點是否屬于特定社區(qū)的函數(shù)，應用該函數(shù)對Bagrow算法進行改進，改進的算法考慮了節(jié)點的更多信息，因此在精確度上取得了進展，但是算法的迭代速度并沒有提高。隨后文中分析了本地社區(qū)中節(jié)點的特點并提出了兩種啟發(fā)式方法，應用啟發(fā)式得出了一種新的算法，新算法在保持準確度的同時提高了算