社交网络中节点影响力的评价与优化机制研究

摘要

因特网和Web2.0技术的飞速发展催生了在线社交网络的迅速普及，如Facebook、Twitter、新浪微博等。大规模在线社交网络已经在很多方面开始影响人们的生活方式，特别是在信息的扩散和传播方面，吸引众多学者对其进行研究。本文对社交网络进行了两方面的研究:节点影响力的评价研究和节点影响最大化研究。
　　以微博网络为代表的新型在线社交网络中存在高影响力节点，对信息在网络中的传播起着至关重要作用。快速高效地找出这些节点有助于研究舆情控制、研究网络个体关系，有助于使网络中信息更有效地传播。在评价节点影响力的问题中，传统的度中心性方法虽然简单但是效果不好;介数中心性具有准确的评价效果，但是计算节点的介数值需要基于网络的全局信息，计算开销大，在大规模网络中并不适用。本文在节点影响力评价问题中基于PageRank算法的投票思想，提出了精确高效的节点影响力排序算法评价网络中节点的影响力。根据在线社会网络中边关系的复杂性，本文在SIR传播模型基础上提出不同边具有不同感染概率的新型传播模型。在新浪微博真实用户关系数据集中，本文提出的新型排序算法相比介数中心性和PageRank算法具有更好的性能表现。
　　在市场营销中，利用用户之间的“口碑效应”的“病毒式营销”方案得到了众多学者的关注。如何有效选择k个节点组成种子集合使得影响范围最广是当前的热点问题，称为节点影响最大化问题。Kempe证明影响最大化是NP-hard，并提出了贪心算法，具有较好结果。对于贪心算法计算开销大，不适用于大规模社会网络的问题，混合式算法有效解决了时间开销问题。混合式算法分为启发阶段和贪心阶段，利用线性阈值模型影响力积累特性，在启发阶段利用节点邻域信息选取最具“潜力”节点，这些激活的“潜力”节点所具有的影响力能够让周围的未激活节点更容易被激活，使得最后种子集合的激活范围更广。本文提出NPG算法在启发阶段充分利用节点邻域信息，考虑节点的连接强度和出边邻居传播能力差异性，提出更有效的“潜力”节点选取策略。在贪心阶段，NPG算法通过每一轮提前对当前种子集合进行传播，得到当前的激活集合，避免对集合中的节点计算边际收益，大大减少了重复的计算量，提高了贪心阶段的效率。

目录

声明

摘要

1 绪论

1．1 相关研究背景

1．2 研究意义和社会网络研究现状

1．3 本文主要研究内容

1．4 论文结构安排

2 相关背景与理论知识

2．1节点影响力评价研究综述

2．1．1 社会网络

2．1．2 节点影响力排序相关研究

2．1．3 SIR传播模型和节点影响力

2．1．4 PageRank算法

2．2 节点影响最大化研究综述

2．2．1 研究背景

2．2．2 节点影响最大化相关研究

2．2．3 影响力传播模型

2．2．4 独立级联模型

2．2．5 线性阈值模型

2．2．6 子模函数和贪心算法

2．2．7 节点影响力排序和节点影响最大化问题的联系和区别

2．3 本章总结

3 节点影响力评价研究

3．1 微博的“关注”关系和转推功能

3．2 传播模型的改进和问题定义

3．2．1 传统SIR模型的改进

3．2．2 问题定义

3．3 PageRank算法存在的问题

3．3．1 收缩机制存在的问题

3．3．2 投票阶段存在的问题

3．4 算法设计与实现

3．4．1 收缩机制的改进

3．4．2 邻居节点差异性的改进

3．5 实验设计和实验结果

3．5．1 实验数据集

3．5．2 性能评价指标

3．5．3 实验对比结果

3．6 本章总结

4 基于二阶邻居的节点影响最大化算法

4．1 传统贪心思想

4．1．1 边际收益

4．1．2 贪心算法

4．2 混合式算法

4．2．1 节点影响力的改进

4．2．2 “潜力”节点的选取

4．3 算法设计与实现

4．3．1 “潜力”节点选择策略的改进

4．3．2 贪心阶段计算效率的改进

4．4 时间复杂度分析

4．5 实验设计与对比结果

4．5．1 实验数据集介绍

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

4．6 本章总结

5 结束语

5．1 工作总结

5．2 进一步的研究工作

参考文献

攻读硕士期间科研项目和研究成果

致谢