一种高效的随机块模型学习算法

来源：软件学报杂志2016年第9期北京时间：

作者：赵学华,杨博,陈贺昌

单位：赵学华，深圳信息职业技术学院数字媒体学院, 广东 深圳 51817211,杨博，吉林大学 计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室 吉林 大学, 吉林 长春 13001202,陈贺昌，吉林大学 计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室 吉林 大学, 吉林 长春 13001203

摘要：由于随机块模型能够有效处理不具有先验知识的网络，对其研究成为了机器学习、网络数据挖掘和社会网络分析等领域的研究热点.如何设计出具有模型选择能力的快速随机块模型学习算法，是目前随机块模型研究面临的一个主要挑战.提出一种精细随机块模型及其快速学习算法.该学习方法基于提出的模型与最小消息长度推导出一个新成本函数，利用期望最大化参数估计方法，实现了边评价模型边估计参数的并行学习策略，以此方式显著降低随机块模型学习的时间复杂性.分别采用人工网络与真实网络，从学习时间和学习精度两方面对提出的学习算法进行了验证，并与现有的代表性随机块模型学习方法进行了对比.实验结果表明：提出的算法能够在保持学习精度的情况下显著降低时间复杂性，在学习精度和时间之间取得很好的折衷；在无任何先验知识的情况下，可处理的网络规模从几百节点提高至几万节点.另外，通过网络链接预测的实验，其结果也表明了提出的模型及学习算法相比现有随机块模型和学习方法具有更好的泛化能力.

关键词：网络数据挖掘;社会网络分析;随机块模型;模型选择;链接预测

基金资助：国家自然科学基金（61133011，61373053，61300146，61170092，61202308，61572226）；吉林省自然科学基金（20150101052JC）；广东省自然科学基金（2016A030310072）；吉林大学符号计算与知识工程教育部重点实验室开放课题（93K172016K19）