隨著近隨著近些年互聯網的飛速發展，社交網絡應運而生，例如國外的Facebook、Twitter以及針對這種特定的營銷模式，學術界也進行了許多研究，關注點在如何選擇最初的用戶作為信ongosRcrsonAgorthm，于概率覆蓋范圍的惰性節點選擇算法（ProbCoverLFAlgorithm。在本文研究成果的基礎上，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;摘 目 第一章緒 研究背景與意 摘 目 第一章緒 研究背景與意 國內外研究現 原始影響最大化問題研究現 現狀總 研究目標及內 論文組織結 相關理論知 社會網 影響力傳播模 獨立級聯模 線性閾值模 其他傳播模 基于成本效益的影響最大化問 形式化定 評價指 問題難 本章小 概率覆蓋算 節點成本建 成本的意 成本的定 節點概率覆蓋范 節點影響力分 算法思 算法描 選擇初始節點集 本章小 利用子模函數特性的惰性節點選擇算 子模函數特 惰性節點選擇算 本章小 實驗設計與分 實驗環 實驗數據 實驗設 實驗結果及分實驗結果及分 固定概率的IC模型實驗結果與分 變概率下的IC模型實驗結果與分 實驗結果小 本章小 第六章系統實 原型系統整體架 原型系統實 開發環 系統實 本章小 第七章總結與展 工作總 研究展 致 參考文 作者簡 第一章緒論第一章緒論1.1研究背景與意第一章緒論第一章緒論1.1研究背景與意（而非“群體明確的邊界和秩序）的社會組織形式，也是西方社會學從19世紀60年代興起的一種分析視角，社會網絡分析并不認為人是由個體規范或者群體會網絡的主體是人，在網絡中以節點來表示，借由人們之間各種不同的社會關系相對穩定的關系體系，社會網絡關注的是人們之間的互動和聯系，社會互動會影社會網絡，圖1.1和圖1.2是CIC1發布的近兩年中國社會化媒體格局概覽。這些在線社交網絡大大降低了人們社交的時間和物質成本，并且在很大程度上將線下真實的人際關系網絡復制到了線上，真實地反映了人們的社會關系，社交網絡在種全新的營銷模式——“病毒式營銷（viralmarketing病毒營銷的基礎是“口（word-mouth，Domingos和Richardson等人[2]最早將影響最大化問題歸納為一個算法問題11Kempe，Kleinberg和Tardos[3]首次把影響Kempe，Kleinberg和Tardos[3]首次把影響最大化問題形式化為一個離散最優化大化，并證明在多種傳播模型下，影響最大化問題是一個NP-hard問題。之后許多成本“一視同仁，然而事實并非如此，請明星做推廣與普通人做推廣所需要的花費相差巨大，不同的明星之間也是千差萬別。文獻[]圖1.12013年中國社會化媒體格1.22014年中國社會化媒體格1.2國內外研究現2第一章緒論 原始影響最大化問第一章緒論 原始影響最大化問題研究G（V,E）中，VE集合，圖中的邊既可以是無向邊也可以是有向邊，例如Facebook和人人網這種Twitter（inactive，在圖中尋找kA（kDomingos和Richardson等人[2]首先將影響最大化問題歸納為一個算法問題，Kempe，KleinbergTardos[3]首次把影響最大化問題形式化為一個離散最優化k個節點作為初始受眾節點使得最終受眾數量最大化，并證明在多種傳播模型下，影響最大化問題是一個NP-hard問題。其形式化定義如下：給定一個正整數k和一個特定傳播模型，如何在網絡A=argmax{R(A)|A?V,|A|=等人首先提出貪心爬山算法來近似求解影響最大化問題，通過蒙3效果可以達到效果可以達到最優解63%，但是其時間復雜度太高，之后許多研究利用社會絡呈現出的“小世界”特性[5][6]提出許多時間效率較高的啟發式算法，例如DegreeDiscount算法[7]、SCG法[8]和k-核算法[9]等等，這些啟發式算法在降低了兩種改進的貪心算法NewGreedy和MixedGreedy，進一步對傳統貪心算法進響的邊，然后在子圖中考慮影響傳播，縮小計算規模。MixedGreedy分兩步選擇kChenWeiDegreeDiscount7]，它優盡可能的把這些種子節點分散，SCG算法[8]通過將節點設置為覆蓋狀態和未覆生鄰居重疊現象。PageRank[11]是Google用來標識網頁重要性的一種方法，這種思想也可以用來在社會網絡中尋找影響力節點。PMIA算法[12]通過計算每個PMIA力傳播方面，核數比度數和介數等節點屬性有更強的傳播力，以k核為基礎的CCA算法[9]也有不錯的表現。利用社區劃分的思想求解影響最大化問題也是一種方法，Galstyan等人[14]第一次提出了利用網絡的社區性質求解影響力最大化問題，之后WangYu[15]等人提出了一種基于社區發現的CGA(Community-basedGreedyAlgorithm)算法獲取，社區中節點選擇策略采用MixGreedy算法。CaoTianyu等人[16]也提出了OASNETOASNET4第一章緒論種子節點。不同的是OASNET算法采用MaxDegree算第一章緒論種子節點。不同的是OASNET算法采用MaxDegree算法，其時間復雜度比CGA 基于成本效益的影響最大化問題研究現Leskovec[10]最早將成本效益（Cost-effective）這個概念引入進來，考慮同節點的成本差異，提出最優性價比與貪心爬山算法相結合的（Cost-EffectiveForwardselection）算法，由文獻[17]可以得知該算法可以達到近似比為最優解的1?1/√e，約為0.394。但是該算法的時間復雜度與貪心爬算法無異，在面對大規模網絡時非常耗時。又提出了改進后Forward，可以比爬山貪心算法提高700倍的計算速度。文獻[18]在CELF算法基礎上又進一步提出了改進算法CPP-SNS，首先估算單個節點的影響力大小并排序，定義一個大小為M的窗口，將估算得到的影響DAG1和DAG2，其中DAG1通過加入一個與所有節點相連的虛擬節點，從該節條件；DAG25時間也得到了改善。同時為了進一步提高運算效率，文章還提出了一種Singel-PassBeliefPropagation法(簡稱SPBP)來替代蒙特卡洛仿時間也得到了改善。同時為了進一步提高運算效率，文章還提出了一種Singel-PassBeliefPropagation法(簡稱SPBP)來替代蒙特卡洛仿真算法描述如Algorithminput:1.σ(S)=foreachv∈DAG(S)doifv∈Sthenendifp(v)=1-∏σ(S)=σ(S)+(()(1 )?(,(10.endforDAG(S)，在子圖上通算法輸入的是根據種子節點集合S劃分好的子圖SPBP算法計算影響范圍σ(S)。1σ(S第2行：開始計算種子節點集合的影響范圍第3-5行：如果節點v屬于種子集合S那么其已經被激活第6-8行：如果節點v不屬于種子集合S，那么其激活概率通過第7行的公式計算，公式表示從種子集合出發激活節點v需要激活路徑上所有的節點；第9行：影響范圍為所有節點被激活概率之實驗結果顯示DAG2-SPBP算法影響范圍和CELF算法相接近，并且時間效1.2.3現狀總6第一章緒論1.3研究目第一章緒論1.3研究目標及內本文研究的總體框架如圖1.3所示7基于成本效益的影響力節點基于成本效益的影響力節點挖掘原型系統設模型驗證、改進與完圖1.3基于成本效益的影響最大化算法研究總體框1.4論文組織結第二章介紹社會網絡相關的理論知識，并詳細闡述了幾種基本影響力傳播8DBLP、Facebook、weibo數據數據基于成本效益的影響最大化節點挖掘研概率覆蓋算 惰性節點選擇算第一章緒論第一章緒論92.1社2.1社會網社會網絡（或稱為社會性網絡）的理論基礎源于六度分隔理論[]（xsofprto）50ueOf15。美國著名社會心理學家米爾格倫(taneyMgra)于20世紀60“六度分離“六度分離“弱連接接的效果，通過弱連接人與人之間的距離變得非常“相近。onenbeg“Tem-ordeoeo[22]unr150定律”[23]15，我們可以預知保持社交關系的人數的最大值。社交網絡[]類第一封電子郵件的誕生其緣起就是為了方便阿帕網（T）項目的科學E-mail到即時通信（IM）和博到即時通信（IM）和博客（Blog）再到C的成立，這些應用越來越強調人的個體意識和社會意識，人們希望在交友的同時展現自己的個性，Facebook的出現使社交網絡趨于成熟。社交網絡大體經歷了這樣一個發展過程：早期概念化階段──SixDegrees的六度分隔理論；結交陌生人階段──Friendster幫你建立弱關系[25]從而帶來更高社會資本的理論；娛樂化階段──MySpace創造的豐富的多媒體個性化空間吸引注意力的理論；社交圖階段──Facebook復制線下真實人際網絡來到線上低成本管SNS2.2影響力傳播模定義2.1會網絡通?？梢猿橄蟪梢粋€有向圖G(V,E)，其中V是網絡中所有節點的集合，E是所有邊的集合?！蔞表示個體，<u,v>∈E表示個體之間的社會u是邊的起點，v是邊的終點，無向圖中的邊可以看成雙向的有向邊。2.2G(V,Evv,u>直接所指向的節點集合稱為節點v的鄰居節點集合N(v)，即(v)={,}。定義2.3節點有激活態(active)和未激活態(inactive)兩種狀態。處于激活態的獨立級聯模型(IndependentCascadeModel，簡稱IC模型)[3][27]和線性閾模型(LinearThresholdModel，簡稱LT模型)[3][28]是目前社會網絡研究中兩種最2.2.1獨立級聯?；顣r，它會以概率Pu,v對未激活的鄰居節點嘗試激活時，它會以概率Pu,v對未激活的鄰居節點嘗試激活，并且這種嘗試僅僅進節點vv有許多鄰居節點在時間t成激活態的鄰居節點對節點vPu,vv容易被激活。但是這種嘗試只進行一次，不論u是否能成功激活v，以后都不會vt+1屬于[0,1Pu,vvv如何確定激活概率Pu,v也是一個研究熱點，在過去的許多研究中，Pu,v通常被許多研究提出了變概率下的獨立級聯模型，根據節點之間的一些屬性來設置2.2.2線性閾值模線性閾值模型是一種影響力積累模型在模型中對每一個節 設置一個∈[0,1]，對v的鄰居節點 ,,滿足1，這里()是v的鄰居節點集合，節點v激活的條件∈(,∑≥(vv∈(,鄰居節點對v的累計影響大于v的激活閾值時v被激于未激活態的鄰居節點，當節點的累計影響力達到其閾值時，即∑∈()≥,值，用θv于未激活態的鄰居節點，當節點的累計影響力達到其閾值時，即∑∈()≥,值，用θv他就會去這家餐館就餐也有一些專門針對線性閾值模型設計的算法[29][30][312.2.3其他傳播模SIR[32]TR[12]等等，這些模型也SIRSIRTrivalency模型(簡稱TR模型)是獨立級聯模型的變種，影響概率Pu,v不再是一個系統常量，每條邊上的傳播概率會從概率集合中隨機選取，比如集合{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時間效率，也即算法的時間復雜度要低，選擇初始節點集合A的時間要影響范圍，在獲得初始集合A之后，要使得最終受影響的節點數最多，也就是被集合A激活的節點數目最大。下一小節會介紹基于成本效益的影響最大化問題是一個NP-Hard問題，無2.3.3NP-Hard問P（o-dtrntcooma）的縮寫。所謂的非P很容易檢查”的問題，這里“P-rdNP完全問題（NP-Complet）和NP-Hard問題不存在有效算法這一猜想，認為該類問題題的經典例子有子集和問題、Hamilton回路問題、旅行商問題和最大團問題等基于成本效益的影響最大化問題是NP-Hard問Kempe，Kleinberg和Tardos等人[3]首先把該問題作為一個在一個特定傳播模型上尋找k個節點能使影響最大化的離散優化問題。并證明在IC模型和并提出了貪心爬并提出了貪心爬山算法，可達到最優解63%效益的影響最大化問題也是NP-Hard問題。2.4本章小文獻[18][19]以及CELF算文獻[18][19]以及CELF算法均是在爬山貪心算法的基礎上，利用蒙特卡洛仿3.1節點成本建，3.1.1成本的意病毒營銷[33]“讓大家告訴大家似乎認為選擇出來的k個人會自愿的提供傳播渠道作為廣告的第一傳播者推廣似乎認為選擇出來的k個人會自愿的提供傳播渠道作為廣告的第一傳播者推廣“k品有即“大V和普通用戶的區別，那么什么樣的經濟刺激才3.1.2成本的定文獻[34]針對病毒營銷的特點，提出了一種定價策略，在產品推廣的不同價策略來獲得最大的利潤，作者把產品折扣所損失的那部分利潤看作成本(cot[35]位置也會影響到傳感器能力的發揮，Leskovec利用影響最大化的模型解決了這個問取了比較實際的方式——利用AmazonMechanicalTurk來獲取節點成本，AmazonMechanicalTurk是一個集雇傭和勞務雙方的網絡交易系統，在該系統上requesterFacebook個人主頁上推薦商品并提供他們的Facebook信息和想要獲得的報酬，同2.v.cost=1.015.3.v.cost=-豬八戒“三打哈”等，網絡營銷在用“計件模式cost(v)=degree(v),v∈cost(v)=degree(v),v∈也即在圖G(V,E)中定義節點的成本為其度數中像Facebook這種以好友關ABAB，但3.2節點概率覆蓋范3.2.1節點影響力分按照圖形理論，聚類系數是表示一個圖形中節點聚集程度的系數。節點i度數為ki，那么與其相連的ki個節點之間最多可能有ki(ki-1)/2條邊，而實際存在的邊數為EiiCi(d)首先我們來看一下k-核的概念，一個圖的k-核（k-core）是指反復去掉度點v屬于k-核而不屬于(k+1)-核，那么v的核數即為k。得節點的影響力更強。M.Kitsak等人通過實驗表明在影響力傳播方面，核數比點點v屬于k-核而不屬于(k+1)-核，那么v的核數即為k。得節點的影響力更強。M.Kitsak等人通過實驗表明在影響力傳播方面，核數比點影響力，比如節點的度數、介數、聚類系數以及PageRank值等等，這些指標在3.2.23.2.3對于節點sV，首先計算節點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>,其中也就是說從節點 開始經過一條路徑激活節 v，這條路徑上的節點順序能是離s越來越遠，只允許節點向相對源點s更遠的節能是離s越來越遠，只允許節點向相對源點s更遠的節點傳播影響力，而禁止一定義3.3：s沿影響力傳播路徑Path(s,v)傳播給v的信號量強度為p(Path(s,v))=∏pp( ),n=|Path(s,v)|-,節點對節點給定一個閾值θ，規定只取路徑傳播概率不小于θ的概率傳播路徑，節點s到節點v有許多條概率傳播路徑。定義3.4：節點v接收到節點s的影響力信號累計∑p(Path(s,Prob(s,v)(,定義3.5：節點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為源節點開始計算它的概率覆蓋范圍2-4計算s他節點v最短距離，采用Dijkstra算法并以θ為終止徑，要求所經過的路徑符合影響力傳播路徑的條件，即所經歷的節點 越來遠以及傳播概率不小于第10-12行：把所有節點獲得的影響力累計加起來，即為節點s的概率覆在遠以及傳播概率不小于第10-12行：把所有節點獲得的影響力累計加起來，即為節點s的概率覆在計算節點概率覆蓋范圍時首先要采用算法計算單源最短距離是實際情況中影響力傳播路徑長度限制在閾值θ以內，所以Dijkstra復雜度為方式相同，所以時間復雜度也為3.3選擇初始節點集（ProbCover(v)/cost(v)AlgorithmProbCoverinput:networkgraphG(V,E),budgetB,andterminatedvalueoutput:thesetofinitialtargetsetAθfor?v∈Vcalculateend()v=(if(cost(v)≤A=A∪endifendreturn1行：初始化種子節點集合為空，集合總成本Cost(A2-4行：計算所有節點的概率覆蓋范圍5-11行：在預算內以性價比最優的方式選擇種子節點集合6行：獲得性價比最優的節點?)，綜上所述總的?)，綜上所述總的算法的時間復雜度為O(?+?log)3.4本章小4.1子模函數特子模函數[function)4.1子模函數特子模函數[function)是指滿足邊際收益遞減(rtr)規律的一類函數。在數學中，子模函數是一種集合函數，當一個元素加一個函數()(S∪})?()是元v，f(?)被稱作子模函數如果符合邊際收益遞減規律：集TSvSTf(S∪{v})?f(S)≥f(T∪{v})?f(T),S?我們分析一下CELFAi輪f(A∪{v})?f(A)≥fA∪{v}?fA,i<也就是說節點v在當前輪數所能獲得的邊際收益不會超過之前輪數所能獲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算法利用子模函數特性減少重復計算提高運算效率，而本文提出的4.2惰性節點選擇算ProbCover(A)=∑∈么做也使得概率覆蓋范圍并不符合子模函數的特性，給定兩個初始節點集合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,(,點集合的增大而減小，以節點v加入到初始節點集合A中所得到的概率覆蓋范Prob(s,v)=p(Path(s,(,點集合的增大而減小，以節點v加入到初始節點集合A中所得到的概率覆蓋范ProbCover(S∪{v})?Probcover(S)≥ProbCover(T∪{v})?ProbCover(T)S? (ProbCover(S{vProbcover(S))/cost(v)作為選擇指標選擇性價比最優的節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最大堆，以節其中maxheap是一個key-value最大堆，以節點概率覆蓋范圍比節點成本作為key節點id作為value建堆調用函數ProbCover()來計算節點概率覆蓋范圍1AA3行：調用ProbCover()函數，并以ProbCover(A{vProbCover(A)計42-5以單節點的性價比為key節點id為value最大堆，以備下第8行：重新計算此輪中節點v的性價比；9-12v并調整預算減去v的成本；第6-18行：重復上述過程，直到預算耗盡，獲得種子集合A修改后的計算節點概率覆蓋范圍的時間復雜度并不會改變，仍為)算法首先需要計算所有節點的概率覆蓋范圍，其時間復雜度為O()，之后利用子模函數特性和惰性計算技術選擇種子節點集合，首先要?覆蓋范圍的重新計算和堆調整，節點平均成本B/avgcost，總的時間復雜度為O(( avgcost，選擇節點的次數)?log))4.3本章小本節首先介紹子模函數特性，以CELF算法為例說明該特性在影響最大化問5.1實驗環1、硬件平臺：一臺惠普PC機，配置為5.1實驗環1、硬件平臺：一臺惠普PC機，配置為Intel(R)Core(TM)i7處理器，8GB2、操作系統：Windows7旗艦版(64位3、軟件工具：Code::Blocks12.11，C++語言5.2實驗數據實驗所用數據集分別為斯坦福大SNAP[39]項目組提供的數據集和從新微博抓取的真實數據集StanfordNetworkAnalysisPlatform(簡稱SNAP)是由JureLeskovec創辦的，同時他也是CELF算法的發明者，SNAP提供了大量的社會網絡我們從SNAP所提供的數據集中選擇Facebook數據集[40]和DBLP數據集[41]，加上從新浪微博抓取的真實數據（以下簡稱weibo數據集據集下進行實驗。Facebook和weibo是國內外有代表性的社交網絡，DBLP是社1）DBLP數據表5.1DBLP數據集統計如表5.1所示，DBLP數據集包含317080個節點，2099732條邊，其節點平均度數為6.622平均聚類系數為0.6324網絡直徑為21平均路徑長度為6.937，并且從圖5.1可以看出度分布符合冪律分布，符合社會網絡的特性。DBLPdatasetAverageAverageclusteringAveragepath圖5.1DBLP數據集節點度分2）Facebook表5.2Facebook數據集統圖5.1DBLP數據集節點度分2）Facebook表5.2Facebook數據集統計資如表5.2所示，Facebook數據集包含4039個節點，176468條邊，其節點并且從圖5.2 圖5.2Facebook數據集節點度分FacebookdatasetAverageAverageclustering8Averagepath3）weibo數據表5.3weibo數據集統計如表5.3所示，weibo3）weibo數據表5.3weibo數據集統計如表5.3所示，weibo數據集包含44514個節點，324796條邊，其節點平度數為7.296，平均聚類系數為0.186，網絡直徑為23，平均路徑長度為并且從圖5.3 圖5.3weibo數據集節點度分5.3實驗設實驗對比的算法及參數設置如表5.4所示由于MaxDegree算法和PageRankweibodatasetAverageAverageclusteringAveragepath5.4推廣預算B的取值范圍從1000到5000，步進間隔為500，并通過蒙特卡洛仿真模擬10000次傳5.4推廣預算B的取值范圍從1000到5000，步進間隔為500，并通過蒙特卡洛仿真模擬10000次傳播過程取平均來獲得一個較為精確的影響范圍。AB預算為i時的差異定義為：(A,i) (B,i)Diff(A,B,其中σ(A,i)為算法A在推廣預算為i時的影響范圍，σ(B,i)為算法B在推廣預算為i時的影響范圍。則算法A和B的平均差異定義為( )∑(,,(1000+?從1000到5000這個區間內影響范圍的平均差異，因為平均差異可以更公平的體實驗，進一步討論算法的適用范圍。()固定概率ICP、aceookeoIC的傳播概率相同，并將傳播概率設置為∈.,.0,.0,0.0}，分析對比不同傳播概率下各算法的性能；(ICeo點之間的傳播概率由節點間的交互強度決定，節點u對節點v轉發的微博數+評論的微博數)/2，也即v對u的轉發率和評論率的平均值5.4實驗結果及分影響范圍對比圖中，X軸表示推廣預算大小，Y軸表示選定種子節點集合之后通Google用于用來標識網頁等級/重要性的算法，阻尼因子設為DAG2-5.4.1固定概率的IC模型實驗結果與分法 算法比以往的啟發式算法有更好的傳播效果。并且與DAG2-SPBP算法的結果不相上下，尤其在傳播概率為0.01時本文所提的兩種算表5.5各個算法與ProbCover算法影響范圍差異表5.5是其他4種算法與ProbCover算法在影響范圍差異上的對比，量化的顯示了其他啟發式算法與ProbCover算法在影響范圍上的百分比差異，不同算法如圖5.4(a)所示，在傳播概率為0.01時，本文所提出的兩種算法以及DAG2-SPBP算法明顯優于MaxDegree算法和PageRank算法，這是因為后兩者下不再適用，與ProbCover算法相比MaxDegree和PageRank算法的影響范圍要小29.97%和58.54%。ProbCoverLF算法影響范圍略有提升，提高了3.59%，DAG2-SPBP算法雖然在預算大于4000時影響范圍比ProbCover略有優勢但在整體上ProbCover算法優于DAG2-SPBP算法9.81%。如圖5.4(b)所示，在傳播概率為0.02時，本文所提出的兩種算法仍然有較大優勢，ProbCover算法比MaxDegree和PageRank算法的影響范圍要大31.3%和63.40%。ProbCoverLF算法此時與ProbCover算法沒有差異，而DAG2-SPBP算法要優于ProbCover算法2.70%。如圖5.4(c)所示，在傳播概率為0.03時，同樣由于設計思想的問題，MaxDegree和PageRank算法表現很差，影響范圍比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算法則要優于ProbCover算法0.037%和2.45%。綜上所述，由于MaxDegree算法和PageRank算法沒有考慮節點成本的差異的差距，這也說明了不同的算法有不同的適用場景。而ProbCover算法、ProbCoverLF算法和DAG2-SPBP算法三者之間差異變化很小，但也互有勝負，有(a)P=(b)P=(c)P=(d)P=圖5.4各個算法在DBLP數據集和不同傳播概率上的影響效MaxDegree算法運行時間在1秒以下，PageRank算法在13秒便可完成計算，ProbCover算法、ProbCoverLF法和DAG2-SPBP運行時間較長，但也未超過1小時，仍在可以接受的范圍之內。DAG2-2各算法Facebook數據集上的結果分是全球知名的社交網絡，能夠真實2各算法Facebook數據集上的結果分是全球知名的社交網絡，能夠真實的反映人們線下的社會關系1743.691，可以看出是一個非常緊密的5.5DBLP并且我們所提出的ProbCover算法及ProbCoverLF算法比以往的啟發式算法有更表5.7各個算法與ProbCover算法影響范圍差異對表5.7是其他4種算法與ProbCover算法在影響范圍差異上的對比，量化的顯示了其他啟發式算法與ProbCover算法在影響范圍上的百分比差異，從表5.7中可以看出，ProbCover算法、ProbCoverLF法和DAG2-SPBP算法整體所呈現的差異不大并且要優于MaxDegree算法和PageRank算法但是與MaxDegree算法如圖5.5(a)所示，當傳播概率為0.01時，本文所提出的兩種算法和DAG2-SPBP算法明顯優于MaxDegree算法和PageRank算法，并且隨著推廣預算的增加各個算法的影響范圍也逐步提升，雖然在預算增加到3500之后PageRank算法的影響范圍上升非常快，但是其整體效果仍與ProbCover算法有較大差距。與ProbCover算法相比MaxDegree算法和PageRank算法的影響范圍要小23.38%和54.41%，ProbCoverLF算法和DAG2-SPBP算法優于ProbCover算法0.94%和2.36%。如圖5.5(b)所示，當傳播概率為0.02時，與MaxDegreePageRank算法相比，ProbCover算法仍然全程領先，影響范圍分別要大5.32%和28.84%。而ProbCoverLF和DAG2-SPBPProbCover算法的差異均不到1%。雖然在預算達到3500之后PageRank算法的影響范圍基本和本文所提出的算法持平如圖5.5(c)所示，當傳播概率為0.03時，預算在1000-2500的范圍內ProbCoverLF、DAG2-SPBPProbCover算法保持絕對優勢，并且三者之間差異非常小，當預算超過3000之后MaxDegree和PageRank算法的影響范圍與其他DAG2三者基本持平，但是總體差異仍然三者基本持平，但是總體差異仍然3.43%18.75%。并且從圖中可以看ProbCoverLF、DAG2-SPBP、ProbCover和MaxDegree算法的影響范圍隨預算增長并不明顯，而PageRank算法的影響范圍則持續上升。如圖5.5(d)所示與傳播概率為0.02和0.03時相似當傳播概率為0.04時，ProbCoverLF、DAG2-SPBPProbCover算法雖然整體保持優勢，但是優勢并不明顯，只比MaxDegree算法影響范圍大4.17%，PageRank算法的影響范圍雖然持續上升但整體上差距仍有11.22%。從以上的分析我們可以看出，并不像DBLP數據集那樣ProbCoverLF、算法之間的差異非常之小，并且MaxDegree算法也有著不錯的影響范圍。我們率為0.04時甚至已經覆蓋網絡規模的一這是因為Facebook數據集比較特殊，絡非常稠密，而且有個別節點的度數達到1000以上，這個時候高度數的節點對影響力傳播起著非常重要的作用，PageRank(a)P=(b)P=(c)P=(d)P=圖5.5不同算法在Facebook數據集和不同傳播概率上的影響效算法在Facebook數據集上的運行時間如表5.8所示，從表中可以看出MaxDegree算法和PageRank算法的運行時間都在1秒以內，ProbCover算法、ProbCoverLF算法和DAG2-SPBP算法的運行時間也都在1分鐘以內，這Facebook數據集節點規模較小有關表5.8不同算法的運行時間(秒3各算法weibo數據集上的結果轉發，信息通過這種方式流通。圖5.6為各Facebook數據集節點規模較小有關表5.8不同算法的運行時間(秒3各算法weibo數據集上的結果轉發，信息通過這種方式流通。圖5.6為各個算法在不同概率下的影響范圍對比表5.9各個算法與ProbCover算法影響范圍差異對如圖5.6(a)所示在傳播概率為文所提出的算法具有較高的優勢并且表現穩定，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算法要優于MaxDegree和PageRank16.51%和14.84%，并且此時PageRank算法的影響范圍要略高于MaxDegree算法。如圖5.6(d)所示在傳播概率為0.04推廣預算的增加，ProbCoverLF、差異很小，ProbCoverLF和DAG2-SPBP算法的影響范圍比ProbCover算法要高0.07%和0.37%。ProbCover算法要優于MaxDegree和PageRank5.13%和4.18%，而MaxDegree綜上所述，由于MaxDegree算法和PageRank算法在設計時沒有考慮節點DAG2DAG2-ProbCover算法、ProbCoverLF算法和DAG2-SPBP算法三者之間差異很小，綜合法的優勢逐漸縮小，這一點文獻[]中也有指出，這是因為隨著預算的增加，初始節點集合的規模逐漸增大，然而影響力傳播所能獲得的邊際收益卻會越來越(a)P=(b)P=(c)P=(d)P=圖ProbCover算法、ProbCoverLF算法和DAG2-SPBP算法三者之間差異很小，綜合法的優勢逐漸縮小，這一點文獻[]中也有指出，這是因為隨著預算的增加，初始節點集合的規模逐漸增大，然而影響力傳播所能獲得的邊際收益卻會越來越(a)P=(b)P=(c)P=(d)P=圖5.6不同算法在weibo數據集和不同傳播概率上的實驗結算法在weibo數據集上的運行時間如表5.10所示，MaxDegree算法在不到1秒的時間內即可運行完畢，而PageRank算法也僅需1秒多的運行時間，其他3種算法雖然比MaxDegree和PageRank算法運行時間要長，但是也僅需幾分鐘的表6.10不同算法的運行5.4.2變概率下的IC模型實驗結果與分DAG2-轉發的微博數點間的交互強度決定，節點u對節點v的傳播概率為評論的微博數)/2vu轉發的微博數點間的交互強度決定，節點u對節點v的傳播概率為評論的微博數)/2vu同算法在weibo數據集上的實驗結果進行分圖5.7變概率下不同算法在weibo數據集上的實如圖5.7所示，在變概率條件下，本文所提出的算法仍然表現優異，影響范圍遠遠大于MaxDegree算法和PageRank算法由表5.10的量化對比分析可以看出ProbCover算法的影響范圍比MaxDegree算法和PageRank算法分別要大71.25%和71.03%，優勢非常明顯這是因為MaxDegree算法和PageRank算法不僅沒有ProbCoverProbCoverDAG2-SPBP微優勢，影響范圍要大1.77%，而ProbCoverLF算法比ProbCover算法又提升了2.38%。綜上所述，ProbCoverProbCoverLF表5.10算法與ProbCover響范圍差異DAG25.11是各個算法的運行時間數據，MaxDegree算法和PageRank算法并沒有考慮傳播模型的特性，所以運行時間與固定概率時基本一致，MaxDegree不到1時間內即可運行完畢，而PageRank算法也僅需1秒多的運行時間他的算法在變概率條件下的運行時間略有改變，雖然比MaxDegree和算法運行時間要長，但是也僅需幾分鐘的時間，在時間效率上也證表5.11不同算法的運行時間(秒表5.11不同算法的運行時間(秒DAG2-5.4.3實驗結果本文提出的算法在影響范圍上遠優于MaxDegree算法和PageRank算法，這是因而與DAG2-SPBP從三個不同數據集上的實驗結果來看，在P數據集和acook數據集上本文提出的算法要略優于DPBP算法，而在eo數據集上與-PBP5.1-5.3現，weibo數據集的聚類系數與其他兩個數據集相差較大，DBLP數據集和Facebook數據集的聚類系數分別為0.6324和0.617，而weibo數據集的聚類系數僅為0.186人以群分”稠密。綜合實驗結果和數據集的統計資料來看DAG2-SPBP算法相比，本5.5本章小第六章系統實第六章系統實現第六章系統實第六章系統實現6.1原型系統整體架本文提出了基于概率覆蓋范圍的啟發式算法ProbCover算法及ProbCoverLF統主要包括輸入模塊、節點選擇算法模塊、傳播模型模塊和結果輸出模塊，原系統整體架構如圖6.1所示傳播模型模結果輸出模固定概變概節點選擇算法模DAG2-輸入模建立網絡拓數據預格式化的數據圖6.1原型系統整體節點選擇算法模塊：該模塊實現了本文所提出的ProbCover算法和PorbCoverLF算節點選擇算法模塊：該模塊實現了本文所提出的ProbCover算法和PorbCoverLF算法及其他經典的算法MaxDegree算法、PageRank算法出，包括節點ID和其屬性。6.2原型系統實6.2.1開發環硬件環境為PC機一臺，配置為Intel(R)Core(TM)i7處理器，8GB內存，操Windows7旗艦版(64C12.11下開6.2.2系統實1ID0存取數據，整體流程如圖6.2所示。本文采用鄰接表的形式來存儲網絡拓撲設計 類來存放節點屬性、節點鄰居以及計算節點距源節點距離等操作以及計算單源最短路徑的以及計算單源最短路徑的算法NY節點ID這里不再贅述，下面主要介紹傳播模型模塊，該模塊實現了IC模型的模擬傳播點間激活概率以節省空間，prob[u][v]代表節點u對節點v的影響概率，固定概影響概率，prob[u][v]采用STL中unordered_map和vector來構建而非矩陣，這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存放節點狀態，被激活為true未激活為false，active_queue是一個隊列存放可以激活其鄰居的激活態節點，result為最第4行開始模擬傳播過程，simulateTime為模擬次數，最后取平均值；第5-7行初始化所有節點為未激活態；第8-11將種子集合中的節點修改為激活態，并入隊列12第13行從隊列中取出一個激活態節點u；第14-20uvprob[u][v]vv，result增加1；第23prob[u][v]vv，result增加1；第23行最后返回多次模擬傳播后影響范圍的平均值26.3 各種選擇。分別選擇數據集、要運行的算法、推廣預算和傳播概率，點擊Run另外以文件的形式保存結果方便查閱，如圖6.4所示，輸出的結果包括種子集合中所包含的節點ID、節點的一些屬性和在傳播模型下模擬傳播得到的影響范圍。以ProbCover法為例，在weibo數據集下推廣預算設置為4000采用率的獨立級聯模型得到的運算結果，第一列為節點ID，第二列為節點的cost即成本，第三列是選擇節點所采取的指標算法中該項為單位成6.46.3本章6.46.3本章小第七章總結與展望7.1工作總第七章總結與展望7.1工作總針對新問題，提出一種基于節點概率覆蓋范圍的啟發式算法ProbCoverProbCoverLF出的ProbCover算法和ProbCoverLF算法在時間效率和影響范圍兩方面均表現優7.2研究展)科學研究是一個從具體到抽象再到具體的過程，針對影響最大化問題，“病毒營銷2015-05-06于東南大學計算機[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.汪小帆,李翔,陳關榮.復雜網絡理論及其應用[M].北京:清華大學出版社,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.網絡科學原理與應用[M].北京：機械工業出版社,Kleinberg,Jon.Thesmall-worldphenomenon:analgorithmperspective.Proceedingsofthethirty-secondannualACMsymposiumonTheoryofcomputing.ACM,2000:163-170.[23