[發(fā)明專利]基于網(wǎng)絡(luò)分解的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點發(fā)現(xiàn)方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201810316574.8
• 申請日: 2018-04-10
• 公開（公告）號: CN108833461B
• 公開（公告）日: 2020-07-17
• 發(fā)明（設(shè)計）人: 王志曉;席景科;袁冠;孟凡榮;牛強;芮曉彬;杜長江
• 申請（專利權(quán)）人: 中國礦業(yè)大學(xué)
• 主分類號: H04L29/08
• 分類號: H04L29/08;H04L12/24;H04L12/26
• 代理公司: 北京天達(dá)知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11386
• 代理人: 龐許倩;胡時冶

1.一種基于網(wǎng)絡(luò)分解的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點發(fā)現(xiàn)方法，其特征在于，包括：

從給定社交網(wǎng)絡(luò)的節(jié)點中確定候選關(guān)鍵節(jié)點集合；

從所述候選關(guān)鍵節(jié)點集合中確定社交網(wǎng)絡(luò)的關(guān)鍵節(jié)點；

所述候選關(guān)鍵節(jié)點是根據(jù)網(wǎng)絡(luò)中各個節(jié)點的中心性值確定的；

所述關(guān)鍵節(jié)點是根據(jù)所述候選關(guān)鍵節(jié)點在網(wǎng)絡(luò)中的連通分支節(jié)點數(shù)量確定的；

所述確定候選關(guān)鍵節(jié)點集合包括以下步驟：

1)根據(jù)給定社交網(wǎng)絡(luò)的中心性指標(biāo)，計算社交網(wǎng)絡(luò)中各個節(jié)點的中心性值；

2)將社交網(wǎng)絡(luò)中心性值最大的節(jié)點判斷為候選關(guān)鍵節(jié)點A，加入到候選關(guān)鍵節(jié)點集合C中，并從所述社交網(wǎng)絡(luò)中刪除該節(jié)點；

3)對剩余網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行連通分支搜索，得到最大連通分支的節(jié)點數(shù)量W_max；

4)判斷是否小于閾值一，否，則進(jìn)入5)；是，則候選關(guān)鍵節(jié)點確定完畢，輸出候選關(guān)鍵節(jié)點集合C，并輸出剩余網(wǎng)絡(luò)；

5)更新網(wǎng)絡(luò)結(jié)構(gòu)，返回1)；

社交網(wǎng)絡(luò)節(jié)點中心性值的計算方法為：

其中，C(v_i)為社交網(wǎng)絡(luò)節(jié)點v_i的中心性值，D(v_i)為節(jié)點v_i的度值，U(i)是節(jié)點v_i的鄰居節(jié)點集合，D(v_j)為鄰居節(jié)點v_j的度值，RLink(v_i)為節(jié)點v_i的所有鄰居節(jié)點之間的邊數(shù)。

2.根據(jù)權(quán)利要求1所述的發(fā)現(xiàn)方法，其特征在于，

所述確定社交網(wǎng)絡(luò)關(guān)鍵節(jié)點包括以下步驟：

1)計算候選關(guān)鍵節(jié)點集合中的節(jié)點單獨放回剩余網(wǎng)絡(luò)后，每個節(jié)點的連通分支節(jié)點數(shù)量；

2)選取連通分支節(jié)點數(shù)量最少的節(jié)點B，記錄該節(jié)點的連通分支節(jié)點數(shù)量W_min；

3)判斷是否小于閾值二，是，則進(jìn)入4)，否，則候選關(guān)鍵節(jié)點集合中節(jié)點即為社交網(wǎng)絡(luò)的關(guān)鍵節(jié)點；

4)將節(jié)點B放回網(wǎng)絡(luò)，并從候選關(guān)鍵節(jié)點集合中刪除節(jié)點B；

5)更新網(wǎng)絡(luò)結(jié)構(gòu)，返回1)。

3.根據(jù)權(quán)利要求2所述的發(fā)現(xiàn)方法，其特征在于，閾值一為1％；閾值二為1％。

4.一種基于網(wǎng)絡(luò)分解的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點發(fā)現(xiàn)系統(tǒng)，其特征在于，包括：節(jié)點中心性值計算模塊，節(jié)點刪除模塊，節(jié)點放回模塊，連通分支搜索模塊；

所述節(jié)點中心性值計算模塊根據(jù)給定的社交網(wǎng)絡(luò)，計算網(wǎng)絡(luò)中各個節(jié)點的中心性值；

所述節(jié)點刪除模塊與所述節(jié)點中心性值計算模塊和連通分支搜索模塊相連，建立候選關(guān)鍵節(jié)點集合輸出到所述節(jié)點放回模塊；

所述節(jié)點放回模塊與所述節(jié)點刪除模塊和連通分支搜索模塊相連，選擇社交網(wǎng)絡(luò)的關(guān)鍵節(jié)點輸出；

所述連通分支搜索模塊與所述節(jié)點刪除模塊和節(jié)點放回模塊相連，搜索社交網(wǎng)絡(luò)中的所有連通分支，返回節(jié)點刪除模塊和節(jié)點放回模塊各個連通分支的節(jié)點數(shù)量及包含的所有節(jié)點，用于判斷最大連通分支的節(jié)點數(shù)量和最小連通分支的節(jié)點數(shù)量；

所述節(jié)點中心性值計算模塊的數(shù)學(xué)模型為：

其中，C(v_i)為社交網(wǎng)絡(luò)節(jié)點v_i的中心性值，D(v_i)為節(jié)點v_i的度值，U(i)是節(jié)點v_i的鄰居節(jié)點集合，D(v_j)為鄰居節(jié)點v_j的度值，RLink(v_i)為節(jié)點v_i的所有鄰居節(jié)點之間的邊數(shù)；

所述節(jié)點刪除模塊找出節(jié)點中心性值最大的節(jié)點A加入到候選關(guān)鍵節(jié)點集合C中，從所述社交網(wǎng)絡(luò)中刪除該節(jié)點；所述連通分支搜索模塊對剩余網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行連通分支搜索，得到最大連通分支的節(jié)點數(shù)量W_max，返回節(jié)點刪除模塊；節(jié)點刪除模塊判斷是否小于閾值一，否，則更新網(wǎng)絡(luò)結(jié)構(gòu)，所述節(jié)點中心性值計算模塊重新計算網(wǎng)絡(luò)中各個節(jié)點的中心性值，輸出至所述節(jié)點刪除模塊進(jìn)行候選關(guān)鍵節(jié)點的確定；是，則候選關(guān)鍵節(jié)點確定完畢，輸出候選關(guān)鍵節(jié)點集合C和剩余網(wǎng)絡(luò)到節(jié)點放回模塊。