[發(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
• 代理公司: 北京天達知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11386
• 代理人: 龐許倩;胡時冶

本發(fā)明涉及一種基于網(wǎng)絡(luò)分解的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點發(fā)現(xiàn)方法及系統(tǒng)，屬于網(wǎng)絡(luò)分析技術(shù)領(lǐng)域；根據(jù)網(wǎng)絡(luò)中各個節(jié)點的中心性值初步確定候選關(guān)鍵節(jié)點集合，根據(jù)所述候選關(guān)鍵節(jié)點在網(wǎng)絡(luò)中的連通分支節(jié)點數(shù)量確定社交網(wǎng)絡(luò)的關(guān)鍵節(jié)點。本發(fā)明解決了鄰居節(jié)點之間的連邊對網(wǎng)絡(luò)破壞能力的影響，設(shè)計了更加準(zhǔn)確的節(jié)點中心性指標(biāo)，選取了更加合理的節(jié)點放回策略，并且無需進行參數(shù)設(shè)置，社交網(wǎng)絡(luò)關(guān)鍵節(jié)點發(fā)現(xiàn)更加高效、準(zhǔn)確。

技術(shù)領(lǐng)域

本發(fā)明涉及網(wǎng)絡(luò)分析技術(shù)領(lǐng)域，尤其是一種基于網(wǎng)絡(luò)分解的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點發(fā)現(xiàn)方法及系統(tǒng)。

背景技術(shù)

關(guān)鍵節(jié)點發(fā)現(xiàn)是社交網(wǎng)絡(luò)分析的一項重要內(nèi)容，其目的是發(fā)現(xiàn)一個盡可能小的節(jié)點集合，使得刪除這些節(jié)點后，網(wǎng)絡(luò)能夠被最大程度地破壞。隨著互聯(lián)網(wǎng)和大數(shù)據(jù)的發(fā)展，網(wǎng)絡(luò)規(guī)模呈現(xiàn)急劇增大的趨勢，社交網(wǎng)絡(luò)關(guān)鍵節(jié)點發(fā)現(xiàn)在網(wǎng)絡(luò)防護以及阻止病毒傳播等方面有重要的應(yīng)用前景。

現(xiàn)有的基于網(wǎng)絡(luò)分解的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點發(fā)現(xiàn)方法主要有兩類：一類是基于去環(huán)策略的，另一類是基于中心性指標(biāo)的。基于去環(huán)策略的算法在節(jié)點刪除階段，雖然通過去環(huán)過程提高了網(wǎng)絡(luò)分解效率，但是去環(huán)過程針對性不強，刪除了很多非關(guān)鍵節(jié)點，導(dǎo)致大量節(jié)點需要放回；基于中心性指標(biāo)的算法試圖通過中心性指標(biāo)針對性地刪除關(guān)鍵節(jié)點，但傳統(tǒng)的中心性指標(biāo)忽略了鄰居節(jié)點之間的連邊對網(wǎng)絡(luò)破壞性的影響，對節(jié)點中心性的評估不夠準(zhǔn)確，同樣刪除了大量非關(guān)鍵節(jié)點；并且，在放回階段，現(xiàn)有的關(guān)鍵節(jié)點發(fā)現(xiàn)算法未研究不同的放回策略對最終結(jié)果的影響，無法選擇合理的放回策略；最后，受到可調(diào)參數(shù)的影響，現(xiàn)有算法的適應(yīng)性和穩(wěn)定性不足。

發(fā)明內(nèi)容

鑒于上述的分析，本發(fā)明旨在提供一種基于網(wǎng)絡(luò)分解的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點發(fā)現(xiàn)方法及系統(tǒng)，解決現(xiàn)有基于網(wǎng)絡(luò)分解的關(guān)鍵節(jié)點發(fā)現(xiàn)方法中節(jié)點刪除針對性不強、忽略鄰居節(jié)點之間的連邊對網(wǎng)絡(luò)破壞能力的影響、節(jié)點放回策略不合理以及需要參數(shù)設(shè)置問題。

本發(fā)明的目的主要是通過以下技術(shù)方案實現(xiàn)的：

一種基于網(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)鍵點是根據(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)進行連通分支搜索，得到最大連通分支的節(jié)點數(shù)量W_max；

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

5)更新網(wǎng)絡(luò)結(jié)構(gòu)，返回1)重新計算社交網(wǎng)絡(luò)中各個節(jié)點的中心性值。

進一步地，所述社交節(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ù)。