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

胡 旭,王雪珊

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

?

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

胡 旭,王雪珊

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

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

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

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

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

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

1 理論基礎

1.1 影響力傳播模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 工作基礎

2.1 單個節(jié)點成本估算

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

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

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

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

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

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

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

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

2.3 GA的流程

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

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

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

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

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

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

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

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

3 仿真實驗

3.1 實驗準備

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

表1 實驗數(shù)據(jù)集

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

3.2 實驗設計

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

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

3.3 實驗結果及分析

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

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

圖3展示了新浪微博數(shù)據(jù)集下三種GA的實驗結果。在優(yōu)化過程中,三種GA的整體優(yōu)化過程都是逐步上升的,其中GA1的上升速度比其他兩個慢,GA2上升速度略低于GA3,這是因為GA1的變異策略是向個體中隨機加入或刪減某一節(jié)點,而GA2變異策略是向個體中加入最有傳播效率的節(jié)點,GA3的變異策略是向個體中加入若干個更有傳播效率的節(jié)點,所以三種算法中GA3的上升速度更快,GA2次之,而GA1的上升速度最慢;在優(yōu)化值方面,GA1的最佳值是146.16,GA2的最佳值是147.37,GA3的最佳值是143.62,這是三者的優(yōu)化策略不同引起的(具體體現(xiàn)在三者的變異策略),而多次的實驗結果顯示出GA2更適合用來尋找最有影響傳播節(jié)點集。圖4展示了新浪微博數(shù)據(jù)集下Mixgreedy_MIC算法的實驗結果。因為Mixgreedy_MIC算法的貪心策略是在每一代有且只尋找出一個最有效率的傳播影響節(jié)點,所以每次的迭代都呈現(xiàn)穩(wěn)健上升的趨勢,同時可以觀察到其上升速度呈現(xiàn)出逐代下降的趨勢,這是因為在每一代中尋找最有效率的傳播影響節(jié)點,其效率是逐漸減小的,所以Mixgreedy_MIC算法能夠觀察到的實驗結果是總體穩(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算法的實驗結果。算法的整體優(yōu)化過程呈現(xiàn)逐步上升趨勢,不同于新浪微博數(shù)據(jù)集上的是,GA1的實驗結果較其他兩個GA具有明顯的差距,最終收斂的值也明顯小于GA2和GA3,說明GA1并不適合用來尋找Twitter數(shù)據(jù)集下的最佳影響傳播節(jié)點集。而GA3在100代以內的上升趨勢大于GA2,但在后面的遺傳過程中其優(yōu)化過程不如GA2,GA2逐步優(yōu)化并收斂于較高的值,GA3 100代之后的優(yōu)化過程波動較大,優(yōu)化效果卻不好,這也是因為三種GA的遺傳策略不同,而GA2更適合用來尋找網(wǎng)絡中最佳影響傳播節(jié)點集。圖6展示了Twitter數(shù)據(jù)集下Mixgreedy_MIC算法的實驗結果。其趨勢和新浪微博數(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求解具有不確定性,所以我們重復做了10組實驗求取平均值,三個數(shù)據(jù)集下均是GA2得到的結果最佳,所以將GA2的最終影響范圍與Mixgreedy_MIC算法進行對比,結果如表2所列。

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

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

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

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

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

4 結論

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

該算法仍有需要改進和值得研究的地方,比如遺傳算法的遺傳操作設計、算法的參數(shù)設置都會對實驗結果產(chǎn)生影響,而這些后續(xù)實驗工作還值得進一步對比分析,以達到遺傳算法求解問題的優(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)絡影響力分析[J].計算機學報,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)絡影響最大化算法[J].計算機學報,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].甘肅科學學報,2016,28(6):142-148.]

10.16468/j.cnki.issn1004-0366.2016.06.027.

2016-08-01;

2016-09-02.

胡旭(1992-)，男，安徽六安人，碩士，研究方向為社交網(wǎng)絡、數(shù)據(jù)挖掘.E-mail:Melance@tju.edu.cn.

TP311

A

1004-0366(2016)06-0142-07