文档介绍：RESEARCH ON MMSB MUNITY DETECTION ALGORITHM IN
WEIGHTED WORK
A Master Thesis Submitted to
University of Electronic Science and Technology of China
Major: Information munication Engineering Author: Xin Baihui Advisor: Hu Guangmin School: School munication and Information
Engineering
独创性声明
本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知,除了文中特别加以标注和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不包含为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。
作者签名: 日期: 年 月 日
论文使用授权
本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定,有权保留并向国家有关部门或机构送交论文的复印件和磁盘, 允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。
(保密的学位论文在解密后应遵守此规定)
作者签名: 导师签名:
日期: 年 月 日
摘要
摘 要
社交网络的一个重要特征是具有社团结构,社团结构在宏观上有助于深入理解网络的拓扑特性和本质,微观上有助于探索网络中用户的行为特点以及用户之间的逻辑关系,同时也能发现信息在网络中的传播特性。因此,寻找社交网络的社团结构也变得尤为重要。
早期的社交网络社团发现方法大多只能对无权或无向的社交网络进行非重叠的社团划分,混合隶属度随机块模型(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 的节点划分准确率和
I
摘要
社团结构的模块度都优于 MMSB。
关键字:社交网络,社团发现,加权混合隶属度随机块模型,变分期望最大算法
II
ABSTRACT
ABSTRACT
Community structure is an important feature of working. It is helpful to the deep understanding of work topology characteristics in macro, exploring work use