基于局部優(yōu)化的重疊社區(qū)發(fā)現(xiàn)方法研究.pdf

1、現(xiàn)實世界中的很多事物都是以網(wǎng)絡(luò)形態(tài)存在的，例如在線社交，人際關(guān)系，人體蛋白質(zhì)模型等。隨著人們對復雜網(wǎng)絡(luò)研究的深入，社區(qū)結(jié)構(gòu)作為復雜網(wǎng)絡(luò)中的一個重要特性被逐漸重視起來。社區(qū)能夠有效地反應(yīng)網(wǎng)絡(luò)中節(jié)點之間的關(guān)系，對于復雜網(wǎng)絡(luò)中社區(qū)結(jié)構(gòu)的研究有助于人們更加深入的了解網(wǎng)絡(luò)系統(tǒng)的結(jié)構(gòu)特性及其演化規(guī)律，以便人們更好的改善現(xiàn)實生活。這也正是近年來社區(qū)發(fā)現(xiàn)問題成為復雜網(wǎng)絡(luò)領(lǐng)域研究熱點的原因。而重疊社區(qū)的發(fā)現(xiàn)可以更為準確的理解網(wǎng)絡(luò)內(nèi)部的拓撲結(jié)構(gòu)信息，在近些

2、年的研究中得到了越來越多的關(guān)注。
　　針對重疊社區(qū)的發(fā)現(xiàn)問題，目前已出現(xiàn)了許多研究成果，總體上可以分為全局優(yōu)化和局部優(yōu)化兩大類?；谌謨?yōu)化的社區(qū)發(fā)現(xiàn)方法主要從全局的角度劃分整個網(wǎng)絡(luò)，需要整個網(wǎng)絡(luò)結(jié)構(gòu)信息，目前主要包括圖劃分、層次聚類、模塊度優(yōu)化、譜聚類及基于模型的方法等?；诰植繑U展的方法一般根據(jù)定義的社區(qū)局部度量，從給定的初始節(jié)點逐步合并引起最大的社區(qū)度量增量的近鄰節(jié)點，如局部擴展優(yōu)化、標簽傳播、派系過濾、局部邊聚類優(yōu)化等，并

3、在社交網(wǎng)絡(luò)分析中有廣泛的應(yīng)用。
　　本文圍繞局部拓展優(yōu)化中的代表算法 LFM，針對其在社區(qū)劃分過程中存在的劃分速度較慢和結(jié)果不夠穩(wěn)定兩大問題開展研究，提出針對性的解決方案。本文主要研究工作包括如下：
　　首先，針對LFM算法劃分速度較慢的情況，提出了一種基于“核心區(qū)域”的改進LFM算法，在改進算法中提出了“核心區(qū)域”的概念，并論證在社區(qū)的拓展階段，如果一個鄰接點屬于該節(jié)點的核心區(qū)域則可以不必再次重復計算適應(yīng)度函數(shù)值，從而減少

4、計算時間，達到提高社區(qū)劃分速度的目的。
　　其次，針對LFM算法得到的社區(qū)劃分結(jié)果不夠穩(wěn)定的問題，提出了一種基于種子節(jié)點篩選的改進LFM算法。主要思路是：借鑒GCE算法和CPM算法的思想，在算法開始時選擇較為優(yōu)質(zhì)的節(jié)點作為種子節(jié)點即對初始的種子節(jié)點進行篩選。具體做法是：引入臨節(jié)點度閾值k，對于鄰接點度達不到閾值的節(jié)點不會被加入種子節(jié)點庫，從而對達到篩選優(yōu)質(zhì)節(jié)點作為種子節(jié)點的目的，進而優(yōu)化社區(qū)劃分結(jié)果。
　　最后，對上述提出的

5、兩種改進算法，分別在真實網(wǎng)絡(luò)數(shù)據(jù)集和人工合成網(wǎng)絡(luò)數(shù)據(jù)集中進行實驗驗證。對于真實網(wǎng)絡(luò)數(shù)據(jù)集，我們選取的是認同度較高的Zachary’s karate club, American College football, Dolphin social network等五組公開數(shù)據(jù)集，使用模塊度函數(shù)作為評價指標。人工合成網(wǎng)絡(luò)數(shù)據(jù)集則是采用LFR基準程序進行構(gòu)造，使用NMI作為評價指標。同時與LFM算法，CPM算法及Copra算法進行比較。實驗結(jié)果