[1]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]
Copy

Weak structure balance analysis of signed network based on WSB-EA evolutionary algorithm

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 13 Number of periods: 2018 5 Page number: 783-790 Column: 学术论文—智能系统 Public date: 2018-09-05
Title:
Weak structure balance analysis of signed network based on WSB-EA evolutionary algorithm
Author(s):
CHANG Xingong;  ZHAO Yajuan
Faculty of Information Management, Shanxi University of Finance and Economics, Taiyuan 030006, China
Keywords:
signed network; evolutionary algorithm; NP-hard problem; structural balance theory; weak structural balance theory; single cross; local search; weak unbalanced degree
CLC:
TP301.6
DOI:
10.11992/tis.201706054
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.
Similar References:

Memo

-

Last Update: 2018-10-25

Copyright © CAAI Transactions on Intelligent Systems