A Community Detection Algorithm Based on Probabilistic Graphical Model

Many community detection algorithms suffer from problems such as low accuracy and efficiency, overfitting or underfitting, and high time complexity. To address the issues in global optimization algorithms proposed so far, GOMK-BP, a community detection algorithm based on the probabilistic graph model, is proposed in this paper. It takes the fully connected Markov random field (MRF) as the probabilistic graph model, maps the node’s similarity and importance indexes to the energy function, which is then optimized to improve the performance of the model, and the combination of weighted sum and exponential function makes the algorithm achieve a better fit. To improve the efficiency and accuracy, the traditional message propagation algorithm is improved, and the convergence is accelerated by using compressed sensing. Because of the fully connected MRF may be affected by the high computational complexity, GOMK-BP adjusts the model structure, and introduces sparse connections to balance the computational efficiency and model performance. Finally, the community structure is obtained. The proposed algorithm is tested on some artificial networks and real networks, the results show that GOMK-BP can detect high-quality community structures.