基于MMSB的加权社交网络社团发现算法研究

摘要

社交网络的一个重要特征是具有社团结构,社团结构在宏观上有助于深入理解网络的拓扑特性和本质,微观上有助于探索网络中用户的行为特点以及用户之间的逻辑关系,同时也能发现信息在网络中的传播特性。因此,寻找社交网络的社团结构也变得尤为重要。
　　早期的社交网络社团发现方法大多只能对无权或无向的社交网络进行非重叠的社团划分,混合隶属度随机块模型(Mixed Membership Stochastic Block Model, MMSB)社团发现方法不仅能够对有向无权网络进行重叠社团划分,而且能定量得到节点在各个社团中的隶属度,受到广泛的关注。然而,现有MMSB并不适用于加权网络,也没有衡量节点社团划分正确性的判断方法,这在一定程度上限制了其应用范围。因此本文通过研究现有的社交网络社团发现方法,分析各自的优点与不足,提出了基于MMSB的有向加权网络的重叠社团划分方法。文章的主要工作如下:
　　1)在MMSB的基础上提出了一种对有向加权社交网络进行重叠社团划分方法,称之为加权混合隶属度随机块模型(Weighted Mixed Membership Stochastic Block Model, WMMSB)社团发现方法。该方法首先通过建立统计模型来模拟观测网络,再利用最大似然准则估计模型中的参数,根据参数,也就是节点的混合隶属度,就能够对网络进行社团划分。由于参数的似然函数复杂度极高,传统的最大似然估计方法无法得到参数的估计值,因此采用变分期望最大值(Variational Expectation Maximization, VEM)算法来估计参数。
　　2)提出了针对混合隶属度随机块模型的节点划分正确性评判方法。该方法首先通过混合隶属度得到各个社团对节点的边占有量,然后判断通过边占有量为节点选出的社团与混合隶属度是否一致,若一致就认为该节点划分是正确的,否则认为节点划分错误。
　　3)将WMMSB应用于期刊引用网络,展示并分析社团划分结果,通过和基于边方向信息抽取的社团划分方法相对比,说明WMMSB不仅能正确划分社团,还有能定量的得到节点和社团之间亲密度的优势。
　　4)使用网络爬虫技术获取新浪微博部分用户的博文转发数据,分别用MMSB和WMMSB对用户进行社团划分,并通过可视化的方法显示网络社团结构。实验结果首先表明了WMMSB中参数的对数似然函数能够收敛;然后,通过似然函数最大值能找出网络的最佳社团数量;最后通过对比WMMSB和MMSB的社团划分结果,结合可视化结果,得到WMMSB的节点划分准确率和社团结构的模块度都优于MMSB。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪 论

1.1 研究背景

1.2 研究意义

1.3 研究现状

1.4 本文研究内容

1.5 本文章节安排

第二章 社交网络社团发现算法综述

2.1 传统社交网络社团发现算法

2.2 基于统计推理的社团发现方法

2.3本章小结

第三章 加权混合隶属度随机块模型

3.1 建立WMMSB模型

3.2 WMMSB模型构建合理性

3.3 参数估计

3.4 本章小结

第四章 WMMSB在实际网络中的应用

4.1 社团划分度量标准

4.2 实验结果展示与分析

4.3 本章小结

第五章 总结与展望

5.1 工作总结

5.2 工作展望

致谢

参考文献

攻读硕士学位期间取得的研究成果