[1]常新功,赵雅娟.WSB-EA进化算法的符号网络弱结构平衡分析[J].智能系统学报,2018,13(5):783-790.[doi:10.11992/tis.201706054]
CHANG Xingong,ZHAO Yajuan.Weak structure balance analysis of signed network based on WSB-EA evolutionary algorithm[J].CAAI Transactions on Intelligent Systems,2018,13(5):783-790.[doi:10.11992/tis.201706054]
点击复制
CHANG Xingong,ZHAO Yajuan.Weak structure balance analysis of signed network based on WSB-EA evolutionary algorithm[J].CAAI Transactions on Intelligent Systems,2018,13(5):783-790.[doi:10.11992/tis.201706054]
WSB-EA进化算法的符号网络弱结构平衡分析
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
13
期数:
2018年第5期
页码:
783-790
栏目:
学术论文—智能系统
出版日期:
2018-09-05
- Title:
- Weak structure balance analysis of signed network based on WSB-EA evolutionary algorithm
- Keywords:
- signed network; evolutionary algorithm; NP-hard problem; structural balance theory; weak structural balance theory; single cross; local search; weak unbalanced degree
- 分类号:
- TP301.6
- 摘要:
- 由于大多数真实符号网络更满足弱结构平衡理论，并且求解符号网络的弱结构平衡问题是NP难问题，因此提出了基于进化算法的符号网络弱结构平衡计算方法——WSB-EA算法。该方法将弱结构平衡定理的能量函数作为适应值函数，首先利用启发式的方法初始化种群，经过锦标赛选择、单路交叉、单点变异、局部搜索4个阶段，迭代有限次之后得到最优解。在此算法中，提出了大型符号网络的存储方法和增量计算方式。通过大量实验，WSB-EA算法得出了4个小型符号网络和2个大型符号网络的弱不平衡度。并且与其他算法相比，WSB-EA算法能更快收敛得到最优解，具有较高鲁棒性。
- Abstract:
- The weak structural balance (WSB) theory is suitable to solve the weak structure balance problem of most signed networks, and it is an NP-hard problem. Here a WSB evolutionary algorithm (WSB-EA) is proposed, which computes the global unbalanced degree of signed network based on evolutionary algorithm. In this method, the energy function of WSB theory is used as the fitness function. First, a heuristic method is used to initialize the population. After the tournament selection, single crossing, single point variation, and local search, the optimal solution is obtained after a finite number of iterations. The algorithm involves a storage of large signed network and incremental calculation. Through several experiments, the weak unbalanced degree of four small signed networks and two large signed networks are derived from WSB-EA algorithm. Compared with other algorithms, the WSB-EA algorithm can converge to the optimal solution faster and has a higher robustness.
- 参考文献/References:
-
[1] 程苏琦, 沈华伟, 张国清, 等. 符号网络研究综述[J]. 软件学报, 2014, 25(1):1-15 CHENG Suqi, SHEN Huawei, ZHANG Guoqing, et al. Survey of signed network research[J]. Journal of software, 2014, 25(1):1-15
[2] 蓝梦微, 李翠平, 王绍卿, 等. 符号社会网络中正负关系预测算法研究综述[J]. 计算机研究与发展, 2015, 52(2):410-422 LAN Mengwei, LI Cuiping, WANG Shaoqing, et al. Survey of sign prediction algorithms in signed social networks[J]. Journal of computer research and development, 2015, 52(2):410-422
[3] AMARAL L A N, SCALA A, BARTHELEMY M, et al. Classes of behavior of small-world networks[J]. arXiv:cond-mat/0001458, 2000.
[4] MOORE M. An international application of Heider’s balance theory[J]. European journal of social psychology, 1978, 8(3):401-405.
[5] PARISIEN C, ANDERSON C H, ELIASMITH C. Solving the problem of negative synaptic weights in cortical models[J]. Neural computation, 2008, 20(6):1473-1494.
[6] HEIDER F. Attitudes and cognitive organization[J]. The journal of psychology, 1946, 21(1):107-112.
[7] LESKOVEC J, HUTTENLOCHER D, KLEINBERG J. Signed networks in social media[C]//Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. Atlanta, USA, 2010:1361-1370.
[8] 孙一翔. 基于进化算法的符号网络结构平衡分析[D]. 西安:西安电子科技大学, 2014:25-36. SUN Yixiang. Structural balance analysis in signed networks based on evolutionary algorithm[D]. Xi’an:Xidian University, 2014:25-36.
[9] CARTWRIGHT D, HARARY F. Structural balance:a generalization of Heider’s theory[J]. Psychological review, 1956, 63(5):277-293.
[10] DAVIS J A. Clustering and structural balance in graphs[J]. Human relations, 1967, 20(2):181-187.
[11] FOGEL D B. An introduction to simulated evolutionary optimization[J]. IEEE transactions on neural networks, 1994, 5(1):3-14.
[12] FOGEL D B. Evolutionary algorithms in theory and practice[J]. Complexity, 1997, 2(4):26-27.
[13] 廖美英, 郭荷清, 张勇军. 一种整数编码的改进遗传算法[J]. 计算机工程与应用, 2003, 39(1):103-105, 120 LIAO Meiying, GUO Heqing, ZHANG Yongjun. An ameliorative integer coded genetic algorithm[J]. Computer engineering and applications, 2003, 39(1):103-105, 120
[14] 邓琨, 张健沛, 杨静. 利用改进遗传算法进行复杂网络社团发现[J]. 哈尔滨工程大学学报, 2013, 34(11):1438-1444 DENG Kun, ZHANG Jianpei, YANG Jing. Community detection in complex networks using an improved genetic algorithm[J]. Journal of Harbin engineering university, 2013, 34(11):1438-1444
[15] YANG Bo, CHEUNG W, LIU Jiming. Community mining from signed social networks[J]. IEEE transactions on knowledge and data engineering, 2007, 19(10):1333- 1348.
[16] KROPIVNIK S, MRVAR A. An analysis of the slovene parliamentary parties network[M]//FERLIGOJ A, KRAMBERGER A. Developments in Statistics and Methodology. FDV, Ljubljana:Metodoloski Zvezki, 1996.
[17] READ K E. Cultures of the central highlands, new guinea[J]. Southwestern journal of anthropology, 1954, 10(1):1-43.
[18] MILO R, SHEN-ORR S, ITZKOVITZ S, et al. Network motifs:simple building blocks of complex networks[J]. Science, 2002, 298(5594):824-827.
[19] FACCHETTI G, IACONO G, ALTAFINI C. Computing global structural balance in large-scale signed social networks[J]. Proceedings of the national academy of sciences of the United States of America, 2011, 108(52):20953-20958.
- 相似文献/References:
-
[1]颜学峰.优化岭参数的非线性岭回归及4-CBA含量软测量[J].智能系统学报,2006,1(1):74.
YAN Xue-feng.Modified nonlinear ridge regression with optimal ridge pa rameter and its application to 4-CBA soft sensor[J].CAAI Transactions on Intelligent Systems,2006,1():74.
[2]陈杰,沈艳霞,陆欣.基于信息反馈和改进适应度评价的人工蜂群算法[J].智能系统学报,2016,11(2):172.[doi:10.11992/tis.201506024]
CHEN Jie,SHEN Yanxia,LU Xin.Artificial bee colony algorithm based on information feedback and an improved fitness value evaluation[J].CAAI Transactions on Intelligent Systems,2016,11():172.[doi:10.11992/tis.201506024]
[3]杨艳霞.一种基于模拟退火操作的混合差分进化算法[J].智能系统学报,2014,9(1):109.[doi:10.3969/j.issn.1673-4785.201305027]
YANG Yanxia.A hybrid differential evolutionary algorithm based on the simulated annealing operation[J].CAAI Transactions on Intelligent Systems,2014,9():109.[doi:10.3969/j.issn.1673-4785.201305027]
[4]刘柏森,张晔,张磊.一种用于大型舰船总体要素优化设计的约束多目标分解进化算法[J].智能系统学报,2016,11(5):635.[doi:10.11992/tis.201605006]
LIU Baisen,ZHANG Ye,ZHANG Lei.A constrained multi-objective decomposition evolutionary algorithmfor the overall element optimization design of large ship[J].CAAI Transactions on Intelligent Systems,2016,11():635.[doi:10.11992/tis.201605006]
[5]苏晓萍,宋玉蓉.符号网络的局部标注特征与预测方法[J].智能系统学报,2018,13(3):437.[doi:10.11992/tis.201710027]
SU Xiaoping,SONG Yurong.Local labeling features and a prediction method for a signed network[J].CAAI Transactions on Intelligent Systems,2018,13():437.[doi:10.11992/tis.201710027]
[6]王朝,秦芳,刘蓉蓉,等.求解电动汽车车辆路径问题的双种群协同进化算法[J].智能系统学报,2024,19(2):438.[doi:10.11992/tis.202209007]
WANG Chao,QIN Fang,LIU Rongrong,et al.Dual-population co-evolutionary algorithm for solving electric vehicle route problems[J].CAAI Transactions on Intelligent Systems,2024,19():438.[doi:10.11992/tis.202209007]
备注/Memo
收稿日期:2017-06-14。
基金项目:山西省哲学社会科学“十二五”规划2015年度课题项目；山西省自然科学基金项目（2013011016-4）.
作者简介:常新功,男,1968年生,教授,博士,CCF会员,主要研究方向为社会网络分析、数据挖掘、进化算法。主持多项山西省重点课题。发表学术论文30余篇;赵雅娟,女,1993年生,硕士研究生,主要研究方向为符号网络分析、进化算法。参与两个省级课题。发表学术论文4篇。
通讯作者:赵雅娟.E-mail:707238065@qq.com.
更新日期/Last Update:
2018-10-25