[發(fā)明專利]社會網(wǎng)絡(luò)合作影響傳播最大化的初始用戶選擇方法

在審

• 申請?zhí)枺?/td>: 201511017710.6
• 申請日: 2015-12-30
• 公開（公告）號: CN105654342A
• 公開（公告）日: 2016-06-08
• 發(fā)明（設(shè)計(jì)）人: 吳鴻;岳昆;劉惟一;張彬彬;李勁
• 申請（專利權(quán)）人: 云南大學(xué)
• 主分類號: G06Q30/02
• 分類號: G06Q30/02
• 代理公司: 成都行之專利代理事務(wù)所(普通合伙) 51220
• 代理人: 溫利平;陳靚靚

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

本發(fā)明屬于社會網(wǎng)絡(luò)技術(shù)領(lǐng)域，更為具體地講，涉及一種社會網(wǎng)絡(luò)合作影 響傳播最大化的初始用戶選擇方法。

背景技術(shù)

Facebook、Twitter、LinkedIn和微信等在線社會網(wǎng)絡(luò)的普及，為商家提供了 豐富的用戶信息，從而促進(jìn)了商品促銷的發(fā)展。研究表明，相比傳統(tǒng)的媒介(如 電視)，人們更信任從朋友和親戚等相關(guān)聯(lián)的個體那獲得的信息。因此，商家可 以利用社會網(wǎng)絡(luò)來傳播信息，采用“病毒式營銷”策略來促銷商品。“病毒式營 銷”是一種廣告策略，它選擇有限的初始用戶(稱為種子)，給他們提供免費(fèi)或 打折的商品，利用客戶之間口碑效應(yīng)的優(yōu)勢來促銷商品。這些初始用戶通過社 會網(wǎng)絡(luò)把商品的信息傳播給其他客戶，使得商品的影響最大化(即社會網(wǎng)絡(luò)影 響最大化)，在商品促銷方面具有重要的實(shí)際應(yīng)用前景。

社會網(wǎng)絡(luò)影響最大化，是指在某種傳播模型下找到給定數(shù)量的最具有影響 力的用戶，使得信息的影響傳播最大。由此可知，建立傳播模型、進(jìn)而找到最 具有影響力的初始用戶，是社會網(wǎng)絡(luò)影響最大化的核心和關(guān)鍵。為此，需要建 立有效的傳播模型及相應(yīng)初始用戶選擇方法。

目前公知的傳播模型主要有線性閾值模型和獨(dú)立級聯(lián)模型，初始用戶的選 擇方法包括貪心法及其他啟發(fā)式算法。田家堂等(<計(jì)算機(jī)學(xué)報(bào)>，2011)提出 一種潛在影響和貪心法相結(jié)合的計(jì)算方法，首先尋找一部分潛在影響最大的節(jié) 點(diǎn)，然后用貪心法尋找另一部分最具有影響力的節(jié)點(diǎn)。張佩云等(<計(jì)算機(jī)工程>， 2013)提出基于概率轉(zhuǎn)移矩陣的社會網(wǎng)絡(luò)影響最大化算法，使用矩陣乘法得到 某時刻節(jié)點(diǎn)之間的影響概率。張伯雷等(<計(jì)算機(jī)學(xué)報(bào)>，2014)提出面向目標(biāo) 市場的信息最大覆蓋算法，采用聚類覆蓋的方法找到最具有影響力的初始用戶。 張波等(<專利CN201410234220.0>，2014)提出基于信任的社會網(wǎng)絡(luò)中最大化 影響節(jié)點(diǎn)的計(jì)算方法，基于節(jié)點(diǎn)的信任度和影響值得到節(jié)點(diǎn)的綜合影響。曹玖 新等(<計(jì)算機(jī)學(xué)報(bào)>，2015)提出核覆蓋的算法，是一種基于核層次特征和影 響半徑的啟發(fā)式算法，根據(jù)核數(shù)和度數(shù)這兩個屬性來選擇最具有影響力的節(jié)點(diǎn)。 吳駿等(<專利CN201510186252.2>，2015)提出一種基于社團(tuán)結(jié)構(gòu)挖掘算法的 在線社會網(wǎng)絡(luò)信息傳播最大化方法，根據(jù)社團(tuán)發(fā)現(xiàn)算法把原有的網(wǎng)絡(luò)分割為不 同社團(tuán)，分別在這些社團(tuán)對應(yīng)的子圖里尋找種子節(jié)點(diǎn)，并最終形成種子節(jié)點(diǎn)集 合，從而進(jìn)行傳播活動。

實(shí)際生活中商品之間可能存在相互關(guān)聯(lián)，商品在社會網(wǎng)絡(luò)上的影響以口碑 效應(yīng)等形式存在。例如，購買智能手機(jī)的客戶會以一定的概率購買充電寶；相 關(guān)聯(lián)商品的影響傳播具有“合作”關(guān)系，即兩種相關(guān)聯(lián)的商品可放在一起進(jìn)行 促銷。公知的初始用戶選擇方法，都只選擇一種商品(或信息)的初始用戶， 從而最大化商品的影響傳播，未考慮兩種可能存在相互關(guān)聯(lián)的商品所對應(yīng)初始 用戶的選擇。

由數(shù)據(jù)挖掘研究可知，顧客在購買一種商品的時候，會很可能同時購買另 一種商品，針對購買行為，商品之間的相互關(guān)聯(lián)可用關(guān)聯(lián)規(guī)則描述。目前公知 的關(guān)聯(lián)規(guī)則研究成果主要應(yīng)用于數(shù)據(jù)挖掘領(lǐng)域，未涉及社會網(wǎng)絡(luò)中相關(guān)聯(lián)的兩 種商品合作影響的最大化傳播。

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

本發(fā)明的目的在于克服現(xiàn)有技術(shù)的不足，提供一種社會網(wǎng)絡(luò)合作影響傳播 最大化的初始用戶選擇方法，基于顧客購買商品的關(guān)聯(lián)規(guī)則來得到用戶同時購 買兩種商品的合作影響傳播圖，進(jìn)而選擇使合作影響傳播最大化的初始用戶。

為實(shí)現(xiàn)上述發(fā)明目的，本發(fā)明社會網(wǎng)絡(luò)合作影響傳播最大化的初始用戶選 擇方法包括以下步驟：

S1：根據(jù)歷史數(shù)據(jù)得到商品A和商品B的影響傳播圖G_A和G_B；

S2：生成商品A和商品B的合作影響傳播圖G_AB，生成方法為：

計(jì)算商品A和B從用戶v向用戶v′的合作傳播概率P_AB(v,v′)：

P_AB(v,v′)＝P(B|A)×P_A(v,v′)

其中，P(B|A)表示商品A和B的置信度，P_A(v,v′)表示商品A的影響傳播圖G_A從用戶v向用戶v′的傳播概率，v,v′∈V，v≠v′；