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

1、社區(qū)發(fā)現(xiàn)是復(fù)雜網(wǎng)絡(luò)研究領(lǐng)域的一個重要的研究方向。一個網(wǎng)絡(luò)由若干社區(qū)組成，每個社區(qū)在內(nèi)部節(jié)點之間聯(lián)系相對緊密，在外部社區(qū)之間的聯(lián)系相對稀疏。SCAN算法是近年來涌現(xiàn)出來的社區(qū)發(fā)現(xiàn)算法中比較優(yōu)秀的算法，它是一種基于結(jié)構(gòu)聚類的算法，這也是它名字的由來（Structural Clustering Algorithmfor Networks）。它的優(yōu)秀表現(xiàn)在線性的時間復(fù)雜度，精準(zhǔn)的劃分結(jié)果，并且可以識別社區(qū)結(jié)構(gòu)之外的信息（樞紐節(jié)點和孤立節(jié)點）。<

2、br>　　雖然SCAN算法有很多的優(yōu)勢，但是缺陷也是很明顯的。SCAN不能識別重疊社區(qū)，而社區(qū)的重疊現(xiàn)象是廣泛存在于網(wǎng)絡(luò)中的;由于在線社交網(wǎng)絡(luò)的發(fā)展，網(wǎng)絡(luò)結(jié)構(gòu)的演進變化大大快于從前，能夠動態(tài)地分析網(wǎng)絡(luò)得出社區(qū)結(jié)構(gòu)應(yīng)該是研究的大趨勢，而SCAN算法缺乏這方面的能力。另外，SCAN算法需要人工設(shè)置兩個參數(shù)并且算法的精確度嚴(yán)重依賴參數(shù)的選擇。結(jié)合以上內(nèi)容，本文在SCAN算法的基礎(chǔ)上改進擴展出兩個算法，具體研究成果如下:
　　(1)SCA

3、N算法優(yōu)化改進
　　SCAN算法包含兩個參數(shù):ε和μ，我們主要對參數(shù)進行優(yōu)化，一是參數(shù)的約減，二是降低算法對于參數(shù)的敏感度。首先，我們只保留了參數(shù)ε用于限定核心網(wǎng)絡(luò)，并且采用一個循環(huán)刪邊的操作降低算法對于這個參數(shù)的依賴，使得閾值α在很大的選擇范圍內(nèi)算法都能得到令人滿意的社區(qū)劃分結(jié)果。
　　(2)SCAN算法功能擴展
　　本文對SCAN算法進行重疊節(jié)點識別的擴展，提出了LED算法。循環(huán)刪邊過程促使社區(qū)分裂，在分裂的時候被