基于概率模型的大规模网络结构发现方法  

Approaches of Structure Exploratory Based on Probabilistic Models in Massive Networks

作　　者：柴变芳[1,2] 贾彩燕[1] 于剑[1] 

机构地区：[1]交通数据分析与挖掘北京市重点实验室(北京交通大学),北京100044 [2]石家庄经济学院信息工程学院,河北石家庄050031

出　　处：《软件学报》2014年第12期2753-2766,共14页Journal of Software

基　　金：国家自然科学基金(61473030;61370129);中央高校科研业务经费(2014YJS039);河北省自然科学基金(F2013205192);北京市科委项目(Z131110002813118);北大方正集团有限公司数字出版技术国家重点实验室开放课题

摘　　要：随着万维网和在线社交网站的发展,规模大、结构复杂、动态性强的大规模网络应用而生.发现这些网络的潜在结构,是分析和理解网络数据的基本途径.概率模型以其灵活的建模和解释能力、坚实的理论框架成为各领域研究网络结构发现任务的有效工具,但该类方法存在计算瓶颈.近几年出现了一些基于概率模型的大规模网络结构发现方法,主要从网络表示、结构假设、参数求解这3个方面解决计算问题.按照模型参数求解策略将已有方法归为两类:随机变分推理(stochastic variational inference)方法和在线EM(online expectation maximazation)方法,详细分析各方法的设计动机、原理和优缺点.定性和定量地对比、分析典型方法的特点和性能,并提出大规模网络结构发现模型的设计原则.最后,概括该领域研究的核心问题,展望未来发展趋势.The growth of the Internet and the emergence of online social websites bring up the development of massive networks which are large in scale, complex in structure, and dynamical in time. Exploring latent structure underlying a network is the fundamental solution to understand and analyze the network. Probabilistic models become effective tools in diverse areas of structure exploratory due to their flexibility in modeling, interpretability and the sound theoretical framework, however they incur computational bottlenecks. Recently, several approaches based on probabilistic models have been developed to explore structure in massive networks, which aim to solve the computational problems from three aspects： representations of a network, assumptions of the structure and methods of parameter estimation. This study classifies existing approaches as two categories by the methods of parameter estimation： approaches based on stochastic variational inference and online EM approaches, and analyzes in detail their designing incentives, principles, pros and cons. The properties and performance of classical models are compared and analyzed qualitatively and quantitatively, and as a result the principles are provided to develop approaches of structure detection in massive networks. Finally, the core problems of structure exploratory in massive networks are summarized based on probabilistic models and the development trend of this area is projected.

关 键 词：大规模网络 结构发现 随机变分推理 在线EM算法 三角形模体 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]