一种基于交叉熵的社区发现算法

摘要

Community detection algorithm is a very significant research topic in the complex network theory,which can be applied in communities’structures search and discovery applications. In this paper,the concept of Cross-Entropy in the field of signal processing is introduced and a community detection algorithm based on Cross-Entropy is proposed.The algorithm defines modularity as the quality function,which uses importance sampling in Cross-Entropy to speed up the convergence,thus the efficiency and accuracy of communities’detection can be improved simultaneously.Comparing with the Girvan-Newman algorithm over networks the computer generated,the proposed algorithm achieves higher NMI and the proportion of correctly division nodes.Moreover, the simulation results over real-world networks further reveal that the proposed algorithm accomplishes higher value of Modularity than Girvan-Newman algorithm,and no less than External Optimization algorithm.It is further verified that the proposed algorithm is more accurate than Girvan-Newman and External Optimization ones.%作为复杂网络中的一个极其重要的研究领域，社区结构的搜寻和发现研究具有重要的应用价值。该文将信号处理领域的交叉熵概念引入到网络社区结构的发现算法中，提出了一种基于交叉熵的社区发现算法。算法利用 Modularity 值作为判别依据，使用交叉熵方法中的重要抽样方法提高收敛速度，从而在提高社区发现算法运算效率的同时，提高算法的精确性。针对计算机生成网络的社区划分结果表明，该算法所得 MNI 值和划分正确节点所占比例高于 Girvan-Newman 算法。在真实网络上的仿真结果表明，该社区划分算法的 Modularity 值高于Girvan-Newman 算法，且不低于极值优化算法，进一步验证了该文提出算法的社区划分准确性优于已有的 Girvan-Newman 算法和极值优化算法。