ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2015, Vol. 52 ›› Issue (2): 410-422.doi: 10.7544/issn1000-1239.2015.20140210

所属专题: 2015大数据管理

• 综述 • 上一篇    下一篇

符号社会网络中正负关系预测算法研究综述

蓝梦微1,2,李翠平1,2,王绍卿1,2,3,赵衎衎1,2,林志侠1,2,邹本友1,2,陈红1,2   

  1. 1(数据工程与知识工程教育部重点实验室(中国人民大学) 北京 100872); 2(中国人民大学信息学院 北京 100872); 3(山东理工大学计算机学院 山东淄博 255091) (lanmengwei@ruc.edu.cn)
  • 出版日期: 2015-02-01
  • 基金资助: 
    基金项目:国家“九七三”重点基础研究发展计划基金项目(2014CB340402,2012CB316205);国家“八六三”高技术研究发展计划基金项目(2014AA015204);国家自然科学基金项目(61272137,61033010,61202114);国家社科基金项目(12&ZD220)

Survey of Sign Prediction Algorithms in Signed Social Networks

Lan Mengwei1,2,Li Cuiping1,2, Wang Shaoqing1,2,3,Zhao Kankan1,2, Lin Zhixia1,2,Zou Benyou1,2, Chen Hong1,2   

  1. 1(Key Laboratory of Data Engineering and Knowledge Engineering (Renmin University of China), Ministry of Education, Beijing 100872); 2(Information School, Renmin University of China, Beijing 100872); 3(School of Computer Science and Technology, Shandong University of Technology, Zibo, Shandong 255091)
  • Online: 2015-02-01

摘要: 一些网络中的边根据其潜在涵义可分为正关系和负关系,若用正号和负号来标记网络中的边,则形成一个符号网络.符号网络的应用场景非常丰富,在社会学、信息学、生物学等多个领域广泛存在,逐渐成为当前研究的热点之一.对符号社会网络中链接的正负预测问题进行研究,其成果对社会网络的个性化推荐、网络中异常节点的识别、用户聚类等都具有非常重要的应用价值.主要介绍符号社会网络中正负关系预测问题在国内外的研究现状和最新进展.首先介绍了社会结构平衡理论和地位理论,并将目前主要的预测算法按照设计思路分成两类:基于矩阵的符号预测算法和基于分类的符号预测算法,详细介绍各类算法的基本思路,并从算法效率、准确性和可伸缩性等角度进行详细的对比和分析,总结了符号社会网络预测问题具有的一些特点以及所面临的挑战,同时指出未来可能的发展方向,为相关研究人员提供有价值的参考.

关键词: 符号网络, 正负预测, 在线社会网络, 数据挖掘, 信息网络

Abstract: According to the potential meaning, the edges in some networks can be divided into positive and negative relationships. When we mark these positive and negative edges with plus and minus signs respectively, a signed network is formed. Signed networks are widespread in sociology, information science, biology and other fields. Nowadays signed networks have become one of research hotspots. Researching on sign prediction problem in signed social networks is valuable to personalized recommendation, abnormal node identification and user clustering in social networks. This paper focus on predicting positive and negative links in signed social networks, and describes domestic and overseas current research status and latest developments. First we introduce the social structural balance theory and status theory. Then we classify several sign prediction algorithms into two categories according to their main ideals: algorithms based on matrix and algorithms based on classification. We introduce the basic idea of these sign prediction algorithms in detail. And then we compare and analyze these algorithms from multiple perspectives such as speed, accuracy, scalability and so on. Finally, we summarize some regularity characteristics and challenges in sign prediction and discuss some possible development directions in signed social networks research.

Key words: signed network, sign prediction, online social network, data mining, information network

中图分类号: