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

doi:10.11772/j.issn.1001-9081.2016.12.3341

计算机应用 ›› 2016, Vol. 36 ›› Issue (12): 3341-3346.DOI: 10.11772/j.issn.1001-9081.2016.12.3341

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

赵晓晖^1,2,3, 刘方爱^1,2

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

收稿日期:2016-06-16 修回日期:2016-08-05 出版日期:2016-12-10 发布日期:2016-12-08
通讯作者: 刘方爱
作者简介:赵晓晖(1981-),女,河南濮阳人,讲师,博士研究生,CCF会员,主要研究方向:社交网络、数据挖掘;刘方爱(1962-),男,山东青岛人,教授,博士生导师,博士,主要研究方向:数据挖掘、大数据分析、分布式计算。
基金资助:
国家自然科学基金资助项目（61572301，90612003）；山东省自然科学基金资助项目（ZR2013AQ008）；山东省高等学校科技计划项目（J15LN24）。

Computing global unbalanced degree of signed networks based on culture algorithm

ZHAO Xiaohui^1,2,3, LIU Fang'ai^1,2

1. School of Information Science and Engineering, Shandong Normal University, Jinan Shandong 250014, China;
2. Shandong Provincial Key Laboratory for Distributed Computer Software Novel Technology, Jinan Shandong 250014, China;
3. School of Mathematical Sciences, Shandong Normal University, Jinan Shandong 250014, China

Received:2016-06-16 Revised:2016-08-05 Online:2016-12-10 Published:2016-12-08
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61572301,90612003), the Natural Science Foundation of Shandong Province (ZR2013AQ008), Shandong Provincial Higher Educational Science and Technology Program (J15LN24).

摘要/Abstract

摘要： 针对已有符号网络不平衡度计算方法大都只关注局部网络单元的平衡信息，没有考虑网络更大范围乃至全局角度的平衡，无法揭示网络中的不平衡区域这一问题，提出基于文化算法的符号网络全局不平衡度计算方法。该方法利用伊辛自旋玻璃模型描述符号网络的全局状态，将不平衡度的计算转换为一个优化问题，并设计一种具有双层进化结构的文化算法——CA-SNB进行求解。首先，该算法采用遗传算法进行种群空间进化；其次，在信度空间中记录较优个体，并采用贪婪算法提取状况知识；最后，利用状况知识引导种群空间的进化，在保证种群多样性的基础上提高了收敛速度。实验表明，与遗传算法和矩阵变换算法相比，CA-SNB能较快地收敛到最优解，具有较高鲁棒性，在计算全局不平衡度的同时识别不平衡区域。

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

Abstract: 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.

Key words: signed network, structural balance, cultural algorithm, genetic algorithm

中图分类号:

TP301.6

赵晓晖, 刘方爱. 基于文化算法的符号网络全局不平衡度计算[J]. 计算机应用, 2016, 36(12): 3341-3346.

ZHAO Xiaohui, LIU Fang'ai. Computing global unbalanced degree of signed networks based on culture algorithm[J]. Journal of Computer Applications, 2016, 36(12): 3341-3346.

参考文献

[1] AMARAL L A N, SCALA A, BARTHÉLÉMY M, et al. Classes of small-world network[J]. Proceedings of the National Academy of Sciences of the United States of America, 2000, 97(21):11149-11152.
[2] NEWMAN M E J. The structure of scientific collaboration networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2001, 98(2):404-409.
[3] ALBERT R, JEONG H, BARABÁSI A L. Diameter of the world wide Web[J]. Nature, 1999, 401(6749):130-131.
[4] 程苏琦,沈华伟,张国清,等.符号网络研究综述[J].软件学报,2014,25(1):1-15.(CHENG S Q, SHEN H W, ZHANG G Q, et al. Survey of signed network research[J]. Journal of Software, 2014, 25(1):1-15).
[5] SZELL M, LAMBIOTTE R, THURNER S. Multirelational organization of large-scale social networks in an online world[J]. Proceedings of the National Academy of Sciences of the United States of America, 2010, 107(31):13636-13641.
[6] LESKOVEC J, HUTTENLOCHER D, KLEINBERG J. Signed networks in social media[C]//CHI'10:Proceeding of the 2010 SIGCHI Conference on Human Factors in Computing Systems. New York:ACM, 2010:1361-1370.
[7] KUNEGIS J, SCHMIDT S, LOMMATZSCH A, et al. Spectral analysis of signed graphs for clustering, prediction and visualization[C]//Proceedings of the 2010 SIAM International Conference on Data Mining. Philadelphia:SIAM, 2010:559-570.
[8] FACCHETTI G, IACONO G, ALTAFINI C. Computing global structural balance in large-scale signed social networks[J]. Proceedings of the National Academy of Sciences, 2011, 108(52):20953-20958.
[9] SUN Y X, DU H F, GONG M G, et al. Fast computing global structural balance in signed networks based on memetic algorithm[J]. Physica A:Statistical Mechanics and its Applications, 2014, 415:261-272.
[10] CAI Q, GONG M G, RUAN S S, et al. Network structural balance based on evolutionary multiobjective optimization:a two-step approach[J]. IEEE Transaction on Evolutionary Computation, 2015,19(6):903-916.
[11] CARTWRIGHT D, HARARY F. Structural balance:a generalization of Heider's theory[J]. Psychological Review, 1956, 63(5):277-293.
[12] COELLO C C A, BECERRA R L. Constrained optimization using an evolutionary programming-based cultural algorithm[M]//Adaptive Computing in Design and Manufacture V. Berlin:Springer, 2002:317-328.
[13] HUANG H Y, GU X S, LIU M D. Research on culture algorithm for solving nonlinear constrained optimization[J]. Acta Automatica Sinica, 2007, 33(10):1115-1120.
[14] WU Y L, XU L Q. An improved multi-objective cultural algorithm based on particle swarm optimization[J]. Control and Decision, 2012, 27(8):1127-1132.
[15] JIN X D, REYNOLDS R G. Mining knowledge in large-scale databases using cultural algorithms with constraint handling mechanisms[C]//Proceedings of the 2000 Congress on Evolutionary Computation. Piscataway, NJ:IEEE, 2000:1498-1506.
[16] HOLLAND J H. Adaptation in natural and artificial systems[M]//Adaptation in Natural and Artificial Systems. Cambridge:MIT Press, 1992:126-137.
[17] KROPIVNIK S, MRVAR A. An analysis of the Slovene parliamentary parties network[C]//Developments in Data Analysis. Ljubljana:FDV, 1996:209-216.
[18] READ K E. Cultures of the central highlands, New Guinea[J]. Southwestern Journal of Anthropology, 1954, 10(1):1-43.
[19] ODA K, MATSUOKA Y, FUNAHASHI A, et al. A comprehensive pathway map of epidermal growth factor receptor signaling[J]. Molecular Systems Biology, 2005, 1(1):1-17.
[20] ODA K, KIMURA T, MATSUOKA Y, et al. Molecular interaction map of a macrophage[J]. Afcs Research Reports, 2004, 2(14):1-12.

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

Computing global unbalanced degree of signed networks based on culture algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[2]	张盟, 郭健全. 需求和回收不确定的闭环供应链渠道结构选择[J]. 计算机应用, 2021, 41(7): 2100-2107.
[3]	杨震, 马健霄, 王宝杰. 设置待行区条件下双环相位信号配时优化模型[J]. 计算机应用, 2021, 41(7): 2108-2112.
[4]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[5]	李舒仪, 韩晓龙. 海铁联运港口混合作业模式下轨道吊与集卡协同调度[J]. 计算机应用, 2021, 41(5): 1506-1513.
[6]	周美玲, 陈淮莉. 基于负荷平衡的电动汽车模糊多目标充电调度算法[J]. 计算机应用, 2021, 41(4): 1192-1198.
[7]	王彬溶, 谭代伦, 郑伯川. 基于旅行商问题转化和遗传算法求解汽配件喷涂顺序[J]. 计算机应用, 2021, 41(3): 881-886.
[8]	马晓梅, 何非. 基于改进遗传算法的标签印刷生产调度技术[J]. 计算机应用, 2021, 41(3): 860-866.
[9]	黄书召, 田军委, 乔路, 王沁, 苏宇. 基于改进遗传算法的无人机路径规划[J]. 计算机应用, 2021, 41(2): 390-397.
[10]	张阳, 王小宁. 基于Word2Vec词嵌入和高维生物基因选择遗传算法的文本特征选择方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3151-3155.
[11]	杨华龙, 王美玉, 辛禹辰. 横向整合战略下异质车辆库存路径优化模型[J]. 计算机应用, 2021, 41(10): 3040-3048.
[12]	黄晓祥, 胡咏梅, 吴丹, 任力杰. 基于变分自编码器的异常颈动脉早期识别和预测[J]. 计算机应用, 2021, 41(10): 3082-3088.
[13]	王永航, 张天宇, 郑红星. 考虑恶劣天气的班轮多阶段重调度方法[J]. 计算机应用, 2021, 41(1): 286-294.
[14]	李华峰, 黄樟灿, 张蔷, 湛航, 谈庆. 求解需求可拆分车辆路径问题的改进的金字塔演化策略[J]. 计算机应用, 2021, 41(1): 300-306.
[15]	陈桢, 钟一文, 林娟. 求解0-1背包问题的混合贪婪遗传算法[J]. 计算机应用, 2021, 41(1): 87-94.