Int J Performability Eng ›› 2019, Vol. 15 ›› Issue (8): 2153-2164.doi: 10.23940/ijpe.19.08.p15.21532164

Previous Articles     Next Articles

Optimization and Parallelization of MRF Community Detection Algorithm for a Specific Network

Jun Lua,b,* and Yuanzhong Zhanga   

  1. a College of Computer Science and Technology, Heilongjiang University, Harbin, 150080, China
    b Key Laboratory of Database and Parallel Computing of Heilongjiang Province, Harbin, 150080, China
  • Submitted on ;
  • Contact: * E-mail address: lujun111_lily@sina.com
  • About author:Jun Lu is a professor and master's supervisor in the College of Computer Science and Technology at Heilongjiang University. Her research interests include computational biology, data coding, parallel computing, and machine learning. Yuanzhong Zhang, Male, Jan 25, 1992. He is a graduate student in the College of Computer Science and Technology, Heilongjiang University. Research Interests include parallel computing and machine learning.

Abstract: Research on the optimization and parallelization of the MRF network community detection algorithm for a specific network is carried out in this paper. Firstly, the principle of the existing algorithm is expounded, the algorithm is analyzed, and some problems are pointed out. Some optimization strategies and rules are proposed, including the extraction of variables and operations from inner loops to outer loops, the merging of related operations in loops, the removal of redundant loops, and the split of loops. In order to achieve better parallelism, OpenMP parallel computing of this method is realized by reversing the order of inner and outer loops. The influence of the density of network edges on the algorithm efficiency is also analyzed in this paper. The optimization and parallel algorithm can be applied to the module partition of Alzheimer's disease gene data, and the efficiency of the algorithm is greatly improved. The optimization strategies and rules proposed in this paper can be further extended to general situations. It is significant in practical applications.

Key words: community detection, MRF, optimization, parallel