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

发布时间：2017-07-17 01:02

  本文关键词：在线社会网络中影响最大化问题的研究

  更多相关文章： 社会网络 贪心算法 影响最大化 带符号网络 信息传播

【摘要】：市场营销中,为了推广某一产品,如何利用有限的资金有效的选择若干个客户来进行产品促销,借助“病毒式营销”(viral marketing)和“口碑效应”(word-of-mouth)的方式来达到产品营销的目的,这是社会网络影响最大化问题提出的背景。随着在线社会网络和web2.0的发展,影响最大化问题再度成为社会网络领域研究的热点。Domingos和Richardson给出影响最大化问题的定义：为了推广一些产品或观念,如何有效选择k个节点作为初始传播对象,通过社会网络中信息的传播与扩散,最终达到传播范围的最大化。 扩大影响范围并降低时间复杂度是在线社会网络影响最大化问题的重要目标。Kempe和Kleinberg提出具有较好影响范围的贪心算法,并证明影响最大化问题是NP-hard。但贪心算法过程非常耗时,不能适用在大型社会网络中,而且不能保证影响范围最优。本文发现了线性阈值模型的“影响积累”特性：激活节点u尝试激活节点v失败之后,影响力buv.被“积累”下来,直到节点v被激活或者传播过程结束。基于此特性,提出了一个该模型下的影响最大化算法的框架,并在此框架基础上给出一个新的HPG算法。同时针对带符号网络的特性,给出乘法规则,将所提算法框架和HPG算法推广到带符号网络。HPG算法综合考虑网络的结构特性和传播特性,首先花费常量时间启发式选择一些最具“潜在影响力”的节点进行影响力的积累,然后动态寻找最具影响力的节点。我们在六个真实的社会网络数据集(有向/无向,有权/无权,稀疏/稠密,带符号/不带符号,在线网络/传统网络,等等)上进行实验,实验结果显示HPG算法在最终影响范围和运行时间上都获得比贪心算法更好的效果。 另外,针对最具“潜在影响力”节点的选择,我们设计实验去验证和分析所给“潜在影响力”计算公式PI的合理性。
【关键词】：社会网络 贪心算法 影响最大化 带符号网络 信息传播
【学位授予单位】：复旦大学
【学位级别】：硕士
【学位授予年份】：2012
【分类号】：TP301.6;F49
【目录】：

• 摘要5-6
• Abstract6-7
• 第一章 引言7-12
• 1.1 研究背景与意义7-9
• 1.2 国内外研究现状9-10
• 1.3 研究目标和内容10
• 1.4 论文组织架构10-12
• 第二章 背景知识和相关工作12-22
• 2.1 背景知识12-19
• 2.1.1 社会网络的数学表达形式12-15
• 2.1.2 两个基本传播模型15-19
• 2.1.3 次模函数(Submodiular Function)19
• 2.2 相关工作19-22
• 2.2.1 爬山贪心算法(Hill Climbing Greedy Algorithm)19-20
• 2.2.2 基于度数的节点选择策略20
• 2.2.3 共它相关算法20-22
• 第三章 新型的混合式影响最大化算法22-28
• 3.1 出发点22
• 3.2 算法框架的提出及HPG算法22-25
• 3.3 算法框架推广到带符号网络25-26
• 3.4 GREEDY算法和HPG算法的时间复杂度分析26-28
• 第四章 节点间影响力计算公式28-32
• 4.1 无权图上b_(DV)的估计公式28-29
• 4.2 带权图上b_(DV)的估计公式29
• 4.3 带符号图上b_(DV)的估计公式29-32
• 第五章 实验和评估32-40
• 5.1 实验数据集32-33
• 5.2 实验设计33-34
• 5.3 实验结果34-39
• 5.3.1 算法框架在无向网络上的效果34-35
• 5.3.2 算法框架在带权网络上的有效性35-36
• 5.3.3 算法框架在有向网络上的效果36
• 5.3.4 HPG算法在带符号网络上的效果36-37
• 5.3.5 Greedy算法和算法框架之间的比较37-38
• 5.3.6 时间复杂度比较38-39
• 5.4 实验总结39-40
• 第六章 潜在影响力计算公式说明40-45
• 6.1 实验设计40
• 6.2 实验结果40-45
• 6.2.1 直接线性组合实验41-42
• 6.2.2 归一化线性组合实验42-43
• 6.2.3 直接线性组合和归一化组合对比实验43-45
• 第七章 总结和展望45-47
• 7.1 论文总结45
• 7.2 未来工作展望45-47
• 参考文献47-50
• 附录一 硕士期间所发表的论文50-51
• 致谢51-52

【相似文献】

中国期刊全文数据库 前10条

1 华军;;让Windows 7不再自作聪明最大化窗口[J];电脑迷;2009年24期

2 书房;;打开最大化窗口的一点经验[J];电脑采购周刊;2001年33期

3 黑暗之客;;寻找最简单的最大化方式[J];电脑爱好者;2008年04期

4 熊国成;;音乐电视“康美药业”的广告效果分析[J];新闻爱好者;2011年03期

5 师晓青;;“并发用户数”限制下的数据库利用效率分析[J];图书馆学研究;2009年06期

6 易水;;外刊精粹[J];微电脑世界;2006年11期

7 杨小芹;;学校虚拟图书馆构建摭谈[J];湘潭师范学院学报(社会科学版);2008年05期

8 冰冰;;关于IE浏览器默认窗口大小的问题[J];网络与信息;2009年01期

9 杜耀桃;;通信企业动力环境集中监控系统应用价值的实现[J];科技资讯;2009年30期

10 白斌;罗军勇;刘琰;;基于搜索引擎的社会网络个体关系评估实现[J];信息工程大学学报;2009年04期

中国重要会议论文全文数据库 前10条

1 吴浩萍;;做好引进国外专家工作,实现引智效益的最大化[A];引进国外智力研究论文选编（2007年—2009年）——献给中华人民共和国60周年华诞[C];2009年

2 何应森;;法律与经济增长之间的关联问题[A];2007年全国法经济学论坛论文集[C];2007年

3 张记山;;成本控制最小化 效益追求最大化[A];河南省建筑业行业优秀论文集(2008)[C];2008年

4 陈正华;;中央与地方分权的成本收益与交易成本——法经济学的视角[A];2007年全国法经济学论坛论文集[C];2007年

5 李红珠;;如何创建人性化服务品牌[A];中国输血协会第五届输血大会论文专集（摘要篇）[C];2010年

6 林碧英;;强化内部会计控制 实现企业价值最大化[A];2003年福建省会计学会理论研讨论文专辑[C];2003年

7 陈典全;黄朝阳;;基于位置的社会网络(LBSN)研究及其产业化[A];第二届中国卫星导航学术年会电子文集[C];2011年

8 李建勇;;论侵权案件审判中原创与再创的法经济学分析[A];2007年全国法经济学论坛论文集[C];2007年

9 李莉;武邦涛;陈忠;;社会网络作为双刃剑:交易网络的摩擦、中介可能性与结构洞[A];第五届全国复杂网络学术会议论文（摘要）汇集[C];2009年

10 艾佳慧;;中国的法官最大化些什么?——实证和比较视野下的经济学分析[A];2007年全国法经济学论坛论文集[C];2007年

中国重要报纸全文数据库 前10条

1 野风集团有限公司副总裁兼首席财务官 蒋建林;企业要在财务文化上有所建树[N];经理日报;2010年

2 李侠 上海交通大学教授;我们为何尊重权威[N];上海科技报;2011年

3 张莹莹;常宝股份变更募资投向斥资7.8亿新建三项目[N];证券时报;2011年

4 ;“快速扩张考验运营水平”[N];经济视点报;2011年

5 谷欢欢　本报记者 董菁;企业家的七秒钟[N];中国企业报;2010年

6 刘厚珉 王富刚;单县交警实现“四个最大化”保群众交通安全[N];菏泽日报;2007年

7 王雅楠;明智管理让城市化好处最大[N];中国建设报;2010年

8 高三学生 王彦龙;“地球一小时”与母亲的365天[N];新华每日电讯;2011年

9 东兴证券 孙继青;钢铁主业将进入盈利周期 业绩弹性或将最大化[N];通信信息报;2009年

10 记者 陈化宇;安瑞电力——规范化运作创效益最大化[N];雅安日报;2008年

中国博士学位论文全文数据库 前10条

1 王洋;社会网络视角下的危机传播机理与治理[D];哈尔滨工业大学;2011年

2 倪顺江;基于复杂网络理论的传染病动力学建模与研究[D];清华大学;2009年

3 袁晓婷;企业R&D团队内部社会网络与团队知识创造关系研究[D];华南理工大学;2010年

4 张淑娟;吴景濂与民国政治：1916～1923[D];复旦大学;2007年

5 徐峰;互联网宏观拓扑结构中社团特征演化分析及应用[D];东北大学;2009年

6 苏春艳;社会网络与职业获得[D];上海大学;2005年

7 王小明;社会资本的经济分析[D];复旦大学;2008年

8 邓学军;企业家社会网络对企业绩效的影响研究[D];暨南大学;2009年

9 丁楠;高管团队社会网络、运作过程与绩效间关系研究[D];江苏大学;2010年

10 谭婷婷;网络微内容推荐方法及支持系统研究[D];华中科技大学;2011年

中国硕士学位论文全文数据库 前10条

1 田家堂;在线社会网络中影响最大化问题的研究[D];复旦大学;2012年

2 冀进朝;社区影响最大化算法及其传播模型研究[D];吉林大学;2010年

3 章云龙;社交网络中基于话题的影响最大化问题研究[D];上海交通大学;2012年

4 艾福娇;成人后悔倾向问卷编制及其相关研究[D];江西师范大学;2010年

5 赵秀涛;Web病毒式营销中的挖掘技术研究[D];沈阳航空工业学院;2010年

6 黎雷;社会网络影响力模型及其算法研究[D];北京交通大学;2010年

7 黄平;消费类电子产品附加设计研究[D];燕山大学;2010年

8 李高吉;社会网络对集群企业绩效的影响研究[D];南华大学;2010年

9 李磊;社会网络与金融危机[D];南京大学;2011年

10 张普玮;我国慈善组织的社会服务能力最大化理财目标[D];首都经济贸易大学;2012年

，

本文编号：551258