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

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

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

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

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