基于馬爾科夫聚類算法的社團(tuán)發(fā)現(xiàn)研究與應(yīng)用.pdf

1、隨著信息技術(shù)的迅猛發(fā)展，復(fù)雜網(wǎng)絡(luò)的研究引起了許多領(lǐng)域人員的關(guān)注。不論是自然環(huán)境還是人類社會(huì)，網(wǎng)絡(luò)無(wú)處不在。任意對(duì)象間只要存在聯(lián)系或具有相互作用就會(huì)形成網(wǎng)絡(luò)。因此，通過(guò)復(fù)雜網(wǎng)絡(luò)可以挖掘各種各樣的復(fù)雜系統(tǒng)，這在諸多領(lǐng)域中都具有重要的意義。網(wǎng)絡(luò)研究的急速發(fā)展使研究者們發(fā)現(xiàn)復(fù)雜網(wǎng)絡(luò)具有社團(tuán)結(jié)構(gòu)，即復(fù)雜網(wǎng)絡(luò)是由不同的社團(tuán)組合而成，社團(tuán)內(nèi)部節(jié)點(diǎn)間聯(lián)系緊密，社團(tuán)間連接則相對(duì)稀疏。利用這一特性可以分析復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)、網(wǎng)絡(luò)發(fā)展規(guī)律信息以及預(yù)測(cè)行為，因

2、此社團(tuán)發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)研究中一個(gè)重要的課題。
　　本文首先對(duì)經(jīng)典的社團(tuán)發(fā)現(xiàn)算法進(jìn)行了詳細(xì)的研究，并對(duì)每種算法進(jìn)行仿真實(shí)現(xiàn)，進(jìn)一步對(duì)四種經(jīng)典算法對(duì)比總結(jié)。利用Matlab軟件分別對(duì)快速社團(tuán)發(fā)現(xiàn)算法（FN）、基于標(biāo)號(hào)傳播的社團(tuán)發(fā)現(xiàn)算法（LPA）、基于種子擴(kuò)散思想的社團(tuán)發(fā)現(xiàn)算法（LFM）、馬爾科夫聚類算法（MCL）進(jìn)行了實(shí)現(xiàn)，將四種算法的劃分結(jié)果進(jìn)行對(duì)比，得到MCL算法在復(fù)雜網(wǎng)絡(luò)中進(jìn)行社團(tuán)發(fā)現(xiàn)具有明顯的優(yōu)勢(shì)的結(jié)論。
　　其次，在研究

3、經(jīng)典的模塊度函數(shù)、劃分密度及社團(tuán)評(píng)價(jià)標(biāo)準(zhǔn)的基礎(chǔ)上，提出了改進(jìn)的評(píng)價(jià)標(biāo)準(zhǔn)，并總結(jié)了其相關(guān)性質(zhì)。通過(guò)仿真對(duì)比，發(fā)現(xiàn)改進(jìn)后的評(píng)價(jià)標(biāo)準(zhǔn)能夠更合理地評(píng)價(jià)社團(tuán)劃分質(zhì)量，且具有較高的靈敏度。
　　再次，鑒于傳統(tǒng)的社團(tuán)發(fā)現(xiàn)算法忽略了小社團(tuán)與邊緣社團(tuán)存在的不合理性，本文以經(jīng)典社團(tuán)發(fā)現(xiàn)算法為基準(zhǔn)點(diǎn)，將MCL算法進(jìn)行改進(jìn)，得到了改進(jìn)的馬爾科夫聚類算法（MCLp）。此算法在MCL算法的基礎(chǔ)上分析是否存在小社團(tuán)與邊緣社團(tuán)，通過(guò)對(duì)比判斷值與閾值得到需要重新劃

4、分的節(jié)點(diǎn)集合，并對(duì)比重新劃分前后的評(píng)價(jià)函數(shù)來(lái)得到最終的網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)。在經(jīng)典數(shù)據(jù)集上進(jìn)行仿真實(shí)驗(yàn)，并與經(jīng)典社團(tuán)發(fā)現(xiàn)算法從多個(gè)角度對(duì)比，發(fā)現(xiàn)MCLp算法得到的社團(tuán)結(jié)構(gòu)與實(shí)際劃分更為貼切，精確度高達(dá)92.8％。隨著網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目與連接邊的增加，改進(jìn)的MCLp算法在時(shí)間復(fù)雜度方面的增長(zhǎng)并不顯著。
　　最后，本文將改進(jìn)的MCLp社團(tuán)發(fā)現(xiàn)算法分別應(yīng)用于包含1000個(gè)節(jié)點(diǎn)的基準(zhǔn)網(wǎng)絡(luò)、美國(guó)西部各州的電力網(wǎng)絡(luò)以及科學(xué)家合作網(wǎng)，得到了合理的社團(tuán)結(jié)構(gòu)，進(jìn)