在线社会网络中影响最大化问题的研究.pdf

《在线社会网络中影响最大化问题的研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、在线社会网络中影响最大化问题的研究指导小组成员名单汪卫教授谢志鹏副教授王轶彤副教授目录目录?5IIIABSTRACTIVm-m弓iwi1.1研宄背景与意义i1.2国内外研宄现状31.3研宄0标和内容41.4论文组织架构4第二章背景知识禾U相关工作62.i背景知识62.1.1社会网络的数学农达形式....62.12两个基本传播模型..92.1.3次模齒数(SubmodularFunction).132.2相关工作132.2.1爬山食心算法(HillClimbingGreedyAlgorithm)..132.22基J—度数的ji点选择策略.142

2、23U它相关算/'之.14第二章fir型的捉公式影响最大化算法163.1出发点163.2算法框架的提出及HP(,铃法1633算法枇架徘）到诏符]M汸193.1Gritd%}dAWilPG兑法的时间复杂度分析20弟四f"节点丨‘丨似响力计算公式221.1I:权阁1h,的沾i

3、公式224.2带权图1的佔汁公式2313L仏的估il公八23第/i令实验和1；

4、'佔265.1文验数据集265.2实验idhl275.3实验结果285.3.1算法框架在无向M热h的效果...285.3.2算d柄架A带权M络丄的有效性.295.3.3縣Hi架在冇向M络上的效

5、果3053.4HPG算法在带符号网络上的效果..305.3.501(^(1算法和算法柩架之间的比较...315.3.6时_复杂度比$父...J25.4实验总结33目录第六章潜在影响力计算公式说明346.1实验设计346.2实验结果346.2.1直接线性组合实验........356.2.3直接线性组合和归一化组合对比实验.................37第七章总结和展望397.1论文总结397.2未来工作展望3941附录一硕士期间所发表的论文44纖45论文独创性声明46论文使用授权声明46II复旦大学硕士学位论文在线社会网络中

6、影响最大化问题的研究摘要市场营销中，为了推广某一产品，如何利用有限的资金有效的选择若干个客户来进行产品促销，借助“病毒式营销”（viralmarketing)和“口碑效应”(word-of-mouth)的方式来达到产品营销的目的，这是社会网络影响最大化问题提出的背景。随着在线社会网络和web2.0的发展，影响最大化问题再度成为社会网络领域研究的热点。Domingos和Richardson给出影响最大化问题的定义：为了推广一些产品或观念，如何有效选择k个节点作为初始传播对象，通过社会网络中信息的传播与扩散，最终达到传播范围的最大化。扩大影响范围并降低时间复杂度是在线社会网络影响最大化问题的

7、重要目标。Kempe和Kleinberg提出具有较好影响范围的贪心算法，并证明影响最大化问题是NP-hard。但贪心算法过程非常耗时，不能适用在大型社会网络中，而且不能保证影响范围最优。本文发现了线性阈值模型的“影响积累”特性：激活节点u尝试激活节点v失败之后，影响力dm.被“积累”下来，直到节点v被激活或者传播过程结束。基于此特性，提出了一个该模型下的影响最大化算法的框架，并在此框架基础上给出一个新的HPG算法。同时针对带符号网络的特性，给出乘法规则，将所提算法框架和HPG算法推广到带符号网络。HPG算法综合考虑网络的结构特性和传播特性，首先花费常量时间启发式选择一些最具“潜在影响力”

8、的节点进行影响力的积累，然后动态寻找最具影响力的节点。我们在六个真实的社会网络数据集（有向/无向，有权/无权，稀疏/稠密，带符号带符号，在线网络/传统网络，等等）上进行实验，实验结果显示HP(;算法在最终影响范围和运行时间上都获得比贪心算法更好的效果。另外，针对最具“潜在影响力”节点的选择，我们设计实验去验证和分析所给“潜在影响力”计算公式PI的合理性。关键字：社会网络，贪心算法，影响最大化，带符号网络，信息传播中图法分类号：TP311复旦大学硕士学位论义在线社会网络中影响最大化问题的研宂AbstractWiththedevelopmentofonlinesocialnetwork,in

9、fluencemaximizationbecomesahotspotinsocialnetworkanalysisfieldonceagain.DomingosandRichardsongavethedefinitionofinfluencemaximization：Inordertopromotesomeproductsorconcepts,howtochoosekinfluentialnodesastheinitialsprea