胡 旭,王雪珊

(天津大學(xué) 管理與經(jīng)濟(jì)學(xué)部,天津 300072)

?

成本約束下影響力最大化問題研究

胡 旭,王雪珊

(天津大學(xué) 管理與經(jīng)濟(jì)學(xué)部,天津 300072)

企業(yè)希望在社交網(wǎng)絡(luò)信息傳播過程中影響到更多的用戶,以便其在有限成本約束下達(dá)到營銷目標(biāo)。依據(jù)此背景,定義了一個(gè)新的社交網(wǎng)絡(luò)影響力最大化問題:成本約束下的影響力最大化問題,即在有限成本條件下選擇一個(gè)初始節(jié)點(diǎn)集傳播信息使得最終狀態(tài)下全網(wǎng)被影響到的范圍最大化?；诰W(wǎng)絡(luò)中用戶的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和用戶交互信息衡量用戶激活成本,并在獨(dú)立級聯(lián)模型下使用遺傳算法求解上述問題,最后通過不同數(shù)據(jù)集上的實(shí)驗(yàn)驗(yàn)證遺傳算法在最終影響范圍和運(yùn)行時(shí)間上都獲得較好的效果。

社交網(wǎng)絡(luò);信息傳播;影響力最大化;遺傳算法

在Web2.0時(shí)代,互聯(lián)網(wǎng)上信息的生產(chǎn)與消費(fèi)模式已經(jīng)發(fā)生了巨大的變化,新一代社交網(wǎng)絡(luò)異軍突起,得到了前所未有的迅猛發(fā)展。社交網(wǎng)絡(luò)作為載體將人們聯(lián)接起來,社交網(wǎng)絡(luò)中的信息傳播和信息擴(kuò)散通過個(gè)體與個(gè)體之間的交互行為實(shí)現(xiàn),使得其中的個(gè)體可以進(jìn)行交流、分享以及推薦消息等各類交互行為。與之對應(yīng),大型社交網(wǎng)絡(luò)下的社會網(wǎng)絡(luò)研究成為研究的熱點(diǎn),而社交網(wǎng)絡(luò)影響力最大化問題是社交網(wǎng)絡(luò)當(dāng)前研究的核心問題之一。

Richardson等[1]將影響力最大化問題歸納為如何選取社交網(wǎng)絡(luò)中某些有影響力的節(jié)點(diǎn),通過他們向網(wǎng)絡(luò)中其他成員推送信息,從而達(dá)到信息傳播的目的。但隨著研究的深入,學(xué)者發(fā)現(xiàn)只是設(shè)定節(jié)點(diǎn)集中的節(jié)點(diǎn)個(gè)數(shù)并不能很好地符合實(shí)際情境,應(yīng)考慮不同的環(huán)境設(shè)置以更好地模擬實(shí)際情境。例如針對每個(gè)節(jié)點(diǎn)激活成本的考量,對于意見領(lǐng)袖和普通用戶的激活成本應(yīng)當(dāng)在量級上區(qū)分開來,而在現(xiàn)實(shí)中這兩類人群的激活成本是大相徑庭的。對于這個(gè)問題,研究者相對應(yīng)地做了資源受限的影響力傳播的研究工作。Goyal等[2]定義了MINTSS(minimum target set selection)問題,意義在于在虛擬的市場營銷中,用最小的預(yù)算取得想要達(dá)到的傳播效果。與此同時(shí),Wang等[3]定義了IMIC(influence maximization with limited cost)問題,給定預(yù)算上限,在此基礎(chǔ)上求取網(wǎng)絡(luò)中的傳播影響范圍。

以上述研究為基礎(chǔ),為了更好地模擬企業(yè)傳播信息影響力的現(xiàn)實(shí)環(huán)境,對模擬信息傳播環(huán)境設(shè)置兩個(gè)基本要素:①節(jié)點(diǎn)間的相互傳播影響概率依照文獻(xiàn)慣例設(shè)為常量p=0.01[4];②初始激活單個(gè)節(jié)點(diǎn)時(shí)需要付出對應(yīng)代價(jià),不同節(jié)點(diǎn)擁有不同的激活成本,而我們的問題會設(shè)定一個(gè)總的成本上限。依據(jù)這兩點(diǎn)提出成本約束下影響力最大化問題,即在成本限制下使得信息在初始節(jié)點(diǎn)集傳播下影響力達(dá)到最大化,并使用優(yōu)化算法來求取影響力最大傳播節(jié)點(diǎn)集。

1 理論基礎(chǔ)

1.1 影響力傳播模型

社交網(wǎng)絡(luò)影響力最大化問題[1]是如何選取k個(gè)種子節(jié)點(diǎn)集合進(jìn)行傳播,從而使最終傳播的影響范圍最大。從文獻(xiàn)[4]中獲知Kempe和 Kleinberg形式化了該問題,基于獨(dú)立級聯(lián)模型和線性閾值模型證明此問題是一個(gè)NP-hard問題,并提出離散優(yōu)化方法來求解該問題。相比較而言,獨(dú)立級聯(lián)模型在現(xiàn)實(shí)工作中應(yīng)用得更為廣泛,而線性閾值模型在關(guān)注鄰居間的累積效應(yīng)時(shí)才會被優(yōu)先考慮。

(1)獨(dú)立級聯(lián)模型 獨(dú)立級聯(lián)模型(independent cascade model)基于概率論描述了一個(gè)動態(tài)的、“多米諾骨牌”式的信息擴(kuò)散過程。在獨(dú)立級聯(lián)模型中,每條有向邊(u,v)都有一個(gè)傳播概率pu,v∈[0,1],pu,v表示通過邊(u,v)的傳播節(jié)點(diǎn)u能夠激活節(jié)點(diǎn)v的概率[6]。

(2)線性閾值模型 線性閾值模型(linear threshold model)來源于數(shù)學(xué)研究,是以承接者為核心的模型。LT模型認(rèn)為社交網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都有一個(gè)信息傳播的閾值,當(dāng)這個(gè)節(jié)點(diǎn)從它的鄰節(jié)點(diǎn)接收到的累積影響大于這個(gè)閾值時(shí),這個(gè)節(jié)點(diǎn)就由未激活狀態(tài)進(jìn)入激活狀態(tài)。對于網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn),都會有一個(gè)設(shè)定的激活閾值θv,每條有向邊(u,v)都有一個(gè)影響權(quán)重bu,v,且這個(gè)權(quán)重需要滿足∑vbu,v≤1[7]。

1.2 影響力最大化問題描述及定義

以有向圖G來表示社交網(wǎng)絡(luò),假設(shè)在G中初始激活節(jié)點(diǎn)集為A,集合A之外的所有節(jié)點(diǎn)都是非激活的,RS(A)表示社交網(wǎng)絡(luò)中最終能處于激活狀態(tài)的節(jié)點(diǎn)集合,則初始節(jié)點(diǎn)激活A(yù)的影響力范圍可以定義為

φ(A)=|RS(A)|,

其中:φ(A)表示最終激活的節(jié)點(diǎn)數(shù)目。

研究在原有的影響力最大化問題的基礎(chǔ)上添加了成本約束,在選擇初始激活節(jié)點(diǎn)集時(shí)加入單個(gè)節(jié)點(diǎn)的激活成本考慮,使得信息在獨(dú)立級聯(lián)模型的傳播能更好地模擬現(xiàn)實(shí)世界的信息擴(kuò)散過程。在此基礎(chǔ)上將影響最大化問題表示為一個(gè)離散最優(yōu)化問題,定義為:在社交網(wǎng)絡(luò)G中,量化設(shè)定單個(gè)節(jié)點(diǎn)的激活成本,給定一個(gè)限制成本C,信息按照特定的傳播模型在G中傳播。找出在有限成本下的一個(gè)合適的初始激活節(jié)點(diǎn)集A,使得A在信息傳播結(jié)束后最終影響的范圍最大,即社交網(wǎng)絡(luò)中最終處于激活狀態(tài)的節(jié)點(diǎn)數(shù)目最多,亦即φ(A)的數(shù)值最大。

1.3 影響力最大化問題的求解

在傳統(tǒng)的影響力最大化問題求解上,采用的方法主要是貪心算法和啟發(fā)式算法。

貪心算法起源于爬山貪心算法[4],每一步都選擇當(dāng)前最有影響力的節(jié)點(diǎn),但貪心算法的時(shí)間復(fù)雜度較高,并不適合大規(guī)模社交網(wǎng)絡(luò)的求解。后面利用IC模型的次模特性給出貪心算法的改進(jìn)方法[8],能夠有效地縮小貪心算法的時(shí)間復(fù)雜度,但在大型社交網(wǎng)絡(luò)表現(xiàn)不佳。

啟發(fā)式算法則是根據(jù)社交網(wǎng)絡(luò)的網(wǎng)絡(luò)結(jié)構(gòu)和傳播特性來解決問題。在社交網(wǎng)絡(luò)中,以度數(shù)遞減的順序選取k個(gè)最大度數(shù)節(jié)點(diǎn)的啟發(fā)式節(jié)點(diǎn)選擇策略是長期以來的一個(gè)標(biāo)準(zhǔn)方法,被學(xué)者們稱為“度中心性”,還有基于節(jié)點(diǎn)的中介中心性、緊密中心性設(shè)計(jì)的啟發(fā)式算法解決影響力最大化問題。但啟發(fā)式算法的一個(gè)很大弊病在于其不能保證最終的影響效果。

也有人提出其他的算法。Estevez等[9]提出集合覆蓋貪心算法,每次選擇覆蓋范圍最大的節(jié)點(diǎn),但再覆蓋并不等于激活,所以其實(shí)驗(yàn)結(jié)果并不好。田家堂等[10]提出HPG算法,先啟發(fā)式地選擇一些具有隱性影響力的節(jié)點(diǎn),再貪心式地搜索出一些當(dāng)前最有影響力的節(jié)點(diǎn),取得了不錯(cuò)的效果。

衡量解決影響力最大化問題算法有兩個(gè)重要指標(biāo):傳播影響范圍和時(shí)間復(fù)雜度[4]。影響范圍意味著傳播效果衡量,而時(shí)間復(fù)雜度則是衡量算法是否能夠應(yīng)用于大型數(shù)據(jù)集的標(biāo)準(zhǔn)。貪心算法能夠取得不錯(cuò)的影響范圍卻擁有很大的時(shí)間復(fù)雜度,所以并不適用于大型網(wǎng)絡(luò),而啟發(fā)式算法雖然極大降低了時(shí)間復(fù)雜度,但在影響范圍上卻有不小的缺陷。針對以上兩點(diǎn)特性,遺傳算法則具有一定優(yōu)勢。遺傳算法(GA,genetic algorithm)是模擬遺傳選擇和自然淘汰的生物進(jìn)化過程的計(jì)算模型,它是一種新的全局優(yōu)化搜索算法,因其簡單通用、魯棒性強(qiáng)、適用于并行處理而被廣泛而深入的研究。遺傳算法從歷來離散的搜索空間的優(yōu)化搜索算法擴(kuò)展到具有獨(dú)特的規(guī)則生成功能的嶄新的機(jī)器學(xué)習(xí)算法,而并行處理的遺傳算法更是縮減不小的計(jì)算時(shí)間。所以在研究中,提出GA來解決影響力最大化問題。

2 工作基礎(chǔ)

2.1 單個(gè)節(jié)點(diǎn)成本估算

Weng等[11]以PageRank為主要方法對節(jié)點(diǎn)影響力做rank,然后根據(jù)rank值對節(jié)點(diǎn)成本賦值。而研究采用的方法是結(jié)合節(jié)點(diǎn)的網(wǎng)絡(luò)拓?fù)浣Y(jié)果與用戶信息兩部分內(nèi)容量化成本的估算。

成本估算主要綜合考慮了節(jié)點(diǎn)的以下信息:節(jié)點(diǎn)的出度(Fan)以及入度(Att),節(jié)點(diǎn)發(fā)布微博的轉(zhuǎn)發(fā)數(shù)(AVGR)、評論數(shù)(AVGC),并結(jié)合這幾方面信息給出單個(gè)節(jié)點(diǎn)成本C的估算公式為

2.2 成本約束下影響力最大化的GA求解

由于以往的算法都會有不同方面的缺陷,我們提出使用GA來解決成本限制下影響力最大化問題。構(gòu)造的GA將備選節(jié)點(diǎn)集S作為一條染色體,采用01編碼,初始傳播節(jié)點(diǎn)集A是由節(jié)點(diǎn)集S中基因位為1對應(yīng)的節(jié)點(diǎn)組成,最終的影響范圍值作為適應(yīng)值函數(shù)(在IC模型下使用蒙特卡洛模擬得出結(jié)果[5]),終止的條件為IC模型中沒有節(jié)點(diǎn)激活的過程。經(jīng)過一系列的遺傳過程,具有最大適應(yīng)值對應(yīng)的初始節(jié)點(diǎn)集便是所求問題的最優(yōu)解。

對GA的遺傳策略主要做以下三部分介紹:

(1)交叉遺傳策略。遺傳算法中的交叉遺傳在遺傳操作中起到核心作用,所謂交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。研究中的GA采用了兩點(diǎn)交叉的策略,即在染色體中隨機(jī)選擇兩個(gè)點(diǎn),將父母染色體這兩個(gè)點(diǎn)之間的基因進(jìn)行交叉替換,生成兩條新的染色體。

(2)變異遺傳策略。遺傳算法的變異遺傳是遺傳操作的重要組成部分。所謂變異是指將個(gè)體染色體的某個(gè)或某些基因位進(jìn)行突變,變異遺傳的最大意義在于幫助算法找出全域最優(yōu)解。研究中的GA采用的具體變異方法是針對單個(gè)染色體,隨機(jī)挑選基因位,將編碼的0或1改為1或0,生成新的染色體。

(3)精英保留策略。精英保留策略是保留當(dāng)代種群中適應(yīng)度最高的染色體,并在進(jìn)化過程中與歷代的精英對比,留下適應(yīng)度更高的個(gè)體作為新的精英個(gè)體,同時(shí)因?yàn)檫x擇遺傳時(shí)采取的是輪盤賭方法,當(dāng)代的精英個(gè)體有更大的概率參與遺傳過程,與其他個(gè)體一起經(jīng)過交叉和變異遺傳操作生成新的個(gè)體。

2.3 GA的流程

(1) 生成初代種群S={S1,S2,…,SM},每一個(gè)節(jié)點(diǎn)集S要滿足總成本低于成本限制C;

(2) 使用蒙特卡洛方法計(jì)算種群中單個(gè)染色體的適應(yīng)值函數(shù)大小,將最大值作為當(dāng)代的最佳值,并與原先的最佳值進(jìn)行比較,較大值作為最佳值保留;

(3) 基于種群中所有染色體的適應(yīng)值函數(shù),進(jìn)行輪盤賭方法抽取父母染色體;

(4) 根據(jù)pc判斷是否進(jìn)行交叉操作;

(5) 根據(jù)pb判斷是否進(jìn)行變異操作;

(6) 將依據(jù)當(dāng)代生成的兩條子代染色體添加進(jìn)入新的種群集S’;

(7) 記錄遺傳操作的代數(shù),若代數(shù)超過G代則遺傳結(jié)束并進(jìn)入下一步,否則將回到第2步繼續(xù)遺傳;

(8) 將記錄下來的最佳值作為最大傳播范圍,對應(yīng)的節(jié)點(diǎn)集A作為最佳初始傳播節(jié)點(diǎn)集。

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)準(zhǔn)備

(1)數(shù)據(jù)集 研究采用了三個(gè)數(shù)據(jù)集,數(shù)據(jù)集1來源于argXiv.org,是學(xué)者間相互合作的統(tǒng)計(jì)網(wǎng)站,如果學(xué)者間有過合作則兩位學(xué)者會有一層聯(lián)系存在;新浪微博和Twitter則是來源于國內(nèi)和國外著名的社交網(wǎng)絡(luò)網(wǎng)站,一個(gè)節(jié)點(diǎn)代表一個(gè)用戶,相互的關(guān)注關(guān)系構(gòu)成邊關(guān)系。具體信息如表1所列。

表1 實(shí)驗(yàn)數(shù)據(jù)集

(2) 實(shí)驗(yàn)環(huán)境 研究的實(shí)驗(yàn)環(huán)境為Intel Pentium4 3.40 GHz的CPU,3.40 GB的內(nèi)存。操作系統(tǒng)為Windows XP,實(shí)驗(yàn)所用算法均用python進(jìn)行編程實(shí)現(xiàn)。

3.2 實(shí)驗(yàn)設(shè)計(jì)

解決影響力最大化問題時(shí)基于獨(dú)立級聯(lián)模型進(jìn)行實(shí)驗(yàn),節(jié)點(diǎn)間傳播概率設(shè)為定值p。所做實(shí)驗(yàn)為了驗(yàn)證GA能夠很好地解決加入成本限制的影響力最大化問題,分別在三個(gè)數(shù)據(jù)集下設(shè)計(jì)三種不同遺傳策略的GA來求取最優(yōu)解,GA1是傳統(tǒng)的遺傳算法,GA2是在變異操作中向初始傳播節(jié)點(diǎn)集加入當(dāng)前邊際影響力與成本比值最大的節(jié)點(diǎn),GA3是在變異操作中向初始傳播節(jié)點(diǎn)集盡可能加入邊際影響力的節(jié)點(diǎn)。遺傳算法參數(shù)設(shè)置:交叉概率設(shè)為0.8,變異概率設(shè)為0.1,種群個(gè)體數(shù)目M設(shè)為100,遺傳代數(shù)G設(shè)為300。

為了便于進(jìn)行實(shí)驗(yàn)效果對比,在提出的Mixgreedy算法[8]基礎(chǔ)上,將每代選擇邊際影響范圍最大的節(jié)點(diǎn)改為每代選擇邊際影響范圍與成本比值最大的節(jié)點(diǎn),設(shè)計(jì)Mixgreedy_MIC算法來求解最大化問題。

3.3 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)結(jié)果將在算法得出的最終影響范圍和算法運(yùn)行時(shí)間兩方面對進(jìn)行比較,以便分析判斷GA能否很好地既有質(zhì)又有效地解決影響力最大化問題。

(1) 固定成本下影響范圍比較 圖1展示了argXiv.org數(shù)據(jù)集下三種GA的實(shí)驗(yàn)結(jié)果。在優(yōu)化過程中,三種GA的整體優(yōu)化過程都是逐步上升的,其中GA1的上升速度相比其他兩個(gè)在上升幅度和最終優(yōu)化結(jié)果上都有較大的差異,GA2上升速度沒有GA3快,這是因?yàn)镚A1的變異策略是向個(gè)體中隨機(jī)加入或刪減某一節(jié)點(diǎn),而GA2變異策略是向個(gè)體中加入最有傳播效率的節(jié)點(diǎn),GA3的變異策略是向個(gè)體中加入若干個(gè)更有傳播效率的節(jié)點(diǎn);在優(yōu)化值方面,GA2和GA3最終收斂的取值差不多,而實(shí)驗(yàn)結(jié)果顯示出GA2更適合用來尋找最有影響傳播節(jié)點(diǎn)集。圖2展示了argXiv.org數(shù)據(jù)集下Mixgreedy_MIC算法的實(shí)驗(yàn)結(jié)果。因?yàn)镸ixgreedy_MIC算法的貪心策略是在每一代有且只尋找出一個(gè)最有效率的傳播影響節(jié)點(diǎn),所以每次的迭代都呈現(xiàn)穩(wěn)健上升的趨勢,而在上升時(shí)呈現(xiàn)直線上升,這跟數(shù)據(jù)集本身有關(guān),argXiv.org數(shù)據(jù)集較小,節(jié)點(diǎn)間沒有很大的差異性,其影響力類似。所以Mixgreedy_MIC算法能夠觀察到的實(shí)驗(yàn)結(jié)果是總體直線上升趨勢。

圖3展示了新浪微博數(shù)據(jù)集下三種GA的實(shí)驗(yàn)結(jié)果。在優(yōu)化過程中,三種GA的整體優(yōu)化過程都是逐步上升的,其中GA1的上升速度比其他兩個(gè)慢,GA2上升速度略低于GA3,這是因?yàn)镚A1的變異策略是向個(gè)體中隨機(jī)加入或刪減某一節(jié)點(diǎn),而GA2變異策略是向個(gè)體中加入最有傳播效率的節(jié)點(diǎn),GA3的變異策略是向個(gè)體中加入若干個(gè)更有傳播效率的節(jié)點(diǎn),所以三種算法中GA3的上升速度更快,GA2次之,而GA1的上升速度最慢;在優(yōu)化值方面,GA1的最佳值是146.16,GA2的最佳值是147.37,GA3的最佳值是143.62,這是三者的優(yōu)化策略不同引起的(具體體現(xiàn)在三者的變異策略),而多次的實(shí)驗(yàn)結(jié)果顯示出GA2更適合用來尋找最有影響傳播節(jié)點(diǎn)集。圖4展示了新浪微博數(shù)據(jù)集下Mixgreedy_MIC算法的實(shí)驗(yàn)結(jié)果。因?yàn)镸ixgreedy_MIC算法的貪心策略是在每一代有且只尋找出一個(gè)最有效率的傳播影響節(jié)點(diǎn),所以每次的迭代都呈現(xiàn)穩(wěn)健上升的趨勢,同時(shí)可以觀察到其上升速度呈現(xiàn)出逐代下降的趨勢,這是因?yàn)樵诿恳淮袑ふ易钣行实膫鞑ビ绊懝?jié)點(diǎn),其效率是逐漸減小的,所以Mixgreedy_MIC算法能夠觀察到的實(shí)驗(yàn)結(jié)果是總體穩(wěn)健上升,而上升速度逐代下降的趨勢。

圖1 GA在數(shù)據(jù)集1的傳播范圍Fig.1 Spreading range of GA algorithm in data set 1

圖2 Mixgreedy_MIC算法在數(shù)據(jù)集1的傳播范圍Fig.2 Spreading range of Mixgreedy_MIC algorithm in data set 1

圖3 GA在數(shù)據(jù)集2的傳播范圍Fig.3 Spreading range of GA algorithm in data set 2

圖4 Mixgreedy_MIC算法在數(shù)據(jù)集2的傳播范圍Fig.4 Spreading range of Mixgreedy_MIC algorithm in data set 2

圖5展示了Twitter數(shù)據(jù)集下三種GA算法的實(shí)驗(yàn)結(jié)果。算法的整體優(yōu)化過程呈現(xiàn)逐步上升趨勢,不同于新浪微博數(shù)據(jù)集上的是,GA1的實(shí)驗(yàn)結(jié)果較其他兩個(gè)GA具有明顯的差距,最終收斂的值也明顯小于GA2和GA3,說明GA1并不適合用來尋找Twitter數(shù)據(jù)集下的最佳影響傳播節(jié)點(diǎn)集。而GA3在100代以內(nèi)的上升趨勢大于GA2,但在后面的遺傳過程中其優(yōu)化過程不如GA2,GA2逐步優(yōu)化并收斂于較高的值,GA3 100代之后的優(yōu)化過程波動較大,優(yōu)化效果卻不好,這也是因?yàn)槿NGA的遺傳策略不同,而GA2更適合用來尋找網(wǎng)絡(luò)中最佳影響傳播節(jié)點(diǎn)集。圖6展示了Twitter數(shù)據(jù)集下Mixgreedy_MIC算法的實(shí)驗(yàn)結(jié)果。其趨勢和新浪微博數(shù)據(jù)集上Mixgreedy_MIC算法的表現(xiàn)類似,呈穩(wěn)步上升趨勢,上升速度逐代減緩。

圖5 GA在數(shù)據(jù)集3的傳播范圍Fig.5 Spreading range of GA algorithm in data set 3

圖6 Mixgreedy_MIC算法在數(shù)據(jù)集3的傳播范圍Fig.6 Spreading range of Mixgreedy_MIC algorithm in data set 3

由于GA求解具有不確定性,所以我們重復(fù)做了10組實(shí)驗(yàn)求取平均值,三個(gè)數(shù)據(jù)集下均是GA2得到的結(jié)果最佳,所以將GA2的最終影響范圍與Mixgreedy_MIC算法進(jìn)行對比,結(jié)果如表2所列。

表2 算法在數(shù)據(jù)集中最終達(dá)到的傳播范圍

從表2可以看到,用GA來解決成本限制下的影響力最大化問題,在三個(gè)數(shù)據(jù)集上的激活范圍都接近或優(yōu)于Mixgreedy_MIC算法,這證明GA能夠達(dá)到Mixgreedy_MIC算法在影響傳播范圍上的效果,可以用來解決成本約束下影響力最大化問題,在一代代的優(yōu)化中,GA求出的可行解能夠不斷優(yōu)化以達(dá)到最優(yōu)解。

(2) 運(yùn)行時(shí)間比較 因?yàn)槿NGA中GA2的影響效果最優(yōu),所以我們將10組GA2時(shí)間的平均值作為GA的運(yùn)行時(shí)間,并與貪心算法的運(yùn)行時(shí)間進(jìn)行算法時(shí)間復(fù)雜度比較。數(shù)據(jù)集下算法的運(yùn)行時(shí)間見圖7。從圖7可以清楚地看到,在較小的數(shù)據(jù)集GA的運(yùn)行時(shí)間略小于Mixgreedy_MIC算法,而在大型數(shù)據(jù)集Twitter中,GA的運(yùn)行時(shí)間明顯少于Mixgreedy_MIC算法。我們可以看到GA在最終影響范圍方面能夠達(dá)到Mixgreedy_MIC算法的同時(shí),在算法運(yùn)行時(shí)間上也有很大程度的優(yōu)化,同時(shí)GA在大規(guī)模數(shù)據(jù)集上具有良好的可拓展性,使得GA更加適合用來求解影響力最大化問題。

圖7 數(shù)據(jù)集下算法的運(yùn)行時(shí)間Fig.7 Operating time of algorithm in data set

在最終影響范圍和算法運(yùn)行時(shí)間兩方面的衡量GA都能達(dá)到不錯(cuò)的效果,所以綜上所述我們得出結(jié)論,可以用GA來對成本約束下影響力最大化問題求解。

4 結(jié)論

在獨(dú)立級聯(lián)模型來模擬信息傳播的基礎(chǔ)上,量化單個(gè)節(jié)點(diǎn)的獨(dú)立激活成本,定義了成本約束下影響力最大化問題,并提出使用遺傳算法來解決該問題。通過實(shí)驗(yàn)對比分析發(fā)現(xiàn),遺傳算法能夠很好地解決成本約束下影響力最大化問題,其實(shí)際的影響范圍能夠達(dá)到貪心算法的效果,并在計(jì)算時(shí)間上有很大程度的優(yōu)化,且GA自身的可拓展性使得其比貪心算法更適用于大型社交網(wǎng)絡(luò)。

該算法仍有需要改進(jìn)和值得研究的地方,比如遺傳算法的遺傳操作設(shè)計(jì)、算法的參數(shù)設(shè)置都會對實(shí)驗(yàn)結(jié)果產(chǎn)生影響,而這些后續(xù)實(shí)驗(yàn)工作還值得進(jìn)一步對比分析,以達(dá)到遺傳算法求解問題的優(yōu)化和完善。

[1]Richardson M,Domingos P,Glance N.Mining Knowledge-sharing Sites for Viral Marketing[C]//Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Edmonton,2002:61-70.

[2] Goyal A,Bonchi F,Lakshmanan L V S,et al.On Minimizing Budget and Time in Influence Propagation over Social Networks[J].Social Network Analysis and Mining,2013,3(2):179-192.

[3]Wang Y,Huang W,Zong L,et al.Influence Maximization with Limit Cost in Social Network[J].Science China Information Sciences,2013,56(7):1-14.

[4] 吳信東,李毅,李磊.在線社交網(wǎng)絡(luò)影響力分析[J].計(jì)算機(jī)學(xué)報(bào),2014,37(4):735-752.

[5] Kempe D,Kleinberg J,Tardos E.Maximizing the Spread of Influence Through a Social Network[C]//Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Washington DC,2003:137-146.

[6]Goldenberg J,Libar B,Muller E.Talk of the Network:A Complex Systems Look at the Underlying Process of Word-of-Mouth[J].Marketing letters,2001,12(3):211-223.

[7] Granovetter M.Threshold Models of Collective Behavior[J].American Journal of Sociology,1978,83(6):1 420-1 443.

[8] Chen Wei,Wang Yajun,Yang Siyu.Efficient Influence Maximization in Social Networks[C]//Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Paris,2009:199-208.

[9]Estevez Pablo A,Vera Pablo,Saito Kazumi.Selecting the Most Influential Nodes in Social Networks[C]//Proceedings of the International Joint Conference on Neural Networks.Orlando,2007:2 397-2 402.

[10] 田家堂,王軼彤,馮小軍.一種新型的社會網(wǎng)絡(luò)影響最大化算法[J].計(jì)算機(jī)學(xué)報(bào),2011,34(10):1 956-1 965.

[11] Weng J,Lim EP,Jiang J, et al.TwitterRank:Finding Topic-sensitive Influential Twitterers[C]//Proceedings of the 3th ACM International Conference on Web Search & Data Mining.New York,2010:261-270.

Study on Influence Maximization Problem under the Cost Constraint

Hu Xu,Wang Xueshan

(College of Management and Economics,Tianjin University,Tianjin 300072,China)

Enterprise excepts to influence more user in the spreading process of social network information so that they can achieve marketing goals under the constraint of limited cost.Based on this background,define a new social network influence maximization problem:the influence maximization problem under cost constraint that is select a initial node set under the condition of limited cost to spread information so that the influenced range in the whole network can be maximized at the final state.This paper bases on the network topological structure of user and user interaction information in the network to measure the user activation cost,solve the above problems by genetic algorithm in the Independent Cascade Model and use the experiments of different data set to verify that the genetic algorithm has good effect on the final influenced range and operating time at last.

Social network;Information spreading;Influence maximization;Genetic algorithm

Hu Xu,Wang Xueshan.Study on Influence Maximization Problem under the Cost Constraint[J].Journal of Gansu Sciences,2016,28(6):142-148.[胡旭,王雪珊.成本約束下影響力最大化問題研究[J].甘肅科學(xué)學(xué)報(bào),2016,28(6):142-148.]

10.16468/j.cnki.issn1004-0366.2016.06.027.

2016-08-01;

2016-09-02.

胡旭(1992-)，男，安徽六安人，碩士，研究方向?yàn)樯缃痪W(wǎng)絡(luò)、數(shù)據(jù)挖掘.E-mail:Melance@tju.edu.cn.

TP311

A

1004-0366(2016)06-0142-07