社会网络中群组探测和话题建模技术研究

摘要

随着社交网络平台的涌现,用户之间不仅可以建立链接关系,而且还可以产生丰富的文本信息。群组探测是重要的链接挖掘技术之一,而话题建模是对社会网络中的文本进行挖掘的主要工具之一。为了将社会网络中的链接和文本进行统一分析,对群组探测和话题建模技术进行更深入的研究并且将两者进行有机的结合,具有十分重要的意义。然而,社会网络的大规模、动态变化、快速更新以及链接和文本共存等特点,给群组探测和话题建模提出了新的挑战。
　　在群组探测方面,针对基于凝聚法和模块度优化的Newman算法效率低下的问题,提出了仅通过一次扫描快速构造紧凑群组的启发式算法OBO-Group。OBO-Group避免了Newman算法在初始合并阶段的大量计算,从而提高了算法的效率。在OBO-Group的基础上,提出了针对有向加权网络的静态群组探测算法S-Group(StaticGroup)。在真实的和人工合成的网络上的实验结果表明,S-Group比Newman算法高效,同时效果与Newman算法接近。针对社会网络的动态变化性,提出了群组变化点检测算法Stream-Group。在人工合成的动态网络和安然邮件网络上的实验结果表明,Stream-Group能够有效地发现社会网络中的群组变化点。
　　针对社会网络快速更新的特点,研究了增量式K-派系(K-Clique)聚类算法。作为增量式K-派系聚类的特例,增量式2-派系聚类问题被转化为局部深度优先森林更新问题,针对该问题提出了一系列局部更新策略,这些策略在保证聚类结果精确性的前提下,尽可能缩小更新的范围,实现高效的增量式计算。然后,将增量式2-派系聚类扩展到K大于等于3的情况。在作者合作网络和安然邮件网络上的实验结果表明,增量式K-派系聚类比对应的静态算法高效,与增量式谱聚类相比,增量式K-派系聚类速度更快而且没有累积误差,与基于快照网络的聚类相比,增量式K-派系聚类能够发现社会网络中聚类的许多演化细节。
　　在话题建模方面,研究了基于排序的话题模型(RankingbasedTopicModel,RankTopic)。RankTopic通过引入文本的链接重要性来改进话题建模性能。传统的话题建模将文本看作同等重要,然而在现实社会网络中,文本的重要程度不尽相同,因此,将文本看作同等重要将不可避免地损害话题建模的性能。在论文引用网络和推特(Twitter)数据上的大量实验结果表明,RankTopic在泛化性能、文本聚类和分类效果方面都优于已有的话题模型,探测出的话题也具有更好的可解释性。
　　大多数已有的模型很少考虑群组和话题之间的相互协同效应。有些模型要么只考虑群组要么只考虑话题从而无法达到同时探测两者的目的,还有些模型则将群组和话题用相同的变量进行建模使得模型的灵活性存在明显不足。针对该问题,提出了相互促进的无穷群组话题模型(MutualEnhancedInfiniteCommunity-TopicModel,MEI),将群组和话题集成到统一的概率生成模型中,实现了对社会网络中的群组和话题的同时探测。MEI将群组和话题分开,同时又利用群组话题分布将两者关联起来,既保证了模型在群组和话题探测时的灵活性,又使得两者能够相互促进。为了自动探测群组和话题的个数,MEI中运用了狄利克雷过程(DirichletProcessMixture,DPM)和分层狄利克雷过程(HierachicalDirichletProcess,HDP)。在论文合作网络上的实验结果表明,MEI比已有的模型具有更好的泛化性能,并且能够自动探测群组和话题的个数。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景和意义

1.2 国内外研究现状

1.3 研究内容

1.4 论文的组织结构

2 基于模块度优化的动态有向加权网络群组挖掘

2.1 引言

2.2 问题定义

2.3 有向加权网络群组探测

2.4 群组变化点检测

2.5 动态网络群组挖掘算法

2.6 实验分析

2.7 本章小节

3 动态社会网络增量式K-派系聚类

3.1 引言

3.2 问题定义

3.3 增量式2-派系聚类

3.4 一般的增量式K-派系聚类

3.5 算法时间复杂度分析

3.6 实验分析

3.7 本章小节

4 基于排序的话题建模

4.1 引言

4.2 背景知识

4.3 基于排序的话题模型

4.4 实验分析

4.5 本章小结

5 相互促进的无穷群组话题模型

5.1 引言

5.2 相互促进的无穷群组话题模型

5.3 基于吉布斯抽样的模型推理和参数估计

5.4 实验分析

5.5 本章小节

6 总结与展望

6.1 论文总结

6.2 工作展望

致谢

参考文献

附录1 攻读学位期间发表的论文

附录2 攻读学位期间参与的科研项目

附录3 攻读学位期间申请的专利和软件著作权

附录4 攻读学位期间获得的学术奖励