主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第4期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
赵学华,杨博,陈贺昌.一种高效的随机块模型学习算法.软件学报,2016,27(9):2248-2264
一种高效的随机块模型学习算法
Fast Learning Algorithm for Stochastic Blockmodel
投稿时间:2014-05-16  修订日期:2015-03-18
DOI:10.13328/j.cnki.jos.004855
中文关键词:  网络数据挖掘  社会网络分析  随机块模型  模型选择  链接预测
英文关键词:network oriented data mining  social network analysis  stochastic block model  model selection  link prediction
基金项目:国家自然科学基金(61133011,61373053,61300146,61170092,61202308,61572226);吉林省自然科学基金(20150101052JC);广东省自然科学基金(2016A030310072);吉林大学符号计算与知识工程教育部重点实验室开放课题(93K172016K19)
作者单位E-mail
赵学华 深圳信息职业技术学院数字媒体学院, 广东 深圳 518172  
杨博 吉林大学 计算机科学与技术学院, 吉林 长春 130012
符号计算与知识工程教育部重点实验室 吉林 大学, 吉林 长春 130012 
ybo@jlu.edu.cn 
陈贺昌 吉林大学 计算机科学与技术学院, 吉林 长春 130012
符号计算与知识工程教育部重点实验室 吉林 大学, 吉林 长春 130012 
 
摘要点击次数: 1163
全文下载次数: 2638
中文摘要:
      由于随机块模型能够有效处理不具有先验知识的网络,对其研究成为了机器学习、网络数据挖掘和社会网络分析等领域的研究热点.如何设计出具有模型选择能力的快速随机块模型学习算法,是目前随机块模型研究面临的一个主要挑战.提出一种精细随机块模型及其快速学习算法.该学习方法基于提出的模型与最小消息长度推导出一个新成本函数,利用期望最大化参数估计方法,实现了边评价模型边估计参数的并行学习策略,以此方式显著降低随机块模型学习的时间复杂性.分别采用人工网络与真实网络,从学习时间和学习精度两方面对提出的学习算法进行了验证,并与现有的代表性随机块模型学习方法进行了对比.实验结果表明:提出的算法能够在保持学习精度的情况下显著降低时间复杂性,在学习精度和时间之间取得很好的折衷;在无任何先验知识的情况下,可处理的网络规模从几百节点提高至几万节点.另外,通过网络链接预测的实验,其结果也表明了提出的模型及学习算法相比现有随机块模型和学习方法具有更好的泛化能力.
英文摘要:
      Stochastic blockmodel (SBM) has become a research focus in the domains of machine learning, network oriented data mining and social network analysis since it can effectively model networks without prior knowledge about their structures. It is a major challenge to develop a fast learning algorithm for stochastic blockmodel that has the capability of effective model selection for large-scale network. This paper presents a refined stochastic blockmodel, named RSBM, and its fast parallel learning method named RFLA. The learning method combines MML criteria with CEMM algorithm to achieve parallel execution in evaluating the model and estimating parameters. This strategy can significantly reduce time complexity of learning process. The accuracy and speed of the learning method are validated against both artificial networks and real networks, and the method is also compared with current representative SBM learning algorithms. The experimental results show that the proposed algorithm is able to greatly improve the efficiency without degenerating the precision of learning process, which indicates it achieves the best tradeoff between accuracy and speed. Furthermore, the proposed model and algorithm demonstrate the best generalization ability in terms of link prediction.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利