ISSN 0253-2778

CN 34-1054/N

open
Free to Publish. Free to Read.
Open AccessOpen Access JUSTC Original Paper

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

  • College of Information Technology, Hebei Normal University

  • 2.

    Hebei Key Lab Network and Information Security, Shijiazhuang 050000,China

  • 3.

    University of Illinois at Urbana Champaign, Illinois 61801,USA

  • 4.

    Department of Information Engineering, Hebei GEO University, Shijiazhuang 050031, China

Cite this:
https://doi.org/10.3969/j.issn.0253-2778.2018.06.001
  • Received Date: 12 June 2017
  • Accepted Date: 14 July 2017
  • Rev Recd Date: 14 July 2017
  • Publish Date: 30 June 2018
    Abstract

  • 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.

    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.
    • FullText(HTML)
  • loading
    • References(19)
  • [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.)
    • Supplements(0)
    • Related Articles
    • Track Citations
  • 加载中

Catalog

    Get Citation
    PDF
    XML
    [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.)
    Recommended articles
    TrendMD
    Volume 48 Issue 6 page: 433-439
    Cover

    Article Metrics

    Article views (50) PDF downloads(107)
    Proportional views

    Copyright © Editorial Office of JUSTC, All Rights Reserved. 皖ICP备05002528号

    Supported by: Beijing Renhe Information Technology Co. Ltd    

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return