资源描述：
《基于时间限制的影响传播方法研究与实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
馨Ｌ硕±研究生学位论文基于时间限制的影响传播方法研究与实现申请人：曲思桐４学号：２１４１３１培养单位：计算机科学献学院：计算机技术，学科专业；／Ｉ研巧方向：数据挖掘气、？奇指导教师：刘勇副教授＇弟Ｖ完成財间：２０１６年３月２５，．片，Ｉ＿■Ｓ；１ＶＪ—＇．‘’．．．Ｖ；巧■－广，．．‘？．心■４＊？气＇＜？？？；古 分类号UDC密级公开硕士研究生学位论文基于时间限制的影响传播方法研究与实现申请人:曲思桐学号:2141341培养单位:计算机科学技术学院学科专业:计算机技术研究方向:数据挖掘指导教师：刘勇副教授完成时间：2016年3月25 独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的硏究工作及取得的硏巧成果。据我所知，除了文中特别加，１＾标注和致谢的地方外论文中不包含他人己经发表或撰写巧的研巧成果，也不包含为获得黑龙江大学或其他教育机构的学位或证书而使用过的材料一。与我同工作的同志对本研巧所作的任何贡献均已在论文中作了明确地说明并表示谢意。学位文作者签名嗦教炯签字日期；許月＾曰学位论文版权使用授权书本学位论文作者完全了解黑龙江大学有关保留、使用学位论文的规定，有权保留并向国家有关部口或机构送交抢文的复印件和磁蟲，允许论文被查阔和借阅。本人授权黑龙江大学可抖将学位论文的全部或部分内容编入有关数据库进行检索，可＾式采用影印、缩印或扫描等复制手段保存、汇编学位论文。保密的学位论文在解密后适用于本授权书）（学位论文作者签名－：、导师签名：Ｍ狗句ｆ＇签字日期：么９１月（＞日签字日期：６月日｜７年６础ｉ年占学位论文作者毕业后去向：工作单位：：电话：通讯地址：邮编 黑龙江大学硕士学位论文中文摘要近年来，社会网络上的影响传播受到了越来越多的关注，而病毒性的市场营销作为社会网络影响传播方向最主要的问题之一，也得到了广泛的研究。在影响传播的问题中我们将社会网络拟作图结构，将社会网络中的人拟作图中的节点，通过从图中大量的节点中寻找到一小部分节点，它们可以通过自身的影响力影响到最大范围的节点，也就是使得最大范围的人接受并购买新的创意或产品，最终在社会网络中实现产品的传播最大化，这就是影响最大化问题。现如今随着社会的不断发展，大众需求不断更新改变，许多不同的营销模式应运而生，比如更注重时效性、利益最大化等方面，而这些营销方式的出现和变化也促使我们需要在影响力传播这一领域考虑更多的新问题，本文主要针对社会网络中基于时间限制的影响传播问题进行研究，主要研究内容有：一、在一般的营销过程中，商家经常会规定一个期望的时间，通过一定的营销手段，来达到在期望时间内实现产品影响最大化的目的。本文根据这个背景，提出了不同营销模式中基于时间的影响传播算法，主要包括基于真实时间的影响力最大化问题和饥饿营销方式的种集最小化问题。主要分为三个步骤：1、基于真实用户动作日志，确定用户之间的有效传播时间区间。2、提出基于时间的影响力分配模型。3、提出了基于真时间的影响力最大化问题和饥饿营销方式的种集最小化问题，并分别提出了有效的近似算法。最后在多个真实社交网络数据集上验证了算法的有效性和高效率。二、在影响传播的过程中，容易发现个人的影响力和人与人之间的影响概率也会受到时间的影响。本文根据这一现象，结合人文学科中影响力传播公式：影响力=活跃度+传播力+社会联系，提出了基于真实时间的影响概率优化算法。主要分为三个步骤：1、定义个人影响力项-活跃度、传播力、社会联系的求解方法并进行规范化。2、给出基于时间的独立传播模型TIIC并在给定数据集上学习模型参数。3、根据期望时间，提出动态更新影响概率的优化算法。最后在多个真实社交网络-II- 中文摘要数据集中进行实验，并应用在问题一中进行比较，证明了本文提出的基于时间的影响力优化算法的有效性。关键词：数据挖掘；社会网络；影响传播；营销时间-III- 黑龙江大学硕士学位论文AbstractInrecentyears,moreandmoreattentionhasbeenattractedtothestudyofinfluencepropagationinsocialnetworks,amongwhichoneofthefundamentalproblemsisviralmarketingalsohasbeenextensivelystudied.Intheproblemofinfluencepropagation,wetreatthesocialnetworkasagraphstructure,andusersinthenetworkasthenodesofgraph.Influencemaximizationistheproblemoffindingasmallsubsetofnodes(seednodes)inasocialnetworkthatcouldmaximizethespreadofinfluencethatisthemaximumnumberofpeoplewhoadoptanewideaorbuyanewproduct.Nowwiththecontinuousdevelopmentofsociety,thedemandsofpublicconstantlyupdateandanumberofdifferentmarketingmodelsareemerging,suchastheonesthatpaymoreattentionstotheeffectivenessandothersmaywanttogainthebiggestbenefit.Andwiththeappearanceofthesemarketingmodels,weshouldconsidermoreissuesinthefieldofinfluencepropagation.Inthispaper,wefocusontheproblemofTime-awareInfluencepropagationinSocialNetwork,themaincontentsarefollowing:First,inthegeneralmarketingprocess,businessmenachievethegoalthattheirproductsmaygainthemaximuminfluencebysetanexpectedtimeandaspecialmarketingrules.Basedonthisbackground,weputforwardatime-basedpropagationalgorithmunderadifferentmarketingmodelincludingtime-basedinfluencemaximizationandseedminimizationproblemunderhugermarketingmodel.Thealgorithmismainlydividedintothreesteps:1.determinetheeffectivepropagationtimeintervalbetweenusersbasedonrealuseractionslog.2.proposeatime-baseinfluenceallocationmodel.3.proposetwoproblemsoneofwhichistime-awareinfluencemaximizationproblemandanotherisseedminimizationproblemunderhugermarketingmodel,andproposeeffectiveapproximationalgorithms.Experimentalresultsonseveralrealsocialdatasetsdemonstratetheeffectivenessandefficiencyofthealgorithms.Second,intheprocessofinfluencepropagation,itiseasytofindthatpersonalinfluenceandtheinfluencebetweenpeoplearealsoaffectedtime.Basedonthisphenomenon,weproposeatime-basedprobabilityoptimizationalgorithmcombined-IV- AbstractwithinfluencepropagationequationsinHumanities:Influence=Activity+thepowerofpropagation+socialtie.Thealgorithmismainlydividedintothreesteps:1.Giveaformaldefinitionofthepersonalinfluenceitem-activity,thepowerofpropagation,socialtie.2.Proposeatime-basedindependentcascademodelandlearntheparametersofthemodelunderthedatasets.3.Accordingtothedesiredtime,proposetheoptimizationalgorithmwhichcandynamicallyupdatetheinfluenceprobability.Wetestouralgorithmonmanyreal-worlddatasetsandcomparewiththeproblemproposedabove,theresultsshowtheeffectivenessofthetime-basedinfluenceoptimizationinthispaper.Keywords：Datamining;Socialnetwork;Influencepropagate;Marketingtime-V- 黑龙江大学硕士学位论文目录中文摘要IIAbstractIV第一章绪论.................................................................................................................11.1.研究目的和意义..............................................................................................11.2.国内外研究现状及发展趋势..........................................................................31.3.本文主要研究工作..........................................................................................51.4.章节安排..........................................................................................................6第二章课题研究基础知识.........................................................................................72.1.社会网络的定义..............................................................................................72.2.社会网络中的影响传播..................................................................................82.2.1.传播模型................................................................................................82.2.2.算法评价指标........................................................................................92.2.3.贪心算法和启发式算法........................................................................92.3.基于时间的影响力传播................................................................................102.4.本章小结.........................................................................................................11第三章不同营销模式中基于时间的影响传播算法...............................................123.1.引言................................................................................................................123.2.传播模型及问题定义....................................................................................143.2.1.有效传播时间区间获取方法..............................................................143.2.2.影响力分配模型..................................................................................163.2.3.问题定义..............................................................................................193.3.基于真实时间的T-INF和HM-INF算法....................................................203.3.1.建立链表，计算节点初始影响力增益..............................................223.3.2.利用CELF优化选择具有最大影响力增益的节点..........................233.3.3.Co-influence算法-计算节点的影响力增益.......................................24-VI- 目录3.3.4.更新影响力..........................................................................................253.3.5.复杂性和近似比..................................................................................263.4.实验结果与分析............................................................................................273.4.1.数据集及实验环境..............................................................................273.4.2.比较方法..............................................................................................283.4.3.营销时间及种子个数对影响范围的影响..........................................293.4.4.时间及种子个数对运行时间的影响..................................................313.4.5.饥饿营销时间对种子个数和运行时间的影响..................................333.4.6.验证用有效传播时间区间删减图结构的作用..................................353.4.7.传播有效时间区间MMW和AVSW方法的准确性....................353.4.8.HM-INF算法联机近似比证明...........................................................363.5.本章小结........................................................................................................37第四章基于真实时间的影响概率优化算法...........................................................384.1.引言................................................................................................................384.2.影响传播项的形式化定义............................................................................394.2.1.影响传播项的形式化表示..................................................................394.2.2.综合影响概率形式化定义..................................................................404.3.基于真实时间的影响概率优化算法............................................................414.3.1.基于真实时间的影响概率求解算法TAIP.........................................414.3.2.学习影响项参数算法..........................................................................424.4.实验结果与分析............................................................................................434.4.1.数据集及实验环境..............................................................................434.4.2.比较方法..............................................................................................444.4.3.不同时间对影响传播项的影响..........................................................454.4.4.营销时间对参数的影响......................................................................464.4.5.利用优化算法后的影响范围比较......................................................474.4.6.验证传播项的有效性..........................................................................48-VII- 黑龙江大学硕士学位论文4.4.7.参数对整体影响范围的影响..............................................................494.4.8.测试集中验证参数有效性..................................................................514.5.本章小结........................................................................................................51结论52参考文献54致谢59攻读硕士学位期间发表的学术论文及参加的科研项目............................................60-VIII- 第1章绪论第1章绪论1.1.研究目的和意义数据挖掘是指利用大量的数据并通过算法挖掘隐藏于大数据中信息的一种过程。近几年来，数据挖掘在计算机行业乃至全社会引起了极大的关注，人们开始利用规模非常大的数据，并且在这些大量数据中发现对生活或学术研究有用的信息。通过这些获取的信息，我们可以将从这些信息挖掘的潜在规律等广泛的应用于各种行业。总的来说，我们可以由于需求的不同而使用这些挖掘到的信息，并可以利用这些信息用于信息管理及查询。因此，数据挖掘这一领域是很重要的前沿学科之一。而近几年来随着计算机科学的不断发展，各类基于社交关系的网站大批量涌现出来，人们开始对诸如微博、facebook等社交网站广泛使用。而淘宝、亚马逊等电子商务类网站也开始普及，在其平台上提出的大量的营销需求也彻底颠覆了传统的信息传播的模式。数据挖掘在这些社会网络领域中则起到了不可替代的巨大作用。例如，比较多的，就是关于信息在社会网中的传播以及传播后对于大量数据的整理和分析。社会网中产生大量的数据，我们通过对这些数据的分析找到其中蕴含的大量潜在信息，然后可以利用这些潜在信息得到有用的数据，并将其应用到生活中不同场景和各种领域。在社会网上一个比较经典的问题就是影响力传播，影响力传播是社会网信息挖掘领域的一个重要问题。在研究中，我们通常将社会网络拟作图结构，而社会网络图是由网络上的节点和边组成，每一个节点都代表社会网络中的一个个体，每一条边则代表个体与个体间的关系，通常象征朋友关系，在这里两个节点之间的边可能是有向边也可能是无向边，这样我们就把具体的社会网络转化成了一个大规模的图结构，尽管社会网络是虚拟的，但是其中每个节点都会受到该网络中其他人或周围邻居的影响。社会网络就这样通过个体与个体之间的信息传播来实-1- 黑龙江大学硕士学位论文现影响的传播。社会网上影响传播的主要问题是病毒性的市场营销，也就是通过寻找一小部分的具有大的影响力的节点，从而影响最大范围的人接受并购买新的创意或产品，最终实现产品的传播最大化。这也就是影响力最大化的问题定义：通过对社会网上大量数据的分析，找到最具影响力的N个种子节点，从而使这N个种子节点可以影响社会网中最大范围的人群。但是其实在过去的很长一段时间里，传统的市场营销都是以口耳相传的方式来进行。简单来说，当一个人接受了一种新的创意或产品，他可能会传播给自己的朋友，当他的朋友也同样接受了这种创意或产品，我们就说影响力在他和朋友之间进行了传播，而朋友还可以影响朋友的朋友，以此类推。而在互联网这种形式的社会网络的平台上，无论是传播速度、规模或是最终影响的范围都要比传统的方式好很多。社会网络能够更快捷方便的加速产品的营销，而且使用户更能清楚地分辨和挑选产品。相对传统的面对面营销，社会网络提供的平台能够面向更多更广的用户，而且更加让人信任，因此在社会网络中，我们可以将一个信息、想法或是产品在很短的时间内就传播给大量的用户，从而使大量的用户可以接受并应用这些新的创意或产品。而这时，我们挑选哪些用户作为最初始接受信息的载体就变得至关重要，这也会直接影响到最后的影响范围，即产品的营销效果。现如今随着社会的不断发展及大众需求的改变，许多不同的营销模式也应运而生，除了传统的发放免费或可观的优惠以达到影响力最大化以外，更出现了如饥饿营销等以“供不应求”为销售手段的营销模式，试图引起更多的用户关注，从而达到商品营销的最大化。比如商家会更注重营销的时效性从而让自己能达到利润的最大化，或者商家会利用减少供给来影响用户心理从而更多的宣传自己的产品等等。而这些营销方式的不断改变也促使我们在影响力传播这一领域考虑更多的新问题。综上所述，影响力的传播技术研究在社会网的领域中具有极其重要的意义和应用价值。-2- 第1章绪论1.2.国内外研究现状及发展趋势影响力最大化问题的雏形首次被提出是在2001年，DomingosandRichardson[1]提出在社会网上通过寻找具有重要影响力的用户进行产品营销的问题。而在2003年，Kempe将影响力最大化的问题定义为一个离散优化问题，他们首次把社会网络拟作图结构拟，节点代表用户边代表用户之间的关系，而人与人之间的影响则是依据一定的传播模型来进行传播，kempe提出的主要的传播模型有IC模型，即[2]独立瀑布模型，LT模型即线性阀值模型，同时Kempe也证明了影响力最大化问[3,4]题是NP-Hard问题，并提出了贪心算法解决影响力最大化问题，贪心算法具有1-1/e-ε近似比。然而虽然近似比较好，但是kempe运用了蒙特卡洛模拟法来进行影响过程的模拟，通过大量的循环迭代得出了较准确的结果，导致运行时间过长，[5]并不能很好地适应于大兴的社会网络。而在2007年，Leskovec提出了一种懒惰向前的高效计算影响力的方法--CELF优化方法对kempe提出的贪心算法进行了改进，非常好的提高了贪心算法的效率，得到了提升700倍效率的结果。WeiChen在2009年提出了Degreediscount启发式算法，Degreediscount算法调整节点的度从而获得有效的节点影响范围，Degreediscount算法有很高的扩展性，运行速度非[5-7]常快，并获得了与贪心算法相近的影响范围。而传统的影响传播研究都是假设社会网络边上的概率为固定的，这显然不符合[8-30][31-41]生活实际。在生活中显然是需要通过历史行为来进行分析更为准确，文献考虑到了一些概率的变动，但是还是没有基于真实数据。2012年，AmitGoyal提出了基于数据的方法，利用用户的行为日志进行影响力最大化问题的计算，通过[42]分析真实的动作日志，每个用户和用户之间边上不同的概率都有不同，从而大大提高了问题的准确性，也将影响力最大化这一领域越来越多的扩展到真实生活的应用层面。近年来，社会网络上的影响传播研究加入了各种生活中的实际因素，这也使得应用场景更合理，信息挖掘更加准确有价值。遵从感知的影响力最大化问题-3- 黑龙江大学硕士学位论文[43]HuiLi2013年提出了出遵从感知的影响力最大化问题，在传统的影响力最大化问题上添加了遵从性的因素，简单来说，遵从感知的影响力最大化问题不止考虑到了影响者具有的影响力的大小，同时也考虑被影响者接受其他人影响的能力的大小，使得概率更准确，影响范围更加精准。JieTang同年提出了同时考虑个人本身影响力、朋友互相的影响力以及群组关系中的影响力的影响传播最大化问题，结合生活实际我们也不难发现，一个人的影响力收到很多其他因素的影响，JieTang[43]综合考虑到了社会网中个体，朋友之间及社团之间的影响力关系，得到了更精确的实验结果。基于地理感知的影响力最大化问题2014年，GuoliangLi提出了基于地理感知的影响力最大化问题，在影响力最大化问题中加入了用户和用户之间的地理信息因素，具体化到将用户的地理信息分块分区，然后考虑距离关系对于两个人之间影响力的影响。并将加入地理因素[44]的问题具体化。实验结果证实地理因素的确会对个人的影响能力和最终的影响范围造成一定的影响，这也是符合生活实际的。基于时间感知的影响力最大化问题2014年，ShanshanFeng提出了新奇衰减的影响力最大化问题，在这个问题中，添加了时间因素对影响力大小的影响，不难想象的，时间对于营销的过程是非常重要的因素之一，随着时间的不断变化，个人影响力、营销的利润等都会受到不同程度的影响并作出相应的变化，ShanshanFeng考虑到了时间因素对于影响力大[45]小的影响，并提出了动态的更新模型来更好的计算影响力的大小。基于主题感知的影响力最大化问题2014年NicolaBarbieri提出基于主题的影响力最大化问题，将问题更细化到不[46]同的主题分布上。其中考虑到了不同商品在不同主题上有不同的概率分布，不同的用户在不同的主题上也有不同的兴趣，通过综合考虑这两种因素，当给出一件商品时，针对商品及用户的历史行为求得准确的综合概率值作为边上的影响概率，再进行影响力最大化等影响传播研究的计算。基于个人属性的影响力最大化问题-4- 第1章绪论2014年KaiyuFeng提出了基于技能覆盖的影响力最大化问题，考虑到了个人属性在影响力传播研究中的应用场景，在现实生活中，经常会有需要覆盖个人技能的场景，同时技能也会有偏序关系出现，而在影响力传播的领域也同样存在互[47]相的影响传播同时还需要考虑技能的覆盖，这也更接近真实的情景。近几年关于社会网上影响传播的问题被越来越广泛的研究，加入了主题、地理、[48-62]技能等许多其他的考虑因素，使的求得的影响力最大化问题的结果更准确，更有针对性并更有实际的应用价值。1.3.本文主要研究工作本文主要针对基于时间限制的影响传播方法研究与实现进行研究，主要内容包括以下几个方面：1、不同营销模式中基于时间的影响传播算法通过生活中的营销方式我们不难发现，现如今的市场营销通常都和时间有着密不可分的关系，商家都希望在一定的时间内达到营销的预期效果，同时我们在研究过程中也发现，影响范围的增长比例是随着时间不断变化的，直观的，营销开始的阶段，影响范围增长较快，而到达一定时间后，影响范围的增长变得缓慢，这也是符合生活规律的。本文就不同营销模式中基于时间的影响传播进行研究，主要包含以下两个问题：（1）基于真实时间的影响力最大化问题。（2）饥饿营销方式的种集最小化问题。解决问题的主要步骤如下：（1）基于真实用户动作日志，确定用户之间的有效传播时间区间。（2）提出基于时间的影响力分配模型。（3）提出了基于真时间的影响力最大化问题和饥饿营销模式中种集最小化问题，并分别提出了有效的近似算法。最后在多个真实社交网络数据集上验证了算法的有效性和高效率。2、基于真实时间的影响概率优化算法在真实的传播过程中，人与人之间的影响受到很多因素的影响，其中就包括时间的影响，一个人对另一个人的影响是有一定时间限制的，研究发现，这种影响基本呈正态分布。本文根据这一现象，结合社会学科中的影响力传播公式，即影-5- 黑龙江大学硕士学位论文响力=活跃度+传播力+社会联系，提出了基于真实时间的影响概率优化算法。算法主要步骤如下：1、定义活跃度、传播力、社会联系的求解方法并进行规范化。2、给出基于时间的独立传播模型TIIC并在给定数据集上学习模型参数。3、根据期望时间，提出动态更新影响概率的优化算法。最后在多个真实社交网络数据集中进行实验，并应用在问题一中进行比较，证明本文提出的基于时间的影响概率优化算法的有效性。1.4.章节安排本文主要研究内容及其他章节安排如下：第2章介绍社会网络影响传播的相关定义和特性。第3章提出不同营销模式中基于时间的影响传播方法，包括基于真时间的影响力最大化问题和饥饿营销模式中种集最小化问题。第4章利用社会学影响力公式提出了基于真实时间的影响概率优化算法。最后是结论。-6- 第2章课题研究基础知识第2章课题研究基础知识2.1.社会网络的定义在社会学的意义上，社会网络是指社会中的成员因为互动等行为而形成的一种稳定的关系，如朋友关系等等。社会网络是一种关注人与人之间互动和联系的体系，而这种互动行为就会发生人与人之间的影响行为的变化。在研究中，我们通常把社会网络拟作一种图结构，以此来代替表现这种社会结构，其中会有很多点，这代表每一个社会网络中的个体。而点与点之间的边则表示一种社会关系，比如a和b是朋友，那么a到b则有边，经由这种模拟，将社会网络拟作一个可以形式化并方便挖掘信息及计算的图结构体系。如图2-1为facebook上社会网络图结构的实例。图2-1社交网络FacebookFig.2-1Facebook-7- 黑龙江大学硕士学位论文社会网络大致主要分为两种。其中一种如图2-1所示的Facebook，在这类社交网站中，用户的朋友关系是需要双方都给予确认的，所以这类的社交网络可以用无向图来表示，即两个用户代表两个顶点，而连接两个顶点的是一条无向边。另一种是如Twitter这类网站，和facebook相反的，Twitter中用户的朋友关系是单向的，是一种关注的社会行为产生的关系，因此可以用有向图来代表。社会网络可以形式化的定义为图结构G=(V,E)，其中V是图G中的节点集合，E为边的集合。W是边上权值的集合，也就是概率的集合。其中用n=|V|和m=|E|分别表示网络中节点数量及边的数量。一般的，我们用链表或邻接矩阵来储存图G。2.2.社会网络中的影响传播在社会网络的图结构中，个体和个体之间由于有互动等行为产生了社会关系的纽带，所以具有社会关系的两个个体之间会产生不同程度的相互影响，这就激发了影响力的传播问题。在这一节，我们分几个角度来介绍社会网络中的影响传播问题。2.2.1.传播模型首先，个体和个体之间的影响是通过具体的影响传播模型来进行传播的，在影响力传播领域中最经典的传播模型就是IC模型（独立瀑布模型）和LT模型（线性阀值模型）。IC（IndependentCascade）模型IC模型（独立瀑布模型）是一种基于概率的传播模型。在IC模型中，社会网络图G中的每个节点只有“激活”和“未激活”两个状态且状态不可逆，也就是说当一个节点被激活，它便不能再转为未激活状态，整个传播过程中，一个节点只能被激活一次。LT(LinearThreshold)模型-8- 第2章课题研究基础知识LT模型，即线性阀值模型，与IC模型相似的是，LT模型中的每个点也遵从激活状态不可逆的规则。但在LT模型中，图G中的每个点v∈V都带有一个非常小的阀值,其中(0,1)，阀值代表了节点能够受到影响的程度，当阀值越大，说明当前节点越不容易受到其他节点的影响。当一个节点的邻居节点对其的综合影响力超过当前节点阀值，该节点变为激活状态，并继续尝试激活其他未激活节点。2.2.2.算法评价指标从评价指标来看，影响力传播问题主要的评价指标有以下几个：1、算法复杂性，即运行算法所需时间，通常用运行时间衡量，我们希望求得算法复杂度低，运行时间快同时又能满足近似比要求的算法来解决影响力传播问题；2、影响范围，即期望输入的k个节点影响的范围，通常用影响的节点数衡量。3、准确度，即通过在训练集中求得的种集，在测试集中验证种集的真实影响范围，从而验证算法的准确度。4、算法近似比，验证算法是否能求得最优解的重要指标，通常在贪心算法中，我们可以求得算法近似比，使得计算结果拥有近似比保证。2.2.3.贪心算法和启发式算法从算法实现的方法来看，主要有两种，分别为贪心算法及启发式算法。贪心算法贪心算法是指在对一个问题进行求解时，总是作出当前情况下最好的选择，贪心算法是一种不从整体上考虑最优解而是每次都考虑局部最优解的一种算法。其中最重要的是贪心策略的选择。在影响力传播问题中，在任意一轮求解中，我们通常将能够带来最大影响收益的节点放入种集，之后再通过k次循环求得能够影响最大范围节点的种集S，|S|=k。kempeetal.就影响力问题提出了贪心近似算法，近似比在（1-1/e）之内。启发式算法启发式算法是相对于最优化的算法提出的，启发式算法的运行速度要远远的快-9- 黑龙江大学硕士学位论文于贪心算法，但是由于启发式算法并不是利用所求问题的每个实例来求得最优解，启发式算法通常是基于经验或者直观来构造的，导致了它并没有近似比的保证，虽然运行速度极为可观，但其结果与最优解的近似程度是不能够保证和预计的。在影响力传播问题中，由于图结构庞大，贪心算法的运行时间过长，在一些研究中，启发式算法也得到了了广泛的应用。2.3.基于时间的影响力传播本节主要介绍本文的研究重点，即基于时间的影响力传播。时间因素对影响力的影响传统的影响力传播问题并不考虑时间因素对其结果的影响，这显然是不合理的，在真实的社会网络传播行为中，个人的影响力、人与人之间的相互影响、营销的效果都受到时间因素的影响。一个简单的例子，淘宝网的商家想要通过网络营销的方式促销一件新的产品，促销的商品一定是有一定的成本的，所以促销一定会有一个最合适的时间，既能影响到更多的人，又能够平衡成本，这就是时间对营销效果的影响。又比如，商家第一天发放了免费或者非常低价格的商品给用户，如果这个用户在这段时间表现活跃，那么他就有更大的可能性去传播到更多的人，那么这类用户就是商家着重要挑选发放试用或免费商品的，因为他们可以使影响范围尽可能增大，这就是时间对于用户个人影响力的影响。之后种子用户开始向自己的朋友传播商品或创意，这时候有的人可能要3天就能够进行传播并且能够让朋友接受，有的人则可能需要用10天的时间，这就是时间对于人与人之间相互的影响力的影响。在实验中我们发现，真实的传播行为时随着时间的增长由快至慢增长最后趋于平稳，考虑我们之前说的时间因素对影响力的影响，我们也发现规定的传播时间不同，求得的最佳的种子节点集合也是不同的。因此，将时间因素加入影响力传播问题是有一定的现实意义的。除了传统的营销方式，近年来在市场营销等领域中更是涌现出了越来越多的营销方式的变体，如我们熟知的捆绑销售、饥饿营销等等，这些营销方式也越来越重视时间对于营销-10- 第2章课题研究基础知识效果的影响，如在饥饿营销的过程中，商家不再像传统的营销方式一样控制免费商品数量，他们力求用最少的免费商品造成一定的影响而非最大的影响，举个例子，我们都知道在小米手机的销售过程中，商家一周只发放定量的手机，也就是说，在饥饿营销的方式中，影响范围是固定的，商家希望在一定的时间内达到期望的影响范围，同时能让自己的成本最低，这些不同于传统营销模式的市场营销方式更多的强调了时间对于问题本身的影响。因此根据营销时间确定最合适的种集有助于帮助商家制定最优的营销策略。所以基于时间的影响力传播问题具有重要的理论意义和广泛的应用价值。2.4.本章小结本章较为详细的介绍了社会网络的特性及其形式化定义，并同时对社会网络中的影响力传播问题进行了简要的说明，对影响力传播的经典模型IC模型和LT模型进行了介绍。最后重点讨论了本文的研究重点，即基于时间限制的影响力传播问题。详细描述了时间关系在影响力传播过程中的重要性。-11- 黑龙江大学硕士学位论文第3章不同营销模式中基于时间的影响传播算法3.1.引言影响力最大化是在数据挖掘这一领域中重要的研究问题之一，简单来说，影响力最大化问题就是在社会网络中找到k个人，在一定的传播模型下，能够传播到尽可能多的人，使得影响力达到最大。影响力传播在市场营销领域中有着非常重要的应用价值，尤其是在产品或创意推广的前期阶段，商家希望能够找到最合适的初始用户来宣传自己的产品从而直接获取好的产品口碑和高质的后期销量。现有的影响力研究中，往往忽略了以下几个问题：1、不考虑两个用户之间的传播时间有效性。在实验前期，我们对大量的真实动作日志进行了分析，其中包含用户行为和用户关系，实验结果证明用户和用户之间是存在一个具有有效性的传播时间的，在这里我们成为传播的有效时间区间。简单的说，a和b是朋友，由于两人的工作都比较忙，基本上四天以上才能有一次通话聊天，但是每个周日他们都一定会在一起用餐，那么我们很容易的可以看出，由于信息在传播过程中受到时间的限制，a和b在一件商品或者创意上的传播时间一定大于4天，而且基本都会小于7天。真实日志的大量数据也帮助证实了这个结论，表3-1是在音乐评论网站Last.fm的动作日志中提取的几个用户的行为信息。在用户关系上，表中的V1和V2是朋友，V3和V4是朋友，所有时间相对时间（以0时刻为基准），如(V1,a)=2表示在2这个时刻，用户V1的行为为a。表3-1在Last.fm数据集上V1V2V3V4四个用户执行动作的时间Table.3-1thetimeofV1V2V3V4todoactionsinLast.fmdatasetabcdefg时间区间V12548634[4,13]V261291519910V31386597[3,11]V44121815161713通过表中数据我们不难发现，V1和V2的传播时间区间为[4,13]，这也就是说-12- 第3章不同营销模式中基于时间的影响传播算法在V1V2的朋友关系里，如果营销时间不超过4，那么传播基本不会发生，基本上概率小到可以忽略不计；若营销时间在4-13之间，则应根据两人的历史行为进行分析再动态的调整V1和V2的传播概率；那么显然的，当营销时间大于13时，则应以最终平稳的传播概率（即V1,V2在13这个时刻的传播概率）进行事件的传播。我们通过对真实网站的历史动作日志进行分析和标准化，确定了用户之间的传播的有效时间区间，然后根据给定的营销时间来判断影响传播概率，进行影响力大小的分配。2、不考虑种集的选择受到真实的营销时间影响在实验中，我们还发现了这样一个有趣的现象同样支持本文的观点，那就是营销时间不同，相应的具有最大影响力的种集也是不同的。表2同样是在音乐评论网站Last.fm行为日志上进行实验的结果（用本文提出的T-INF算法，设种集个数为3），其中T表示设置的时间（单位时间），S表示当前具有最大影响力的3个节点的种集。很明显的，从表3-2我们可以看到，在营销时间不同的情况下，种集也并不相同。因此，本文提出的根据营销时间的不同来动态的分配影响力是符合生活实际场景的。表3-2在Last.fm数据集上不同的营销时间vs种集(k=3)Table.3-2thetimeTvsseedsetinLast.fmdataset(k=3)T10203040506012732621543142314231423S1543553147498498166656750926217416661473、营销方式的不断更迭，传统的影响力最大化方法已经不能适用于特定的营销方式。同时这类新型的营销方式更注重时间因素现如今营销方式不断改变，我们考虑生活中现在常见的一种营销方式--饥饿营销。饥饿营销指在一段时间内，商品的供应者提供固定量的商品，在市场上制造一种供小于求的现象，以期待商品长期拥有较高利润率的营销方式。在饥饿营销的一次过程中，商家固定了营销时间，同时也固定了商品供应量，即影响范围。这也就有别于传统的影响力最大化问题了，在这个场景下，我们可以找出能达到-13- 黑龙江大学硕士学位论文商家期望影响范围的最小的种集以满足商家要求。针对这一饥饿营销场景，本文提出了饥饿营销中基于时间的种集最小化问题。基于以上三点，本章提出了基于时间的影响力传播的两个子问题，分别为基于时间的影响力最大化问题和饥饿营销方式的种集最小化问题。其中我们首先提出了一个TIIC模型进行影响力的分配，基于TIIC模型进行了T-INF和HM-INF问题的求解，本章提出的方法在基于真实时间的基础上，更好更准确地进行了影响力的计算，在真实网络数据集中进行的实验表明了T-INF和HM-INF算法解决基于时间的影响力最大化问题及饥饿营销方式的种集最小化问题的有效性。3.2.传播模型及问题定义在本节中，首先我们给出了两种获取传播的有效时间范围的方法，其次，我们提出了一个TIIC模型进行影响力的分配，最后，我们给出了基于时间的影响力（TIM）最大化问题和饥饿营销方式的种集最小化问题(HMTSM)的形式化定义，并证明了TIM和HMTSM问题均为NP-hard问题。3.2.1.有效传播时间区间获取方法在3.1节我们提到了用户和用户之间是存在有效传播时间的，这个时间一般是一段区间，当传播发生在区间中，则应按照用户历史行为动态的确定两个用户之间的影响概率。如果传播发生在区间范围前，那么我们认为它传播概率可忽略，如果传播发生在区间范围后，那么我们认为它以平稳的恒定概率进行传播。这一节我们提出了有效时间区间的获取方法，我们给出了两种方法，一种为最大最小值法（MMW），一种为均值标准差法（ASW）。最后我们通过真实数据集上的实验来比较这两种方法的有效性。在这一节的方法中，我们给定一个图G，一个历史动作日志A，动作日志A中记录着用户、用户执行动作、用户执行动作时间。我们利用日志A中的行为关联性来计算用户之间的有效传播时间的区间。(1)最大最小值(MMW)直观的，最大最小值法就是直接通过分析历史传播事件的时间的最大时间-14- 第3章不同营销模式中基于时间的影响传播算法间隔和最小时间间隔作为两个用户之间的传播的有效时间的区间。两个用户之间所有传播行为的最小和最大时间间隔可以直接体现两个用户间动作传播的有效传播时间。具体定义如下：א݁ٿሻሻݐᇱݐሺٿܣאሻᇱݐ,ܽ,ݒሺٿܣאሻݐ,ܽ,ݑሺሺܽ|ݐെᇱݐሼnimൌݐܧሽ(3-1)௨,௩௨,௩א݁ٿሻሻݐᇱݐሺٿܣאሻᇱݐ,ܽ,ݒሺٿܣאሻݐ,ܽ,ݑሺሺܽ|ݐെᇱݐሼnimൌ୶ୟݐܧ(3-2)௨,௩௨,௩其中݁௨,௩אܧ表示从u和v是朋友，在图G中有一条有向边，从u指向v。而最后ݐ,ݐ]间区的成组୶ୟݐ和ݐୟ୶]就是u传播一条信息到u的传播的有效时间的௨,௩௨,௩௨,௩௨,௩区间。(2)平均值+标准差(ASW)MMW方法虽然直观的利用用户之间的最大最小传播时间定义了传播的有效时间的区间，但是由于MMW方法可能会含有一些异常项，比如某一个动作u传播到v用了30天，原因可能是u出差了，但是我们并不能认为，u到v的最大传播时间可以达到30，因为它是一个特殊情况。由此我们又提出了平均值+标准差(ASW)法来更准确计算两个用户之间的传播的有效的时间区间。定义如下:ݐൌߤെߜ(3-3)௨,௩௨,௩௨,௩ݐୟ୶ൌߤߜ(3-4)௨,௩௨,௩௨,௩其中ߤ௨,௩和ߜ௨,௩表示平均值和标准差，为u所有传播到v的行为动作，即u和v所有的相同行为中，u在v之前执行的所有行为的时间间隔的均值和标准差，ߤ௨,௩、ߜ௨,௩定义如下:∑ሼ࢚‘ି࢚|ࢇ൫ሺ࢛,ࢇ,࢚ሻא࢜,࢛ࢋٿ൯ሻ௧வ’࢚ሺٿאሻ‘࢚,ࢇ,࢜ሺٿאࡱሽߤ௨,௩ൌ(3-5)|ࢇ|ሺ࢛,ࢇ,࢚ሻא࢜,࢛ࢋٿ௧வ’࢚ٿۯאሻ‘࢚,ࢇ,࢜ሺٿۯאࡱ|ට∑ሼሺ࢚‘ି࢚ିఓೠ,ೡሻ|ࢇ൫ሺ࢛,ࢇ,࢚ሻאٿሺ࢜,ࢇ,࢚‘ሻאٿሺ࢚’வ௧ሻ൯ሽߜ௨,௩ൌ(3-6)|ࢇ|ሺ࢛,ࢇ,࢚ሻא࢜,࢛ࢋٿ௧வ’࢚ٿۯאሻ‘࢚,ࢇ,࢜ሺٿۯאࡱ|如MMW方法一样，[ݐ,ݐୟ୶]即为u到v的传播的有效时间区间。௨,௩௨,௩图3-1是一个边上含有传播的有效时间的例子。-15- 黑龙江大学硕士学位论文在图中我们可以看到，每一条有向边上都有两个用户之间传播的有效时间区间，如v1到v5的边上显示它们之间的传播的有效时间区间为ݐ௩ଵ,௩ହൌሾ5,10ሿ，也就是说，一个动作如果想在它们之间传播，则一定是在5时刻之后才能进行传播，而当营销时间超过10这个时刻，则应该保持两人之间的固定传播概率进行动作的传播，当营销时间恰好在二人之间传播的有效时间区间内，则根据给定的营销时间来决定此时二人之间的影响概率。图3-1.带有传播的有效时间区间的社会网Fig.3-1thesocialnetworkwiththeeffectivepropagatetimeinterval3.2.2.影响力分配模型本节给出了一个有效的基于时间分配影响力的模型TIIC，利用我们在3.2.1节求得的传播的有效时间区间，根据给定的营销时间，更有效的为每个节点分配影响力。首先我们用给定的营销时间对原始的图ܩൌሺܸ,ܧሻ进行处理，在3.2.1节中我们提出，当营销时间小于用户之间传播的有效时间区间的最小值，我们认为传播几率非常小，可以忽略不计。那么，对于图G中每一条边上的两个点u和v，当给定营销时间小于ݐ时，我们就认为u->v的这条边上并不能构成传播行为，所௨,௩以，我们可以首先将所有传播的有效时间区间最小值大于给定营销事件的边删掉，这样我们就得到了一个有效的新图ܩԢൌሺܸ,ܧԢሻ，所以对于图ܩԢൌሺܸ,ܧԢሻ中的所有边-16- 第3章不同营销模式中基于时间的影响传播算法eאܧԢ，我们都可以认为是在给定的营销时间T之内可能有传播行为发生的边，那么接下来我们的模型就在图ܩԢ中进行，这样其实是将原有的图缩小了，同时可以减少运行时间，提升运行速度，具体的有效性我们将在3.4节进行验证。那么我们现在有有向图ܩԢൌሺܸ,ܧԢሻ，给定的营销时间T，一个记录用户历史动作的日志A。下面详述TIIC模型是如何进行影响力分配的。影响力分配的过程如下：在给定营销时间T内，图ܩԢ中存在有向边ݒ՜ݑ，u将某些行为动作通过边ݒ՜ݑ传播到节点v，当v收到影响执行了相同的动作，那么v就可以反过来为u分配影响力，这也同时影响了u的祖先节点的影响力，所以v同时也要为u的祖先节点分配这次传播带来的影响力。那么我们就可以直接得到，在给定的营销时间T的范围内，v的父亲节点，也就是能够直接向v进行动作传播的节点集合为ܰൌሼݑ|݁ᇱאܧԢሽ，也就是说当前节点v要向ܰ集合中的每௩௨,௩௩一个父亲节点u分配当前一轮传播带来的影响力，我们将v向u分配的影响力定义为ܫ்݊݀，并且v向所有父亲节点分配的影响力满足∑ܫ்݊݀1。被分配的௩,௨௨אேೡ௩,௨影响力ܫ்݊݀的有很多种标准化的方式，在本节中，我们根据给定的营销时间T和௩,௨行为动作日志中u和v执行及传播的动作数给出定义如下：்|ሺ࢛,ࢇ,࢚ሻٿࡱא࢜,࢛ࢋٿ࢜אሻ‘࢚,ࢇ,࢜ሺ|࢛אሺ࢚’ି࢚ሻழ்|ܫ݊݀௩,௨ൌ(3-7)ೠ其中分母ܣ௨表示节点u所有执行了的动作的总数，而分子表示在给定时间T内，v收到u影响而执行的动作的总数，对于v向父亲节点分配的影响力我们需要保证∑ܫ்݊݀1，所以我们对ܫ்݊݀进行了规范化，给出定义如下：௨אேೡ௩,௨௩,௨ூௗ்ೡ,ೠܫ݊݀௩,௨ൌ(3-8)∑ೠאಿೡூௗೡ,ೠ公式(8)给出的是v向其父亲节点分配的直接影响力，那么接下来我们定义v向其祖先节点分配的间接影响力，我们将其定义为ܫ்݊݀，形式化定义如下：௩,௪ܫ்݊݀ൌ∑ܫ்݊݀כܫ்݊݀(3-9)௩,௪௨אேೡ௩,௨௨,௪很显然的，ܫ݊݀௨,௨ൌ1。那么，对于每个图ܩԢ中的节点u，我们都要计算一个最终的综合影响力，也就是把在给定时间内u的所有子孙节点向其分配的影响力进行聚集。记为ܫ்݂݊,也就是u在给定营销时间T时间内的综合影响力.定义如下：௨-17- 黑龙江大学硕士学位论文ܫ்݂݊ൌ∑ܫ்݊݀(3-10)௨௩א௩,௨那么，对于当前具有最大影响力的种集S（ܵكܸ），根据公式（3-10），我们也可以根据给定的营销时间T,定义出种集S收到节点v分配的影响力，定义如下：ܫ்݊݀ൌ∑ܫ்݊݀כܫ்݊݀(3-11)௩,S௨אேೡ௩,௨௨,ௌ在种集S中的每个节点אݑS，那么ܫ்݊݀ൌ1，那么种集的综合影响力，我们௨,ௌ定义为ܫ்݂݊，具体定义如下：ௌܫ்݂݊ൌ∑ܫ்݊݀(3-12)ௌ௩א௩,ௌ我们利用一个例子来说明TIIC模型.假设有向图ܩൌሺܸ,ܧሻ如图3-2所示，给定营销时间T=5，图2对应的历史动作日志为：Aൌሼሺv1,a,0ሻ,ሺv2,a,1ሻ,ሺv3,a,2ሻ,ሺv4,b,2ሻ,ሺv3,b,3ሻ,ሺv1,b,5ሻ,ሺv2,c,7ሻ,ሺv4.c,6ሻ,ሺv4,d,7ሻሽ根据我们给出的TIIC模型，首先我们发现ݐൌ6ܶ,所以我们直接删除v௩ଵ,௩ସ1->v4这条边，然后我们就得到了每一条边都可以进行传播行为的图ܩԢ，根据图ܩԢ构造的邻接链表如图3-3所示，接下来我们进行分配过程的计算。v1[3,6][6,8]V2[4,8]V4[2,5][1,4]V3图3-2.带有时间区间的图结构图3-3.在T=5时对应的分配链表结构Fig.3-2thegraphwiththetimeintervalFig.3-3thestructureoflinklistwhenT=5首先我们计算v2节点的影响力，通过对动作日志的分析，v2的祖先节点v1共执行了2个动作，而由v1传播到v2的动作为1个，所以首先更新v2被分配的影响力为1/2。下面我们计算v3的综合影响力，首先我们先找到v3影的父亲节点ܰൌሼݒ向ݒ看再们我后然，3/1ൌ்݀݊ܫ，的显明很么那。ሽݒ,ݒ,ݒ分配的影௩ଷଵଶସ௩ర,௩యଷଶ响力，通过动作日志很直观的看到，ݒଶ共执行了1个动作，ݒଷ接受ݒଶ传播的动作-18- 第3章不同营销模式中基于时间的影响传播算法也只有1个，那么ܫ்݊݀ൌ1，但是由于ݒ还有祖先节点ݒ，所以还需要向祖先௩మ,௩యଷଵ节点分配间接地影响力，根据公式(3-9)，ܫ்݊݀ൌ1/3+1/3*1=2/3，其他节点也是௩భ,௩య,同样的方法进行计算。最终计算结果如图3-4所示，由此更新了在给定时间T的条件下，图结构对应邻接链表上的所有的节点分配的影响力。图3-4.经过影响力分配后的邻接链表Fig.3-4thelinklistforallottingtheinfluence3.2.3.问题定义本节在TIIC传播模型的基础上提出了基于时间的影响力最大化问题（TIM）及饥饿营销中心基于时间的种集最小化问题（HMTSM）的问题定义，并证明了两个问题均为NP-hard问题。一、基于时间的影响力最大化问题（TIM）输入：有向图ܩൌሺܸ,ܧሻ，动作日志A，种子个数k，营销时间T输出：在营销时间T内能够达到最大影响范围的种集S（|S|=k）定理3-1:基于真实时间的影响最大化问题(TIM)是NP-hard问题.证明:如果我们假设给定的营销时间T是整个图ܩ中所有边上所求传播的有效时间区间的最大时间ݐୟ୶，那么我们提出的TIIC模型也就等价于CD影响力传播௩,୳[11]模型，那么CD传播模型解决的影响力传播问题就是TIM问题的一个子问题，即当时间趋向于无穷大时，求解影响力最大化问题，CD模型解决影响力最大化问-19- 黑龙江大学硕士学位论文题已经被证明为NP-hard问题，所以TIM问题也是NP-hard问题。□二、饥饿营销中基于时间的种集最小化问题(HMTSM)输入：有向图ܩൌሺܸ,ܧሻ，动作日志A，期望影响范围Q，营销时间T输出：在营销时间T内能够达到影响范围Q的最小种集S（|S|>0）定理3-2:饥饿营销中基于时间的种集最小化问题(HMTSM)是NP-hard问题.证明:这里使用反证法进行证明，首先我们假设HMTSM问题不是NP-hard问题，那么根据NP-hard问题的定义，HMTSM问题一定存在一个在多项式时间内可以解决的算法，在这里我们定义为算法A，此时我们设HMTSM问题中的期望影响范围取值是从最大影响范围到最小进行变化，那么我们不难发现，对于HMTSM问题的每一组实例，运行算法A我们都能得到一个大小为k的种集S，那么显然的，S也是在TIM问题中，给定种集大小为k时的最优解。也就是说，TIM的求解也是在多项式时间内可以完成的，但是在定理1中我们证明了TIM问题为NP-hard问题，不存在一个在多项式时间内可以完成的算法能够对TIM问题进行求解，所以，假设是错误的，HMTSM也不存在一个多项式算法，所以HMTSM问题是NP-hard问题。□3.3.基于真实时间的T-INF和HM-INF算法本节给出了两个有效算法T-INF和HM-INF分别来求解基于时间的影响力最大化问题（TIM）和饥饿营销模式中的种集最小化问题（HMTSM）首先我们详述两个算法的核心过程及结构，给出有向图ܩൌሺܸ,ܧሻ，动作日志A，在解决TIM和HMTSM问题时，我们首先要输入一个营销时间T（T的单位为单位时间，以0时刻为基准），T根据具体的应用场景来确定具体单位。接下来我们利用TIIC模型对图ܩൌሺܸ,ܧሻ进行处理，根据输入的时间T和ݐ୧୬对比然后从௩,୳图ܩൌሺܸ,ܧሻ将传播的有效时间区间最小值大于T的边从图ܩൌሺܸ,ܧሻ中删除得到图ܩԢൌሺܸ,ܧԢሻ，此时图ܩ的规模被缩小，可以减少运行时间成本。之后我们根据图ܩԢൌሺܸ,ܧԢሻ建立邻接链表ܫ݊݀݁_݈݅ݏݐ用来分配影响力，邻接链表利用每个节点的入度节点建立，即每个节点的链表中存储该节点的父亲节点。对-20- 第3章不同营销模式中基于时间的影响传播算法于邻接链表中的每个节点利用TIIC模型进行影响力的分配，建立优先级队列ݍݑ݁ݑ݁，并将每个节点的影响力增益加入优先级队列，最后我们采用CELF优化来进行每一轮的种子节点选择，并在每一次选择后更新其他节点相对于当前种集的影响力增益。下面给出T-INF算法的伪代码，算法描述如算法3-1所示。算法3-1基于时间的影响力最大化TIM算法输入：社会网ܩൌሺܸ,ܧሻ，历史动作日志A，营销时间T，正整数k输出：T时间内,具有最大影响范围的种集Sሺ|S|ൌkሻ1)Foreach(u,v)אܧ2)计算用户的有效传播时间区间[ݐ,ݐ௫];௨,௩௨,௩3)If(ݐ>T)௨,௩4)删除边(u,v);5)最后得到的图记为ܩᇱൌሺܸ,ܧᇱሻ;6ሻሺInde_list,queueሻൌparentslinkሺG’,Aሻ;7)ܵ;8)While(|ܵ|10时，运行时间已经超过了1000s，图中并没有给出。CELF优化算法是对部分图结构使用蒙特卡洛模拟方法，运行时间虽然有所提升，但是综合来看也并不够好。模拟退火方法不断的生成随机数，更换种集，进行影响力的计算，而且通过了降温的迭代过程，所以运行时间也相对较高。下面我们分析IM-CD算法，IM-CD算法利用建立邻接链表来进行影响力的分配，不需要进行迭代过程，运行速度远远小于其他贪心方法，但是由于IM-CD算法为每个节点再每个动作上建立链表，导致建立的链表过于庞大，扫描链表比较耗费时间。我们的T-INF算法由于已经对图结构进行了删减，只为每个节点建立邻接链表，运行时间要好于IM-CD算法。最后我们来看图中运行最快的degree和degreediscount算法，虽然这两个算法在运行速度上达到了最优，但是启发式算法没有近似比的保证，对比图3-5，我们可以发现，他们的运行速虽然快，但是影响范围并不理想。所以本节提出的T-INF算法的效率远高于其他的对比方法。下面我们用实验来验证种子个数变化时，运行时间的变化关系。其中我们设置营销时间T=10。图3-8是用Last.fm数据获得的种子个数和运行时间成本之间的关系，图3-8在Last.fm数据集上运行时间vs种集个数k(T=10)Fig.3-8runningtimevsseedsizekinLast.fmdataset(T=10)-32- 第3章不同营销模式中基于时间的影响传播算法随着种子个数的不断增加，影响范围也不断增加，并逐渐有趋于平稳的趋势。综合观察图3-8和3-6可以看出，本节提出的T-INF算法同时获得了较好的影响范围，和适当的运行时间，在Digg上进行的实验同样证实了这一结论。证明了我们提出的T-INF算法的高效率和有效性。3.4.5.饥饿营销时间对种子个数和运行时间的影响本节实验我们验证饥饿营销模式中种集最小化问题的HM-INF算法的有效性。目前已有的算法并没有直接解决饥饿营销中种集最小化问题的，所以我们将T-INF问题其中4个比较算法进行了一些处理，与我们提出的HM-INF算法进行比较。本节比较算法分别为IM-CD、GeneralGreedy、GreedyCELF和Degree。其中我们依然设置传播概率为0.1，蒙特卡洛模拟循环次数为10000.在图3-9的实验中，我们设定期望的影响范围为100（即可影响到100人），首先我们比较不同营销时间和最小种集之间的关系，图3-9(a)是在Last.fm上的实验，图3-9(b)是在Digg数据上进行的实验，其中设置期望影响范围3000。从两个实验图中可知，HM-INF算法比其他算法获得了更好的实验结果，当影响范围相同，HM-INF算法求得的种集更小，也就是说以更少的种子节点实现了问题要求。这在现实中也是愿意被看到的，商家付出了更小的成本，获得了同样的宣传效果，扩大了利润。图3-9(a)在Last.fm数据集上营销时间vs种集个数k(Q=100)Fig.3-9(a)timeTvsseedsizekinLast.fmdataset(Q=100)-33- 黑龙江大学硕士学位论文图3-9(b)在Digg数据集上营销时间vs种集个数k(Q=3000)Fig.3-9(b)timeTvsseedsizekinLast.fmdataset(Q=3000)图3-10是利用Last.fm数据，做出的营销时间和运行时间的实验图。图3-10在Last.fm数据集上运行时间vs营销时间T(Q=100)Fig.3-10timeTvsrunningtimeinLast.fmdataset(Q=100)从图中我们可以看到，在取得相同的影响范围的同时，我们提出的HM-INF算法要比传统的贪心方法快1000倍左右，在图3-10中我们发现了一个很有意思的现象，就是基于度的degree算法的运行时间较长，理论上来说，degree算法运行时-34- 第3章不同营销模式中基于时间的影响传播算法间应该非常快，但是由于该算法并不能够提供一个好的影响范围，导致了需要不断的计算来达到期望的影响范围，反而时间变得不理想了。这一节的实验证实了我们提出的HM-INF算法在解决HMTSM问题上的有效性和高效率，和其他算法的变体进行比较均获得了最好的实验结果。3.4.6.验证用有效传播时间区间删减图结构的作用在本节中，我们主要来验证我们提出的用传播的有效时间区间最小值ݐ和营௨,௩销时间T进行比较对图结构进行删减起到的作用。图3-11显示了删减图结构及未删减图结构的两种方法在不同营销时间下运行时间的变化，其中设置种集大小k=5，显然的，对图结构进行的删减对影响范围不会产生影响，但是运行时间则不同，有效的图结构越小，运行时间就越小。从实验的结果我们可以看到，我们提出的用营销时间进行比较删减图结构的方法很大程度上提高了算法的运行时间，所以，删减图结构的过程达到了理想的提高算法效率的效果。图3-11在Last.fm数据集上营销时间Tvs是否删减图(k=5)Fig.3-11timeTvscutinggraphinLast.fmdataset(T=10)3.4.7.传播有效时间区间MMW和AVSW方法的准确性本节验证我们之前提出的计算传播的有效时间区间的最大最小值法MMW和平均值标准差方法AVSW的准确性。-35- 黑龙江大学硕士学位论文我们将数据集中的数据按照1:4的比例分为测试集合训练集，用IM-CD方法和我们的算法做比较。实我们用IM-CD算法和T-INF算法在训练集中进行实验得到种子节点，然后应用在测试集数据中求真实的影响范围。图3-12给出了实验结果，其中营销时间T=10。图3-12在Last.fm测试集上影响范围vs种子个数k(T=10)Fig.3-12realspreadvsseedsizekinLast.fmtestingset(T=10)图中的实验结果证明了我们提出的两种求得传播的有效时间区间的方法都获得了更好的效果，通过对MMW和AVSW的方法进行比较我们发现，利用平均值标准差的方法准确性要好于MMW方法。这也是符合真实场景的，最大最小值方法可能很容易受到极值的影响，从而导致结果出现偏差。3.4.8.HM-INF算法联机近似比证明在问题定义中，我们证明了HM-INF算法的联机近似比为l/k，这一节中我们验证联机近似比的正确性。我们在Last.fm数据上进行的试验结果如图3-13所示（T=10）。通过图3-13的实验结果显示出,当期望的影响范围Q=100时，联机近似比l/k=2/1=2，图中所有数据中显示HM-INF算法的最大联机近似比为8/3，我们在两-36- 第3章不同营销模式中基于时间的影响传播算法个数据集上进行的多次试验也证明HM-INF算法的联机近似比最大接近于3.8这个数值，从而验证了我们证明联机近似比的正确性。Fig.3-13realspreadvsseedsizekinLast.fmdataset(T=10)图3-13在Last.fm数据集上影响范围Qvs种子个数k(T=10)3.5.本章小结在本章中，我们基于真实的营销时间和真实的用户行为日志，首先提出了MMW和AVSW方法求得用户和用户之间传播的有效时间区间，通过有效传播时间区间提出了TIIC模型进行影响力的分配。基于TIIC模型我们提出了基于时间的影响力最大化问题和饥饿营销方式中的种集最小化问题，并证明了TIM和HMTSM问题都为NP-hard问题。之后我们又提出了能够有效解决TIM和HMTSM问题的T-INF和HM-INF算法，接下来在两个真实社会网络数据集上的实验证实了我们提出的T-INF和HM-INF算法的有效性和高效率。-37- 黑龙江大学硕士学位论文第4章基于真实时间的影响概率优化算法4.1.引言在上一章中，我们利用历史行为日志数据确定了用户的传播力作为两个用户边上的概率，然后利用我们提出的TIIC模型进行影响力的分配和传播，在这一章中，我们会对影响概率进行优化，加入更多影响传播项来进行更精确的影响力求解。在生活情境中我们不难发现，两个用户之间的传播概率是受到很多因素的影响的。直观的，第一，用户在某段时间的活跃程度，活跃程度直接影响了用户可以影响到多少好友，如果一个用户在这段时间没有过登陆行为或者其他发帖等活跃行为，那么他影响其他用户的可能性也相应减小；第二，用户的共同好友个数（socialtie），一个用户的好友个数直接体现了他的影响力，而用户和用户之间的相互影响则可以用共同好友个数来表示，用户的共同好友越多，证明社会联系越紧密，则发生影响传播行为的可能性越大；第三，用户在某段时间的传播时间多少，即第三章中提出的个人传播力，主要靠行为动作来衡量，即一段时间传播给指定用户的动作数有多少，不难发现这些都是可以影响用户彼此之间的影响概率的因素。从社会学的意义来说，微博、facebook等社交网站这样定义一个人的影响力，即个人影响力=活跃度+覆盖度+传播能力，这是根据一个个体的影响力来说的，基于这个设定，我们可以看到，这三个因素可以在不同程度上对个人影响力造成影响。针对这三个因素，我们根据社会学定义，制定了传播概率公式，即传播概率=用户活跃度+传播力+社会联系，在设定公式中，显然用户活跃度、传播力、社会联系这三个影响传播项都会受到时间因素的影响，这一章里我们根据这一公式，将用户活跃度、传播力、社会联系三个影响传播项进行形式化表示，并对每一个输入的营销时间T，对三个影响传播项进行参数的学习，利用当前营销时间下最合适的参数进行综合影响概率的求解，最终利用综合影响概率，通过第三章提出的TIIC模型进行影响力的分配和求解。在我们第三章提出的模型和算法中，我们设定的边上概率是单一的用户的传播力，在这一章里，我们通过真实的历史行为日-38- 第4章.基于真实时间的影响概率优化算法志对着三个因素进行参数学习，更新更准确地影响概率，在真实动作日志上的实验结果证明加入了我们的优化概率算法，得到了更接近于真实影响的的影响范围，并验证了我们提出的影响传播项的有效性。4.2.影响传播项的形式化定义本章着重介绍三个影响力传播项—用户活跃度、传播力、社会联系的形式化表示，以及用在给定不同营销时间时，进行传播项参数的学习，最终对综合影响力进行分配求解。4.2.1.影响传播项的形式化表示本节中我们首先给出三个影响传播项—个人活跃度、传播力、社会联系的形式化表示方式。1、个人活跃度我们利用用户的行为日志数据来进行个人活跃度的定义，明显的，当我们输入一个营销时间T，那么用户在T时间内执行的动作就能很清晰的表示这一点，我们将用户u的活跃度௧形式化定义如下：௨௧|ሺ࢛,ࢇ,࢚ሻٿࡱא࢜,࢛ࢋ|࢛א࢚ழ்|௨ൌ（4-1）ೠ其中，ܣ௨值得是用户u的所有的行为动作个数，分子表示的则是在给定营销时间T之前，用户u执行的行为动作个数，且u->v有边。之后我们来定义两个用户之间的形式化活跃度，我们这么考虑这个问题，当用户u和v都处于活跃状态时（也就是௧和௧都比较大时），那么u,v应该很容易௨௩发生传播行为。如果u和v中只有一个人比较活跃，那么影响概率应该相应降低；如果u,v都不是活跃用户，那么影响概率应该很小，传播行为很难发生，因此我们将用户之间相互的活跃度定义如下：ೠೌכೡೌ௧ൌ（4-2）௨,௩ೌ௩ሺ|௫אሻ其中分子为u的活跃度和v活跃度的乘积，可以很好的表示我们形容的活跃度-39- 黑龙江大学硕士学位论文关系，为了标准化用户的活跃度，我们用所有图中节点的平均活跃度作为分母，保证௧൏1。௨,௩2、用户传播力用户传播力的表现形式比较简单，是利用第三章的公式（7）来进行求解的，主要是利用用户u,v之间的相同动作个数来进行一条有向边上的影响概率的求解，若u->v有边，则用户传播力形式化定义如下：|ሺ࢛,ࢇ,࢚ሻٿࡱא࢜,࢛ࢋٿ࢜אሻ‘࢚,ࢇ,࢜ሺ|࢛אሺ࢚’ି࢚ሻழ்|௨,௩ൌ（4-3）ೠ其中分子表示在给定营销时间T内，从u传播到v的动作个数。很明显的，௨,௩൏1。3、社会联系（socialtie）我们利用同一条有向边上的两个用户的共同好友个数来定义他们的社会联系，直观的，当两个用户之间的共同好友越多，说明他们的社会联系越强，他们执行同一动作即受到影响的几率就越大，社会联系也叫socialtie，形式化定义如下：௩|௫|ೠ,א,ೡתாאா|௨,௩ൌ|݁௨,௩תܧאt=T（4-4）|௫|ೠ,אாೡ,אா|其中分子为u和v的共同好友的个数，分母为u,v的所有好友的个数，௩൏1。௨,௩4.2.2.综合影响概率形式化定义上一节我们形式化定义了三个影响传播项，那么当我们输入一个给定的营销时间T，对于u->v来说，影响概率应符合传播项元组(௧,,௩)，那么综合的௨,௩௨,௩௨,௩影响概率应定义如下：௧ൌߙכߙ+,כߙ௧כ௩（4-5）௨,௩ଵ௨,௩ଶ௨,௩ଷ௨,௩其中ߙଵߙଶߙଷ均小于1，且ߙଵߙଶߙଷൌ1。所以为了方便验证，我们定义公式（18）来表示你影响综合概率，定义如下：௧ൌߙכሻߙെߙെ1ሺ+,כߙ௧כ௩（4-6）௨,௩ଵ௨,௩ଶ௨,௩ଵଶ௨,௩我们将在后文的实验中不断调整ߙଵ和ߙଶ的取值，从而验证时间对于传播项参数的影响，通过实验中学习参数的过程求得更准确地影响概率。并验证将优化方法-40- 第4章.基于真实时间的影响概率优化算法求得的概率应用在已有算法中能够带来更好的影响范围。4.3.基于真实时间的影响概率优化算法本节给出基于时间的影响概率优化算法，包括各自影响项和综合概率的求解，以及学习影响项参数的具体算法。4.3.1.基于真实时间的影响概率求解算法TAIP在4.2.1节中我们给出了三个影响传播项—个人活跃度、传播力及社会联系的形式化定义，并给出了综合影响概率的计算方式，这一节中我们具体的给出求解基于真实时间的影响概率求解算法TAIP。下面给出TAIP算法的伪代码，描述如算法4-1所示：算法4-1基于真实时间的影响概率求解算法TAIP输入：社会网ܩൌሺܸ,ܧሻ，历史动作日志A，营销时间T输出：在营销时间为T时，图ܩൌሺܸ,ܧሻ中每条边ݑെݒ上的综合概率௧௨,௩1)FOReachאݑܸ2)IF(ݑሾݐݏ݈݅_݁݀݊ܫאݒሿሻೠೌכೡೌ3)compute௧ൌ௨,௩ೌ௩ሺ|௫אሻ|ሺ࢛,ࢇ,࢚ሻٿࡱא࢜,࢛ࢋٿ࢜אሻ‘࢚,ࢇ,࢜ሺ|࢛אሺ࢚’ି࢚ሻழ்|4)compute௨,௩ൌೠ௩|௫|ೠ,א,ೡתாאா|5)compute௨,௩ൌ|݁௨,௩אܧ|௫|ೠ,אாೡ,אா|6)compute௧ൌߙכሻߙെߙെ1ሺ+,כߙ௧כ௩௨,௩ଵ௨,௩ଶ௨,௩ଵଶ௨,௩7)Endif8)Endfor9)Returnall௧௨,௩首先，我们对所有图ܩൌሺܸ,ܧሻ中的分别根据公式（4-2）（4-3）（4-4）求得个人活跃度、传播力、社会联系三个传播项的结果，然后根据公式（4-6）求得每条边的综合概率，当求得了所有边在当前时间T下的综合概率，我们将优化算法应-41- 黑龙江大学硕士学位论文用在已有算法中，算法4-1给出的为应用在我们在第3章提出的T-INF算法中计算影响增益的co-influence算法中。4.3.2.学习影响项参数算法这一节我们主要给出影响传播项参数ߙଵߙଶߙଷ的学习方法，为方便验证，在算法中，我们设ߙଷൌ1െߙଵെߙଶ，在实验中，我们固定ߙଵ的值，不断改变ߙଶ的值来验证时间对参数的影响关系，然后固定ߙଶ，同理调整ߙଵ，其中我们每次都将参数按加0.1的标准进行调节。下面给出参数学习算法的伪代码，描述如算法4-2所示。首先我们将动作日志以4:1的比例分为训练集和测试集，本算法在训练集上完成，首先我们在测试集中通过分析日志，找到影响力最大的k个节点作为种集，在真实日志中我们很容易统计出当前种集S的影响范围，设为Rel_mg，当我们不断调整参数值，得到图中每条边ݑെݒ上的概率௧，利用新的综合概率，利用第三௨,௩章提出的co-influence函数求得预测影响范围，设为Pro_mg，显然的，预测值与真实值越接近，说明参数越接近于最佳的值，我们不断的求Pro_mg和Rel_mg的差值，当差值不断收敛并逐渐平稳到最小时，输出当前参数ߙଵ，ߙଶ，也就是说，在当前营销时间T时，最佳的参数为当前求得的ߙଵ，ߙଶ，之后实验中我们会在测试集进行这部分有效性的测试。未来我们会采用em算法对参数进行更准确地估计，以求得当前营销时间T下更准确地参数值，并更准确地预估影响范围。-42- 第4章.基于真实时间的影响概率优化算法算法4-2影响传播项参数学习算法输入：社会网ܩൌሺܸ,ܧሻ，历史动作日志A，营销时间T,种集大小k输出：营销时间T时，使ܩൌሺܸ,ܧሻ中的边ݑെݒ上综合概率௧的最优参数ߙ，ߙ௨,௩ଵଶ1)ߙଵൌ0，݉݅݊_݁ݎݎൌ2)while(ߙଵ<=1)3)ߙଶൌ04)while(ߙଶ<=1)5)Foreach݁௨,௩אܧ6)compute௧ൌߙכሻߙെߙെ1ሺ+,כߙ௧כ௩௨,௩ଵ௨,௩ଶ௨,௩ଵଶ௨,௩7)S=TIM(G,A,T,k)//第三章TIM算法输出k个种子集合S8)Pro_mg=co-influence(S)//计算预测的影响范围ܲݎ_݉݃。9)扫描真实日志，计算S的真实影响范围，记为ܴ݈݁_݉݃10)If(݉݅݊_݁ݎݎ൏ܴ݈݁_݉݃െܲݎ_݉݃ሻ//当误差变小，更新最优参数11)opt_ߙଵൌߙଵ，opt_ߙଶൌߙଶ，݉݅݊_݁ݎݎൌܴ݈݁_݉݃െܲݎ_݉݃；12)endif13)ߙଶൌߙଶ0.1；14)endwhile15)ߙଵൌߙଵ0.1；16)endwhile17)Returnopt_ߙଵ，opt_ߙଶ4.4.实验结果与分析本节我们同样在第三章实验中两个社会网络的真实数据上进行了TAIP算法的实验，并应用于多种已有算法中进行比较，证明了我们提出的基于时间的概率优化求解算法TAIP得到了更好的影响范围。4.4.1.数据集及实验环境数据集由于本章提出了一个优化概率算法，除了时间对于影响传播项参数的影响，为-43- 黑龙江大学硕士学位论文了验证其有效性，我们在已有算法中加入影响传播项的因素来进行求解，所以为了方便验证比较，我们同样在第三章使用的Last.fm和Digg数据集上进行我们的实验，具体数据信息见表3-3.实验环境本文所有算法的实验都是用C语言编写的，电脑处理器为Intel(R)Core(TM)2DuoCPU、内存8GB、硬盘500GB、操作系统Windows7，编译环境MicrosoftVisualC++6.04.4.2.比较方法为了验证基于时间的概率优化算法TAIP的有效性，我们选择了我们在第三章提出的几种传播算法进行实验，从而验证我们提出的TAIP能够带来更好的实验效果。我们共选择了3种不同的算法进行比较，详述如下：(1).T-INF算法：本文第三章提出的算法，基于真实时间利用邻接链表对影响力进行分配。[44](2).IM-CD算法：利用真实动作日志,对每一个节点的每一个动作建立邻接链表进行影响力的分配，不考虑时间的因素，进行影响力的分配。[3](3).GeneralGreedy:经典的贪心算法，利用蒙特卡洛模拟迭代进行影响力的计算。选择每一轮具有最大影响力的节点加入种集。边上概率由人为设定，在我们的实验中，对比了人为设定概率和应用TAIP算法的实验结果。在本节实验中国，为了方便比较时间，我们仍然利用给定的营销时间T对图结构进行了删减。参数设置：在GeneralGreedy算法的对比实验中我们设置传播概率p=0.1，蒙特卡洛模拟的次数为10000，T-INF中都采用AVSW的方法进行传播的有效时间区间的计算。-44- 第4章.基于真实时间的影响概率优化算法4.4.3.不同时间对影响传播项的影响在这一节中我们首先验证时间对于三个影响传播项的影响，在这一章中我们提出3个影响传播项来优化边上概率，首先我们验证这三个传播项都是与时间有着密不可分的关系的，以及我们首先验证时间分别和每个影响传播项之间的关系，从而再取验证参数变化的关系，其中我们取了两对节点做了两组实验来验证，时间和传播项关系如图4-1（a）和4-1（b）所示。图4-1(a)时间对每个影响传播项的影响(第一组用户)Fig.4-1(a)Theeffectonitemsofinfluencefortime（thefirstgroupofusers）图4-1(b)时间对每个影响传播项的影响(第二组用户)Fig.4-1(b)Theeffectonitemsofinfluencefortime（thesecondgroupofusers）-45- 黑龙江大学硕士学位论文从图4-1我们可以看出，活跃度、传播力、社会联系都是随着营销时间的变化而不断变化的。而且通过这两组实验我们可以看到，活跃度并不是跟时间成正比的，这也是符合生活场景的，在一个社交网站上，我们可能在某一段时间活跃，在某一段时间不太活跃，但是基本会在一段时间之后稳定在一个值上。而社会联系，虽然随着时间的增加，共同好友个数也会不断增加，但是由于我们进行了形式化的定义，两个用户的总好友数也不断增加，所以当时间不断增加，两个人的社会联系应该呈现先增长到趋于平缓再到略有下降的过程，因为两个人之间的共同好友数会逐渐收敛于一个值，但是好友总数确实不断增加的，从实验途中我们也可以看出这样一个过程。传播力也是不断随着时间变化而变化的，它主要和不同用户的行为情况有关，所以并没有太多的趋势变化。因此我们定义的三个影响传播项-活跃度、传播力和社会联系都和时间有着密不可分的关系。验证了我们提出的公式及定义确实与营销时间有着相关性。4.4.4.营销时间对参数的影响本节主要验证，当营销时间T不同时，对具体的影响传播项参数也会产生不同的影响，我们通过算法4-2来计算不同时间T下的最优参数，形成图4-2。图4-2时间对每个影响传播项参数的影响Fig.4-2Theeffectonparameterforitemsofinfluencefortime-46- 第4章.基于真实时间的影响概率优化算法从图中我们可以看到，随着营销时间的不断变化，每个影响传播项的参数也是不断变化的，且和始终为1，首先我们来看活跃度参数，活跃度参数随着时间逐渐减小直到趋于平稳；而传播力参数却一直处于逐渐增大的趋势；社会联系的参数也有减小的趋势，这也是符合生活场景的，随着时间的推移，用户行为增多，传播力开始占据传播概率的主要决定因素位置，但是在每一个给定的营销时间T下，我们所求的得影响传播项参数都是有意义的，它帮助我们获得当前营销时间T下更准确的影响范围。4.4.5.利用优化算法后的影响范围比较这一节我们在T-INF、IM-CD和.GeneralGreedy上利用我们提出的概率优化算法进行影响范围的比较，我们在Last.fm和Digg数据集上分别利用基础的三种算法和加上优化算法后进行实验，对比影响范围的效果。采用4.3.2节的算法，我们固定ߙଵ的值，不断改变ߙଶ的值来验证时间对影响传播项的影响关系，然后固定ߙଶ，同理调整ߙଵ，其中我们每次都将参数按加0.1的标准进行调节。实验中我们设定种子数k=5，营销时间和影响范围之间的关系如图4-3所示，其中实线为加上优化概率算法的方法，虚线为原始基础算法。图4-3在T-INF、IM-CD和Generalgreedy算法上比较影响范围Fig.4-3comparethespreadofinfluenceonT-INF、IM-CD、Generalgreedy-47- 黑龙江大学硕士学位论文通过图4-3我们可以看到，加上影响概率优化算法的T-INF、IM-CD、Generalgreedy算法都获得了比之前更好的影响范围，这说明我们的算法确实在优化了概率的基础上增加了影响范围，证明了我们算法的有效性。同时我们也在第三章我们提出的HM-INF算法中利用了优化概率算法，来更好的解决饥饿营销中的种集最小化问题，实验结果如图4-4所示。通过实验我们可以看到，加入了概率优化算法的方法大部分情况都获得了更小的种集，证明我们的概率优化算法能够有效的增加影响范围，更好的解决影响力传播的相关问题。图4-4比较饥饿营销中的种集最小化问题Fig.4-4compareintheHMTSMalgorithm4.4.6.验证传播项的有效性上一节我们对比了整体的综合影响范围，这一节中我们验证我们提出的三个影响传播项的有效性。在这一节中，我们在我们提出的T-INF算法上分别用单一影响传播项和三个影响传播项来比较影响范围。实验结果如图4-5所示。-48- 第4章.基于真实时间的影响概率优化算法图4-5在T-INF算法比较单一影响传播项VS三个影响传播项Fig.4-5compareoneitemVSthreeitemsinT-INFalgorithm从实验结果我们发现，无论单独添加哪一种影响传播项都能带来更高的影响范围，实验结果都高于IM-CD算法和基础的T-INF算法，但同时添加三种影响传播项带来了最佳的影响范围，要高于单独加入一项。从而验证了我们所提出的社会学演变来的影响概率公式，影响概率=活跃度+传播力+社会联系是真实有效的，同时也证明了概率优化算法在解决这类问题上的有效性。4.4.7.参数对整体影响范围的影响这一节我们讨论影响传播项参数对影响范围的影响，在这一节的实验中，我们在T-INF算法上，设置种子数k=5，首先我们固定ߙଵ的值，不断改变ߙଶ的值来验证时间对参数的影响关系，然后固定ߙଶ，同理调整ߙଵ，其中我们每次都将参数按加0.1的标准进行调节，来观察参数对影响范围的影响，这也对于在某个营销时间下确定最合适的参数起了关键作用。图4-6是固定ߙଵ为0.2时，在不同营销时间下（分别设定为5、10、15、20、25时）不断改变ߙଶ的值影响范围的变化。-49- 黑龙江大学硕士学位论文图4-6在T-INF算法比较参数VS影响范围Fig.4-6compareparameterVSspreadofinfluenceinT-INFalgorithm实验中我们发现，当ߙଵ为0.2，ߙଶ不断增加，影响范围也不断增加，并且有增长加快的趋势，这是因为活跃度一开始可能会占有比较大的影响，但是随着时间的增加，传播力逐渐会变成最能影响影响范围的因素。图4-7是我们固定固定ߙଶ为0.2时，在不同营销时间下（分别设定为5、10、15、20、25时）不断改变ߙଵ的值影响范围的变化。其中得到了相似的结果，但是影响范围趋势随时间变化变得平缓，也证实了我们在4-5中分析的结论。图4-7在T-INF算法比较参数VS影响范围Fig.4-7compareparameterVSspreadofinfluenceinT-INFalgorithm-50- 第4章.基于真实时间的影响概率优化算法4.4.8.测试集中验证参数有效性本节我们在测试集数据中验证训练集求得的参数是否有效。我们将数据集按4:1比例分成两部分，在训练集中我们学习参数求得了在营销时间T时最佳的影响传播项参数，然后将其应用在训练集中，分别用IM-CD、T-INF、应用TAIP概率优化算法的T-INF算法求得训练集中的预测影响范围，并和真实的训练集中影响范围相比较，图4-8证实了我们TAIP算法求得的最佳参数得到的概率，在T-INF算法中获得了不错的影响范围，证实了参数的有效性，并证明了我们提出的TAIP概率优化算法的有效性。。图4-8在T-INF算法比较真实影响范围Fig.4-8comparerealspreadofinfluenceinT-INFalgorithm4.5.本章小结本章提出了一种影响概率优化算法，综合考虑了活跃度、传播力和社会联系三方面的因素，优化了图结构边上的影响概率，使得影响概率更加精准，该方法可以有效的增加影响范围，解决影响传播问题，在真实社会网络中的实验也证明了我们提出的基于真实时间的影响概率优化算法得到了更好的实验结果，并优于其他的不应用概率优化算法的同类型方法。-51- 黑龙江大学硕士学位论文结论社会网络中的影响力传播问题是当前数据挖掘领域重要的研究课题之一，社会网络是一个复杂的图结构，用户和用户之间也存在着这各种各样的关系影响，因此，如何找到社会网络中最具有影响力的一部分人来达到商家不同时间不同情况不用需求下的要求是非常重要的，本文首先针对于近年来市场上新兴的一些营销手段做了概述，并将时间因素加入到影响传播问题中进行求解，提出了不同营销模式下基于时间的影响传播问题。之后在此基础上又提出了一个可以改善边上概率的基于时间的影响传播概率优化算法。具体来讲，本文主要研究内容概括如下：1、通过对近年来市场营销的各种营销方式的了解，在考虑影响力传播的过程中，我们认识到时间因素对于选取初始用户的重要性，同时影响传播问题也应该更好的适应各种影响传播问题。本文根据普通营销方式和饥饿营销的方式提出了基于时间的影响最大化问题和饥饿营销中的种集最小化问题，主要是在其中考虑到了时间因素，并且优化了链表结构，运行时间更快，影响范围更大，并更接近于真实的影响结果，同时我们也证明了我们提出算法的近似比和复杂度。在真实的社会网络数据集上进行的实验也证明了我们提出的方法的有效性和高效率。2、考虑到社会学的影响力公式，演变出影响概率公式，即影响概率=活跃度+传播力+社会联系，更精准的求得了两个用户边上的影响概率，并应用在传统方法和我们提出的两个算法中，在真实社会网络中进行的实验也反映出了我们提出的三个影响传播项都具有有效性，能够更有效的解决影响传播问题。社会网络上的影响传播问题其实涉及到很多问题，其中包括社会学意义上的、技术上的、心理因素、社交关系上的等等，由于市场营销方式不断变化，大家对于商品或创意接受能力的不同，影响传播问题仍然是一个很难得到完全解决及应用的问题。尽管现有研究已经较为深入，但是仍然有很多问题有待解决，之后的研究方向如下：1、虽然我们提出了影响概率优化算法，但是我们主要是在其中考虑影响范围-52- 黑龙江大学硕士学位论文是否收到了这几个传播项的影响，并没有非常准确地对参数进行学习，对于一个营销时间，应该有更快的找到传播项参数的方式以优化概率。2、在影响传播的过程中，考虑竞争关系的存在，不同商家可能同时或非同时投放同类型产品，这时对于用户的接受能力存在冲击，可以考虑这种冲击的存在，然后选择最适合的初始用户，这也是之后可以研究的方向之一。3.我们一直致力于寻找最具有影响力的种子节点，但是在现实生活中，这类最具有影响力的人通常是一些名人明星，虽然影响力大，但是接触成本过高，之后可以考虑找到次优的用户，也就是可以影响这些最有影响力节点的节点，同时营销成本可以降低。-53- 黑龙江大学硕士学位论文参考文献[1]P.DomingosandM.Richardson.Miningthenetworkvalueofcustomers.InProceedingsofthe7thACMSIGKDDConferenceonKnowledgeDiscoveryandDataMining,pages57–66,2001.[2]D.Kempe,J.M.Kleinberg,andÉ.Tardos.Maximizingthespreadofinfluencethroughasocialnetwork.InProceedingsofthe9thACMSIGKDDConferenceonKnowledgeDiscoveryandDataMining,pages137–146,2003.[3]Kempe,D.,Kleinberg,J.M.,Tardos,′E.:InfluentialNodesinaDiffusionModelforSocialNetworks.In:Caires,L.,Italiano,G.F.,Monteiro,L.,Palamidessi,C.,Yung,M.(eds.)ICALP2005.LNCS,vol.3580,pp.1127–1138.Springer,Heidelberg,2005.[4]M.KimuraandK.Saito.Tractablemodelsforinformationdiffusioninsocialnetworks.InthProceedingsofthe10EuropeanConferenceonPrinciplesandPracticeofKnowledgeDiscoveryinDatabases,pages259–271,2006.[5]W.Chen,Y.Wang,andS.Yang.Efficientinfluencemaximizationinsocialnetworks.InthProceedingsofthe15ACMSIGKDDConferenceonKnowledgeDiscoveryandDataMining,2009.[6]W.Chen,C.Wang,andY.Wang.Scalableinfluencemaximizationforprevalentviralmarketinginlargescalesocialnetworks.InProceedingsofthe16thACMSIGKDDConferenceonKnowledgeDiscoveryandDataMining,2010.[7]Y.Shen,T.N.Dinh,H.Zhang,andM.T.Thai.Interest-MatchingInformationPropagationinMultipleOnlineSocialNetworks.Proceedingsofthe21stACMInternationalConferenceonInformationandKnowledgeManagement(CIKM),2012.[8]YangY,ChenE,LiuQ,etal.Onapproximationofreal-worldinfluencespread[M]//MachineLearningandKnowledgeDiscoveryinDatabases.SpringerBerlinHeidelberg,2012:548-564.[9]ChaudhuryA,BasuchowdhuriP,MajumderS.Spreadofinformationinasocialnetworkusinginfluentialnodes[M]//AdvancesinKnowledgeDiscoveryandDataMining.SpringerBerlinHeidelberg,2012:121-132.[10]ShakarianP,PauloD.LargeSocialNetworksCanBeTargetedforViralMarketingwithSmallSeedSets[C].//AdvancesinSocialNetworksAnalysisandMining(ASONAM),2012IEEE/ACMInternationalConferenceon.IEEE,2012:1-8.[11]GuilleA,HacidH,FavreC,etal.InformationDiffusioninOnlineSocialNetworks:ASurvey[J].ACMSIGMODRecord,2013,42(2):17-28.-54- 参考文献[12]FarahatA.Howeffectiveistargetedadvertising?[C].//AmericanControlConference(ACC),2013.IEEE,2013:6014-6021.[13]K.Saito,R.Nakano,andM.Kimura.Predictionofinformationdiffusionprobabilitiesforindependentcascademodel.InProceedingsofthe12thInternationalConferenceonKnowledge-BasedIntelligentInformationandEngineeringSystems(KES’08)[14]TangJ,SunJ,WangC,etal.Socialinfluenceanalysisinlarge-scalenetworks[J].InuhuProceedingsofthe15thACMSIGKDDConferenceonKnowledgeDiscoveryandDataMining,2009.[15]A.Goyal,F.Bonchi,andL.V.S.Lakshmanan.Learninginfluenceprobabilitiesinsocialnetworks.InWSDM2010,pages241–250.[16]KhrabrovA,CybenkoG.DiscoveringInfluenceinCommunicationNetworksUsingDynamicGraphAnalysis[C].//SocialComputing(SocialCom),2010IEEESecondInternationalConferenceon.IEEE,2010:288-294.[17]DuBoisT,GolbeckJ,SrinivasanA.PredictingTrustandDistrustinSocialNetworks.[J].Privacy,Security,RiskandTrust(PASSAT)and2011IEEEThirdInernationalConferenceonSocialComputing(SocialCom),2011IEEEThirdInternationalConferenceon,2011:418-424.[18]JavierOrtegaF,TroyanoJA,CruzFL,etal.Propagationoftrustanddistrustforthedetectionoftrollsinasocialnetwork[J].ComputerNetworks,2012,56(12):2884–2895.[19]KimM,LeskovecJ.TheNetworkCompletionProblem:InferringMissingNodesandEdgesinNetworks.[J].SDM,2011.[20]P.DomingosandM.Richardson.Miningthenetworkvalueofcustomers.InProceedingsofthe7thACMSIGKDDConferenceonKnowledgeDiscoveryandDataMining,pages57–66,2001.[21]M.RichardsonandP.Domingos.Miningknowledge-sharingsitesforviralmarketing.InProceedingsofthe8thACMSIGKDDConferenceonKnowledgeDiscoveryandDataMining,pages61–70,2002.[22]D.Kempe,J.M.Kleinberg,andÉ.Tardos.Maximizingthespreadofinfluencethroughasocialnetwork.InProceedingsofthe9thACMSIGKDDConferenceonKnowledgeDiscoveryandDataMining,pages137–146,2003.[23]Kempe,D.,Kleinberg,J.M.,Tardos,′E.:InfluentialNodesinaDiffusionModelforSocialNetworks.In:Caires,L.,Italiano,G.F.,Monteiro,L.,Palamidessi,C.,Yung,M.(eds.)ICALP2005.LNCS,vol.3580,pp.1127–1138.Springer,Heidelberg(2005).[24]M.KimuraandK.Saito.Tractablemodelsforinformationdiffusioninsocialnetworks.InthProceedingsofthe10EuropeanConferenceonPrinciplesandPracticeofKnowledge-55- 黑龙江大学硕士学位论文DiscoveryinDatabases,pages259–271,2006.[25]M.Kimura,K.Saito,andR.Nakano.Extractinginfluentialnodesforinformationdiffusiononsocialnetwork.InAAAI,pages1371-1376,2007.[26]NemhauserGL,WolseyLA,FisherML.Ananalysisofapproximationsformaximizingsubmodularsetfunctions—I[J].MathematicalProgramming,1978,14(1):265-294.[27]MaH,YangH,LyuMR,etal.Miningsocialnetworksusingheatdiffusionprocessesformarketingcandidatesselection[C]//Proceedingsofthe17thACMconferenceonInformationandknowledgemanagement.ACM,2008:233-242.[28]R.NarayanamandY.Narahari,“Ashapleyvaluebasedapproachtodiscoverinfluentialnodesinsocialnetworks,”IEEETrans.onAutomationScienceandEngineering,2010.[29]LuZ,WenY,CaoG.Informationdiffusioninmobilesocialnetworks:Thespeedperspective[C].//INFOCOM,2014ProceedingsIEEE.IEEE,2014:1932-1940.[30]AggarwalC,KhanA,YanX.Oninfluentialnodediscoveryindynamicsocialnetworks[J].SDM’11,2011:522-533.[31]AgrawalD,BudakC,AbbadiAE.InformationDiffusionInSocialNetworks:ObservingandInfluencingSocietalInterests[J].ProceedingsoftheVLDBEndowment,2011.[32]YangDN,LeeWC,ChiaNH,etal.Onbundleconfigurationforviralmarketinginsocialnetworks[C]//Proceedingsofthe21stACMinternationalconferenceonInformationandknowledgemanagement.ACM,2012:2234-2238.[33]SunY,HanJ,AggarwalCC,etal.Whenwillithappen?relationshippredictioninheterogeneousinformationnetworks[C]//ProceedingsofthefifthACMinternationalconferenceonWebsearchanddatamining.ACM,2012:663-672.[34]HsuT,ChiangM,PengW.Inferringsocialrelationshipsacrosssocialnetworksforviralmarketing[J].TechnologiesandApplicationsofArtificialIntelligence(TAAI),2012Conferenceon,2012:143-150.[35]Gomez-RodriguezM,LeskovecJ,KrauseA.InferringNetworksofDiffusionandInfluence[J].ACMTRANSACTIONSONKNOWLEDGEDISCOVERYFROMDATA,2012,5(4):1019-1028.[36]ZhengX,XZ,ZhengX,etal.Socialinfluenceandspreaddynamicsinsocialnetworks[J].FrontiersofComputerScience,2012,30(5):611-620.[37]W.Chen,Y.Yuan,andL.Zhang.Scalableinfluencemaximizationinsocialnetworksunderthelinearthresholdmodel.InProceedingsofthe10thIEEEInternationalConferenceonDataMining,2010.[38]Y.Wang,G.Cong,G.Song,andK.Xie.Community-basedgreedyalgorithmformining-56- 参考文献top-kinfluentialnodesinmobilesocialnetworks.InProceedingsofthe16thACMSIGKDDConferenceonKnowledgeDiscoveryandDataMining,2010.[39]A.Goyal,F.Bonchi,andL.V.S.Lakshmanan.Learninginfluenceprobabilitiesinsocialnetworks.InWSDM,2010.[40]Q.Jiang,G.Song,G.Cong,Y.Wang,W.Si,andK.Xie,“Simulatedannealingbasedinfluencemaximizationinsocialnetworks,”inAAAI,2011.[41]A.Goyal,F.Bonchi,andL.V.S.Lakshmanan,“Adata-basedapproachtosocialinfluencemaximization,”inVLDB,2012.[42]HuiLi,SouravSBhowmick,AixinSun“CINEMA:Conformity-AwareGreedyAlgorithmforInfluenceMaximizationinOnlineSocialNetworks”inEDBT,2013[43]JieTang.SenWu.JimengSun,“Confluence:ConformityInfluenceinLargeSocialNetworks”inKDD,2013[44]GuoliangLi,ShuoChen,JianhuaFeng,Kian-leeTan,Wen-SyanLiEfficient“Location-AwareInfluenceMaximization”inSIGMOD,2014[45]ShanshanFeng,XuefengChen,GaoCong,“InfluenceMaximizationwithNoveltyDecayinSocialNetworks”inAAAI,2014[46]CigdemAslay,NicolaBarbier,FrancescoBonchi,RicardoBaeza-Yates“OnlineTopic-awareInfluenceMaximizationQueries”inEDBT,2014[47]KaiyuFeng,GaoCongSourav,S.BhowmickShuaiMa“InSearchofInfluentialEventOrganizersinOnlineSocialNetworks”inSIGOMD,2014[48]夏涛,陈云芳,张伟等.社会网络中的影响力综述[J].计算机应用,2014,34(4):980-985.DOI:10.11772/j.issn.1001-9081.2014.04.0980.[49]W.Chen,Y.Wang,andS.Yang.Efficientinfluencemaximizationinsocialnetworks.InKDD2009,pages199–208.[50]W.Chenetal.Scalableinfluencemaximizationinsocialnetworksunderthelinearthresholdmodel.InICDM2010,pages88–97.[51]W.Chen,C.Wang,andY.Wang.Scalableinfluencemaximizationforprevalentviralmarketinginlarge-scalesocialnetworks.InKDD2010,pages1029–1038.[52]CaoT,WuX,WangS,etal.OASNET:anoptimalallocationapproachtoinfluencemaximizationinmodularsocialnetworks[C]//Proceedingsofthe2010ACMSymposiumonAppliedComputing.ACM,2010:1088-1094.[53]PathakN,BanerjeeA,SrivastavaJ.AGeneralizedLinearThresholdModelforMultipleCascades.[J].DataMining(ICDM),2010IEEE10thInternationalConferenceon,2010:965-970.-57- 黑龙江大学硕士学位论文[54]RaghavanUN,AlbertR,KumaraS.Nearlineartimealgorithmtodetectcommunitystructuresinlarge-scalenetworks.[J].PhysicalReviewE,2007,76(3).[55]WangY,CongG,SongG,etal.Community-basedgreedyalgorithmforminingtop-kinfluentialnodesinmobilesocialnetworks[C]//Proceedingsofthe16thACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining.ACM,2010:1039-1048.[56]ChawlaNV,YangY,PanditS.MaximizingInformationSpreadthroughInfluenceStructuresinSocialNetworks[C].//DataMiningWorkshops,IEEEInternationalConferenceon.IEEE,2012:258-265.[57]J.Leskovec,A.Krause,C.Guestrin,C.Faloutsos,J.VanBriesen,andN.S.Glance.Cost-effectiveoutbreakdetectioninnetworks.InProceedingsofthe13thACMSIGKDDConferenceonKnowledgeDiscoveryandDataMining,pages420–429,2007.[58]GoyalA,LuW,LakshmananLVS.CELF++:Optimizingthegreedyalgorithmforinfluencemaximizationinsocialnetworks[J].InProceedingsofthe19thInternationalWorldWideWebConference,2011.[59]GoyalA,LuW,LakshmananLVS.SIMPATH:AnEfficientAlgorithmforInfluenceMaximizationundertheLinearThresholdModel.[J].DataMining,IEEEInternationalConferenceon,2011:211-220.[60]BarbieriN,BonchiF,MancoG.Topic-AwareSocialInfluencePropagationModels[C].//DataMining(ICDM),2012IEEE12thInternationalConferenceon.IEEE,2012:81-90.[61]NguyenH,ZhengR.Influencespreadinlarge-scalesocialnetworks–Abeliefpropagationapproach[M]//MachineLearningandKnowledgeDiscoveryinDatabases.SpringerBerlinHeidelberg,2012:515-530.-58- 致谢致谢四年的本科生活，两年的研究生生活即将结束，在黑龙江大学的六年里，在学习专业知识的同时留下了非常美好的回忆，在毕业论文即将截稿之际，我要在这里感谢培养了我这么多年的黑龙江大学，也更好感谢这么多年来教我知识的老师、给我帮助的同学们。首先我要感谢我的导师—刘勇老师，刘勇老师在我读研期间无论是在学习、科研还是生活都给予了极大的关心和帮助，老师兢兢业业的工作态度，严谨的教学、科研态度都在我对我整个研究生期间甚至整个人生产生了影响，老师平和宽容的心态也是我们不断学习和努力的方向，在整个研究生的学习生活中，老师在我的科研方向、论文选题、论文撰写发表过程中都给予了极大的帮助，非常感谢刘勇老师，非常庆幸自己在读研期间遇到刘勇老师，不仅教会了我永远严谨向上的学习态度，更是教会了我在生活中永远保持乐观向上的精神。其次，还要感谢我的同学和朋友，在学术探讨的过程中和程序的编写上对我都有很大的帮助，在329的两年时光也是我最难忘和最怀念的，收获了知识，收获了友谊，更收获了太多的回忆。再有，我要感谢黑龙江大学计算机科学技术学院对我的培养，领导和老师在我学习期间给我帮助和支持。各位老师渊博的学识和严谨的教学态度给我留下了深刻的印象。最后，还要感谢我的母校——黑龙江大学，在校六年的时间里提供了良好的学习环境，广泛的资源，舒适的生活环境，在我即将毕业之际，也对于我的母校表示深深的谢意。由于时间的仓促及自身专业水平的不足，整篇论文肯定存在尚未发现的缺点和错误。恳请阅读此篇论文的老师、同学，多予指正，不胜感激，在此致以诚挚的感谢！-59- 攻读硕士学位期间发表的学术论文及参加的科研项目攻读硕士学位期间发表的学术论文及参加的科研项目(一)攻读硕士学位期间发表的学术论文[1]刘勇;曲思桐;王楠;郭龙江.不同营销模式中基于时间的影响传播方法研究[J].计算机科学与探索.2016，10(3):338-349.-60-
