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

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

2、法。
　　目前基于相似度的算法中有兩個經典算法,分別是GN算法以及AP算法。GN算法中的時間復雜度非常高,針對這個弱點,可以提出一種基于擴散核特征矩陣相似度的分裂算法和一種基于DSD相似度的分裂算法。這兩個算法都是基于網絡拓撲結構的算法,避免了GN算法中的計算邊介數(shù)的時間復雜度高的弱點。實驗的結果表示,兩個算法的劃分效果和GN算法差不多,在效率上有很大的提高,對于相似度的度量方法的研究有一定的價值。
　　Newman貪婪算法