有向网络的混合模型新退火算法研究

doi:10.3969/j.issn.0253-2778.2018.06.001

中国科学技术大学学报 ›› 2018, Vol. 48 ›› Issue (6): 433-439.DOI: 10.3969/j.issn.0253-2778.2018.06.001

• 论著 • 下一篇

有向网络的混合模型新退火算法研究

王静红，柴变芳，李笔

1河北师范大学信息技术学院,河北省网络与信息安全重点实验室，河北石家庄 050000;2.伊利诺伊大学香槟分校，伊利诺伊乌尔班纳 6180; 3.河北地质大学信息学院，河北石家庄 050001;4.河北师范大学商学院，河北石家庄 050240

收稿日期:2017-06-12 修回日期:2017-07-14 接受日期:2017-07-14 出版日期:2018-06-30 发布日期:2017-07-14
通讯作者: 柴变芳
作者简介:王静红，女，博士/教授，研究方向：机器学习与数据挖掘，复杂网络. E-mail: wangjinghong@126.com
基金资助:
国家科学基金（61672206）；河北自然科学基金（F2013205192）；河北省教育厅项目（ZD2018023）资助.

Research on a new annealing algorithm for mixed model of directed networks

WANG Jinghong, CAI Bianfang, LI Bi

1. College of Information Technology, Hebei Normal University; Hebei Key Lab Network and Information Security, Shijiazhuang 050000，China; 2. University of Illinois at Urbana Champaign, Illinois 61801，USA; 3. Department of Information Engineering, Hebei GEO University, Shijiazhuang 050031, China; 4. Business College, Hebei Normal University, Shijiazhuang 050024，China

Received:2017-06-12 Revised:2017-07-14 Accepted:2017-07-14 Online:2018-06-30 Published:2017-07-14

摘要/Abstract

摘要： 混合模型的传统期望最大化（EM）算法可以有效地探索网络的结构规律性.但它总是陷入局部最大值.为此提出了确定性退火期望最大化（NMEM）算法来解决这个问题，该算法不仅能够防止局部最优，而且提高了收敛速度，因此NMEM算法适用于估计混合模型的参数.该算法通过经验设置其初始参数β0，设计了有向网络的混合模型新退火算法，并设计了β0的参数选择方法.

关键词: 混合模型, 退火算法, 收敛速度, 有向网络

Abstract: Although the traditional expectation-maximization (EM) algorithm of the mixed model can effectively explore the structural regularity of the network, it always gets stuck in some local maximum. A deterministic annealing expectation maximization (NMEM) algorithm is proposed to solve this problem, which not only prevents local optimum but also improves convergence speed and is thus used to estimate the parameters of the hybrid model. The algorithm always sets its initial parameters β0 through experience. If β0 is too small, the results are meaningless, or if β0 is too large, it will converge to the local maximum more frequently. Furthermore, a new hybrid model of directional network and a parameter selection method of β0 were designed.

Key words: mixture model, annealing algorithm, convergence rate, directed network

中图分类号:

TP391

王静红，柴变芳，李笔. 有向网络的混合模型新退火算法研究[J]. 中国科学技术大学学报, 2018, 48(6): 433-439.

WANG Jinghong, CAI Bianfang, LI Bi. Research on a new annealing algorithm for mixed model of directed networks[J]. Journal of University of Science and Technology of China, 2018, 48(6): 433-439.

参考文献

［1］
FORTUNATO S. Community detection in graphs[J]. Physics Report, 2010, 486(3): 75-174.
[2] HOLLAND P W, LASKEY K B, LEINHARDT S. Stochastic blockmodels: First steps[J]. Social Networks, 1983, 5(2): 109-137.
[3] SNIJDERS T A B, NOWECKI K. Estimation and prediction for stochastic blockmodels for graphs with latent block structure[J]. Journal of. Classification, 1997, 14 (1): 75-100.S
[4] DAUDIN J J, PICARD F, ROBIN S. A mixture model for random graphs[J]. StatISTICS and Computing, 2008,18(2): 173-183.
[5] SHEN W H, CHENG X Q, GUO J F. Exploring the structural regularities in networks[EB/OL]. [2011-05-04].https://doi.org/10.1103/PhysRevE.84.056111.
[6] CHAI B F, YU J, JIA C Y, et al. Combining a popularity-productivity stochastic block model with a discriminative-content model for general structure detection[J]. Physical Review E ,2013, 88 (1): 012807.
[7] LATOUCHE P, BIRMEL E, AMBROISE C. Variational Bayesian inference and complexity control for stochastic block models[J]. Statistical Modelling, 2012,12(1): 93-115.
[8] DECELLE A, KRZAKALA F, MOORE C, et al. Inference and phase transitions in the detection of modules in sparse networks[J]. Physical Review Letters, 2011, 107(6): 065701.
[9] YANG B, HE H, HU X. Detecting community structure in networks via consensus dynamics and spatial[J] Statistical Mechanics and its Applications, 2017, 483(1): 156-170.
[10] UEDA N, NAKANO R. Deterministic annealing em algorithm[J]. Neural Network, 1998, 11(2): 271-282.
[11] NAIM I, GILDEA D. Convergence of the EM algorithm for Gaussian mixtures with unbalanced mixing coefficient[C]// Proceedings of the 29th International Conference on Machine Learning. Edinburgh, UK: ACM Press, 2012: 1427-1431.
[12] VON LUXBURG U, BEN-DAVID S. Towards a statistical theory of clustering[M]// Pascal Workshop on Statistics and Optimization of Clustering, 2005.
[13] XU L, JORDAN M I. On convergence properties of the EM algorithm for Gaussian mixtures[J] .Neural Computation, 1996, 8 (1): 129-151.
[14] XIONG H, SHANG P. Weighted multifractal cross-correlation analysis based on Shannon entropy[J]. Science and Numerical Simulation, 2016, 30(1): 268-283.
[15] CHAOMURILIGE C, YU J, YANG M S. Analysis of parameter selection for Gustafson-Kessel fuzzy clustering using Jacobian matrix[J]. IEEE Transactions on Fuzzy Systems, 2015, 23(6): 2329-2342.
[16] WU C F J. On the convergence properties of the EM algorithm[J]. Annual Statistics, 1983, 11(1): 95-103.
[17] 陈宇，许莉薇，江露，等. 成像流型辨识算法[J]. 哈尔滨理工大学学报，2014, 19(4): 111-116.
CHEN Y, XU L W, JIANG L, et al. Electrical capacitance tomography identification algorithm based on GMM model[J]. Journal of Harbin University of Science and Technology, 2014, 19(4): 111-116.
[18] MA J W, FU S Q. On the correct convergence of the EM algorithm for Gaussian mixtures[J]. Pattern Recognition, 2005, 38(12): 2602-2611.
[19] OLVER P J. Lecture notes on numerical analysis[EB/OL]. [2008-05-18]. http://www.math.umn.edu/olver/num.html.

()
()

[1]	黄立航，朱旻明，叶桃红. 改进密度耦合的稀疏拉格朗日FDF方法模拟Sandia火焰E[J]. 中国科学技术大学学报, 2020, 50(5): 589-595.
[2]	房炜杰，金百锁. 方差变点的加权累积和估计的极限性质[J]. 中国科学技术大学学报, 2020, 50(4): 389-395.
[3]	汪中, 施培蓓, 刘贵全. 基于自学习的行人检测方法[J]. 中国科学技术大学学报, 2020, 50(1): 79-85.
[4]	彭玉青，王纬华，刘璇，赵晓松，魏铭. 基于深度学习与Dense SIFT融合的人脸表情识别[J]. 中国科学技术大学学报, 2019, 49(2): 105-111.
[5]	蒋硕然，陈亚瑞*，秦智飞，杨巨成. 基于KS检验的高斯混合模型分裂与合并算法[J]. 中国科学技术大学学报, 2018, 48(6): 477-485.
[6]	张倩，韦来生. 刻度指数族参数的经验Bayes双边检验问题 ——加权损失函数情形[J]. 中国科学技术大学学报, 2013, 43(2): 156-161.

有向网络的混合模型新退火算法研究

Research on a new annealing algorithm for mixed model of directed networks

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价