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

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

Fast Learning Algorithm for Stochastic Blockmodel

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.