基于文化算法的符号网络全局不平衡度计算  

Computing global unbalanced degree of signed networks based on culture algorithm

作　　者：赵晓晖[1,2,3] 刘方爱[1,2] 

机构地区：[1]山东师范大学信息科学与工程学院,济南250014 [2]山东省分布式计算机软件新技术重点实验室,济南250014 [3]山东师范大学数学科学学院,济南250014

出　　处：《计算机应用》2016年第12期3341-3346,共6页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61572301;90612003);山东省自然科学基金资助项目(ZR2013AQ008);山东省高等学校科技计划项目(J15LN24)~~

摘　　要：针对已有符号网络不平衡度计算方法大都只关注局部网络单元的平衡信息,没有考虑网络更大范围乃至全局角度的平衡,无法揭示网络中的不平衡区域这一问题,提出基于文化算法的符号网络全局不平衡度计算方法。该方法利用伊辛自旋玻璃模型描述符号网络的全局状态,将不平衡度的计算转换为一个优化问题,并设计一种具有双层进化结构的文化算法——CA-SNB进行求解。首先,该算法采用遗传算法进行种群空间进化;其次,在信度空间中记录较优个体,并采用贪婪算法提取状况知识;最后,利用状况知识引导种群空间的进化,在保证种群多样性的基础上提高了收敛速度。实验表明,与遗传算法和矩阵变换算法相比,CA-SNB能较快地收敛到最优解,具有较高鲁棒性,在计算全局不平衡度的同时识别不平衡区域。Many approaches which are developed to compute structural balance degree of signed networks only focus on the balance information of local network without considering the balance of network in larger scale and even from the whole viewpoint, which can＇t discover unbalanced links in the network. In order to solve the problem, a method of computing global unbalanced degree of signed networks based on culture algorithm was proposed. The computation of unbalanced degree was converted to an optimization problem by using the Ising spin glass model to describe the global state of signed network. A new cultural algorithm with double evolution structures named Culture Algorithm for Signed Network Balance （CA-SNB） was presented to solve the optimization problem. Firstly, the genetic algorithm was used to optimize the population space. Secondly, the better individuals were recorded in belief space and the situation knowledges were summarized by using greedy strategy. Finally, the situation knowledge was used to guide population space evolution. The convergence rate of CA-SNB was improved on the basis of population diversity. The experimental results show that, the CA-SNB can converge to the optimal solution faster and can be more robust than genetic algorithm and matrix transformation algorithm. The proposed algorithm can compute the global unbalanced degree and discover unbalanced links at the same time.

关 键 词：符号网络 结构平衡 文化算法 遗传算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]