CAJ | 학술논문

作为复杂网络中的一个极其重要的研究领域，社区结构的搜寻和发现研究具有重要的应用价值。该文将信号处理领域的交叉熵概念引入到网络社区结构的发现算法中，提出了一种基于交叉熵的社区发现算法。算法利用 Modularity 值作为判别依据，使用交叉熵方法中的重要抽样方法提高收敛速度，从而在提高社区发现算法运算效率的同时，提高算法的精确性。针对计算机生成网络的社区划分结果表明，该算法所得 MNI 值和划分正确节点所占比例高于 Girvan-Newman 算法。在真实网络上的仿真结果表明，该社区划分算法的 Modularity 值高于Girvan-Newman 算法，且不低于极值优化算法，进一步验证了该文提出算法的社区划分准确性优于已有的 Girvan-Newman 算法和极值优化算法。
작위복잡망락중적일개겁기중요적연구영역，사구결구적수심화발현연구구유중요적응용개치。해문장신호처리영역적교차적개념인입도망락사구결구적발현산법중，제출료일충기우교차적적사구발현산법。산법이용 Modularity 치작위판별의거，사용교차적방법중적중요추양방법제고수렴속도，종이재제고사구발현산법운산효솔적동시，제고산법적정학성。침대계산궤생성망락적사구화분결과표명，해산법소득 MNI 치화화분정학절점소점비례고우 Girvan-Newman 산법。재진실망락상적방진결과표명，해사구화분산법적 Modularity 치고우Girvan-Newman 산법，차불저우겁치우화산법，진일보험증료해문제출산법적사구화분준학성우우이유적 Girvan-Newman 산법화겁치우화산법。
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.