基于k-核过滤的社交网络影响最大化算法-李阅志.pdf

《基于k-核过滤的社交网络影响最大化算法-李阅志.pdf》由会员分享，可在线阅读，更多相关《基于k-核过滤的社交网络影响最大化算法-李阅志.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Journal of Computer Applications计算机应用，2018，38(2)：464470ISsN 10019081CODEN JYIIDU20180210http：wwwjocacn文章编号：1001-9081(2018)02-046407 DOI：1011772jissn100190812017071820基于k核过滤的社交网络影响最大化算法李阅志12，祝园园1扩，钟 鸣12(1软件工程国家重点实验室(武汉大学)，武汉430072； 2武汉大学计算机学院，武汉430072)(通信作者电子邮箱yr&uwhueduca)摘要：针对现有社交网络影响最大化算法影响范围小和时间复

2、杂度高的问题，提出一种基于独立级联模型的矗一核过滤算法。首先，介绍了一种节点影响力排名不依赖于整个网络的现有影响力最大化算法；然后，通过预训练k，找到对现有算法具有最佳优化效果且与选择种子数无关的k值；最后，通过计算图的_j核过滤不属于核子图的节点和边，在_|-核子图上执行现有影响最大化算法，达到降低计算复杂度的目的。为验证核过滤算法对不同算法有不同的优化效果，在不同规模数据集上进行了实验。结果显示，应用_|一核过滤算法后：与原PMIA算法相比，影响范围最多扩大1389，执行时间最多缩短834；与原核覆盖算法(CCA)相比，影响范围没有太大差异，但执行时间最多缩短285；与OutDegree算

3、法相比，影响范围最多扩大2181，执行时间最多缩短2696；与Random算法相比，影响范围最多扩大7199，执行时间最多缩短2421。进一步提出了一种新的影响最大化算法GIMS，它比PMIA和IRIE的影响范围更大，执行时间保持在秒级另q，而且GIMS算法的l|一核过滤算法与原GIMS算法的影响范围和执行时间差异不大。实验结果表明，_|一核过滤算法能够增大现有算法选择种子节点集合的影响范围，并且减少执行时间；GIMS算法具有更好的影响范围效果和执行效率，并且更加鲁棒。关键词：社交网络；影响最大化；k-核；独立级联模型；传播树中图分类号：TP312 文献标志码：Akcore filtered

4、influence maximization algorithms in social networksLI Yuezhil一，ZHU Yuanyuanl，r，ZHONG Min912(1State研Laboratory of SoftEngineering(Wuhan Univers缸y)，Wuan Hubei 430072，China；2School of Computer,Wuhan University,Wuhan Hubei 430072，China)Abstract：Concerning the limited influence scope and higll time comp

5、lexity of existing influence maximization algorithmsin social networks，a k-core filtered algorithm based on independent cascade model was proposedFimfly，an existinginfluence maximization algorithm was introduced，its rank of nodes does not depend on the entire networkSecondly，pro-training was carried

6、 out to find the value of k which has the best optimization effect on existing algorithms but has no relationwith the number of selected seedsFinally，the nodes and edges that do not belong to the k-core subgraph were filtered bycomputing the k-core of the graph，then the existing influence maximizati

7、on algorithms were applied on the k-core subgraph，thus reducing computational complexitySeveral experiments were conducted on datasets with different scale to prove that thek-core filtered algorithm has different optimization effects on different influence maximization algorithmsAfter combined withk

8、-core filtered algorithm，compared with the original Prefix excluding Maximum Influence Arborescenee(PMIA)algorithm，the influence range is increased by 1389and the execution time is reduced by as much as 834；compared with theoriginal Core Covering Algorithm(CCA)，the influence range has no obvious dif

9、ference and the execution time is reduced byas much as 285；compared with the original OutDegree algorithm，the influence range is increased by 2181and theexecution time is reduced by as much as 2696；compared with the original Random algorithm，the influence range isincreased by 7199and the execution t

10、ime is reduced by as much as 2421Furthermore，a new influence maximizationalgorithm named GIMS(General Influence Maximization in Social network)was proposedCompared witll PIMA and InfluenceRank Influence Estimation(IRIE)，it has wider influence range while still keeping execution time at second levelW

11、hen itwas combined with k-core filtered algorithm，the influence range and execution time do not have significant changeTheexperimiental results show that k-core fdtered algorithm can effectively increase the influence ranges of existing algorithms andreduce their execution times；in addition，the prop

12、osed GIMS algorithm has wider influence range and better efficiency，and itis more robustKey words：social network；Influence Maximization(IM)；k-core；independent cascade model；diffusion tree收稿日期：20170725；修回日期：20170910。基金项目：国家自然科学基金资助项目(61502349)；湖北省自然科学基金资助项目(2015CFB339)；苏州市科技发展项目(SYG201442)。作者简介：李阅志(1

13、993一)，男，湖北黄冈人，硕士研究生，主要研究方向：社交网络、数据挖掘；祝园园(1984一)，女，河南周口人，副教授，博士，CCF会员，主要研究方向：图数据库、大规模数据分析、数据挖掘；钟鸣(1982一)，男，湖北孝感人，副教授，博士，CCF会员，主要研究方向：大规模数据分析、图查询与处理、数据挖掘。万方数据第2期 李阅志等：基于|-核过滤的社交网络影响最大化算法0 引言随着Facebook和微信微博等社交网络的流行，越来越多的用户喜欢在社交网络中分享自己的观点和其他信息，使得网络影响力传播的研究成为社交网络分析的热点J。影响力最大化问题作为病毒式营销和广告投放等社交网络推荐研究领域的一个重

14、要问题，引起了广泛的关注和研究热情。影响最大化问题最早由Domingos等旧1定义为如何寻找t个初始节点，使得信息的最终传播范围最广。Kempe等口1将影响最大化定义为一个离散优化问题，证实了这个问题在独立级联模型下是NP难问题，提出了对后续研究影响极大的两种传播模型：独立级联(Independent Cascade，IC)模型和线性阈值(Linear Threshhold，LT)模型，并基于子模性质(submodularity)提出了一个基本的贪心算法Greedy。为了降低Greedy算法的时间复杂度，后来的研究者又提出了若干改进算法，如CELF(CostEffective Lary For

15、ward)算法”1、DegreeDiscount算法”1、核覆盖算法(Core Coveting Algorithm，CCA)Ee、PMIA(Prefexcluding Maximum InfluenceArborescence)算法71、IRIE(Influence Rank InfluenceEstimation)算法”o等。其中PMIA算法和IRIE算法被认为是现有影响力最大化算法中影响范围和时间效率排名靠前的算法。这些算法基本都使用了子模性质，虽然时间效率有了很大的提升，但是影响范围效果仍然比不上Greedy算法p1。Kempe等o已经证明具有子模性的影响范围函数使用Greedy算法求

16、解，能取得最优解的63pj。该结论表明当前取得最大影响范围的Greedy算法和最优解仍有差距。为了缩小现有影响最大化算法和最优解的差距，本文提出一种采用J|核过滤的算法，可以应用于现有的大多数基于子模性质的影响最大化算法，扩大它们的影响范围，降低它们的时间复杂度。基于该|I核过滤算法，本文对PMIA算法、CCA、OutDegree算法、Random算法分别进行优化，扩大了影响范围，降低了执行时间，尤其对于CCA，在不减小影响范围的情况下执行时间缩短了285。并且通过预训练k首次发现同一算法在同一数据集上取得最佳优化效果的k是固定值。李国良等叫提出了一种针对多网络实体影响最大化的算法，本文将矗核

17、过滤算法结合该算法思想应用到单个社交网络上，提出了一种新的影响最大化算法GIMS(General InfluenceMaximization in Social networks)，该算法比PMLA和IRIE的影响范围更大，执行时间更短。1传播模型和问题定义设有向图G=(y，E)表示一个社交网络，其中：V表示节点集合，n表示节点总数；E表示边集，m表示边的总数。V。y表示节点，Ve(u，”)E E表示一条u指向甜的有向边。11 独立级联模型独立级联模型是一个概率模型。对于网络G中的每个节点都有两个状态：激活和未激活。每个节点只能从未激活状态转变为激活状态，每个节点可以被它的相邻节点激活。对于每

18、条边e(u，”)E E，需指定一个影响概率p(M，口)E0，1，P(u，”)表示节点“通过边e(u，”)影响节点口的概率。给定初始激活节点集合S0，传播过程以如下方式进行：当传播至第t+1步时，利用在第t步中被激活的节点，根据成功概率P(“，”)试图去激活它们的邻居节点，并将在这一步中被激活的节点加入到Js。形成S。；重复这一过程，直至不再有新的节点被激活。整个过程中u只尝试激活”一次，激活成功则”由未激活变为激活状态，激活失败则不再尝试激活。12 问题定义定义l 有向图G=(y，E)中，给定一个输入t，独立级联模型下的影响最大化(Influence Maximization，IM)问题是找到

19、G一个节点子集SV，S的最终影响范围盯(S)满足：盯(S+)=max盯(S)l|S l=t，SVSt sI=t定义2 一个集合函数f：2一R是单调的，如果以S)灭r)对所有sr都成立。定义3 一个集合函数f：2一R是子模的，如果以S u,)一，(|s)八ruld,)一八r)对所有|sry和ld,y都成立。Kempe等1证明了影响最大化问题是NP难问题，并且证明影响范围函数满足单调性和子模性，由此提出了可获得(1一le)的近似最优解Greedy算法。Greedy算法的影响范围是现有影响最大化算法中效果最好的，能取得最优解的63【3 J，但时间效率很低，执行一次需要几个小时甚至几天。本文提出一种_

20、|-核过滤算法，可以扩大现有算法的影响范围，并且降低算法的执行时间复杂度。2基于尼核过滤的影响最大化算法本文提出了一种蠡核过滤算法，可以应用于很多影响最大化算法，扩大它们的影响范围，缩短其执行时间。同时，本文还提出了一种新的单社交网络影响最大化算法GIMS，其影响范围比广泛认可的PMIA算法和IRIE算法效果更好，执行时间比PMIA算法更少。21七核定义4集合KV的任一节点口的度数不少于k，由K所推导出的最大诱导子图q(K，B)称为七-核。矗核概念由Seidman【l于1983年提出，可用来描述度分布所不能描述的网络特征，揭示源于系统特殊结构的结构性质和层次性质。虽然节点度在影响最大化问题中被

21、研究者广泛关注，但是度较大的节点可能较为分散，而|-核使得度较大的节点聚集起来，网络分布越集中，就越能受到彼此影响，从而产生更大的网络影响力。因此本文采用七核来优化现有影响最大化算法。22|-核过滤算法本文提出的|核过滤算法不是一个独立的影响最大化算法，而是通过与现有影响最大化算法相结合来扩大现有算法的影响范围，并缩短其执行时间。|-核过滤算法的基本思想是通过预训练k，找到对现有算法具有最佳优化效果、并且与选择种子节点数t无关的固定k值，在给定需要选择的节点数t时，通过计算图的|核过滤不属于矗核子图的节点和边，在尼核子图上执行现有影响最大化算法，从而达到减少计算量的目的。七核过滤算法涉及两个步

22、骤：1)通过预先训练找到能产生优化效果最好的参数k，如算法1所示；2)计算网络的J一核，并应用在现有算法中，如算法2所示。万方数据计算机应用 第38卷算法1预训练_|。输入有向图G=(y，E)，迭代次数iter；输出最佳优化效果k。1)optk=0，女=0，t=md(O，10)，盯“=0；2)while盯opl6) optk=女；盯“。盯；7) k+；8)return optk；算法2 k核优化现有算法。输入有向图C=(y，E)，最佳优化效果_|，种子节点数t；输出 种子集合s。1)compute CI，the k-core subgraph ofG；2)s=商出ngIN algorithm

23、onGI；3)leurn|s；算法1的预训练过程需要提前完成以选出最佳优化效果奄，由本文实验可知，在选取不同的种子个数t时，取得最佳优化效果的矗是固定值。接着采用算法2计算G的种子集合s，此时的执行时间会减少很多，影响范围效果也会更好。本文利用Baugeli等21提出的算法计算I|-核子图q，通过迭代删除度小于|的所有顶点和与之相连的边，剩下的子图就是蠡核，时间复杂度为D(m)。针对不同的现有算法，_|核过滤算法有不同的结合方式，算法的时间复杂度取决于现有算法的时间复杂度，但通常比结合前的原算法效率更高。假设现有算法的时间复杂度为只n，m)，那么|核过滤算法的时间复杂度为max0(m)，八n。

24、，m。)，其中m和m。表示I|-核子图的节点数和边数。通常以n，m)都是大于0(m)的复杂度，通过后一核过滤之后算法时间复杂度不超过0(m)租厂(，l。，m。)的最大值，但一定小于火乃，m)。算法2也可以脱离算法1直接执行，可以任意选择k，对现有算法的影响范围和执行时间都会有改进，只是没有预训练J的优化效果好。23_|-核优化现有算法现有影响最大化算法中，PMIA算法和IIUE算法传播影响效果较好，其中PlVlI哺的内存耗费较大，IBIE算法执行时间较长。本文将_|核过滤算法分别与CCA引、PMIA算法71、OutDegree算法和Random算法相结合，得到KCoreCCA算法、KCoreP

25、MIA算法、Kco陀olltDree算法和KCoreIl丑rldom算法，以扩大原算法的影响范围，缩短其执行时间。IRIE算法和Pageltank算法13 3是基于节点排名的算法，节点排名依赖于整个网络所有节点的收敛，|-核过滤算法原理是先剪枝不重要的节点，因此无法应用在这两个算法中。231 KCoreCCA核覆盖算法(CCA)是基于覆盖距离选择核数最大的t个节点作为种子节点。核数|表示节点属于|核，而不属于(k+1)-核。CCA和七一核过滤算法都是基于蠡-核的概念提出的，较小核数的节点对CCA毫无贡献，剪枝核数较小的节点虽然对CCA的影响范围没有改变，但是可以大大缩短CCA的执行时间。算法3

26、 KCoreCCA。输入有向图G(V，E)，种子节点数t，覆盖距离d；输出种子集合|s。1)initializeS=；2)compute G(吒，Et)，the k-core sub目raph ofC；3)eomlmteCores(GI)；4)fo嘲eh velteX口E K do5) CO。=false；6)fori=1 tot do7) 埘=盯g maxC，I pKs，CO。=false；8) =arg m眠d。I ph、S。C，=C。，CO。=false；口9) S=S Uu；10)foreaeh vertex口in口I dd，口吒do11) CO。=true；12)mhuns：其中：C

27、为节点的核数，co，表示节点覆盖属性，d。表示节点u和口之间的距离。算法3是将l|-核过滤算法应用于CCA，CCA的时间复杂度是0(tm)M J。KCoreCCA先计算出七一核子图(第2)行)，时间复杂度是0(m)；第3)一12)行遵循CCA的基本思路，但只针对_|核计算，而不是整个网络，时间复杂度是0(tm。)。所以KCoreCCA的时间复杂度是ma】【0(m)，0(tm。)，因为剪枝了很多节点，减少了计算量。KCoreCCA是以核数考量选择种子节点，而以出度考量选取种子节点的算法，称为OutDegree算法，类似优化CCA的方式，应用七一核过滤算法于OutDegree算法，得到KcoreO

28、utDegn算法，oIltD叼m算法时间复杂度为0(+m)，KCoreOmDegree算法时间复杂度为m娃O(m)，0(以，m。)。I|-核过滤算法应用于随机选取种子节点的Random算法，得到KCoreR衄dom算法，Random算法时间复杂度为0(t)，KCoreltandom算法时间复杂度为m娃D(m)，0(t)=0(m)。232 KCo弛PM认算法PMIA算法先计算每个节点V口V的本地树结构PMIIA和PMIOA，基于本地树结构PMIIA计算当前种子集合s对每个节点u的影响印(u，S，PMIIA(v，0)，并根据影响线性(Intluenee IAne盯ity)性质计算影响系数a(口，u

29、)，然后根据本地树结构结合子模性选出影响最大的t个节点。PMIA算法需计算每个节点的本地树结构，虽然加快了影响传播的计算和更新，但保存每个节点的本地树结构需要耗费大量内存，计算全部节点本地树结构效率也较低。本文采用|核过滤算法筛选出可能是最具影响力的节点，只需计算这些节点的本地树结构，从而减少了大量计算。算法4 KCorePMIA算法。输入有向图G(y，E)，种子节点数t，路径传播阈值一；输出种子集合S。1)sets=；2)set胁坝口)=0for each node口V3)compute瓯(K，EI)，the k-core subgraph ofG；4)foreherlex口GI do5)

30、compute PMIIA(口，0，S)；6) set ap(，S，PMIIA(口，0，S)=0，Vu E IMIIA(口，0。S)；7) computea(口，u)，Vu E PMIIA(F，0，s)8) foreaeh veltex u E PMIIA(p，0。S)do9)l，IcInf()+=a(口，)(1一ap(1，S，PMIIA(口，口，S)；10)fori=1tot do11)pick u=arg u)；H E,7m、aoxlrlclnf(12) compute PMIOA(“，0，_s)；13) foneaehE PMIOA(“，0，S)n K do万方数据第2期 李阅志等：基于

31、_|一核过滤的社交网络影响最大化算法 46714) forPMIIA(口，日，S)、S do15)lnclnf()一=n(口，)(1一ap(W，S，PMIIA(v,O，S)；16)S=S uu；17)forl3 E PMIOA(u，日，S、u)、un K do18)compute PMIIA(v,O，S)；19) compute印(，S，PMIIA(口，日，S)，VPMIIA(13，0，_s)20) computea(口，w)，VPMIIA(，0，S)21) forE PMIIA(v,O，S)、|s do22)lnclnf()一=a(v，)+(1一口p(，S，PMIIA(v，0，S)；23)r

32、eturn_s；PMIA算法的时间复杂度是0(tit毋+tit卯log，1)，其中n押和分别是所有节点的PMIIA本地树结构和PMIOA本地树结构的最大节点数，t。是计算所有节点的PMIIA本地树结构的最长时间7，由于每个节点都需要计算PMIIA和PMIOA子树结构，PMIA算法的时间复杂度一定大于0(m)。而KCorePMIA算法先计算七一核子图仁(第3)行)，时间复杂度是0(m)，过滤掉部分节点后，只需在G。上再执行PMIA算法(第4)23)行)，时间复杂度是0(nkt泓+tnmn磷log)，因此KCorePMIA算法的时间复杂度为max0(m)，0(+tn毹n潍lognI)。当k较大时，

33、n远小于7,，KCorePMIA算法的时间复杂度不大于D(m)。24 GIMS算法李国良等叫提出的BoundBasedIMMS(BoundBasedInfluence Maximization in Multiple Social networks)算法可以有效解决存在实体对应关系的多网络影响最大化问题，本文对该算法进行扩展，以设计一种可以有效解决单个社交网络上的影响最大化问题的算法GIMS。GIMS扩展了基于树的算法模型【_“，结合独立级联模型的单调性和子模性，降低了时间复杂度，同时也保证了影响范围效果。路径P=(n。=I，n：，rt。=口)表示经由节点it到节点”的一条路径。在独立级联模型

34、下，节点u沿路径P激活节点a的概率为：mlpp(P。)=p(，l。)节点H可以通过多条路径影响到节点”，为减少计算量，采用最大影响路径MPP(u，”)来近似节点“对节点口的影响概率：pp(“，口)一PP(刎DP(“，口)=PP(arg m8)【(pp(只，)通过计算所有节点到节点u的影响概率，可以构建最大逆向传播树ITree(M)，考虑到当pp(u，”)小于某一个阈值p时，节点。被11,激活的概率较小，则忽略此节点。同理，计算节点u到所有其他节点的影响概率，可以构建最大传播树Otree(It)。给定激活的种子集合s，假设s中的每个节点独立地影响其他未激活的节点，并且只在已构建的传播树中传播影响

35、，则S对未激活节点”的影响概率为：，。 、 f1， E s烈虬”21 1一n(1-pp(“，口)，口擘so HE3在种子集合s中加入一个新激活的节点H后，种子集合对节点”的影响增益gain(u S，”)为：gain(uIs，口)=pp(s UM，口)一pp(s，移)=卜。玎。l 1一pp(印)一1一职(1一pp()2pp(u，口)(1-pp(t，移)=pp(u，移)(1-pp(s，口)假设每个节点都是独立影响其他节点，那么种子集合S中新增加一个激活节点u后总的影响增益gain(H Js)为：gain(uI s)=gaiit(uI s，口)=pp(u，”)(1一pp(s，”)根据影响最大化问题的

36、子模性，每次选取影响增益gain(uls)最大的节点加入种子集合s中，直到选取t个节点。算法5 GIMS算法。输入有向图G(y，E)，种子节点数t，路径传播阈值p；输出种子集合|s。1)preeompute lTree(v)and OTree(口)with 0，for V口E y；2)initialize big heap日of Noden id，n spread，n status，forV舯y：3)setS=；4)initializeeP(S，口)=0，for V”y；5、fori=1 tot do6) Nodetnode=且top()；7) while(tnodestatus!=i)do8

37、) compute gain(rhodedlS)；9) modespread=gain(rhodeidlS)；10)tnodestatus=i；11) 且sort()；12)tnode=且印()；13)tnode=日pop()；14) S=S tJmode试；15) updatepp(s，口)，for V口y；16)匣sort()；17)return S；算法5通过构造树模型近似计算传播概率(第1)行)，时间复杂度是0(nt。)，其中t。是所有ITree(v)和OTree(v)的最大顶点数。然后依据独立影响假设简化了影响增益计算，构造大根堆避免了很多影响力小的节点的计算(第6)16)行)。每次

38、计算gain(modeid I|s)的时间复杂度是O(t。)，调整堆日的时间复杂度是0(109 n)，每次迭代更新常量次节点status即可选出最优mode，所以第6)16)行的时间复杂度是0(t口+log n)。因此GIMS的时间复杂度为0(Ittp+t(t口+logn)。在此基础上，本文应用|j一核优化GIMS算法，称为KCoreGIMS算法。KCoreGIMS算法先通过计算l|一核剪枝部分影响力小的节点，时间复杂度为D(m)，在计算算法5的第1)行和第2)行时无需计算全部网络节点，而只需在矗一核子图上执行GIMS算法从而减少计算量，时间复杂度为O(nkt。+t(t。+log，l。)。因此

39、KCo糟GIMS的算法时间复杂度为max0(m)，0(nttD+t(t日+log n)。25算法复杂度比较分析经过24节对各算法分析，总结各算法和其七一核过滤算法的时间复杂度如表1。可以看到，对于影响范围效果好的算法GIMS、PMIA、CCA、OutDegree，计算l|-核的时间复杂度是O(m)，但执行现有影响最大化算法时由于只需要考虑矗一核子万方数据计算机应用 第38卷图的节点和边，使得原算法的复杂度有所降低。对于效果较差的Random算法，由于是随机选择种子节点，使用矗核过滤时计算矗一核使时间复杂度有所增加。因此，对于一般影响最大化算法而言，Ii核过滤算法使得原算法的时间复杂度有所降低。

40、裹1 不同影响最大化算法及其核过滤算法的时闻复杂度比较Tab1 Time complexity comparison of differentIM algorithms and their k-core filtered versions算法 时间复杂度GIMS O(nt口+t(b+logn)KCoreGIMS maxO(m)，O(nit口+t(b+log“I)PMIA 0(眦毋+tn棚n坩log n)KCorePMIA max0(m)，O(nktat+m艰n溉log“)CCA 0(tm)KCoreCCA max0(m)，0(tm)OutDegree O(n+m)KCoreOutDegree

41、maxO(lrl)，O(8I+mt)Random O(t)KCoreRandom O(m)3 实验与分析31数据集本文实验在三个真实数据集上进行，分别是ArXiv(https：arxivors)物理领域作者合作关系网络NetHEPT(collaboration Network of Hish Energy Physics Theory fromarXivorg)、社交网络Slashdot和商品团购网络Amazon(http：snapstanfordedudataindexhtml)。这三个数据集的统计特性如表2所示。表2实验中的数据集Tab2 Experimental datasets32实验

42、设计本文实验比较了GIMS算法、PMIA算法、IRIE算法、CCA、OutDegree算法、PageRank算法和Random算法，以及0 5 10 15 20 25 30 35 40 45 50种子数t(a)传播范围10510-6它们的_|核过滤算法。其中IRIE算法和PageRank由于依赖全局节点排名不适合J核过滤；CCA的覆盖距离d设置为2；GIMS算法、PMIA算法传播概率阈值0设置为1320；社交网络中节点“到节点口的传播概率初始化为1InDeg(”)，其中InDeg(”)表示节点的人度。由于模型的随机性，在计算选择的t个节点的影响范围时采用蒙特卡罗重复模拟10000次，取平均值。

43、所有程序代码都是基于C+语言编程，计算机配置为：centos 66，Intel Xeon CPU E5-2640 v3 260 GHz，8 GB内存。为了评估|-核过滤算法对现有算法的优化效果，本文定义两个评估指标，影响范围优化百分比influ_opt和执行时间优化百分比time_opt。假设A算法的|核过滤算法是KCoreA，当选择t个种子节点时，算法KCoreA的影响范围和执行时间分别是kcoreinflu和kcore_time，算法A的影响范围和执行时间分别是i妒u和time，那么：influ_opt=(kcore_influinflu)influtime_opt=(timekcore_

44、time)time当种子节点数1t50时，定义平均影响范围优化百分比avg_influ_opt和平均执行时间优化百分比avg_time_opt分别为所有t值下influ_opt和time_opt的平均值。33实验结果与分析图1(a)、(b)分别是NetHEPT上各个算法及其|核过滤算法的传播范围和执行时间。通过算法1的预训练k发现选取不同种子个数时取得最佳优化效果的k是固定值：KCoreGIMS最佳优化效果k为3或4，KCorePMIA的最优k为1或2，KCoreCCA的最优k为8，KCoreOutDegree的最优k为3，KCoreRandom的最优k为4或5。从图l可以看到，本文提出的GI

45、MS算法及其优化算法KCoreGIMS比现有算法中效果较好的PMIA算法和IRIE算法选出的节点传播效果更好，执行时间保持在毫秒级别，比IRIE算法更有效率。七一核过滤对于不同算法的优化效果不同。对算法本身效果较优的GIMS算法、PMIA算法来说，l|核优化效果比原算法的影响范围扩大了l左右；对OutDegree算法和Random算法影响范围扩大了10以上；对CCA传播范围没有影响，但是执行时间缩短了27。也即，对所有算法影响范围都扩大了，执行时间都缩短了。0 5 lO 15 20 25 30 35 40 45 5种子数t(b)执行时间图l NetHEPT数据集上的传播范围和执行时间Fig1

46、Influence range and execution time Oil NetHEPT dataset图2(a)、(b)分别是Slashdot数据集上各个算法及其k核过滤算法的传播范围和执行时间。通过算法1的预训练k发现选取不同种子个数时取得最佳优化效果的k是固定值：-o-KCoreGIMS-oGIMS争KCorePMIA夺PMIAe卜IRIE心KCoreCCA台CCA。*KCoreoutDegree，口0utDegree廿KCoreRandom4Random-t-PageRankKCoreGIMS的最优k为22或44，KCorePMIA的最优k为5或6，KCoreCCA的最优k为50，

47、KCoreOutDegree的最优k为加或50，KCoreRandom的最优k为42或44。从图2可以看到，mi。、匿苔靶暴万方数据第2期 李阅志等：基于后-核过滤的社交网络影响最大化算法本文提出的GIMS算法及其优化算法KCoreGIMS仍然是传播范围最好的算法，比PMIA算法和IRIE算法高出2000多节点，执行时间远少于IRIE算法和PMIA算法。座核过滤算法对GIMS算法和PMIA算法影响范围扩大了2以上，执行时间缩短了2以上，对CCA和OutDegree算法执行时间缩短了27左右。图3(a)、(b)是Amazon数据集上各算法及其k核过滤算法的影响范围和执行时间。通过算法1的预训练k

48、发现选取色疆罐匹越0 5 lo 15 20 25 30 35 40 45 50种子数t(a)传播范围不同种子个数时取得最佳优化效果的k是固定值：GIMS的最优k为11，KCorePMIA的最优k为10，KCoreCCA的最优k为19，KCoreOutDegree的最优k为5或7，KCoreRandom的最优k为3或6。从图3可以看到，本文提出的GIMS及其优化算法KCoreGIMS仍是影响范围最大的算法，执行时间也远低于IRIE算法。尽核过滤算法对GIMS算法和PMIA算法影响范围扩大了1以上，对OutDegree算法影响范围扩大了2l以上，对CCA的执行时间缩短了28左右。) 5 lO 15 20 25 30 35 40 45 50种子数t(b)执行时问图2 Slashdot数据集上的传播范围和执行时间Fig2 Influence range and execution time on Slashdot dataset