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

有效

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

本發(fā)明涉及一種基于影響力最大化的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法及系統(tǒng)，所述方法包括如下步驟：對于給定的社交網(wǎng)絡(luò)，根據(jù)節(jié)點(diǎn)度值計(jì)算所有節(jié)點(diǎn)影響力的初始值；對節(jié)點(diǎn)影響力進(jìn)行排序，迭代更新節(jié)點(diǎn)影響力值，直到節(jié)點(diǎn)影響力值趨于全局穩(wěn)定；根據(jù)全局穩(wěn)定的節(jié)點(diǎn)影響力值，依據(jù)影響力最大原則，進(jìn)行關(guān)鍵節(jié)點(diǎn)識(shí)別。本發(fā)明充分利用社交網(wǎng)絡(luò)中節(jié)點(diǎn)影響力排名信息，并考慮節(jié)點(diǎn)鄰居間影響力的差異性，采用全局策略進(jìn)行關(guān)鍵節(jié)點(diǎn)選擇，確保社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別的準(zhǔn)確性。

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

本發(fā)明涉及網(wǎng)絡(luò)分析技術(shù)領(lǐng)域，尤其是一種基于影響力最大化的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法及系統(tǒng)。

背景技術(shù)

利用社交網(wǎng)絡(luò)中影響力最大的關(guān)鍵節(jié)點(diǎn)可以讓信息的擴(kuò)散范圍盡可能地大，在市場營銷和廣告投放等方面有重大的意義和廣泛的應(yīng)用?；谟绊懥ψ畲蠡纳缃痪W(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法大致可以分為兩類：基于網(wǎng)絡(luò)拓?fù)涞姆椒ê突趥鞑サ姆椒ā?/p>

基于網(wǎng)絡(luò)拓?fù)涞姆椒ㄒ话阌?jì)算簡單，復(fù)雜度低，但是這類方法無法準(zhǔn)確評估節(jié)點(diǎn)的影響力，對于不同網(wǎng)絡(luò)的適應(yīng)性也不夠強(qiáng)?；趥鞑サ姆椒m然能夠準(zhǔn)確地評估節(jié)點(diǎn)的影響力，對于不同網(wǎng)絡(luò)的適應(yīng)性也很強(qiáng)，但是由于這類方法需要進(jìn)行大量的蒙特卡洛模擬，導(dǎo)致復(fù)雜度很高，難以適用于大規(guī)模社交網(wǎng)絡(luò)。

綜上所述，現(xiàn)有基于影響力最大化的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法存在以下不足：(1)在節(jié)點(diǎn)影響力評估過程中，默認(rèn)鄰居節(jié)點(diǎn)最多的節(jié)點(diǎn)影響力最強(qiáng)，而沒有進(jìn)一步考慮這些鄰居節(jié)點(diǎn)自身影響力的強(qiáng)弱，缺乏合理性；(2)在關(guān)鍵節(jié)點(diǎn)選取過程中，大多都是選取度值或修正后度值最大的節(jié)點(diǎn)，度值反映的信息過于局部化，無法反映全局信息，使得關(guān)鍵節(jié)點(diǎn)的選取不夠準(zhǔn)確。

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

鑒于上述的分析，本發(fā)明旨在提供一種基于影響力最大化的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法及系統(tǒng)，用于解決現(xiàn)有基于影響力最大化的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)識(shí)別方法忽略鄰居節(jié)點(diǎn)間影響力的差異，以及關(guān)鍵節(jié)點(diǎn)選取策略過于局部化的問題。

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

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

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

對節(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í)別。

進(jìn)一步地，計(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)度值降序排列中的排名。

進(jìn)一步地，所述更新節(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)重新排序。

進(jìn)一步地，所述更新節(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)影響力值降序排列中的排名。

進(jìn)一步地，所述關(guān)鍵節(jié)點(diǎn)識(shí)別方法包括：

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