基于成本效益影響大化算法分析與設(shè)計

隨著近隨著近些年互聯(lián)網(wǎng)的飛速發(fā)展，社交網(wǎng)絡(luò)應(yīng)運而生，例如國外的Facebook、Twitter以及針對這種特定的營銷模式，學(xué)術(shù)界也進行了許多研究，關(guān)注點在如何選擇最初的用戶作為信ongosRcrsonAgorthm，于概率覆蓋范圍的惰性節(jié)點選擇算法（ProbCoverLFAlgorithm。在本文研究成果的基礎(chǔ)上，IAstheAsthedevelopmentoftheInternet,moreandmoreonlinesocialnetworksemerge,suchasFacebookandTwitter,Chineserenrenandsina-weibo.Theonlinesocialnetworkprovidesanewsocialmodeltothepeople,andreflectsthesocialrelationsinreallife.Atthesametime,anewnetworksbasedontheword-of-mouth,justasadvertisement.Howtoselectasetofseednodestodisseminatetheinformationthatmaximizesthetotalnumberofnodesinfluencedisahottopic,calledinfluencemaximizationproblem.However,theresearchonclassicinfluencemaximizationproblemhasignoredthedifferencesbetweenuserswhenchoosingtheinitialsourceofinformation.Butdiffererntnodeshavedifferentcoststobeselected,theactualmarketinghasbudgetconstraints,howtogetthebestmarketingeffectinthisconditionneedstoreconsider.Basedontheabove,thispapergivesthedefinitionofusercost,andputsforwardtheinfluencemaximizationproblembasedoncost-effective.Tosolvethisproblem,thispapercombinesthefeaturesofnetworktopologyandinfluencepropagationmodel,andproposesaheuristicalgorithmbasedonprobabilitycoverage(ProbCoverAlgorithm),thenproposestheimprovedcoveragealgorithm(ProbCoverLFAlgorithm)usingsubmodularandlazyforwardcomputingtechnology.Basedontheresearch,aprototypesystemisdesignedandimplementationed.Inthispaper,experimentswerecarriedoutonthethreedatasetsandindependentcascademodel,andtheindependentcascademodelusesfixedprobabilityandvariableprobabilityrespectively,theexperimentalresultsshowthat:(a)intherangeofinfluence,thealgorithmsproposedinthispaperisbetterthanthetraditionalheuristicalgorithm,especiallyinthevariableprobabilityindependentcascademodel;(b)inthetimeefficiency,althoughtherunningtimeofthealgorithmsproposedinthispaperislongthanthetraditionalheuristicalgorithms,butisstillintheacceptablerange.TwoaspectsoftheinfluencescopeandtimeefficiencyprovetheeffectivenessoftheproposedalgorithmsinthisKeywords:socialnetworks;influencemaximization;cost-effective;probabilitycoverage;摘 目 第一章緒 研究背景與意 摘 目 第一章緒 研究背景與意 國內(nèi)外研究現(xiàn) 原始影響最大化問題研究現(xiàn) 現(xiàn)狀總 研究目標(biāo)及內(nèi) 論文組織結(jié) 相關(guān)理論知 社會網(wǎng) 影響力傳播模 獨立級聯(lián)模 線性閾值模 其他傳播模 基于成本效益的影響最大化問 形式化定 評價指 問題難 本章小 概率覆蓋算 節(jié)點成本建 成本的意 成本的定 節(jié)點概率覆蓋范 節(jié)點影響力分 算法思 算法描 選擇初始節(jié)點集 本章小 利用子模函數(shù)特性的惰性節(jié)點選擇算 子模函數(shù)特 惰性節(jié)點選擇算 本章小 實驗設(shè)計與分 實驗環(huán) 實驗數(shù)據(jù) 實驗設(shè) 實驗結(jié)果及分實驗結(jié)果及分 固定概率的IC模型實驗結(jié)果與分 變概率下的IC模型實驗結(jié)果與分 實驗結(jié)果小 本章小 第六章系統(tǒng)實 原型系統(tǒng)整體架 原型系統(tǒng)實 開發(fā)環(huán) 系統(tǒng)實 本章小 第七章總結(jié)與展 工作總 研究展 致 參考文 作者簡 第一章緒論第一章緒論1.1研究背景與意第一章緒論第一章緒論1.1研究背景與意（而非“群體明確的邊界和秩序）的社會組織形式，也是西方社會學(xué)從19世紀(jì)60年代興起的一種分析視角，社會網(wǎng)絡(luò)分析并不認(rèn)為人是由個體規(guī)范或者群體會網(wǎng)絡(luò)的主體是人，在網(wǎng)絡(luò)中以節(jié)點來表示，借由人們之間各種不同的社會關(guān)系相對穩(wěn)定的關(guān)系體系，社會網(wǎng)絡(luò)關(guān)注的是人們之間的互動和聯(lián)系，社會互動會影社會網(wǎng)絡(luò)，圖1.1和圖1.2是CIC1發(fā)布的近兩年中國社會化媒體格局概覽。這些在線社交網(wǎng)絡(luò)大大降低了人們社交的時間和物質(zhì)成本，并且在很大程度上將線下真實的人際關(guān)系網(wǎng)絡(luò)復(fù)制到了線上，真實地反映了人們的社會關(guān)系，社交網(wǎng)絡(luò)在種全新的營銷模式——“病毒式營銷（viralmarketing病毒營銷的基礎(chǔ)是“口（word-mouth，Domingos和Richardson等人[2]最早將影響最大化問題歸納為一個算法問題11Kempe，Kleinberg和Tardos[3]首次把影響Kempe，Kleinberg和Tardos[3]首次把影響最大化問題形式化為一個離散最優(yōu)化大化，并證明在多種傳播模型下，影響最大化問題是一個NP-hard問題。之后許多成本“一視同仁，然而事實并非如此，請明星做推廣與普通人做推廣所需要的花費相差巨大，不同的明星之間也是千差萬別。文獻(xiàn)[]圖1.12013年中國社會化媒體格1.22014年中國社會化媒體格1.2國內(nèi)外研究現(xiàn)2第一章緒論 原始影響最大化問第一章緒論 原始影響最大化問題研究G（V,E）中，VE集合，圖中的邊既可以是無向邊也可以是有向邊，例如Facebook和人人網(wǎng)這種Twitter（inactive，在圖中尋找kA（kDomingos和Richardson等人[2]首先將影響最大化問題歸納為一個算法問題，Kempe，KleinbergTardos[3]首次把影響最大化問題形式化為一個離散最優(yōu)化k個節(jié)點作為初始受眾節(jié)點使得最終受眾數(shù)量最大化，并證明在多種傳播模型下，影響最大化問題是一個NP-hard問題。其形式化定義如下：給定一個正整數(shù)k和一個特定傳播模型，如何在網(wǎng)絡(luò)A=argmax{R(A)|A?V,|A|=等人首先提出貪心爬山算法來近似求解影響最大化問題，通過蒙3效果可以達(dá)到效果可以達(dá)到最優(yōu)解63%，但是其時間復(fù)雜度太高，之后許多研究利用社會絡(luò)呈現(xiàn)出的“小世界”特性[5][6]提出許多時間效率較高的啟發(fā)式算法，例如DegreeDiscount算法[7]、SCG法[8]和k-核算法[9]等等，這些啟發(fā)式算法在降低了兩種改進的貪心算法NewGreedy和MixedGreedy，進一步對傳統(tǒng)貪心算法進響的邊，然后在子圖中考慮影響傳播，縮小計算規(guī)模。MixedGreedy分兩步選擇kChenWeiDegreeDiscount7]，它優(yōu)盡可能的把這些種子節(jié)點分散，SCG算法[8]通過將節(jié)點設(shè)置為覆蓋狀態(tài)和未覆生鄰居重疊現(xiàn)象。PageRank[11]是Google用來標(biāo)識網(wǎng)頁重要性的一種方法，這種思想也可以用來在社會網(wǎng)絡(luò)中尋找影響力節(jié)點。PMIA算法[12]通過計算每個PMIA力傳播方面，核數(shù)比度數(shù)和介數(shù)等節(jié)點屬性有更強的傳播力，以k核為基礎(chǔ)的CCA算法[9]也有不錯的表現(xiàn)。利用社區(qū)劃分的思想求解影響最大化問題也是一種方法，Galstyan等人[14]第一次提出了利用網(wǎng)絡(luò)的社區(qū)性質(zhì)求解影響力最大化問題，之后WangYu[15]等人提出了一種基于社區(qū)發(fā)現(xiàn)的CGA(Community-basedGreedyAlgorithm)算法獲取，社區(qū)中節(jié)點選擇策略采用MixGreedy算法。CaoTianyu等人[16]也提出了OASNETOASNET4第一章緒論種子節(jié)點。不同的是OASNET算法采用MaxDegree算第一章緒論種子節(jié)點。不同的是OASNET算法采用MaxDegree算法，其時間復(fù)雜度比CGA 基于成本效益的影響最大化問題研究現(xiàn)Leskovec[10]最早將成本效益（Cost-effective）這個概念引入進來，考慮同節(jié)點的成本差異，提出最優(yōu)性價比與貪心爬山算法相結(jié)合的（Cost-EffectiveForwardselection）算法，由文獻(xiàn)[17]可以得知該算法可以達(dá)到近似比為最優(yōu)解的1?1/√e，約為0.394。但是該算法的時間復(fù)雜度與貪心爬算法無異，在面對大規(guī)模網(wǎng)絡(luò)時非常耗時。又提出了改進后Forward，可以比爬山貪心算法提高700倍的計算速度。文獻(xiàn)[18]在CELF算法基礎(chǔ)上又進一步提出了改進算法CPP-SNS，首先估算單個節(jié)點的影響力大小并排序，定義一個大小為M的窗口，將估算得到的影響DAG1和DAG2，其中DAG1通過加入一個與所有節(jié)點相連的虛擬節(jié)點，從該節(jié)條件；DAG25時間也得到了改善。同時為了進一步提高運算效率，文章還提出了一種Singel-PassBeliefPropagation法(簡稱SPBP)來替代蒙特卡洛仿時間也得到了改善。同時為了進一步提高運算效率，文章還提出了一種Singel-PassBeliefPropagation法(簡稱SPBP)來替代蒙特卡洛仿真算法描述如Algorithminput:1.σ(S)=foreachv∈DAG(S)doifv∈Sthenendifp(v)=1-∏σ(S)=σ(S)+(()(1 )?(,(10.endforDAG(S)，在子圖上通算法輸入的是根據(jù)種子節(jié)點集合S劃分好的子圖SPBP算法計算影響范圍σ(S)。1σ(S第2行：開始計算種子節(jié)點集合的影響范圍第3-5行：如果節(jié)點v屬于種子集合S那么其已經(jīng)被激活第6-8行：如果節(jié)點v不屬于種子集合S，那么其激活概率通過第7行的公式計算，公式表示從種子集合出發(fā)激活節(jié)點v需要激活路徑上所有的節(jié)點；第9行：影響范圍為所有節(jié)點被激活概率之實驗結(jié)果顯示DAG2-SPBP算法影響范圍和CELF算法相接近，并且時間效1.2.3現(xiàn)狀總6第一章緒論1.3研究目第一章緒論1.3研究目標(biāo)及內(nèi)本文研究的總體框架如圖1.3所示7基于成本效益的影響力節(jié)點基于成本效益的影響力節(jié)點挖掘原型系統(tǒng)設(shè)模型驗證、改進與完圖1.3基于成本效益的影響最大化算法研究總體框1.4論文組織結(jié)第二章介紹社會網(wǎng)絡(luò)相關(guān)的理論知識，并詳細(xì)闡述了幾種基本影響力傳播8DBLP、Facebook、weibo數(shù)據(jù)數(shù)據(jù)基于成本效益的影響最大化節(jié)點挖掘研概率覆蓋算 惰性節(jié)點選擇算第一章緒論第一章緒論92.1社2.1社會網(wǎng)社會網(wǎng)絡(luò)（或稱為社會性網(wǎng)絡(luò)）的理論基礎(chǔ)源于六度分隔理論[]（xsofprto）50ueOf15。美國著名社會心理學(xué)家米爾格倫(taneyMgra)于20世紀(jì)60“六度分離“六度分離“弱連接接的效果，通過弱連接人與人之間的距離變得非?！跋嘟?。onenbeg“Tem-ordeoeo[22]unr150定律”[23]15，我們可以預(yù)知保持社交關(guān)系的人數(shù)的最大值。社交網(wǎng)絡(luò)[]類第一封電子郵件的誕生其緣起就是為了方便阿帕網(wǎng)（T）項目的科學(xué)E-mail到即時通信（IM）和博到即時通信（IM）和博客（Blog）再到C的成立，這些應(yīng)用越來越強調(diào)人的個體意識和社會意識，人們希望在交友的同時展現(xiàn)自己的個性，F(xiàn)acebook的出現(xiàn)使社交網(wǎng)絡(luò)趨于成熟。社交網(wǎng)絡(luò)大體經(jīng)歷了這樣一個發(fā)展過程：早期概念化階段──SixDegrees的六度分隔理論；結(jié)交陌生人階段──Friendster幫你建立弱關(guān)系[25]從而帶來更高社會資本的理論；娛樂化階段──MySpace創(chuàng)造的豐富的多媒體個性化空間吸引注意力的理論；社交圖階段──Facebook復(fù)制線下真實人際網(wǎng)絡(luò)來到線上低成本管SNS2.2影響力傳播模定義2.1會網(wǎng)絡(luò)通常可以抽象成一個有向圖G(V,E)，其中V是網(wǎng)絡(luò)中所有節(jié)點的集合，E是所有邊的集合?！蔞表示個體，<u,v>∈E表示個體之間的社會u是邊的起點，v是邊的終點，無向圖中的邊可以看成雙向的有向邊。2.2G(V,Evv,u>直接所指向的節(jié)點集合稱為節(jié)點v的鄰居節(jié)點集合N(v)，即(v)={,}。定義2.3節(jié)點有激活態(tài)(active)和未激活態(tài)(inactive)兩種狀態(tài)。處于激活態(tài)的獨立級聯(lián)模型(IndependentCascadeModel，簡稱IC模型)[3][27]和線性閾模型(LinearThresholdModel，簡稱LT模型)[3][28]是目前社會網(wǎng)絡(luò)研究中兩種最2.2.1獨立級聯(lián)?；顣r，它會以概率Pu,v對未激活的鄰居節(jié)點嘗試激活時，它會以概率Pu,v對未激活的鄰居節(jié)點嘗試激活，并且這種嘗試僅僅進節(jié)點vv有許多鄰居節(jié)點在時間t成激活態(tài)的鄰居節(jié)點對節(jié)點vPu,vv容易被激活。但是這種嘗試只進行一次，不論u是否能成功激活v，以后都不會vt+1屬于[0,1Pu,vvv如何確定激活概率Pu,v也是一個研究熱點，在過去的許多研究中，Pu,v通常被許多研究提出了變概率下的獨立級聯(lián)模型，根據(jù)節(jié)點之間的一些屬性來設(shè)置2.2.2線性閾值模線性閾值模型是一種影響力積累模型在模型中對每一個節(jié) 設(shè)置一個∈[0,1]，對v的鄰居節(jié)點 ,,滿足1，這里()是v的鄰居節(jié)點集合，節(jié)點v激活的條件∈(,∑≥(vv∈(,鄰居節(jié)點對v的累計影響大于v的激活閾值時v被激于未激活態(tài)的鄰居節(jié)點，當(dāng)節(jié)點的累計影響力達(dá)到其閾值時，即∑∈()≥,值，用θv于未激活態(tài)的鄰居節(jié)點，當(dāng)節(jié)點的累計影響力達(dá)到其閾值時，即∑∈()≥,值，用θv他就會去這家餐館就餐也有一些專門針對線性閾值模型設(shè)計的算法[29][30][312.2.3其他傳播模SIR[32]TR[12]等等，這些模型也SIRSIRTrivalency模型(簡稱TR模型)是獨立級聯(lián)模型的變種，影響概率Pu,v不再是一個系統(tǒng)常量，每條邊上的傳播概率會從概率集合中隨機選取，比如集合{0.1,0.01,0.001}，概率的大小意味著傳播能力的高低基于成本效益的影響最大化問2.3.1形式化定A，AC(A，AC(A)B使得最終影響范圍R(A)最大。公式描述A=argmax{R(A)|A?V,C(A)≤B},C(A)=2.3.2時間效率，也即算法的時間復(fù)雜度要低，選擇初始節(jié)點集合A的時間要影響范圍，在獲得初始集合A之后，要使得最終受影響的節(jié)點數(shù)最多，也就是被集合A激活的節(jié)點數(shù)目最大。下一小節(jié)會介紹基于成本效益的影響最大化問題是一個NP-Hard問題，無2.3.3NP-Hard問P（o-dtrntcooma）的縮寫。所謂的非P很容易檢查”的問題，這里“P-rdNP完全問題（NP-Complet）和NP-Hard問題不存在有效算法這一猜想，認(rèn)為該類問題題的經(jīng)典例子有子集和問題、Hamilton回路問題、旅行商問題和最大團問題等基于成本效益的影響最大化問題是NP-Hard問Kempe，Kleinberg和Tardos等人[3]首先把該問題作為一個在一個特定傳播模型上尋找k個節(jié)點能使影響最大化的離散優(yōu)化問題。并證明在IC模型和并提出了貪心爬并提出了貪心爬山算法，可達(dá)到最優(yōu)解63%效益的影響最大化問題也是NP-Hard問題。2.4本章小文獻(xiàn)[18][19]以及CELF算文獻(xiàn)[18][19]以及CELF算法均是在爬山貪心算法的基礎(chǔ)上，利用蒙特卡洛仿3.1節(jié)點成本建，3.1.1成本的意病毒營銷[33]“讓大家告訴大家似乎認(rèn)為選擇出來的k個人會自愿的提供傳播渠道作為廣告的第一傳播者推廣似乎認(rèn)為選擇出來的k個人會自愿的提供傳播渠道作為廣告的第一傳播者推廣“k品有即“大V和普通用戶的區(qū)別，那么什么樣的經(jīng)濟刺激才3.1.2成本的定文獻(xiàn)[34]針對病毒營銷的特點，提出了一種定價策略，在產(chǎn)品推廣的不同價策略來獲得最大的利潤，作者把產(chǎn)品折扣所損失的那部分利潤看作成本(cot[35]位置也會影響到傳感器能力的發(fā)揮，Leskovec利用影響最大化的模型解決了這個問取了比較實際的方式——利用AmazonMechanicalTurk來獲取節(jié)點成本，AmazonMechanicalTurk是一個集雇傭和勞務(wù)雙方的網(wǎng)絡(luò)交易系統(tǒng)，在該系統(tǒng)上requesterFacebook個人主頁上推薦商品并提供他們的Facebook信息和想要獲得的報酬，同2.v.cost=1.015.3.v.cost=-豬八戒“三打哈”等，網(wǎng)絡(luò)營銷在用“計件模式cost(v)=degree(v),v∈cost(v)=degree(v),v∈也即在圖G(V,E)中定義節(jié)點的成本為其度數(shù)中像Facebook這種以好友關(guān)ABAB，但3.2節(jié)點概率覆蓋范3.2.1節(jié)點影響力分按照圖形理論，聚類系數(shù)是表示一個圖形中節(jié)點聚集程度的系數(shù)。節(jié)點i度數(shù)為ki，那么與其相連的ki個節(jié)點之間最多可能有ki(ki-1)/2條邊，而實際存在的邊數(shù)為EiiCi(d)首先我們來看一下k-核的概念，一個圖的k-核（k-core）是指反復(fù)去掉度點v屬于k-核而不屬于(k+1)-核，那么v的核數(shù)即為k。得節(jié)點的影響力更強。M.Kitsak等人通過實驗表明在影響力傳播方面，核數(shù)比點點v屬于k-核而不屬于(k+1)-核，那么v的核數(shù)即為k。得節(jié)點的影響力更強。M.Kitsak等人通過實驗表明在影響力傳播方面，核數(shù)比點影響力，比如節(jié)點的度數(shù)、介數(shù)、聚類系數(shù)以及PageRank值等等，這些指標(biāo)在3.2.23.2.3對于節(jié)點sV，首先計算節(jié)點svSP(s,v)<s,s1v>定義3.1：sv的最短距離：distance(s,v)|SP(s,v)|1定義3.2：s到v的影響力傳播路徑Path(s,v)=<s,s1,…,v>,其中也就是說從節(jié)點 開始經(jīng)過一條路徑激活節(jié) v，這條路徑上的節(jié)點順序能是離s越來越遠(yuǎn)，只允許節(jié)點向相對源點s更遠(yuǎn)的節(jié)能是離s越來越遠(yuǎn)，只允許節(jié)點向相對源點s更遠(yuǎn)的節(jié)點傳播影響力，而禁止一定義3.3：s沿影響力傳播路徑Path(s,v)傳播給v的信號量強度為p(Path(s,v))=∏pp( ),n=|Path(s,v)|-,節(jié)點對節(jié)點給定一個閾值θ，規(guī)定只取路徑傳播概率不小于θ的概率傳播路徑，節(jié)點s到節(jié)點v有許多條概率傳播路徑。定義3.4：節(jié)點v接收到節(jié)點s的影響力信號累計∑p(Path(s,Prob(s,v)(,定義3.5：節(jié)點s的概率覆蓋范圍：ProbCover(s)=∑∈Prob(s,v)Algorithmθinput:networkgraphG(V,E),sourcenodes,andterminatedvalueoutput:nodes’sprobabilitycoveragesetnodesassourcenodefor?v∈VcalculateendforeveryPath(s,v)if(p(Path(s,v))≥θ)endifendfor?v∈endforreturn第1行：以s為源節(jié)點開始計算它的概率覆蓋范圍2-4計算s他節(jié)點v最短距離，采用Dijkstra算法并以θ為終止徑，要求所經(jīng)過的路徑符合影響力傳播路徑的條件，即所經(jīng)歷的節(jié)點 越來遠(yuǎn)以及傳播概率不小于第10-12行：把所有節(jié)點獲得的影響力累計加起來，即為節(jié)點s的概率覆在遠(yuǎn)以及傳播概率不小于第10-12行：把所有節(jié)點獲得的影響力累計加起來，即為節(jié)點s的概率覆在計算節(jié)點概率覆蓋范圍時首先要采用算法計算單源最短距離是實際情況中影響力傳播路徑長度限制在閾值θ以內(nèi)，所以Dijkstra復(fù)雜度為方式相同，所以時間復(fù)雜度也為3.3選擇初始節(jié)點集（ProbCover(v)/cost(v)AlgorithmProbCoverinput:networkgraphG(V,E),budgetB,andterminatedvalueoutput:thesetofinitialtargetsetAθfor?v∈Vcalculateend()v=(if(cost(v)≤A=A∪endifendreturn1行：初始化種子節(jié)點集合為空，集合總成本Cost(A2-4行：計算所有節(jié)點的概率覆蓋范圍5-11行：在預(yù)算內(nèi)以性價比最優(yōu)的方式選擇種子節(jié)點集合6行：獲得性價比最優(yōu)的節(jié)點?)，綜上所述總的?)，綜上所述總的算法的時間復(fù)雜度為O(?+?log)3.4本章小4.1子模函數(shù)特子模函數(shù)[function)4.1子模函數(shù)特子模函數(shù)[function)是指滿足邊際收益遞減(rtr)規(guī)律的一類函數(shù)。在數(shù)學(xué)中，子模函數(shù)是一種集合函數(shù)，當(dāng)一個元素加一個函數(shù)()(S∪})?()是元v，f(?)被稱作子模函數(shù)如果符合邊際收益遞減規(guī)律：集TSvSTf(S∪{v})?f(S)≥f(T∪{v})?f(T),S?我們分析一下CELFAi輪f(A∪{v})?f(A)≥fA∪{v}?fA,i<也就是說節(jié)點v在當(dāng)前輪數(shù)所能獲得的邊際收益不會超過之前輪數(shù)所能獲Algorithminput:networkgraphG(V,E),sizeofresultkoutput:thesetofinitialtargetAlgorithminput:networkgraphG(V,E),sizeofresultkoutput:thesetofinitialtargetsetAinitialize:fori=1tokcalculateσ(A{vσ(Avpushσ(A∪{v})?σ(A)tomaxheapendforpopvfrommaxheapcalculateσ(A∪{v})?σ(A)A=A∪{v}k=k-endifpushσ(A∪{v})?σ(A)tomaxheapendelse16.end算法利用子模函數(shù)特性減少重復(fù)計算提高運算效率，而本文提出的4.2惰性節(jié)點選擇算ProbCover(A)=∑∈么做也使得概率覆蓋范圍并不符合子模函數(shù)的特性，給定兩個初始節(jié)點集合S和T，且S是T的子集，此時ProbCover(S∪{v})?Probcover(S)=ProbCover(T∪{v})?S?Path(s,v)=<s,s1,…,v>，其中distance(s,sdistance(s,s1distance(sv{ss1v}A=Prob(s,v)=p(Path(s,(,點集合的增大而減小，以節(jié)點v加入到初始節(jié)點集合A中所得到的概率覆蓋范Prob(s,v)=p(Path(s,(,點集合的增大而減小，以節(jié)點v加入到初始節(jié)點集合A中所得到的概率覆蓋范ProbCover(S∪{v})?Probcover(S)≥ProbCover(T∪{v})?ProbCover(T)S? (ProbCover(S{vProbcover(S))/cost(v)作為選擇指標(biāo)選擇性價比最優(yōu)的節(jié)input:networkgraphG(V,E),budgetB,andterminatedvalueθoutput:thesetofinitialtargetsetAv∈Vpush(ProbCover(A∪{v})?ProbCover(A))/cost(v)toendforpopvfromcalculatetemp=(ProbCover(A∪{v})?ProbCover(A))/cost(v)if(cost(v)<B&&temp>maxheap.head)A=A∪endifpushProbCover(A∪{v})?ProbCover(A)tomaxheapendif18.end 其中maxheap是一個key-value最大堆，以節(jié)其中maxheap是一個key-value最大堆，以節(jié)點概率覆蓋范圍比節(jié)點成本作為key節(jié)點id作為value建堆調(diào)用函數(shù)ProbCover()來計算節(jié)點概率覆蓋范圍1AA3行：調(diào)用ProbCover()函數(shù)，并以ProbCover(A{vProbCover(A)計42-5以單節(jié)點的性價比為key節(jié)點id為value最大堆，以備下第8行：重新計算此輪中節(jié)點v的性價比；9-12v并調(diào)整預(yù)算減去v的成本；第6-18行：重復(fù)上述過程，直到預(yù)算耗盡，獲得種子集合A修改后的計算節(jié)點概率覆蓋范圍的時間復(fù)雜度并不會改變，仍為)算法首先需要計算所有節(jié)點的概率覆蓋范圍，其時間復(fù)雜度為O()，之后利用子模函數(shù)特性和惰性計算技術(shù)選擇種子節(jié)點集合，首先要?覆蓋范圍的重新計算和堆調(diào)整，節(jié)點平均成本B/avgcost，總的時間復(fù)雜度為O(( avgcost，選擇節(jié)點的次數(shù))?log))4.3本章小本節(jié)首先介紹子模函數(shù)特性，以CELF算法為例說明該特性在影響最大化問5.1實驗環(huán)1、硬件平臺：一臺惠普PC機，配置為5.1實驗環(huán)1、硬件平臺：一臺惠普PC機，配置為Intel(R)Core(TM)i7處理器，8GB2、操作系統(tǒng)：Windows7旗艦版(64位3、軟件工具：Code::Blocks12.11，C++語言5.2實驗數(shù)據(jù)實驗所用數(shù)據(jù)集分別為斯坦福大SNAP[39]項目組提供的數(shù)據(jù)集和從新微博抓取的真實數(shù)據(jù)集StanfordNetworkAnalysisPlatform(簡稱SNAP)是由JureLeskovec創(chuàng)辦的，同時他也是CELF算法的發(fā)明者，SNAP提供了大量的社會網(wǎng)絡(luò)我們從SNAP所提供的數(shù)據(jù)集中選擇Facebook數(shù)據(jù)集[40]和DBLP數(shù)據(jù)集[41]，加上從新浪微博抓取的真實數(shù)據(jù)（以下簡稱weibo數(shù)據(jù)集據(jù)集下進行實驗。Facebook和weibo是國內(nèi)外有代表性的社交網(wǎng)絡(luò)，DBLP是社1）DBLP數(shù)據(jù)表5.1DBLP數(shù)據(jù)集統(tǒng)計如表5.1所示，DBLP數(shù)據(jù)集包含317080個節(jié)點，2099732條邊，其節(jié)點平均度數(shù)為6.622平均聚類系數(shù)為0.6324網(wǎng)絡(luò)直徑為21平均路徑長度為6.937，并且從圖5.1可以看出度分布符合冪律分布，符合社會網(wǎng)絡(luò)的特性。DBLPdatasetAverageAverageclusteringAveragepath圖5.1DBLP數(shù)據(jù)集節(jié)點度分2）Facebook表5.2Facebook數(shù)據(jù)集統(tǒng)圖5.1DBLP數(shù)據(jù)集節(jié)點度分2）Facebook表5.2Facebook數(shù)據(jù)集統(tǒng)計資如表5.2所示，F(xiàn)acebook數(shù)據(jù)集包含4039個節(jié)點，176468條邊，其節(jié)點并且從圖5.2 圖5.2Facebook數(shù)據(jù)集節(jié)點度分FacebookdatasetAverageAverageclustering8Averagepath3）weibo數(shù)據(jù)表5.3weibo數(shù)據(jù)集統(tǒng)計如表5.3所示，weibo3）weibo數(shù)據(jù)表5.3weibo數(shù)據(jù)集統(tǒng)計如表5.3所示，weibo數(shù)據(jù)集包含44514個節(jié)點，324796條邊，其節(jié)點平度數(shù)為7.296，平均聚類系數(shù)為0.186，網(wǎng)絡(luò)直徑為23，平均路徑長度為并且從圖5.3 圖5.3weibo數(shù)據(jù)集節(jié)點度分5.3實驗設(shè)實驗對比的算法及參數(shù)設(shè)置如表5.4所示由于MaxDegree算法和PageRankweibodatasetAverageAverageclusteringAveragepath5.4推廣預(yù)算B的取值范圍從1000到5000，步進間隔為500，并通過蒙特卡洛仿真模擬10000次傳5.4推廣預(yù)算B的取值范圍從1000到5000，步進間隔為500，并通過蒙特卡洛仿真模擬10000次傳播過程取平均來獲得一個較為精確的影響范圍。AB預(yù)算為i時的差異定義為：(A,i) (B,i)Diff(A,B,其中σ(A,i)為算法A在推廣預(yù)算為i時的影響范圍，σ(B,i)為算法B在推廣預(yù)算為i時的影響范圍。則算法A和B的平均差異定義為( )∑(,,(1000+?從1000到5000這個區(qū)間內(nèi)影響范圍的平均差異，因為平均差異可以更公平的體實驗，進一步討論算法的適用范圍。()固定概率ICP、aceookeoIC的傳播概率相同，并將傳播概率設(shè)置為∈.,.0,.0,0.0}，分析對比不同傳播概率下各算法的性能；(ICeo點之間的傳播概率由節(jié)點間的交互強度決定，節(jié)點u對節(jié)點v轉(zhuǎn)發(fā)的微博數(shù)+評論的微博數(shù))/2，也即v對u的轉(zhuǎn)發(fā)率和評論率的平均值5.4實驗結(jié)果及分影響范圍對比圖中，X軸表示推廣預(yù)算大小，Y軸表示選定種子節(jié)點集合之后通Google用于用來標(biāo)識網(wǎng)頁等級/重要性的算法，阻尼因子設(shè)為DAG2-5.4.1固定概率的IC模型實驗結(jié)果與分法 算法比以往的啟發(fā)式算法有更好的傳播效果。并且與DAG2-SPBP算法的結(jié)果不相上下，尤其在傳播概率為0.01時本文所提的兩種算表5.5各個算法與ProbCover算法影響范圍差異表5.5是其他4種算法與ProbCover算法在影響范圍差異上的對比，量化的顯示了其他啟發(fā)式算法與ProbCover算法在影響范圍上的百分比差異，不同算法如圖5.4(a)所示，在傳播概率為0.01時，本文所提出的兩種算法以及DAG2-SPBP算法明顯優(yōu)于MaxDegree算法和PageRank算法，這是因為后兩者下不再適用，與ProbCover算法相比MaxDegree和PageRank算法的影響范圍要小29.97%和58.54%。ProbCoverLF算法影響范圍略有提升，提高了3.59%，DAG2-SPBP算法雖然在預(yù)算大于4000時影響范圍比ProbCover略有優(yōu)勢但在整體上ProbCover算法優(yōu)于DAG2-SPBP算法9.81%。如圖5.4(b)所示，在傳播概率為0.02時，本文所提出的兩種算法仍然有較大優(yōu)勢，ProbCover算法比MaxDegree和PageRank算法的影響范圍要大31.3%和63.40%。ProbCoverLF算法此時與ProbCover算法沒有差異，而DAG2-SPBP算法要優(yōu)于ProbCover算法2.70%。如圖5.4(c)所示，在傳播概率為0.03時，同樣由于設(shè)計思想的問題，MaxDegree和PageRank算法表現(xiàn)很差，影響范圍比ProbCover算法要小DAG252.67ProbCover算法、ProbCoverLF算法和DAG2-SPBP算法三者幾乎重合，差異只有-0.025%和0.08%。如圖5.4(d)所示，在傳播概率52.67ProbCover算法、ProbCoverLF算法和DAG2-SPBP算法三者幾乎重合，差異只有-0.025%和0.08%。如圖5.4(d)所示，在傳播概率為0.04時，MaxDegreePageRank算法仍與ProbCover算法有一定差距，分別為14.21%和13.81%。ProbCoverLF算法和DAG2-SPBP算法則要優(yōu)于ProbCover算法0.037%和2.45%。綜上所述，由于MaxDegree算法和PageRank算法沒有考慮節(jié)點成本的差異的差距，這也說明了不同的算法有不同的適用場景。而ProbCover算法、ProbCoverLF算法和DAG2-SPBP算法三者之間差異變化很小，但也互有勝負(fù)，有(a)P=(b)P=(c)P=(d)P=圖5.4各個算法在DBLP數(shù)據(jù)集和不同傳播概率上的影響效MaxDegree算法運行時間在1秒以下，PageRank算法在13秒便可完成計算，ProbCover算法、ProbCoverLF法和DAG2-SPBP運行時間較長，但也未超過1小時，仍在可以接受的范圍之內(nèi)。DAG2-2各算法Facebook數(shù)據(jù)集上的結(jié)果分是全球知名的社交網(wǎng)絡(luò)，能夠真實2各算法Facebook數(shù)據(jù)集上的結(jié)果分是全球知名的社交網(wǎng)絡(luò)，能夠真實的反映人們線下的社會關(guān)系1743.691，可以看出是一個非常緊密的5.5DBLP并且我們所提出的ProbCover算法及ProbCoverLF算法比以往的啟發(fā)式算法有更表5.7各個算法與ProbCover算法影響范圍差異對表5.7是其他4種算法與ProbCover算法在影響范圍差異上的對比，量化的顯示了其他啟發(fā)式算法與ProbCover算法在影響范圍上的百分比差異，從表5.7中可以看出，ProbCover算法、ProbCoverLF法和DAG2-SPBP算法整體所呈現(xiàn)的差異不大并且要優(yōu)于MaxDegree算法和PageRank算法但是與MaxDegree算法如圖5.5(a)所示，當(dāng)傳播概率為0.01時，本文所提出的兩種算法和DAG2-SPBP算法明顯優(yōu)于MaxDegree算法和PageRank算法，并且隨著推廣預(yù)算的增加各個算法的影響范圍也逐步提升，雖然在預(yù)算增加到3500之后PageRank算法的影響范圍上升非?？欤瞧湔w效果仍與ProbCover算法有較大差距。與ProbCover算法相比MaxDegree算法和PageRank算法的影響范圍要小23.38%和54.41%，ProbCoverLF算法和DAG2-SPBP算法優(yōu)于ProbCover算法0.94%和2.36%。如圖5.5(b)所示，當(dāng)傳播概率為0.02時，與MaxDegreePageRank算法相比，ProbCover算法仍然全程領(lǐng)先，影響范圍分別要大5.32%和28.84%。而ProbCoverLF和DAG2-SPBPProbCover算法的差異均不到1%。雖然在預(yù)算達(dá)到3500之后PageRank算法的影響范圍基本和本文所提出的算法持平如圖5.5(c)所示，當(dāng)傳播概率為0.03時，預(yù)算在1000-2500的范圍內(nèi)ProbCoverLF、DAG2-SPBPProbCover算法保持絕對優(yōu)勢，并且三者之間差異非常小，當(dāng)預(yù)算超過3000之后MaxDegree和PageRank算法的影響范圍與其他DAG2三者基本持平，但是總體差異仍然三者基本持平，但是總體差異仍然3.43%18.75%。并且從圖中可以看ProbCoverLF、DAG2-SPBP、ProbCover和MaxDegree算法的影響范圍隨預(yù)算增長并不明顯，而PageRank算法的影響范圍則持續(xù)上升。如圖5.5(d)所示與傳播概率為0.02和0.03時相似當(dāng)傳播概率為0.04時，ProbCoverLF、DAG2-SPBPProbCover算法雖然整體保持優(yōu)勢，但是優(yōu)勢并不明顯，只比MaxDegree算法影響范圍大4.17%，PageRank算法的影響范圍雖然持續(xù)上升但整體上差距仍有11.22%。從以上的分析我們可以看出，并不像DBLP數(shù)據(jù)集那樣ProbCoverLF、算法之間的差異非常之小，并且MaxDegree算法也有著不錯的影響范圍。我們率為0.04時甚至已經(jīng)覆蓋網(wǎng)絡(luò)規(guī)模的一這是因為Facebook數(shù)據(jù)集比較特殊，絡(luò)非常稠密，而且有個別節(jié)點的度數(shù)達(dá)到1000以上，這個時候高度數(shù)的節(jié)點對影響力傳播起著非常重要的作用，PageRank(a)P=(b)P=(c)P=(d)P=圖5.5不同算法在Facebook數(shù)據(jù)集和不同傳播概率上的影響效算法在Facebook數(shù)據(jù)集上的運行時間如表5.8所示，從表中可以看出MaxDegree算法和PageRank算法的運行時間都在1秒以內(nèi)，ProbCover算法、ProbCoverLF算法和DAG2-SPBP算法的運行時間也都在1分鐘以內(nèi)，這Facebook數(shù)據(jù)集節(jié)點規(guī)模較小有關(guān)表5.8不同算法的運行時間(秒3各算法weibo數(shù)據(jù)集上的結(jié)果轉(zhuǎn)發(fā)，信息通過這種方式流通。圖5.6為各Facebook數(shù)據(jù)集節(jié)點規(guī)模較小有關(guān)表5.8不同算法的運行時間(秒3各算法weibo數(shù)據(jù)集上的結(jié)果轉(zhuǎn)發(fā)，信息通過這種方式流通。圖5.6為各個算法在不同概率下的影響范圍對比表5.9各個算法與ProbCover算法影響范圍差異對如圖5.6(a)所示在傳播概率為文所提出的算法具有較高的優(yōu)勢并且表現(xiàn)穩(wěn)定，MaxDegree和PageRank算法影響范圍比ProbCover要低和26.60%。其他算法的影響范圍非常接近，幾乎沒有差異如圖5.6(b)所示，在傳播概率為0.02時，ProbCoverLF和DAG2-SPBP算和PageRank34.2935.23%。如圖5.6(c)所示，在傳播概率為0.03時，ProbCoverLF和DAG2-SPBP算法與ProbCover算法的差異也非常小分別為0.35%和0.12%。ProbCover算法要優(yōu)于MaxDegree和PageRank16.51%和14.84%，并且此時PageRank算法的影響范圍要略高于MaxDegree算法。如圖5.6(d)所示在傳播概率為0.04推廣預(yù)算的增加，ProbCoverLF、差異很小，ProbCoverLF和DAG2-SPBP算法的影響范圍比ProbCover算法要高0.07%和0.37%。ProbCover算法要優(yōu)于MaxDegree和PageRank5.13%和4.18%，而MaxDegree綜上所述，由于MaxDegree算法和PageRank算法在設(shè)計時沒有考慮節(jié)點DAG2DAG2-ProbCover算法、ProbCoverLF算法和DAG2-SPBP算法三者之間差異很小，綜合法的優(yōu)勢逐漸縮小，這一點文獻(xiàn)[]中也有指出，這是因為隨著預(yù)算的增加，初始節(jié)點集合的規(guī)模逐漸增大，然而影響力傳播所能獲得的邊際收益卻會越來越(a)P=(b)P=(c)P=(d)P=圖ProbCover算法、ProbCoverLF算法和DAG2-SPBP算法三者之間差異很小，綜合法的優(yōu)勢逐漸縮小，這一點文獻(xiàn)[]中也有指出，這是因為隨著預(yù)算的增加，初始節(jié)點集合的規(guī)模逐漸增大，然而影響力傳播所能獲得的邊際收益卻會越來越(a)P=(b)P=(c)P=(d)P=圖5.6不同算法在weibo數(shù)據(jù)集和不同傳播概率上的實驗結(jié)算法在weibo數(shù)據(jù)集上的運行時間如表5.10所示，MaxDegree算法在不到1秒的時間內(nèi)即可運行完畢，而PageRank算法也僅需1秒多的運行時間，其他3種算法雖然比MaxDegree和PageRank算法運行時間要長，但是也僅需幾分鐘的表6.10不同算法的運行5.4.2變概率下的IC模型實驗結(jié)果與分DAG2-轉(zhuǎn)發(fā)的微博數(shù)點間的交互強度決定，節(jié)點u對節(jié)點v的傳播概率為評論的微博數(shù))/2vu轉(zhuǎn)發(fā)的微博數(shù)點間的交互強度決定，節(jié)點u對節(jié)點v的傳播概率為評論的微博數(shù))/2vu同算法在weibo數(shù)據(jù)集上的實驗結(jié)果進行分圖5.7變概率下不同算法在weibo數(shù)據(jù)集上的實如圖5.7所示，在變概率條件下，本文所提出的算法仍然表現(xiàn)優(yōu)異，影響范圍遠(yuǎn)遠(yuǎn)大于MaxDegree算法和PageRank算法由表5.10的量化對比分析可以看出ProbCover算法的影響范圍比MaxDegree算法和PageRank算法分別要大71.25%和71.03%，優(yōu)勢非常明顯這是因為MaxDegree算法和PageRank算法不僅沒有ProbCoverProbCoverDAG2-SPBP微優(yōu)勢，影響范圍要大1.77%，而ProbCoverLF算法比ProbCover算法又提升了2.38%。綜上所述，ProbCoverProbCoverLF表5.10算法與ProbCover響范圍差異DAG25.11是各個算法的運行時間數(shù)據(jù)，MaxDegree算法和PageRank算法并沒有考慮傳播模型的特性，所以運行時間與固定概率時基本一致，MaxDegree不到1時間內(nèi)即可運行完畢，而PageRank算法也僅需1秒多的運行時間他的算法在變概率條件下的運行時間略有改變，雖然比MaxDegree和算法運行時間要長，但是也僅需幾分鐘的時間，在時間效率上也證表5.11不同算法的運行時間(秒表5.11不同算法的運行時間(秒DAG2-5.4.3實驗結(jié)果本文提出的算法在影響范圍上遠(yuǎn)優(yōu)于MaxDegree算法和PageRank算法，這是因而與DAG2-SPBP從三個不同數(shù)據(jù)集上的實驗結(jié)果來看，在P數(shù)據(jù)集和acook數(shù)據(jù)集上本文提出的算法要略優(yōu)于DPBP算法，而在eo數(shù)據(jù)集上與-PBP5.1-5.3現(xiàn)，weibo數(shù)據(jù)集的聚類系數(shù)與其他兩個數(shù)據(jù)集相差較大，DBLP數(shù)據(jù)集和Facebook數(shù)據(jù)集的聚類系數(shù)分別為0.6324和0.617，而weibo數(shù)據(jù)集的聚類系數(shù)僅為0.186人以群分”稠密。綜合實驗結(jié)果和數(shù)據(jù)集的統(tǒng)計資料來看DAG2-SPBP算法相比，本5.5本章小第六章系統(tǒng)實第六章系統(tǒng)實現(xiàn)第六章系統(tǒng)實第六章系統(tǒng)實現(xiàn)6.1原型系統(tǒng)整體架本文提出了基于概率覆蓋范圍的啟發(fā)式算法ProbCover算法及ProbCoverLF統(tǒng)主要包括輸入模塊、節(jié)點選擇算法模塊、傳播模型模塊和結(jié)果輸出模塊，原系統(tǒng)整體架構(gòu)如圖6.1所示傳播模型模結(jié)果輸出模固定概變概節(jié)點選擇算法模DAG2-輸入模建立網(wǎng)絡(luò)拓數(shù)據(jù)預(yù)格式化的數(shù)據(jù)圖6.1原型系統(tǒng)整體節(jié)點選擇算法模塊：該模塊實現(xiàn)了本文所提出的ProbCover算法和PorbCoverLF算節(jié)點選擇算法模塊：該模塊實現(xiàn)了本文所提出的ProbCover算法和PorbCoverLF算法及其他經(jīng)典的算法MaxDegree算法、PageRank算法出，包括節(jié)點ID和其屬性。6.2原型系統(tǒng)實6.2.1開發(fā)環(huán)硬件環(huán)境為PC機一臺，配置為Intel(R)Core(TM)i7處理器，8GB內(nèi)存，操Windows7旗艦版(64C12.11下開6.2.2系統(tǒng)實1ID0存取數(shù)據(jù)，整體流程如圖6.2所示。本文采用鄰接表的形式來存儲網(wǎng)絡(luò)拓?fù)湓O(shè)計 類來存放節(jié)點屬性、節(jié)點鄰居以及計算節(jié)點距源節(jié)點距離等操作以及計算單源最短路徑的以及計算單源最短路徑的算法NY節(jié)點ID這里不再贅述，下面主要介紹傳播模型模塊，該模塊實現(xiàn)了IC模型的模擬傳播點間激活概率以節(jié)省空間，prob[u][v]代表節(jié)點u對節(jié)點v的影響概率，固定概影響概率，prob[u][v]采用STL中unordered_map和vector來構(gòu)建而非矩陣，這Functioninput:networkgraphG(V,E),seedFunctioninput:networkgraphG(V,E),seedsetoutput:propagationrange1.result=0forj=0tondoendforforj=0toseed.size()doactive[seed[j]]=trueendforforv:u.neighbordoif(!active[v]&&(rand()/RAND_MAX)<prob[u][v])active[v]=endifendwhileendRETURNresult/simulateTime 第1-3行聲明要使用的變量，active存放節(jié)點狀態(tài)，被激活為true未激活為false，active_queue是一個隊列存放可以激活其鄰居的激活態(tài)節(jié)點，result為最第4行開始模擬傳播過程，simulateTime為模擬次數(shù)，最后取平均值；第5-7行初始化所有節(jié)點為未激活態(tài)；第8-11將種子集合中的節(jié)點修改為激活態(tài)，并入隊列12第13行從隊列中取出一個激活態(tài)節(jié)點u；第14-20uvprob[u][v]vv，result增加1；第23prob[u][v]vv，result增加1；第23行最后返回多次模擬傳播后影響范圍的平均值26.3 各種選擇。分別選擇數(shù)據(jù)集、要運行的算法、推廣預(yù)算和傳播概率，點擊Run另外以文件的形式保存結(jié)果方便查閱，如圖6.4所示，輸出的結(jié)果包括種子集合中所包含的節(jié)點ID、節(jié)點的一些屬性和在傳播模型下模擬傳播得到的影響范圍。以ProbCover法為例，在weibo數(shù)據(jù)集下推廣預(yù)算設(shè)置為4000采用率的獨立級聯(lián)模型得到的運算結(jié)果，第一列為節(jié)點ID，第二列為節(jié)點的cost即成本，第三列是選擇節(jié)點所采取的指標(biāo)算法中該項為單位成6.46.3本章6.46.3本章小第七章總結(jié)與展望7.1工作總第七章總結(jié)與展望7.1工作總針對新問題，提出一種基于節(jié)點概率覆蓋范圍的啟發(fā)式算法ProbCoverProbCoverLF出的ProbCover算法和ProbCoverLF算法在時間效率和影響范圍兩方面均表現(xiàn)優(yōu)7.2研究展)科學(xué)研究是一個從具體到抽象再到具體的過程，針對影響最大化問題，“病毒營銷2015-05-06于東南大學(xué)計算機[1]/zh/社會[2] [1]/zh/社會[2] customers[C]//ProceedingsoftheseventhACMSIGKDDinternationalKempeD,KleinbergJ,Tardosé.Maximizingthespreadofinfluencethroughasocialnetwork[C]//ProceedingsoftheninthACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining.ACM,2003:137-146.SingerY.Howtowinfriendsandinfluencepeople,truthfully:influencemaximizationmechanismsforsocialnetworks[C]//ProceedingsofthefifthACMinternationalconferenceonWebsearchanddatamining.ACM,2012:733-742.WattsDJ,StrogatzSH.Collectivedynamicsof‘small-world’networks[J].nature,1998,393(6684):440-442.汪小帆,李翔,陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京:清華大學(xué)出版社,ChenW,WangY,YangS.Efficientinfluencemaximizationinsocialnetworks[C]//Proceedingsofthe15thACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining.ACM,2009:199-208.P.A.Estévez,P.A.Vera,andK.Saito.SelectingtheMostInfluentialNodesInSocialNetworks,IJCNN,2007:2397–2402.networks[C]//Proceedingsofthe13thACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining.ACM,2007:420-429.PageL,BrinS,MotwaniR,etal.ThePageRankcitationranking:Bringingordertotheweb[J].1999W.Chen,C.WangandY.Wang.Scalableinfluencemaximizationforprevalentviralmarketinginlarge-scalesocialnetworks.KDD,2010:1029-1038.M.Kitsak,L.K.GallosandS.Havlinetal.Identificationofinfluentialspreadersincomplexnetworks.naturephysics,2010(6):888-893.AramGalstyanetal.Maximizinginfluencepropagationinnetworkswithcommunitystructure.APS,2009,79(5):056102.YuWangetal.Community-basedGreedyAlgorithmforMiningTop-KInfluentialNodesinMobileSocialNetworks.KDD,2010:1039-1048.TianyuCaoetal.OASNET:AnOptimalAllocationApproachtoInfluenceMaximizationinModularSocialNetworks.SAC,2010:1088-1094.S.Khuller,A.Moss,andJ.Naor.Thebudgetedmaximumcoverageproblem.Inf.Proc.Let.,1999,70(1):39-45.QianyiZhan,HongchaoYang,ChongjunWang,JunyuanXie.CPP-SNS:Asolutiontoinfluencemaximizationproblemundercostcontrol.ICTAI2013.HuyNguyen,HuyNguyen,RongZheng.Onbudgetedinfluencemaximizationinsocialnetworks.IEEEJournalonSelectedAreasinCommunications,2013,31(6):LewisTG.網(wǎng)絡(luò)科學(xué)原理與應(yīng)用[M].北京：機械工業(yè)出版社,Kleinberg,Jon.Thesmall-worldphenomenon:analgorithmperspective.Proceedingsofthethirty-secondannualACMsymposiumonTheoryofcomputing.ACM,2000:163-170.[23