在线社会网络中社区发现技术及其应用研究

摘要

随着Web2.0的飞速发展，在线社会网络OSNs(Online SocialNetworks)作为其中一种实用的、新兴的交友模式已经成为人们生活和工作中不可或缺的一部分。在线社会网络中的人们通过各种关系相互联系在一起，形成了一个个内容丰富、关系复杂的社区。面对商业领域的实际应用，目前对社区的研究面临两大挑战。一是，由于在线社会网络的虚拟性和开放性，如何自动发现其中的社区成为一个亟待解决的问题。二是，社区作为一个新的营销领域，如何有效评估用户在社区中的社会影响力也成为一个备受关注的焦点问题。
　　 本论文首先介绍了基于节点属性相似性的社区发现算法（简称为NAS算法）和基于共有邻居相似性的社区发现算法（简称为CNS算法），并针对这些算法中的缺点，基于在线社会网络的独有特性，提出了用户紧密度的概念，设计了一种基于用户紧密度的社区发现算法（简称为UTCD算法）。该算法首先对所有边计算用户紧密度，然后用层次聚类算法对其进行处理，以便发现社区。最后通过模块度测试和正确率测试来验证算法的有效性。实验结果表明，本文所提出的算法比NAS算法和CNS算法发现的社区凝聚度更高，正确率更高。
　　 另外，本论文通过分析在线社会网络社区的独特结构及其中的人际互动行为，发现朋友数量和质量以及社区标签是影响用户影响力的三大主要因素。为了更有效地评估用户在社区中的社会影响力，提出了影响能力和社区标签的概念，设计了一种用户社区影响力UCI(User Community Influence)的评估模型。本论文的初始模型是基于PageRank而建立，然后通过计算得到的任意两个用户间影响能力来改进该初始模型。实验结果表明，本文提出的模型比传统的评估模型评估的用户影响力有更高的效率和更好的合理性。
　　 总之，本论文既解决了大规模在线社会网络中自动发现社区的问题，也解决了在线社会网络社区应用于营销领域评估用户影响力的问题。这些研究成果将被应用到实际中，希望能够改变在线社会网络社区“研究多、应用少”的现状。

目录

声明

摘要

第一章 绪论

1．1 研究背景及其意义

1．2 社区的分析

1．2．1 社区的结构

1．2．2 社区的特征

1．2．3 社区发现及其应用

1．3 论文研究的内容及意义

1．4 论文结构

第二章 在线社会网络社区发现与用户影响力研究

2．1 社区的理论基础

2．2 社区发现的研究

2．2．1 社区发现概述

2．2．2 常用聚类算法

2．2．3 社区发现算法

2．3 用户影响力的研究

2．3．1 用户影响力概述

2．3．2 用户影响力评估模型

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

2．4 本章小结

第三章 基于用户紧密度的社区发现算法

3．1 相关工作

3．2 算法描述

3．2．1 创建初步用户图

3．2．2 创建完整用户图

3．2．3 创建社区图

3．3 实验研究及分析

3．3．1 模块度测试

3．3．2 正确率测试

3．4 本章小结

第四章 一种用户社区影响力评估模型

4．1 相关工作

4．1．1 PageRank算法简介

4．1．2 问题定义

4．2 用户社区影响力模型

4．2．1 解决框架

4．2．2 初始评估模型

4．2．3 扩散评估模型

4．2．4 本文评估模型

4．3 模型计算

4．3．1 马尔科夫链

4．3．2 UCI马尔科夫模型的表示

4．3．3 收敛性分析

4．4 实验研究及分析

4．4．1 数据源

4．4．2 实验设计

4．4．3 实验结果

4．4 本章小结

第五章 结束语

5．1 研究工作总结

5．2 未来工作和展望

参考文献

致谢

攻读学位期间主要的研究成果