[發(fā)明專利]基于社交網(wǎng)絡(luò)層級(jí)結(jié)構(gòu)的影響最大化種子集建立方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201811037119.0
• 申請(qǐng)日: 2018-09-06
• 公開(kāi)（公告）號(hào): CN109508415B
• 公開(kāi)（公告）日: 2021-01-05
• 發(fā)明（設(shè)計(jì)）人: 李侃;李玲玲
• 申請(qǐng)（專利權(quán)）人: 北京理工大學(xué)
• 主分類(lèi)號(hào): G06F16/9535
• 分類(lèi)號(hào): G06F16/9535;G06Q50/00
• 代理公司: 北京正陽(yáng)理工知識(shí)產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11639
• 代理人: 鮑文娟

本發(fā)明涉及基于社交網(wǎng)絡(luò)層級(jí)結(jié)構(gòu)的影響最大化種子集建立方法，屬社交網(wǎng)絡(luò)技術(shù)領(lǐng)域，步驟如下：a，輸入網(wǎng)絡(luò)G(V,E)、信源節(jié)點(diǎn)、種子節(jié)點(diǎn)數(shù)K、傳播概率；b，計(jì)算節(jié)點(diǎn)緊密程度并降序排列；c，初始化層級(jí)數(shù)M,各層級(jí)斷點(diǎn)g_Mx，結(jié)構(gòu)穩(wěn)定性FL_M，計(jì)算節(jié)點(diǎn)緊密程度不一致性最小值f_Mx；d，M增1，更新f_Mx,g_Mx，F(xiàn)L_M；e，判斷FL_M是否增長(zhǎng)，若是，重復(fù)步驟d,否則，進(jìn)行步驟f；f，初始化種子節(jié)點(diǎn)集，以及在前m個(gè)層級(jí)中，挖掘第k個(gè)種子節(jié)點(diǎn)的影響程度R[m,k]和所在層級(jí)s[m,k],k＝1時(shí)，進(jìn)行步驟g；g，更新R[m,k]、s[m,k]，在s[m,k]層中，尋找使影響程度增加最大的節(jié)點(diǎn)作為第k個(gè)種子節(jié)點(diǎn)，加入種子集中；h，k增1，判斷k是否大于K，若是，進(jìn)行步驟i,否則，重復(fù)步驟g；i,輸出種子節(jié)點(diǎn)集。

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

本發(fā)明涉及基于社交網(wǎng)絡(luò)層級(jí)結(jié)構(gòu)的影響最大化種子集建立方法，屬于社交網(wǎng)絡(luò)技術(shù)領(lǐng)域。

背景技術(shù)

任何社會(huì)性動(dòng)物在個(gè)體與個(gè)體、群體與個(gè)體之間都存在著相互影響的關(guān)系。而人類(lèi)作為具有復(fù)雜交流手段的高級(jí)社會(huì)性動(dòng)物，社交影響力在社會(huì)生活中更是無(wú)處不在。深入認(rèn)識(shí)影響力的產(chǎn)生和傳播模式有助于理解人類(lèi)群體和個(gè)體的行為，從而能夠預(yù)期人們的行為，為政府、機(jī)構(gòu)、企業(yè)等各部門(mén)的決策提供可靠的依據(jù)和建議。比如，企業(yè)在進(jìn)行新產(chǎn)品推廣時(shí)，可以利用用戶對(duì)用戶影響力及其傳播的了解，選擇有影響力的用戶和傳播渠道幫助產(chǎn)品推廣。政府可以選擇合適的影響力群體和渠道來(lái)擴(kuò)大其政策的影響或阻止謠言的傳播。

盡管信息和影響力在社交網(wǎng)絡(luò)中的傳播復(fù)雜多樣，但排除一些干擾因素之后仍然有章可循。影響力傳播模型用來(lái)刻畫(huà)影響力在社交網(wǎng)絡(luò)中的傳播模式，目前最為流行的影響力傳播模型是獨(dú)立級(jí)聯(lián)模型和線性閾值模型，以及它們的改進(jìn)模型。而影響力傳播建模的一個(gè)主要目的是控制和優(yōu)化影響力的傳播，這其中被廣泛研究的一個(gè)核心問(wèn)題就是影響力最大化問(wèn)題。影響力最大化是在給定社交網(wǎng)絡(luò)結(jié)構(gòu)、影響力傳播模型及其參數(shù)(如獨(dú)立級(jí)聯(lián)模型和邊上的概率)的情況下，選擇k個(gè)節(jié)點(diǎn)作為種子節(jié)點(diǎn)集合，使得該集合最終影響到的節(jié)點(diǎn)數(shù)最多，它是一個(gè)NP-hard的組合優(yōu)化問(wèn)題。解決NP-hard優(yōu)化問(wèn)題的一個(gè)重要方法是利用有效的近似算法來(lái)接近最優(yōu)值，Kempe等人首先提出用Monte-Carlo模擬來(lái)模擬影響力傳播，雖然該貪心算法能夠達(dá)到(1-1/e)近似解，但是時(shí)間效率很低，尤其是當(dāng)規(guī)模很大時(shí)。后來(lái)，為了更好地平衡效率和準(zhǔn)確率這兩個(gè)問(wèn)題，諸多研究提出了各種可擴(kuò)展的影響力最大化算法，這些算法基本可以分為兩類(lèi)，一種是仍然以單個(gè)節(jié)點(diǎn)，即個(gè)體作為研究對(duì)象，在此基礎(chǔ)上加以動(dòng)力學(xué)(dynamics)特征例如時(shí)間來(lái)尋找動(dòng)態(tài)網(wǎng)絡(luò)中的種子節(jié)點(diǎn)集，或者使用最優(yōu)化方法例如模擬退火來(lái)提升算法的效率，或者加以某種限制例如成本最小化來(lái)尋找成本限制下的種子集合，或者加以更多的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)例如構(gòu)造某一節(jié)點(diǎn)的最大影響力子樹(shù)來(lái)替代Monte-Carlo模擬估計(jì)該節(jié)點(diǎn)的影響力，等等。另一種是利用群體，即社團(tuán)作為研究對(duì)象，Yu Wang等人首先提出了基于社團(tuán)的貪心算法來(lái)挖掘移動(dòng)社交網(wǎng)絡(luò)中的前k個(gè)影響力節(jié)點(diǎn)；Chen Y C等人提出一種基于社團(tuán)的影響力最大化算法，該算法包括三個(gè)步驟，即社團(tuán)檢測(cè)，候選集生成和種子選擇；Zhu C等人提出了基于分層社區(qū)結(jié)構(gòu)的算法，該方法考慮每個(gè)節(jié)點(diǎn)的2跳輸入分層網(wǎng)絡(luò)和輸出分層網(wǎng)絡(luò)，分別用于計(jì)算該節(jié)點(diǎn)所受到2跳鄰居節(jié)點(diǎn)的影響和該節(jié)點(diǎn)對(duì)2跳鄰居節(jié)點(diǎn)產(chǎn)生的影響，與啟發(fā)式算法相比，該算法獲得了更廣泛的影響范圍和更少的運(yùn)行時(shí)間。

上述方法通過(guò)改進(jìn)貪心或啟發(fā)式算法或利用社交網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu)來(lái)改進(jìn)效率和準(zhǔn)確率問(wèn)題，但是，它們都沒(méi)有考慮根據(jù)節(jié)點(diǎn)的一階和二階鄰近度劃分的社交網(wǎng)絡(luò)節(jié)點(diǎn)的層次結(jié)構(gòu)，因此還有改進(jìn)的空間。直觀地說(shuō)，影響隨著信息的擴(kuò)散而傳播，假定信息的發(fā)布者已知，那么信息的擴(kuò)散是逐層進(jìn)行的，首先傳播到與信源節(jié)點(diǎn)聯(lián)系最為緊密的節(jié)點(diǎn)，其次傳播到相對(duì)緊密的節(jié)點(diǎn)，就這樣一層一層進(jìn)行下去。本發(fā)明涉及的問(wèn)題就是劃分信息擴(kuò)散層級(jí)，然后從這些層級(jí)中找到使得影響力最大化的種子節(jié)點(diǎn)。使用本發(fā)明尋找大規(guī)模社交網(wǎng)絡(luò)中的影響力最大化種子節(jié)點(diǎn)集，可以在保證準(zhǔn)確率可比的情況下，提高運(yùn)算的效率，而且該方法還有良好的可擴(kuò)展性。