面向web的社会网络挖掘与信息传播分析关键技术研究（可编辑）.doc

面向Web的社会网络挖掘与信息传播分析关键技术研究

国防科学技术大学
博士学位论文
面向Web的社会网络挖掘与信息传播分析关键技术研究
姓名:唐晋韬
申请学位级别:博士
专业:计算机科学与技术
指导教师:王挺
2011-04
国防科学技术大学研究生院博士学位论文
摘要
时代,各种类型的社会媒体不断涌现,深刻地改变了人们工作、生活
和交流的方式。在此背景下,研究 时代的社会网络结构和信息传播规律、
理解现代社会中人们获取信息的方式成为一个迫切的任务。本文针对 社会
媒体的新特点,围绕面向互联网的社会网络挖掘和信息传播分析两个方面展开了
如下四个关键问题的研究: 1 面向社会媒体的社会网络挖掘问题, 2 时
代社会网络分析的效率问题, 3 面向社会媒体的信息流挖掘问题, 4 以及社会
媒体中社会网络结构信息传播的影响。
首先,本文研究了面向社会媒体的社会网络挖掘及重名用户消歧问题。在社
会关系挖掘方面,针对 中社会交往隐藏在网页文本和链接中的特点,本文
结合链接结构特征、文本语义特征以及 特征,综合计算社会媒体中用户显
式的在线交往行为和潜在的相似兴趣,有效地挖掘了社会媒体中用户之间的社会
关系。在行动者用户节点抽取方面,针对社会媒体中的用户重名问题,本文基于
社会关系特征构建了重名用户身份消歧算法。该算法抽取不同网页中重名用户的
社会关系组成社会网络的二部子图,并对二部图聚类从而有效地区分重名用户节
点。在此基础上,本文还构建了一个基于两阶段聚类的消歧方法,分别对社会关
系特征和文本特征建模,既利用社会关系特征区分了社会网络中的重名用户,又
结合文本特征区分了属于不同用户的述信息、文章等网页文本。
其次,针对从社会媒体中抽取的社会网络规模较大的问题,本文基于复杂网
络理论研究了优化社会网络分析性能的方法。本文统计分析了从 社会媒体
中抽取的社会网络结构特征, 社会网络是一种典型的复杂网络。根
据无标度特征和小世界特征,本文出了复杂网络中最短路径分布不均衡的假设,
认为最短路径通过少量度数较高的活跃节点的可能性更大。基于该假设,本文优
化了最短路径近似方法在社会网络中的效率及准确率,并出了一种适用于复杂
网络的 CDZ 最短路径近似算法。该算法利用通过活跃节点的一条路径近似最短路
径,在具有无标度特征的社会网络最短路径近似计算上,有着很高的近似准确性
和较低的计算复杂度。在 CDZ 最短路径近似算法的基础上,本文出了结合 CDZ
算法近似计算介数中心性、接近中心性的方法,以及优化 K-Medoids 、
Girvan-Newman 等聚类算法性能的方法,使得上述社会网络分析方法在面向
社会媒体的应用中能取得更好的性能与准确率。同时,本文利用复杂网络
特征指导聚类算法选择参数,为面向缺乏先验知识的现实世界社会网络中的社区
发现供了一种可行的方法。
然后,本文研究了在社会媒体中挖掘信息流的相关问题。针对 社会媒
第 i 页
国防科学技术大学研究生院博士学位论文
体中用户生成内容偏短、质量不高等问题,本文结合维基百科资源出了一种基
于语义图的话题表示模型。该模型使用实体、概念及其语义关联表示文本的主要
信息,能较好地解决用户生成内容较短造成的语义信息不足等问题,对语义关联
关系的建模使得该模型可以有效地过滤用户生成内容中的噪声。结合维基百科语
义关联信息的图编辑距离算法,能够度量短文本间隐含的真实语义关系,更好地
处理在社会媒体中话题演变迅速等问题。为了应对社会媒体信息流挖掘任务中的
信息过载等问题,本文出了基于社会网络的话题发现和信息流跟踪新方法。通
过将社会网络上的话题发现问题述为一个多目标优化问题进行求解,有针对性
地挖掘社会网络中最有可能参与话题传播的部分用户发布的内容,实现了以较小
的数据处理代价发现社会媒体中热点话题的目标。在此基础上,本文利用参与话
题传播用户的社会关系,出了基于社会关系在相邻节点之间跟踪/ 回溯信息流的
方法,减少了需要处理的数据量,更好地跟踪信息传播过程。而且,该方法通过
结合社会网络特征度量文章和话题相似性,增强了应对话题演变问题的能力。
在上述工作的基础上,本文研究了社会网络结构对信息传播范围的影响,分
时代信息传播的内在规律。为量化评价社区结构是否会影响信息传播,
本文基于图的相似性计算出了一种影响力度量方法。该方法通过计算由社区组
成的社会网络子图与信息传播网络的相似性,