Research about Optimizing Prediction Accuracy and Time Complexity in Signed Networks

doi:10.3969/j.issn.1007-7375.e16-4208

Abstract

Abstract: In signed networks, different sign predicting algorithms have been proposed. The prediction accuracy of the algorithm is improving, but the time complexity is also increasing. A way must be found to reduce the time complexity. In order to ensure the high prediction accuracy and low time complexity, an optimization algorithm is designed to analyze the relation between prediction accuracy and time complexity with increasing steps and an optimization scheme is also proposed through using the balanced cycle algorithm for predicting sign at first and then fitting the function of prediction accuracy and step, time complexity and step respectively. Experiments show that the optimization algorithm can effectively obtain the relation between prediction accuracy and time complexity. This research can be used in working out design symbol prediction algorithms.

Key words: signed networks, sign prediction, time complexity, optimization

TENG Shaohua, SU Qingjia, LIU Dongning, ZHANG Wei. Research about Optimizing Prediction Accuracy and Time Complexity in Signed Networks[J]. Industrial Engineering Journal , 2017, 20(1): 59-64.

References

[1] 程苏琦, 沈华伟, 张国清, 等. 符号网络研究综述[J]. 软件学报, 2014, 25(1):1-15. CHENG Suqi, SHEN Huawei, ZHANG Guoqing, et al. A survey of signed network research[J]. Ruan Jian XueBao/Journal ofSoftware, 2014, 25(1):1-15.
[2] CHIANG K Y, NATARAJAN N, TEWARI A, et al. Exploiting longer cycles for link prediction in signed networks[C]//ACM Conference on Information and Knowledge Management, CIKM 2011. Glasgow, United Kingdom, 2011:1157-1162.
[3] LESKOVEC J, HUTTENLOCHER D, KLEINBERG J. Predicting positive and negative links in online social networks[C]//Proceedings of the 19th International Conference on World Wide Web. Raleigh, North, Carolina, USA, 2010:641-650.
[4] PAPAOIKONOMOU A, KARDARA M, TSERPES K, et al. Predicting edge signs in social networks using frequent subgraph discovery[J]. IEEE Internet Computing, 2014, 18(5):36-43.
[5] LESKOVEC J, KREVL A. soc-sign-epinions, wiki-RfA and soc-sign-Slashdot 081106. Stanford Large Network Dataset Collection[EB/OL]. http://snap.stanford.edu/data/#signnets. Jun.2014.
[6] GUHA R, KUMAR R, RAGHAVAN P, et al. Propagation of trust and distrust[C]//Proceedings of the 13th international conference on World Wide Web. New York, NY, USA, 2004:403-412.
[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, Georgia, USA, 2010:1361-1370.
[8] 张维玉, 吴斌, 刘旸. 融合多特征的符号网络连边符号预测[J]. 北京邮电大学学报, 2014(5):80-84. ZHANG Weiyu, WU Bin, LIU Yang. Integrating multi-feature for link sign prediction in signed networks[J]. Journal of Beijing University of Posts and Telecommunications, 2014(5):80-84.
[9] ALTAFINI C, LINI G. Achieving unanimous opinions in signed social networks[C]//Control Conference. IEEE, 2014:184-189.
[10] ANCHURI P, MAGDONISMAIL M. Communities and balance in signed networks:a spectral approach[C]//Ieee/acm International Conference on Advances in Social Networks Analysis and Mining. IEEE, Washington, DC, USA, 2012:235-242.
[11] KERCHOVE C D, DOOREN P V. The pagetrust algorithm:How to rank web pages when negative links are allowed?[C]//Siam International Conference on Data Mining, SDM 2008, April 24-26, 2008. Atlanta, Georgia, Usa. 2008:346-352.
[12] 蓝梦微, 李翠平, 王绍卿, 等. 符号社会网络中正负关系预测算法研究综述[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.
[13] LIU F, LIU B, SUN C, et al. Deep belief network-based approaches for link prediction in signed social networks[J]. Entropy, 2015, 17(4):2140-2169.
[14] YE J, CHENG H, ZHU Z, et al. Predicting positive and negative links in signed social networks by transfer learning[C]//In Proceedings of the 22nd international conference on World Wide Web (WWW'13). ACM, New York, NY, USA. 2013:1477-1488.
[15] CHIANG K Y, HSIEH C J, NATARAJAN N, et al. Prediction and clustering in signed networks:a local to global perspective[J]. Journal of Machine Learning Research, 2013, 15(1):1177-1213.