动态复杂网络中的影响最大化算法的研究

摘要

近年来，社交网络的快速发展为广大用户提供了丰富的服务，成为结交好友，信息交流，商品推销等的重要媒介，影响最大化旨在发现社交网络中影响力大的节点集合，在社会网络分析领域占据重要位置，有着广泛的实际应用例如市场营销、广告发布等，因此具有很高的研究价值和应用价值。
　　但是，社交网络用户数量庞大，网络拓扑复杂为有影响力的用户筛选带来困难，网络规模的不断扩张和进化则让选择用户更是难上加难，所带来的亟待解决的挑战就是如何在持续变化的网络中快速准确地选取影响力大的用户。而且社交网络中信息类型丰富，用户对此有不同的偏好度，这会影响信息在网络中的传播，也会决定选取的种集是否能够在特定主题下达到最好的效果。同时，社交网站也会使用丰富的形式发送消息给用户，社交网站本身也是一个隐含的影响者，在基于主题的社交网络中如何合理使用网站本身的影响力将成为影响最大化崭新的问题。
　　针对上述影响最大化研究中的挑战和问题，本文从以下两个方面进行研究:
　　(1)针对现有静态算法不能适应社会网络的持续进化发展，网络变化需要重新计算耗时巨大的问题，本文基于影响局部化特征，提出动态影响最大化算法DIM。算法包含两个阶段:初始种集获取算法Init_Seed和增量式更新种集算法Inc_Seed。初始种集获取算法Init_Seed可以确定节点的影响路径集合以及初始种集，为下一阶段的种集更新做准备。增量式更新算法Inc_Seed可以快速确定改变的影响范围，仅为受变动影响的节点重新计算影响力，减少时间开销。为进一步提高算法的执行效率，本文提出两个剪枝策略:影响力增值剪枝策略和度剪枝策略，提出结合剪枝策略的优化算法Opt-DIM，在保证影响范围的情况下，提高种集选取过程时间效率。
　　(2)考虑用户对主题的偏好以及网站本身的影响力等因素，已有算法虽对主题感知进行了大量研究，却未考虑网站本身对影响传播的推动作用。本文将网站本身表示为外部因素，并提出推荐社交网络中基于主题的影响最大化算法TIP，结合实际因素确定用户之间以及网站对用户的影响概率，以影响路径为单元计算网站用户的影响力，根据网站本身对用户的激活情况，自适应地选择种子节点，以达到种集与网站共同的影响范围最大。并且提出两个优化策略:影响力优化策略和度排名优化策略，算法的执行效率进一步提高。

目录

摘要

第一章 绪论

1．1 研究目的和意义

1．2 影响最大化研究现状

1．3 存在的主要问题

1．4 本文主要研究内容

1．5 本文的组织安排

第2章 背景知识和相关工作

2．1 背景知识

2．1．1 经典网络模型和图存储结构

2．1．2 影响传播模型

2．1．3 影响最大化问题定义

2．2 相关工作

2．3 本章小结

第3章 动态社交网络中增量式影响最大化算法

3．1 引言

3．2 动态影响最大化DIM

3．2．1 活边模型

3．2．2 动态影响最大化问题定义

3．2．3 动态影响最大化算法DIM

3．3 初始种集获取算法Init_Seed

3．3．1 用户影响力的计算

3．3．2 路径遍历算法GetAllPath

3．3．3 Init_Seed算法

3．4 种集更新算法Inc_Seed

3．4．1 拓扑变动算法

3．4．2 种集更新算法Inc_Seed

3．5 剪枝策略以及优化算法

3．5．1 剪枝策略

3．5．2 优化算法Opt_DIM

3．6 实验结果与分析

3．6．1 实验数据和评价指标

3．6．2 实验结果与分析

3．7 本章小结

第4章 推荐社交网络中基于主题的影响最大化

4．1 引言

4．2 主题感知超级影响传播模型(TSID)

4．3 影响概率的计算

4．3．1 内部影响概率计算

4．3．2 外部影响概率计算

4．4 基于路径的主题感知影响最大化算法(TIP)

4．4．1 推荐社交网中影响最大化问题定义

4．4．2 用户偏好值的计算

4．4．3 用户影响力的计算

4．4．4 TIP算法

4．5 实验结果与分析

4．5．1 实验设置

4．5．2 实验结果与分析

4．6 本章小结

结论

参考文献

致谢

攻读硕士学位期间发表的学术论文

声明