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

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

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

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