[發(fā)明專利]一種基于改進密度峰值的多粒度社區(qū)發(fā)現(xiàn)方法

在審

• 申請?zhí)枺?/td>: 201710963914.1
• 申請日: 2017-10-17
• 公開（公告）號: CN107909497A
• 公開（公告）日: 2018-04-13
• 發(fā)明（設計）人: 龐紫玲;王國胤;楊潔;李苑
• 申請（專利權(quán)）人: 重慶郵電大學
• 主分類號: G06Q50/00
• 分類號: G06Q50/00;G06K9/62
• 代理公司: 重慶市恒信知識產(chǎn)權(quán)代理有限公司50102
• 代理人: 劉小紅

1.一種基于改進密度峰值的多粒度社區(qū)發(fā)現(xiàn)方法，其特征在于，包括以下步驟：

1)、采用改進的密度峰值聚類算法與leading tree思想，形成包含所有節(jié)點的最粗粒度下的大型社區(qū)；改進的密度峰值聚類算法改進在：對密度峰值聚類的距離度量公式替換為能代表社交成員間關(guān)系的拓撲結(jié)構(gòu)距離；，leading tree思想主要體現(xiàn)在：將社交的所有節(jié)點，通過Leading tree算法將真實社交網(wǎng)絡中復雜的關(guān)系簡化為聯(lián)系強烈的從屬拓撲結(jié)構(gòu)；

2)、根據(jù)定義的粒化規(guī)則進行粒層的細化，采用分解機制將步驟1)最粗粒度下的大型社區(qū)分解為多個規(guī)模較小的社區(qū)；

3)、根據(jù)最終社區(qū)中心點集FCT進行社區(qū)網(wǎng)絡粒層的劃分，同時進行最優(yōu)求解粒層的尋優(yōu)，粒層劃分終止即尋優(yōu)結(jié)束后，得到最終的社區(qū)結(jié)構(gòu)。

2.根據(jù)權(quán)利要求1所述的基于改進密度峰值的多粒度社區(qū)發(fā)現(xiàn)方法，其特征在于，所述改進后的密度峰值聚類算法進行社交網(wǎng)絡節(jié)點的聚類處理，得到γ中心點決策圖，聚類后形成的引導樹代表全局社區(qū)拓撲結(jié)構(gòu)圖，因為每個成員鏈接到與其可達且社會重要度比其更大的成員，該全局社區(qū)拓撲圖視為最粗粒度的問題求解空間。

3.根據(jù)權(quán)利要求1或2所述的基于改進密度峰值的多粒度社區(qū)發(fā)現(xiàn)方法，其特征在于，步驟1)改進的密度峰值算法具體為：

設數(shù)據(jù)點i，其密度值ρ_i由以下公式(1)計算：

其中d_ij是節(jié)點i與節(jié)點j的距離，采用歐式距離來計算二維數(shù)據(jù)點的距離，d_c是截斷距離；數(shù)據(jù)點i的與密度吸引點即密度比它大且相對距離比它更大的點距離計算為公式(2):Is表示數(shù)據(jù)集

其中，

將密度峰值算法中距離d_ij，采用社交網(wǎng)絡中成員間的拓撲結(jié)構(gòu)來替換，用節(jié)點間的拓撲距離來替代d_ij，社交網(wǎng)絡的拓撲距離如下所示：

Γ(i)和Γ(j)分別代表社交網(wǎng)絡節(jié)點i和節(jié)點j的鄰接節(jié)點集，如果節(jié)點i和節(jié)點j之間不可達，則d_ij＝∞；若節(jié)點i和節(jié)點j之間可達，但二者不存在其它公共節(jié)點，則d_ij＝1；若節(jié)點i和節(jié)點j之間可達且存在多個公共節(jié)點，則d_ij<1。

4.根據(jù)權(quán)利要求2所述的基于改進密度峰值的多粒度社區(qū)發(fā)現(xiàn)方法，其特征在于，步驟2)根據(jù)定義的粒化規(guī)則進行粒層的細化，采用分解機制將步驟1)最粗粒度下的大型社區(qū)分解為多個規(guī)模較小的社區(qū)，具體包括如下步驟：

S21：采用冗余法從γ決策圖中選擇多個中心，構(gòu)成潛在社區(qū)中心集合CT；

S22：計算CT中每個中心點引導的聚簇SC；

S23：對CT中的每個點，計算SC與從全局引導圖T中截去SC剩余部分的相似度；

S24：根據(jù)具體網(wǎng)絡的分布設定閾值thres，進行聚簇間相似程度的控制；

S25：從SC中選擇相似度小于閾值thres且距離閾值thres最遠的中心點作為一個社區(qū)中心，加入最終社區(qū)中心點集合FCT，同時將改點從CT中移除，令T＝T-SC；

S26：重復步驟S25，直至到達終止條件：CT中沒有潛在中心的相似度小于閾值，完成真實社區(qū)中心節(jié)點的尋找。

5.根據(jù)權(quán)利要求4所述的基于改進密度峰值的多粒度社區(qū)發(fā)現(xiàn)方法，其特征在于，所述步驟S23計算SC(i)與T-SC(i)的相似度公式為：

Similarity(SC,T-SC)＝RI(SC,T-SC)*RC(SC,T-SC)^α(5)

其中，RI(SC,T-SC)表示SC與T-SC的相對互連性，RC(SC,T-SC)表示SC與T-SC的相對近似度，α表示相對互連性與相對近似度之間的重要程度，取值范圍為[0,1]，α＝1表示二者同等重要；

其中，EC(SC,T-SC)表示SC與T-SC的絕對互連性，SC與T-SC中相連邊的總權(quán)重，EC(SC)和EC(T-SC)分別代表SC與T-SC內(nèi)部的邊權(quán)重和，表示連接SC與T-SC中相連邊的平均權(quán)重，和分別表示SC與T-SC做最小截斷時的平均權(quán)重，|SC|和|T-SC|分別表示SC與T-SC集合的元素個數(shù)。

6.根據(jù)權(quán)利要求5所述的基于改進密度峰值的多粒度社區(qū)發(fā)現(xiàn)方法，其特征在于，所述最終社區(qū)中心集FCT的計算過程：對于如果similarity(i)<thres，且maximum|similarity(i)-thres|同時滿足，則將節(jié)點i加入FCT，同時將節(jié)點i從CT中移除，將SC(i)從T中移除；循環(huán)操作，直至不存在更多的i∈CT使similarity(i)<thres終止，得到最終社區(qū)中心集FCT后，根據(jù)中心點來對初始全局社區(qū)結(jié)構(gòu)圖進行劃分，依次得到下一層細粒度上的多個小社區(qū)結(jié)構(gòu)，可從多個劃分粒層中選取適合問題求解的粒層，選擇出最優(yōu)的社區(qū)結(jié)構(gòu)劃分。