论文摘要
社团发现是非常重要的网络数据分析任务.统计模型类社团发现方法由于具有坚实的理论基础和优越的性能,因此越来越被人们关注.然而,已有社团发现模型一般都基于有向概率图模型,作为无向概率图模型的马尔可夫随机场极少被用于社团发现领域.2018年我们提出了一个网络导向的马尔可夫随机场模型NetMRF,该模型虽具有良好的性能,但仍存在如下问题:（1）NetMRF的能量函数不够完整,缺少往往在MRF中起主导作用的单点势函数,仅采用了常被视为起辅助作用的成对势函数对社团进行描述;（2）也正因为如此,为了使成对势函数能有效建模网络中不规则的拓扑信息,NetMRF采用了复杂的三层全连接马尔可夫随机场结构,这虽会增强其描述能力,却给推断算法带来了O（n3）级时间复杂度,n为网络节点数.本文针对上述问题对NetMRF进行改进.首先基于网络嵌入方法,结合吉布斯分布设计有效的单点势函数,解决了NetMRF能量函数不完整的缺陷;进而通过对成对势函数结构的有效稀疏化,缓解了其效率不高的问题;从而构建了一个高精度、近线性的马尔可夫随机场新模型iMRF.本文采用"最大化-加和"版本的信念传播算法对iMRF进行推断,通过最大化联合后验概率获得最优的社团配置.在两组人工网络和20个真实网络上,我们将iMRF与6个统计模型类社团发现方法（包含NetMRF）进行比较,结果显示iMRF的平均精度高于对比算法2.6%～12.9%;iMRF的平均运行速度在对比算法中也名列前茅,尤其是对于大规模网络具有更强的处理能力.
论文目录
文章来源
类型: 期刊论文
作者: 金弟,尤心心,刘岳森,何东晓
关键词: 社交网络,社团发现,网络嵌入,马尔可夫随机场,信念传播
来源: 计算机学报 2019年12期
年度: 2019
分类: 信息科技,基础科学
专业: 数学
单位: 天津大学智能与计算学部
基金: 国家自然科学基金（61772361,61876128）资助~~
分类号: O157.5
页码: 2821-2835
总页数: 15
文件大小: 1536K
下载量: 229