現(xiàn)實(shí)世界可被看作由許多不同的復(fù)雜系統(tǒng)組成。為了建模分析復(fù)雜系統(tǒng)中個(gè)體間隱藏的規(guī)律及功能,將復(fù)雜系統(tǒng)抽象為由節(jié)點(diǎn)和邊組成的復(fù)雜網(wǎng)絡(luò)。挖掘復(fù)雜網(wǎng)絡(luò)中的社區(qū)結(jié)構(gòu)在內(nèi)容推薦、行為預(yù)測和疾病擴(kuò)散等方面具有重要的理論意義和實(shí)際價(jià)值。隨著復(fù)雜系統(tǒng)內(nèi)個(gè)體的不斷變化,多個(gè)社區(qū)間出現(xiàn)了重疊節(jié)點(diǎn),有效且準(zhǔn)確地挖掘社區(qū)中的重疊節(jié)點(diǎn)具有一定的挑戰(zhàn)性。為了有效發(fā)現(xiàn)社區(qū)中的重疊節(jié)點(diǎn),提出了一種基于粗糙集和距離動(dòng)態(tài)模型的重疊社區(qū)發(fā)現(xiàn)方法（Overlapping Community Detection based on Rough sets and Distance Dynamics model,OCDRDD）。該方法首先根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu),結(jié)合節(jié)點(diǎn)度中心性和距離選出K個(gè)核心節(jié)點(diǎn);然后按照定義的距離比率關(guān)系初始化社區(qū)的近似集和邊界域,結(jié)合距離動(dòng)態(tài)模型,迭代變化邊界域節(jié)點(diǎn)與下近似集節(jié)點(diǎn)間相連的邊的距離,且在每次迭代過程中將符合定義的距離比率關(guān)系的邊界域節(jié)點(diǎn)劃分到社區(qū)下近似集中,以縮小邊界域節(jié)點(diǎn)（即縮小邊界域的范圍）,直到找到最佳重疊社區(qū)結(jié)構(gòu);最后根據(jù)定義的兩條規(guī)則處理"偽"重疊節(jié)點(diǎn)。在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集和LFR Benchm... 

【文章來源】：計(jì)算機(jī)科學(xué). 2020,47(10)北大核心CSCD

【文章頁數(shù)】：8 頁

【部分圖文】：

OCDRDD算法在Dolphins數(shù)據(jù)集上的劃分結(jié)果(電子版為彩色)

距離動(dòng)態(tài)模型的主要思想是:網(wǎng)絡(luò)中節(jié)點(diǎn)間的距離是逐漸變化的,隨著時(shí)間的推移,距離會(huì)存在兩種變化方式,屬于同一個(gè)社區(qū)的節(jié)點(diǎn)間距離會(huì)逐漸變小,屬于不同社區(qū)間的節(jié)點(diǎn)間距離會(huì)逐漸變大,最終達(dá)到一個(gè)穩(wěn)定的狀態(tài),使得社區(qū)結(jié)構(gòu)呈現(xiàn)出來。距離動(dòng)態(tài)模型是通過檢測節(jié)點(diǎn)間距離的變化動(dòng)態(tài)地發(fā)現(xiàn)社區(qū)結(jié)構(gòu),如圖1(a)所示,節(jié)點(diǎn)vi和節(jié)點(diǎn)vj間距離d(vi,vj)的變化會(huì)受到3種不同鄰居節(jié)點(diǎn)的影響,如圖1中(b)-(d)所示,從而引出3種交互模式。交互模式1:來自直接鏈接節(jié)點(diǎn)的影響。直接鏈接節(jié)點(diǎn)是指直接相連的兩個(gè)端節(jié)點(diǎn)vi和vj之間的影響。兩個(gè)端節(jié)點(diǎn)之間會(huì)彼此吸引,使得距離d(vi,vj)減小,如圖1(b)所示。直接鏈接節(jié)點(diǎn)的影響DI定義為:

對邊界域節(jié)點(diǎn)進(jìn)行迭代處理后,此時(shí)識(shí)別出來的重疊節(jié)點(diǎn)有部分是非重疊節(jié)點(diǎn)。產(chǎn)生這種現(xiàn)象的原因是這類節(jié)點(diǎn)離所有的核心節(jié)點(diǎn)較遠(yuǎn),且不滿足比值關(guān)系。我們稱這類節(jié)點(diǎn)為“偽”重疊節(jié)點(diǎn)�！皞巍敝丿B節(jié)點(diǎn)存在兩種情況:1)只有一個(gè)鄰居節(jié)點(diǎn)的葉子節(jié)點(diǎn);2)該節(jié)點(diǎn)有多個(gè)鄰居節(jié)點(diǎn),且該節(jié)點(diǎn)只有一個(gè)鄰居節(jié)點(diǎn)屬于一個(gè)社區(qū),大于或等于2個(gè)鄰居節(jié)點(diǎn)屬于另外一個(gè)社區(qū)。具體如圖2所示。我們對這類節(jié)點(diǎn)的處理分兩種情況,分別如圖2(a)和圖2(b)所示。為此,本文提出了兩條對“偽”重疊節(jié)點(diǎn)進(jìn)行處理的規(guī)則。規(guī)則1 當(dāng)“偽”重疊節(jié)點(diǎn)為只有一個(gè)鄰居節(jié)點(diǎn)的葉子節(jié)點(diǎn)時(shí),該類節(jié)點(diǎn)被劃分到其鄰居節(jié)點(diǎn)所屬的社區(qū)中。如圖2(a)所示,節(jié)點(diǎn){a,b,c}為社區(qū)C,節(jié)點(diǎn)mmccmyi為“偽”重疊節(jié)點(diǎn),此時(shí)應(yīng)該將節(jié)點(diǎn)gsiuoiw劃分到社區(qū)C。

【參考文獻(xiàn)】：
期刊論文
[1]一種新的基于粗糙集K-均值的社區(qū)發(fā)現(xiàn)方法[J]. 張?jiān)评?吳斌,劉宇.  電子與信息學(xué)報(bào). 2017(04)
[2]基于鏈接密度聚類的重疊社區(qū)發(fā)現(xiàn)算法[J]. 朱牧,孟凡榮,周勇.  計(jì)算機(jī)研究與發(fā)展. 2013(12)



本文編號(hào)：3342691