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

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