基于相似度的社區(qū)發(fā)現(xiàn)算法研究.pdf

1、在許多真實(shí)的網(wǎng)絡(luò)中都存在模塊或社區(qū)。社區(qū)的檢測(cè)是社會(huì)網(wǎng)絡(luò)學(xué)習(xí)的重要的課題,對(duì)于我們了解社會(huì)網(wǎng)絡(luò)的內(nèi)部關(guān)系和結(jié)構(gòu),進(jìn)而應(yīng)用到與社會(huì)網(wǎng)絡(luò)相關(guān)的很多領(lǐng)域都有重要的意義。
　　傳統(tǒng)的基于相似度的社區(qū)發(fā)現(xiàn)算法比如GN算法在計(jì)算的時(shí)候時(shí)間復(fù)雜度非常高,而基于相似度的社區(qū)發(fā)現(xiàn)算法的結(jié)果主要取決于相似度的選擇,有些相似度選擇可能使得結(jié)果更準(zhǔn)確,但是針對(duì)規(guī)模較大的網(wǎng)絡(luò),時(shí)間也要是考慮的主要因素之一,所以可以根據(jù)網(wǎng)絡(luò)的不同要求來選擇相似度的不同度量方

2、法。
　　目前基于相似度的算法中有兩個(gè)經(jīng)典算法,分別是GN算法以及AP算法。GN算法中的時(shí)間復(fù)雜度非常高,針對(duì)這個(gè)弱點(diǎn),可以提出一種基于擴(kuò)散核特征矩陣相似度的分裂算法和一種基于DSD相似度的分裂算法。這兩個(gè)算法都是基于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的算法,避免了GN算法中的計(jì)算邊介數(shù)的時(shí)間復(fù)雜度高的弱點(diǎn)。實(shí)驗(yàn)的結(jié)果表示,兩個(gè)算法的劃分效果和GN算法差不多,在效率上有很大的提高,對(duì)于相似度的度量方法的研究有一定的價(jià)值。
　　Newman貪婪算法