基于成本效益影响大化算法分析与设计

随着近随着近些年互联网的飞速发展，社交网络应运而生，例如国外的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是所有边的集合。∈V表示个体，<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独立级联模活时，它会以概率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