[1]苏晓萍,宋玉蓉.符号网络的局部标注特征与预测方法[J].智能系统学报,2018,13(03):437-444.[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(03):437-444.[doi:10.11992/tis.201710027]
点击复制

符号网络的局部标注特征与预测方法(/HTML)
分享到:

《智能系统学报》[ISSN:1673-4785/CN:23-1538/TP]

卷:
第13卷
期数:
2018年03期
页码:
437-444
栏目:
出版日期:
2018-05-05

文章信息/Info

Title:
Local labeling features and a prediction method for a signed network
作者:
苏晓萍1 宋玉蓉2
1. 南京工业职业技术学院 计算机与软件学院, 江苏 南京 210046;
2. 南京邮电大学 自动化学院, 江苏 南京 210003
Author(s):
SU Xiaoping1 SONG Yurong2
1. School of Computer and Software Engineering, Nanjing Institute of Industry Technology, Nanjing 210046, China;
2. College of Automation, Nanjing University of Posts and Telecommunications, Nanjing 210003, China
关键词:
符号网络符号预测低秩矩阵分解标注偏置结构平衡理论弱结构平衡理论地位理论
Keywords:
signed networkssign predictionlow rankmatrix factorizationsigned biasstructural balance theoryweak structural balance theorystatus theory
分类号:
TP399
DOI:
10.11992/tis.201710027
摘要:
当复杂网络的边具有正、负属性时称为符号网络。符号为正表示两用户间具有相互信任(朋友)关系,相反,符号为负表示不信任(敌对)关系。符号网络中的一个重要研究任务是给定部分观测的符号网络,预测未知符号。分析发现,具有弱结构平衡特征的符号网络,其邻接矩阵呈现全局低秩性,在该特征下链路符号预测问题可以近似表达为低秩矩阵分解问题。但基本低秩模型中,相邻节点间符号标注的局部行为特征未得到充分利用,论文提出了一种带偏置的低秩矩阵分解模型,将邻居节点的出边和入边符号特征作为偏置信息引入模型,以提高符号预测的精度。利用真实符号网络数据进行的实验证明,所提模型能够获得较其他基准算法好的预测效果且算法效率高。
Abstract:
A complex network may be considered as a symbol network when links have a positive or negative sign attribute. In signed social networks, positive links represent a trust (friends) relationship between users. In contrast, negative links indicate distrust (hostility). An important task in a signed network is to define a signed network based on partial observation to predict an unknown symbol. Through analysis, we found that for a signed network with weak structural balance, its adjacent matrix has a global low-rank characteristic and the prediction of the link sign can be approximated as a low-rank matrix factorization. However, in a basic low-rank model, it is difficult to sufficiently utilize the local behavior features for labeling the signs of links between the neighboring nodes. Herein, a low-rank matrix factorization model with bias was proposed. In this model, the sign features of the exit and entry links of a neighboring node were introduced to improve the precision of sign prediction. Experiments based on real data revealed that the low-rank model with bias can obtain better prediction results than other benchmark algorithms and that the proposed algorithm performed with a high efficiency.

参考文献/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] TANG Jiliang, AGGARWAL C, LIU Huan. Recommendations in signed social networks[C]//Proceedings of the 25th International Conference on World Wide Web. Montréal, Canada, 2016:31-40.
[3] LI Dong, XU Zhiming, CHAKRABORTY N, et al. Polarity related influence maximization in signed social networks[J]. PLoS one, 2014, 9(7):e102199.
[4] EVERETT M G, BORGATTI S P. Networks containing negative ties[J]. Social networks, 2014, 38:111-120.
[5] HEIDER F. Attitudes and cognitive organization[J]. The Journal of psychology:interdisciplinary and applied, 1946, 21(1):107-112.
[6] 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.
[7] CHU Lingyang, WANG Zhefeng, PEI Jian, et al. Finding gangs in war from signed networks[C]//Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Francisco, USA, 2016:1505-1514.
[8] DAVIS J A. Clustering and structural balance in graphs[J]. Human relations, 1967, 20(2):181-187.
[9] 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.
[10] 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, USA, 2004:403-412.
[11] 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, USA, 2010:641-650.
[12] WANG Guannan, GAO Hui, CHEN Lian, et al. Predicting positive and negative relationships in large social networks[J]. PLoS one, 2015, 10(6):e0129530.
[13] CHIANG K Y, NATARAJAN N, TEWARI A, et al. Exploiting longer cycles for link prediction in signed networks[C]//Proceedings of the 20th ACM international Conference on Information and Knowledge Management. Glasgow, Scotland, UK, 2011:1157-1162.
[14] 蓝梦微, 李翠平, 王绍卿, 等. 符号社会网络中正负关系预测算法研究综述[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.
[15] SONG Dongjin, MEYER D A. Link sign prediction and ranking in signed directed social networks[J]. Social network analysis and mining, 2015, 5:52.
[16] 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. Columbus, USA, 2010:559-570.
[17] HSIEH C J, CHIANG K Y, DHILLON I S. Low rank modeling of signed networks[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Beijing, China, 2012:507-515.
[18] MENON A K, ELKAN C. Link prediction via matrix factorization[C]//Proceedings of the 2011 European Conference on Machine Learning and Knowledge Discovery in Databases. Athens, Greece, 2011:437-452.
[19] AGRAWAL P, GARG V K, NARAYANAM R. Link label prediction in signed social networks[C]//Proceedings of the 23rd International Joint Conference on Artificial Intelligence. Beijing, China, 2013:2591-2597.
[20] CARTWRIGHT D, HARARY F. Structural balance:a generalization of Heider’s theory[J]. Psychological review, 1956, 63(5):277-293.
[21] CANDÈS E J, TAO T. The power of convex relaxation:near-optimal matrix completion[J]. IEEE transactions on information theory, 2010, 56(5):2053-2080.

备注/Memo

备注/Memo:
收稿日期:2017-10-30。
基金项目:国家自然科学基金项目(61672298,61373136);教育部人文社会科学研究规划基金项目(17YJAZH071);江苏省高校优秀科技创新团队项目.
作者简介:苏晓萍,女,1971年生,教授,主要研究方向为复杂网络上动态信息传播、信息检索。主持省部级项目2项,发表学术论文10余篇;宋玉蓉,女,1971年生,教授,博士生导师,博士,主要研究方向为复杂网络上动态信息传播、网络控制与优化。主持国家自然科学基金项目2项、教育部人文社科项目1项,发表学术论文30余篇,被SCI、EI收录多篇。
通讯作者:苏晓萍.E-mail:419033424@qq.com.
更新日期/Last Update: 2018-06-25