[發(fā)明專利]基于影響力最大化的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法及系統(tǒng)

有效

• 申請(qǐng)?zhí)枺?/td>: 201810482392.8
• 申請(qǐng)日: 2018-05-18
• 公開（公告）號(hào): CN108809697B
• 公開（公告）日: 2021-05-18
• 發(fā)明（設(shè)計(jì)）人: 孟凡榮;王志曉;袁冠;牛強(qiáng);芮曉彬
• 申請(qǐng)（專利權(quán)）人: 中國(guó)礦業(yè)大學(xué)
• 主分類號(hào): H04L12/24
• 分類號(hào): H04L12/24;H04L12/58;G06Q50/00
• 代理公司: 北京天達(dá)知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11386
• 代理人: 龔頤雯;胡時(shí)冶

1.一種基于影響力最大化的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法，其特征在于，包括以下步驟：

對(duì)于給定的社交網(wǎng)絡(luò)，根據(jù)節(jié)點(diǎn)度值計(jì)算所有節(jié)點(diǎn)影響力的初始值；所述社交網(wǎng)絡(luò)為真實(shí)網(wǎng)絡(luò)；

計(jì)算所述節(jié)點(diǎn)影響力的初始值包括：

式中，SNR₀(v)為節(jié)點(diǎn)v的節(jié)點(diǎn)影響力初始值，N為社交網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)；neigh(v)為節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)集合；rankD(v)為節(jié)點(diǎn)v在節(jié)點(diǎn)度值降序排列中的排名；

對(duì)節(jié)點(diǎn)影響力進(jìn)行排序，迭代更新節(jié)點(diǎn)影響力值，直到節(jié)點(diǎn)影響力值趨于全局穩(wěn)定；當(dāng)節(jié)點(diǎn)影響力值更新之前和更新之后，節(jié)點(diǎn)影響力的排序不變時(shí)，即達(dá)到所述全局穩(wěn)定；

根據(jù)全局穩(wěn)定的節(jié)點(diǎn)影響力值，依據(jù)影響力最大原則，進(jìn)行關(guān)鍵節(jié)點(diǎn)識(shí)別。

2.根據(jù)權(quán)利要求1所述的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法，其特征在于，所述更新節(jié)點(diǎn)影響力值包括：

1)按照節(jié)點(diǎn)影響力值降序排列所有節(jié)點(diǎn)，得到節(jié)點(diǎn)v在所述節(jié)點(diǎn)影響力值降序排列中的排名rankS(v)；

2)根據(jù)節(jié)點(diǎn)影響力排列結(jié)果更新節(jié)點(diǎn)的影響力值；

3)判斷節(jié)點(diǎn)的影響力值是否趨于全局穩(wěn)定，是，則進(jìn)入下一步；否，則返回1)重新排序。

3.根據(jù)權(quán)利要求2所述的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法，其特征在于，所述更新節(jié)點(diǎn)的影響力值包括：

其中，SNR(v)為節(jié)點(diǎn)v更新后的影響力值，N為社交網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)；neigh(v)為節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)集合；rankS(v)為節(jié)點(diǎn)v在所述節(jié)點(diǎn)影響力值降序排列中的排名。

4.根據(jù)權(quán)利要求2所述的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法，其特征在于，所述關(guān)鍵節(jié)點(diǎn)識(shí)別方法包括：

1)選取影響力最大的節(jié)點(diǎn)，將其放入關(guān)鍵節(jié)點(diǎn)集合；

2)從社交網(wǎng)絡(luò)中刪除放入關(guān)鍵節(jié)點(diǎn)集合的節(jié)點(diǎn)以及其所有鄰居節(jié)點(diǎn)，更新網(wǎng)絡(luò)結(jié)構(gòu)；

3)判斷社交網(wǎng)絡(luò)中是否還有剩余節(jié)點(diǎn)，是，則迭代更新剩余節(jié)點(diǎn)的影響力值，直到影響力值趨于全局穩(wěn)定后，再次進(jìn)行關(guān)鍵節(jié)點(diǎn)識(shí)別；否，則關(guān)鍵節(jié)點(diǎn)識(shí)別過(guò)程結(jié)束，輸出識(shí)別出的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)。

5.一種應(yīng)用權(quán)利要求1-4任一項(xiàng)所述識(shí)別方法的基于影響力最大化的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別系統(tǒng)，其特征在于，包括：初始影響力計(jì)算模塊、影響力迭代計(jì)算模塊和關(guān)鍵節(jié)點(diǎn)選取模塊；

所述初始影響力計(jì)算模塊，用于根據(jù)給定的社交網(wǎng)絡(luò)，按照節(jié)點(diǎn)度值降序排列所有節(jié)點(diǎn)，并根據(jù)節(jié)點(diǎn)度值降序排序結(jié)果計(jì)算所有節(jié)點(diǎn)影響力的初始值；

所述影響力迭代計(jì)算模塊，用于對(duì)節(jié)點(diǎn)影響力值進(jìn)行降序排列，根據(jù)排列結(jié)果計(jì)算得到新的節(jié)點(diǎn)影響力值再進(jìn)行降序排列，迭代此過(guò)程，直至計(jì)算出的節(jié)點(diǎn)影響力趨于全局穩(wěn)定；

所述關(guān)鍵節(jié)點(diǎn)選取模塊，用于選取全局穩(wěn)定的影響力最大的節(jié)點(diǎn)放入關(guān)鍵節(jié)點(diǎn)集合，并從社交網(wǎng)絡(luò)中刪除所述節(jié)點(diǎn)及其所有鄰居節(jié)點(diǎn)，更新網(wǎng)絡(luò)結(jié)構(gòu)；之后判斷更新后的網(wǎng)絡(luò)中是否有剩余節(jié)點(diǎn)，是，則調(diào)用所述影響力迭代計(jì)算模塊迭代更新剩余節(jié)點(diǎn)的影響力值直至全局穩(wěn)定，再次進(jìn)行關(guān)鍵節(jié)點(diǎn)識(shí)別；否，則關(guān)鍵節(jié)點(diǎn)識(shí)別過(guò)程結(jié)束，輸出識(shí)別出的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)。

6.根據(jù)權(quán)利要求5所述的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別系統(tǒng)，其特征在于，所述初始影響力值計(jì)算模塊包括：節(jié)點(diǎn)度值排序單元和初始影響力計(jì)算單元；

所述度值排序單元根據(jù)節(jié)點(diǎn)度值降序排列所有節(jié)點(diǎn)，并保存排序結(jié)果；

所述節(jié)點(diǎn)初始影響力計(jì)算單元根據(jù)所述節(jié)點(diǎn)度值降序排列結(jié)果計(jì)算所有節(jié)點(diǎn)影響力的初始值。

7.根據(jù)權(quán)利要求6所述的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別系統(tǒng)，其特征在于，所述節(jié)點(diǎn)初始影響力計(jì)算單元的計(jì)算函數(shù)為：

式中，SNR₀(v)表示社交網(wǎng)絡(luò)節(jié)點(diǎn)v的初始影響力；N為社交網(wǎng)絡(luò)的節(jié)點(diǎn)總數(shù)；neigh(v)為節(jié)點(diǎn)v的鄰居節(jié)點(diǎn)集合；rankD(v)為節(jié)點(diǎn)v在所述節(jié)點(diǎn)度值降序排列中的排名。