社區(qū)發(fā)現(xiàn)技術(shù)的研究與實(shí)現(xiàn).pdf

1、近年來隨著復(fù)雜網(wǎng)絡(luò)的發(fā)展，在現(xiàn)實(shí)世界中復(fù)雜網(wǎng)絡(luò)無處不在，從因特網(wǎng)到萬維網(wǎng)，從航空路線到大型電力網(wǎng)絡(luò)，從超大規(guī)模集成電路圖到人際關(guān)系網(wǎng)等等。隨著近年來對復(fù)雜網(wǎng)絡(luò)性質(zhì)的物理意義和數(shù)學(xué)特性的深入研究，人們發(fā)現(xiàn)許多實(shí)際網(wǎng)絡(luò)都具有一個(gè)共同的性質(zhì)，即社區(qū)結(jié)構(gòu)。所以在復(fù)雜網(wǎng)絡(luò)中自動搜尋或發(fā)現(xiàn)社區(qū)具有重要的實(shí)用價(jià)值，發(fā)現(xiàn)這些網(wǎng)絡(luò)中的社區(qū)有助于更加有效的理解和開發(fā)這些網(wǎng)絡(luò)。 特別是Internet的迅速發(fā)展，互聯(lián)網(wǎng)上的信息量越來越龐大，它已成為全

2、球最大的信息發(fā)布庫。目前互聯(lián)網(wǎng)上的信息紛繁復(fù)雜，如何對其內(nèi)容進(jìn)行分析從而挖掘出人們所需要的內(nèi)容這一問題亟待解決。社區(qū)發(fā)現(xiàn)技術(shù)可在一定程度上解決這個(gè)問題，不僅節(jié)省了用戶的時(shí)間，而且提高了分析的效率。因此，將此技術(shù)用于Web挖掘具有重要的理論意義和實(shí)用價(jià)值。本文將從理論、算法和實(shí)現(xiàn)等三個(gè)方面研究社區(qū)發(fā)現(xiàn)技術(shù)。 但是，由于我們事先不知道到底應(yīng)該將網(wǎng)絡(luò)分為多少個(gè)社區(qū)，這使得這一問題極具挑戰(zhàn)性。本文首先闡述了社區(qū)發(fā)現(xiàn)技術(shù)基本理論，對現(xiàn)有的

3、典型社區(qū)發(fā)現(xiàn)算法作了分析，例如，Belief Propagation算法、k-means（k-centers）算法、Kernighan-Liu算法、譜平分法、W-H算法、GN算法、派系過濾算法等，并研究了各個(gè)算法的核心思想，算法復(fù)雜度，以及適用范圍等。 我們將社區(qū)發(fā)現(xiàn)經(jīng)典的GN算法加以實(shí)現(xiàn)，并用數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。此外，我們還實(shí)現(xiàn)了Frey提出的Affinity Propagation（AP）算法，通過編程和實(shí)驗(yàn)分析，對AP算法的算