[發(fā)明專利]一種度量社會(huì)網(wǎng)絡(luò)影響力的方法

在審

• 申請(qǐng)?zhí)枺?/td>: 202010066714.8
• 申請(qǐng)日: 2020-01-20
• 公開(kāi)（公告）號(hào): CN111242794A
• 公開(kāi)（公告）日: 2020-06-05
• 發(fā)明（設(shè)計(jì)）人: 吳晴晴;周麗華;黃亞群
• 申請(qǐng)（專利權(quán)）人: 云南大學(xué)
• 主分類號(hào): G06Q50/00
• 分類號(hào): G06Q50/00
• 代理公司: 成都東恒知盛知識(shí)產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 51304
• 代理人: 何健雄;廖祥文

本發(fā)明公開(kāi)了一種度量社會(huì)網(wǎng)絡(luò)影響力的方法，本發(fā)明以有效地選擇種子節(jié)點(diǎn)。算法1顯示了CCIM算法的偽代碼。首先，通過(guò)社區(qū)檢測(cè)算法將網(wǎng)絡(luò)G(V,E)劃分為M個(gè)社區(qū)，然后計(jì)算節(jié)點(diǎn)的影響并找到影響力最大的種子節(jié)點(diǎn)。為了避免重復(fù)計(jì)算，我們采用邊際增益策略的增量計(jì)算。選擇種子節(jié)點(diǎn)后，刪除重疊影響并重新計(jì)算其余節(jié)點(diǎn)的影響。最后，種子節(jié)點(diǎn)以特定的擴(kuò)散模型在網(wǎng)絡(luò)中傳播影響力以最大化影響范圍。

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

本發(fā)明涉及互聯(lián)網(wǎng)技術(shù)領(lǐng)域，尤其涉及一種度量社會(huì)網(wǎng)絡(luò)影響力的方法。

背景技術(shù)

近年來(lái)，互聯(lián)網(wǎng)技術(shù)的飛速發(fā)展促進(jìn)了Twitter，微博和微信等社交網(wǎng)絡(luò)的發(fā)展。社交網(wǎng)絡(luò)是具有個(gè)體之間錯(cuò)綜復(fù)雜關(guān)系的網(wǎng)絡(luò)，它促進(jìn)了信息在個(gè)體之間的傳播。影響力最大化(Influence Maximization,IM)的目的是確定一定數(shù)量的最具影響力的用戶，通過(guò)信息擴(kuò)散使最終受影響的用戶的預(yù)期數(shù)量最大化。由于其廣泛的實(shí)際應(yīng)用，如病毒營(yíng)銷[1,2]，謠言控制[3,4]和級(jí)聯(lián)檢測(cè)[5]，影響最大化引起了研究人員和專家的極大關(guān)注。

IM問(wèn)題首先由Kempe等人[6]提出，證明了其是NP難問(wèn)題，并提出了具有保證求解精度的貪心算法。傳統(tǒng)的貪心算法具有較高的時(shí)間復(fù)雜度，因此無(wú)法應(yīng)用于規(guī)模較大的網(wǎng)絡(luò)。為了解決這個(gè)問(wèn)題，近年來(lái)研究者提出了許多近似算法和啟發(fā)式方法，例如基于仿真的算法[5,7]，基于中心度的算法[8,9,10]，基于路徑的算法[11，12,13]和基于社區(qū)的算法[14,15,16,17,18]。基于社區(qū)的算法通常利用社區(qū)中節(jié)點(diǎn)的影響來(lái)近似其對(duì)整個(gè)網(wǎng)絡(luò)的影響。

社區(qū)結(jié)構(gòu)[19]是網(wǎng)絡(luò)最突出的特征之一，其被描述為一個(gè)特殊的群體，其中節(jié)點(diǎn)在社區(qū)內(nèi)連接緊密，而在社區(qū)間連接稀疏。它揭示了網(wǎng)絡(luò)的組織結(jié)構(gòu)和功能組件，并從中觀層面描述了網(wǎng)絡(luò)的結(jié)構(gòu)。對(duì)于社區(qū)中的兩個(gè)節(jié)點(diǎn)，即使由于數(shù)據(jù)的稀疏性，它們?cè)谖⒂^結(jié)構(gòu)中僅具有弱關(guān)系，但由于社區(qū)結(jié)構(gòu)的限制，它們之間的影響將得到加強(qiáng)。另外，由于一個(gè)人的影響范圍是有限的，因此可以用一個(gè)社區(qū)的影響來(lái)近似其對(duì)整個(gè)網(wǎng)絡(luò)的影響。利用社區(qū)的規(guī)模比整個(gè)網(wǎng)絡(luò)小得多的優(yōu)勢(shì)，可以在保證解決方案精度的情況下更有效地計(jì)算節(jié)點(diǎn)的影響力；

現(xiàn)有的基于社區(qū)的IM算法已經(jīng)取得了一些成果，例如CoFIM[17]和IMPC[18]。但是，這些算法僅考慮了社區(qū)中節(jié)點(diǎn)的數(shù)量，而忽略了社區(qū)中邊的連接密度。如圖1(a)所描述的具有社區(qū)結(jié)構(gòu)的網(wǎng)絡(luò)，社區(qū)C₃與C₄中有相同數(shù)量的節(jié)點(diǎn)，但是中的邊數(shù)比.C₃.中的要多。僅考慮節(jié)點(diǎn)數(shù)量，兩個(gè)社區(qū)的影響是相同的。但是，社區(qū)中邊的數(shù)量越多，表明節(jié)點(diǎn)之間進(jìn)行交互的可能性就越高，這可能會(huì)增加激活非激活節(jié)點(diǎn)的機(jī)會(huì)。因此，區(qū)分C₃和.C₄.的影響有利于更準(zhǔn)確地度量節(jié)點(diǎn)的影響力。

另外，現(xiàn)有方法只能應(yīng)用于非重疊的社區(qū)結(jié)構(gòu)。但在現(xiàn)實(shí)世界中，社區(qū)通常是重疊的，即一個(gè)節(jié)點(diǎn)可能屬于許多社區(qū)。例如，在圖1(b)中，節(jié)點(diǎn)v₁屬于C₁，和C₄三個(gè)社區(qū)，因此其對(duì)三個(gè)社區(qū)中的節(jié)點(diǎn)都具有影響。

IM的研究一直是社會(huì)網(wǎng)絡(luò)分析中的熱門研究課題，旨在尋找社交網(wǎng)絡(luò)中最具影響力的用戶，以最大程度地?cái)U(kuò)大影響力。近年來(lái)，許多研究都集中在IM的問(wèn)題上，利用小規(guī)模社區(qū)結(jié)構(gòu)來(lái)提高運(yùn)行效率。但是，現(xiàn)有的基于社區(qū)的影響力最大化方法僅考慮社區(qū)中節(jié)點(diǎn)的數(shù)量，而忽略社區(qū)中節(jié)點(diǎn)之間連接的密度。此外，現(xiàn)有研究方法只能應(yīng)用于非重疊的社區(qū)結(jié)構(gòu)。

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

本發(fā)明的目的就在于為了解決上述問(wèn)題而提供一種度量社會(huì)網(wǎng)絡(luò)影響力的方法。

本發(fā)明通過(guò)以下技術(shù)方案來(lái)實(shí)現(xiàn)上述目的：

本發(fā)明包括以下步驟：

問(wèn)題定義：

給定一個(gè)網(wǎng)絡(luò)G，目標(biāo)是選擇一組最具影響力的節(jié)點(diǎn)S，在特定的擴(kuò)散模型下最大化預(yù)期的總激活節(jié)點(diǎn)數(shù)σ(S)：