第13卷第3期 智能系统学报 Vol.13 No.3 2018年6月 CAAI Transactions on Intelligent Systems Jun.2018 D0:10.11992/tis.201710027 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20180404.1358.012.html 符号网络的局部标注特征与预测方法 苏晓萍，宋玉蓉2 (1.南京工业职业技术学院计算机与软件学院，江苏南京210046,2.南京邮电大学自动化学院，江苏南京 210003) 摘要：当复杂网络的边具有正、负属性时称为符号网络。符号为正表示两用户间具有相互信任（朋友）关系，相反， 符号为负表示不信任（敌对）关系。符号网络中的一个重要研究任务是给定部分观测的符号网络，预测未知符号。分 析发现，具有弱结构平衡特征的符号网络，其邻接矩阵呈现全局低秩性，在该特征下链路符号预测问题可以近似表达 为低秩矩阵分解问题。但基本低秩模型中，相邻节点间符号标注的局部行为特征未得到充分利用，论文提出了一种 带偏置的低秩矩阵分解模型，将邻居节点的出边和入边符号特征作为偏置信息引入模型，以提高符号预测的精度。 利用真实符号网络数据进行的实验证明，所提模型能够获得较其他基准算法好的预测效果且算法效率高。 关键词：符号网络：符号预测：低秩：矩阵分解：标注偏置：结构平衡理论：弱结构平衡理论：地位理论 中图分类号：TP399文献标志码：A 文章编号：1673-4785(2018)03-0437-08 中文引用格式：苏晓萍，宋玉蓉.符号网络的局部标注特征与预测方法.智能系统学报，2018,13(3)：437-444. 英文引用格式：SU Xiaoping,SONG Yurong.Local labeling features and a prediction method for a signed networkJ.CAAI trans- actions on intelligent systems,2018,13(3):437-444. Local labeling features and a prediction method for a signed network SU Xiaoping SONG Yurong (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) Abstract:A complex network may be considered as a symbol network when links have a positive or negative sign at- tribute.In signed social networks,positive links represent a trust(friends)relationship between users.In contrast,negat- ive links indicate distrust(hostility).An important task in a signed network is to define a signed network based on par- tial observation to predict an unknown symbol.Through analysis,we found that for a signed network with weak struc- tural balance,its adjacent matrix has a global low-rank characteristic and the prediction of the link sign can be approx- imated 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 factoriz- ation 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. Keywords:signed networks;sign prediction;low rank;matrix factorization;signed bias;structural balance theory;weak structural balance theory;status theory 符号网络是指边具有正或负符号属性的网络， 收稿日期：2017-10-30.网络出版日期：2018-04-04。 基金项目：国家自然科学基金项目(61672298,61373136)：教育部 符号为正表示网络中两节点间具有相互信任的、积 人文社会科学研究规划基金项目(17 YJAZH071):江苏 省高校优秀科技创新团队项目. 极的朋友关系，负边则表示不信任的、消极的敌对 通信作者：苏晓萍.E-mail:419033424@qq.com. 关系。具有符号属性的网络普遍存在，研究链路
DOI: 10.11992/tis.201710027 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20180404.1358.012.html 符号网络的局部标注特征与预测方法 苏晓萍1 ，宋玉蓉2 （1. 南京工业职业技术学院 计算机与软件学院，江苏 南京 210046; 2. 南京邮电大学 自动化学院，江苏 南京 210003） 摘 要：当复杂网络的边具有正、负属性时称为符号网络。符号为正表示两用户间具有相互信任 (朋友) 关系，相反， 符号为负表示不信任 (敌对) 关系。符号网络中的一个重要研究任务是给定部分观测的符号网络，预测未知符号。分 析发现，具有弱结构平衡特征的符号网络，其邻接矩阵呈现全局低秩性，在该特征下链路符号预测问题可以近似表达 为低秩矩阵分解问题。但基本低秩模型中，相邻节点间符号标注的局部行为特征未得到充分利用，论文提出了一种 带偏置的低秩矩阵分解模型，将邻居节点的出边和入边符号特征作为偏置信息引入模型，以提高符号预测的精度。 利用真实符号网络数据进行的实验证明，所提模型能够获得较其他基准算法好的预测效果且算法效率高。 关键词：符号网络；符号预测；低秩；矩阵分解；标注偏置；结构平衡理论；弱结构平衡理论；地位理论 中图分类号：TP399 文献标志码：A 文章编号：1673−4785(2018)03−0437−08 中文引用格式：苏晓萍, 宋玉蓉. 符号网络的局部标注特征与预测方法[J]. 智能系统学报, 2018, 13(3): 437–444. 英文引用格式：SU Xiaoping, SONG Yurong. Local labeling features and a prediction method for a signed network[J]. CAAI transactions on intelligent systems, 2018, 13(3): 437–444. Local labeling features and a prediction method for a signed network 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) 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. Keywords: signed networks; sign prediction; low rank; matrix factorization; signed bias; structural balance theory; weak structural balance theory; status theory 符号网络是指边具有正或负符号属性的网络， 符号为正表示网络中两节点间具有相互信任的、积 极的朋友关系，负边则表示不信任的、消极的敌对 关系。具有符号属性的网络普遍存在[1] ，研究链路 收稿日期：2017−10−30. 网络出版日期：2018−04−04. 基金项目：国家自然科学基金项目 (61672298，61373136)；教育部 人文社会科学研究规划基金项目 (17YJAZH071)；江苏 省高校优秀科技创新团队项目. 通信作者：苏晓萍. E-mail: 419033424@qq.com. 第 13 卷第 3 期 智 能 系 统 学 报 Vol.13 No.3 2018 年 6 月 CAAI Transactions on Intelligent Systems Jun. 2018
·438· 智能系统学报 第13卷 的符号属性有利于理解网络的基本结构特征，理解 测。Hsieh等发现满足弱结构平衡理论的符号网 信任和不信任的传播方式。另外，社会符号网络的 络其邻接矩阵具有低秩特征，于是将符号预测问题 边符号属性能够直接反映节点间的态度，因此在推 转化为矩阵填充问题，用低秩填充法有效地进行了 荐系统、舆情分析与观点形成、网络欺凌与社会 符号预测。他们还将符号预测近似为低秩矩阵分解 排斥等问题中均能通过符号分析获得应用。符号 问题进行了符号预测。文献[18]也研究了矩阵分解 网络的研究始于Heider基于社会心理学对人类关 在符号预测中的应用并解决了数据不平衡对预测精 系的研究，而随着复杂网络研究兴起，符号网络的 度的影响。文献[19]提出了一种区别于Hsieh以逐 结构特征与演化规律受到更多研究者的关注6-)，如 点误差衡量原矩阵与结果矩阵误差的方法，他们将 何通过部分观测到的网络符号预测未知的边符号成 成对误差应用到矩阵分解的损失函数中，给出的算 为符号网络中非常重要的研究方向。 法MF-LiSP取得了较高精确度。通过以上介绍发 符号预测方法大致可以分为两类：1)考虑网络 现，符号网络的局部结构特征与全局特征联系紧 局部特征的方法：2)考虑网络全局特征的方法。考 密，符号预测方法仅使用局部特征或全局特征都不 虑网络局部特征的方法主要利用节点的邻域特征， 够全面，在预测算法中如何同时利用局部和全局特 如：节点出边、入边的符号以及相邻三元组各边标 征是一个值得研究的问题。 注符号特征进行符号预测。这类方法主要基于网络 受以上研究的启发，从真实网络数据的统计分 局部特征以及社会学相关理论实现边符号的预测， 析出发，结合节点局部标注特征和网络全局结构特 所有基于弱结构平衡和地位理论的预测方法均 征设计了一种新的基于低秩矩阵分解的符号预测模 要求两节点间具有共同邻居时算法才有效，但统计 型，解决了符号网由于数据稀疏和网络局部特征利 结果发现，现实的符号网络中有很大比例的节点不 用不足带来的预测精度不高的问题。 能构成三元组。Guha等o最早基于网络模型研究 符号预测问题，他们将信任网络表示为矩阵并运用 1相关理论 不同的矩阵运算代表信任关系在网络上的不同传播 1.1基本定义 方式，实现了信任关系的预测。Leskovec等u采用 定义符号网络G为G=(V,E,S),其中V={1,2 机器学习的方法对符号预测问题进行了研究，他们 3,…,n川为节点集合，E={1,2,3,…,m为边集合， 利用节点的出度、入度、节点的嵌入性以及基于地 S={-1,0,1表示边符号，i,jeV,ei,)eE,si,)eS 位理论的所有16种待预测边所处的三角形的关系 设O为被观测到的边集，则0二E。符号网络G对应 模式作为特征采用逻辑回归模型训练分类器，得到 邻接矩阵A,其中： 了较高的预测精度。文献[12]则通过网络局部特征 1, 与之间有正边 和地位理论为特征采用SVM算法进行二值分类实 0. 边符号未知或不存在边 现符号预测。相对于Leskovec考虑长度为3的有 -1, 与之间有负边 序环构建的网络特征，Chiang等1利用Katz指标提 符号网络G可能为有向图也可能为无向图，当 出一个不平衡测度指标并通过长度为κ的环的平衡 G为有向图时A为非对称矩阵，若G为无向图则A为 程度构建特征集，然后使用逻辑回归模型进行符号 对称矩阵。 预测，当环的长度从3增加到5时，预测精度有所 1.2结构平衡与弱结构平衡理论 提高，但是当k>5后对预测精确度的影响不大。文 结构平衡理论把人与人之间的关系分为积极和 献[14]指出：能够反映符号网络不平衡程度的测度 消极两种，被形式化地描述为符号网络，边的正、负 都可以用于符号预测。文献[15]通过分析两节点间 符号分别表示积极关系和消极关系。此时符号网络 不同的连接形式，提出符号预测的方法，使得在没 中3个节点间的关系共形成4种三角形模体，如图 有共同邻居的情形下的预测精度有所提高：符合符 1所示。从社会心理学角度看，以下结论成立：朋友 号网络局部倾向于结构平衡或弱结构平衡的特征反 的朋友是朋友；朋友的敌人是敌人。据此判定图 过来会促使符号网铬的全局特征出现，因此有很多 1(a)、(b)是平衡的，而图l(c)、(d)是不平衡的。不 利用网络全局结构进行符号预测的方法。文献[16] 平衡的结构具有向平衡结构转换的趋势。在三角形 就从谱分析的角度出发进行符号预测，并指出许多 模体中判断局部平衡性时可以通过三条边符号之积 基于谱分析的方法可以从简单的二值网络扩展到符 来实现：三符号积为正则平衡，否则不平衡。 号网络。他们将拉普拉斯矩阵的定义扩充到符号网 Cartwright和Harary2ol将Heider的社会学结论形 络，通过拉普拉斯矩阵的核函数进行网络符号的预 式化地描述为图结构并证明符号网络平衡的充分必
的符号属性有利于理解网络的基本结构特征，理解 信任和不信任的传播方式。另外，社会符号网络的 边符号属性能够直接反映节点间的态度，因此在推 荐系统[2] 、舆情分析与观点形成[3] 、网络欺凌与社会 排斥[4]等问题中均能通过符号分析获得应用。符号 网络的研究始于 Heider[5]基于社会心理学对人类关 系的研究，而随着复杂网络研究兴起，符号网络的 结构特征与演化规律受到更多研究者的关注[6-7] ，如 何通过部分观测到的网络符号预测未知的边符号成 为符号网络中非常重要的研究方向。 κ κ > 5 符号预测方法大致可以分为两类：1) 考虑网络 局部特征的方法；2) 考虑网络全局特征的方法。考 虑网络局部特征的方法主要利用节点的邻域特征， 如：节点出边、入边的符号以及相邻三元组各边标 注符号特征进行符号预测。这类方法主要基于网络 局部特征以及社会学相关理论实现边符号的预测， 所有基于弱结构平衡[8]和地位理论[9]的预测方法均 要求两节点间具有共同邻居时算法才有效，但统计 结果发现，现实的符号网络中有很大比例的节点不 能构成三元组。Guha 等 [10]最早基于网络模型研究 符号预测问题，他们将信任网络表示为矩阵并运用 不同的矩阵运算代表信任关系在网络上的不同传播 方式，实现了信任关系的预测。Leskovec 等 [11]采用 机器学习的方法对符号预测问题进行了研究，他们 利用节点的出度、入度、节点的嵌入性以及基于地 位理论的所有 16 种待预测边所处的三角形的关系 模式作为特征采用逻辑回归模型训练分类器，得到 了较高的预测精度。文献[12]则通过网络局部特征 和地位理论为特征采用 SVM 算法进行二值分类实 现符号预测。相对于 Leskovec 考虑长度为 3 的有 序环构建的网络特征，Chiang 等 [13]利用 Katz 指标提 出一个不平衡测度指标并通过长度为 的环的平衡 程度构建特征集，然后使用逻辑回归模型进行符号 预测，当环的长度从 3 增加到 5 时，预测精度有所 提高，但是当 后对预测精确度的影响不大。文 献[14]指出：能够反映符号网络不平衡程度的测度 都可以用于符号预测。文献[15]通过分析两节点间 不同的连接形式，提出符号预测的方法，使得在没 有共同邻居的情形下的预测精度有所提高；符合符 号网络局部倾向于结构平衡或弱结构平衡的特征反 过来会促使符号网络的全局特征出现，因此有很多 利用网络全局结构进行符号预测的方法。文献[16] 就从谱分析的角度出发进行符号预测，并指出许多 基于谱分析的方法可以从简单的二值网络扩展到符 号网络。他们将拉普拉斯矩阵的定义扩充到符号网 络，通过拉普拉斯矩阵的核函数进行网络符号的预 测。Hsieh[17]等发现满足弱结构平衡理论的符号网 络其邻接矩阵具有低秩特征，于是将符号预测问题 转化为矩阵填充问题，用低秩填充法有效地进行了 符号预测。他们还将符号预测近似为低秩矩阵分解 问题进行了符号预测。文献[18]也研究了矩阵分解 在符号预测中的应用并解决了数据不平衡对预测精 度的影响。文献[19]提出了一种区别于 Hsieh 以逐 点误差衡量原矩阵与结果矩阵误差的方法，他们将 成对误差应用到矩阵分解的损失函数中，给出的算 法 MF-LiSP 取得了较高精确度。通过以上介绍发 现，符号网络的局部结构特征与全局特征联系紧 密，符号预测方法仅使用局部特征或全局特征都不 够全面，在预测算法中如何同时利用局部和全局特 征是一个值得研究的问题。 受以上研究的启发，从真实网络数据的统计分 析出发，结合节点局部标注特征和网络全局结构特 征设计了一种新的基于低秩矩阵分解的符号预测模 型，解决了符号网由于数据稀疏和网络局部特征利 用不足带来的预测精度不高的问题。 1 相关理论 1.1 基本定义 G G = (V,E,S ) V = {1,2, 3,··· ,n} E = {1,2,3,··· ,m} S = {−1,0,1} i, j ∈ V e(i, j) ∈ E s(i, j) ∈ S O O ⊆ E G A 定义符号网络 为 ，其中 为节点集合， 为边集合， 表示边符号， , , ， 设 为被观测到的边集，则 。符号网络 对应 邻接矩阵 ，其中： Ai j = 1, i与j之间有正边 0, 边符号未知或不存在边 −1, i与j之间有负边 符号网络 G 可能为有向图也可能为无向图，当 G 为有向图时 A 为非对称矩阵，若 G 为无向图则 A 为 对称矩阵。 1.2 结构平衡与弱结构平衡理论 结构平衡理论把人与人之间的关系分为积极和 消极两种，被形式化地描述为符号网络，边的正、负 符号分别表示积极关系和消极关系。此时符号网络 中 3 个节点间的关系共形成 4 种三角形模体，如图 1 所示。从社会心理学角度看，以下结论成立：朋友 的朋友是朋友；朋友的敌人是敌人。据此判定图 1(a)、(b) 是平衡的，而图 1(c)、(d) 是不平衡的。不 平衡的结构具有向平衡结构转换的趋势。在三角形 模体中判断局部平衡性时可以通过三条边符号之积 来实现：三符号积为正则平衡，否则不平衡。 Cartwright 和 Harary[20]将 Heider[2]的社会学结论形 式化地描述为图结构并证明符号网络平衡的充分必 ·438· 智 能 系 统 学 报 第 13 卷
第3期 苏晓萍，等：符号网络的局部标注特征与预测方法 ·439· 要条件是：网络中的节点能够被划分为两个子集， 同时矩阵填充的运算速度较慢，因此矩阵填充也经 每个子集内的所有边均为正，子集间的边均为负。 常用低秩矩阵分解来近似。 ⑧+ (B B + (a)关系模式1(b)关系模式2(c)关系模式3(d关系模式4 图1符号网中4种三角形关系模式 Fig.1 Four relationship patterns of triads in signed net- work 平衡网络的判别条件比较严苛，现实中很难找 到平衡网络的情形，因此Davis⑧放宽结构平衡的约 束提出了弱结构平衡理论，弱结构平衡理论规定： (a)符号网络示例 只要三角形模体中不存在两正一负的关系就构成弱 /011-10000 平衡，在该条件下，图l(a)、(b)、(d)代表的情形均可 1010-10-10 看作平衡的结构。当网络满足弱平衡结构时，节点 110-10-100 可以被分成k个子集，且子集内节点间的边全为正， -10-10 1-100 A= 子集间节点的边全为负。这类符号网也被称为K平 0-101000-1 衡网。 00-1-1.0011 1.3矩阵的秩与结构平衡 0-100010 1 根据弱结构平衡的定义，当符号网络满足k-平 0000-1110 (b)图2(a)对应的邻接矩阵 衡条件时，网络节点可以被分成k个子集，当对网络 节点按编号排序，邻接矩阵将是块对角矩阵。 0 11-1-1-1-1-1 图2(a)给出了一个满足弱平衡网的示例，图中 101-1-1-1-1-1 8个节点被分成3个子集，图2(b)为图2(a)对应的 110:-1-1-1-1-1 邻接矩阵A,若补齐图2(a)中缺失的边，使其成为完 -1-1-101-1-1-1 X= 全图，该图对应的邻接矩阵为块对角矩阵X,块内很 -1-1-1:10:-1-1-1 明显矩阵的秩Rank(X)=3小于矩阵的行列数8。根 -1-1-1-1-1011 据以上分析可知符号网络添加相应具有固定符号的 1 -1-1-1-1101 -1 边将使符号网络向完全K平衡网靠近。 -1-1-1-1110 因此可以把符号预测问题看作矩阵填充问题： (c)图2(a)对应的完全图邻接矩阵 已知被部分观测到的矩阵A,采用矩阵填充的方法 图2弱平衡结构与矩阵的低秩特性 找到矩阵X。此时符号预测问题可被看作优化问 Fig.2 Weakly balanced network and low-rank structure 题：填充矩阵中零值使得目标矩阵X的秩最小。该 2符号预测 问题可形式化描述为 min Rank(X) 当符号预测被近似为低秩矩阵分解问题时，邻 S.t. Xy=A,Ye(i,)∈O, (1) 接矩阵A可被分解为两个κ行列的矩阵P和Q,优 Xe{±1}，He(i,)年O 化目标是使PQ与A之间的误差最小，原矩阵可以 式(1)的目标函数是x矩阵的秩，即其奇异值构 被=(PQ,值填充，就是预测到的用户对用户 成向量的稀疏性，通常上述优化问题是NP难的，而 函数Rank()在矩阵谱范数单位球上的凸包络是矩 的评价。矩阵分解模型可被形式化地描述为 阵的核范数（即矩阵所有奇异值的和），因此可以用 (2) 凸的核范数最小化来近似秩最小化问题，文献[21] 表明：当被观测矩阵均匀抽样且O≥Cμnog2n)'成 式(2)中1为损失函数用于评价预测值与原矩 立时，矩阵X可以以1-n3的概率被恢复。但是对 阵间的误差，后两项为正则化项，用来防止过拟合 于符号网络来说，均匀抽样不容易做到，因为通过 损失函数，可根据具体问题进行选择。虽然上式是 4.1节数据描述可以看到符号网络80%的边为正， 非凸的，但是实践证明该方法在很多矩阵填充问题
要条件是：网络中的节点能够被划分为两个子集， 每个子集内的所有边均为正，子集间的边均为负。 κ κ 平衡网络的判别条件比较严苛，现实中很难找 到平衡网络的情形，因此 Davis[8]放宽结构平衡的约 束提出了弱结构平衡理论，弱结构平衡理论规定： 只要三角形模体中不存在两正一负的关系就构成弱 平衡，在该条件下，图 1(a)、(b)、(d) 代表的情形均可 看作平衡的结构。当网络满足弱平衡结构时，节点 可以被分成 个子集，且子集内节点间的边全为正， 子集间节点的边全为负。这类符号网也被称为 -平 衡网。 1.3 矩阵的秩与结构平衡 κ κ 根据弱结构平衡的定义，当符号网络满足 -平 衡条件时，网络节点可以被分成 个子集，当对网络 节点按编号排序，邻接矩阵将是块对角矩阵。 Rank(X) = 3 κ 图 2(a) 给出了一个满足弱平衡网的示例，图中 8 个节点被分成 3 个子集，图 2(b) 为图 2(a) 对应的 邻接矩阵 A，若补齐图 2(a) 中缺失的边，使其成为完 全图，该图对应的邻接矩阵为块对角矩阵 X，块内很 明显矩阵的秩 小于矩阵的行列数 8。根 据以上分析可知符号网络添加相应具有固定符号的 边将使符号网络向完全 -平衡网靠近。 A X X 因此可以把符号预测问题看作矩阵填充问题： 已知被部分观测到的矩阵 ，采用矩阵填充的方法 找到矩阵 。此时符号预测问题可被看作优化问 题：填充矩阵中零值使得目标矩阵 的秩最小。该 问题可形式化描述为 min Rank(X) s.t. Xi j = Ai j,∀e(i, j) ∈ O, Xi j ∈ {±1},∀e(i, j) < O (1) X Rank(X) |O| ⩾ Cµ 4n ( log2n )2 1−n −3 式 (1) 的目标函数是 矩阵的秩，即其奇异值构 成向量的稀疏性，通常上述优化问题是 NP 难的，而 函数 在矩阵谱范数单位球上的凸包络是矩 阵的核范数 (即矩阵所有奇异值的和)，因此可以用 凸的核范数最小化来近似秩最小化问题，文献[21] 表明：当被观测矩阵均匀抽样且 成 立时，矩阵 X 可以以 的概率被恢复。但是对 于符号网络来说，均匀抽样不容易做到，因为通过 4.1 节数据描述可以看到符号网络 80% 的边为正， 同时矩阵填充的运算速度较慢，因此矩阵填充也经 常用低秩矩阵分解来近似。 2 符号预测 A κ n P TQ rˆi j = (P TQ)i j rˆi j i j 当符号预测被近似为低秩矩阵分解问题时，邻 接矩阵 可被分解为两个 行 列的矩阵 P T 和 Q，优 化目标是使 与 A 之间的误差最小，原矩阵可以 被 值填充， 就是预测到的用户 对用户 的评价。矩阵分解模型可被形式化地描述为 min PT,Q∈Rk×n C = ∑ e(i, j)∈O l(Ai j, ∑κ k=1 PikQk j)+λ∥P∥ 2 +λ∥Q∥ 2 (2) 式 (2) 中 l 为损失函数用于评价预测值与原矩 阵间的误差，后两项为正则化项，用来防止过拟合 损失函数，可根据具体问题进行选择。虽然上式是 非凸的，但是实践证明该方法在很多矩阵填充问题 A B C + + + A B C − − + A B C + + − A B C − − − (a) ڟ㈧Ὅᐻ1 (b) ڟ㈧Ὅᐻ2 (c) ڟ㈧Ὅᐻ3 (d) ڟ㈧Ὅᐻ4 图 1 符号网中 4 种三角形关系模式 Fig. 1 Four relationship patterns of triads in signed network + + + + + + + 1 2 3 4 5 6 7 8 − − − − − − − (a) 符号网络示例 0 1 1 -1 0 0 0 0 1 0 1 0 -1 0 -1 0 1 1 0 -1 0 -1 0 0 -1 0 -1 0 1 -1 0 0 0 -1 0 1 0 0 0 -1 0 0 -1 -1 0 0 1 1 0 -1 0 0 0 1 0 1 = 0 0 0 0 -1 1 1 0 A 0 1 1 -1 -1 -1 -1 -1 1 0 1 -1 -1 -1 -1 -1 1 1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 1 0 -1 -1 -1 -1 -1 -1 -1 -1 0 1 1 -1 -1 -1 -1 -1 1 0 1 -1 -1 -1 -1 -1 1 1 0 = X (b) 图2(a)对应的邻接矩阵 (c) 图2(a)对应的完全图邻接矩阵 图 2 弱平衡结构与矩阵的低秩特性 Fig. 2 Weakly balanced network and low-rank structure 第 3 期 苏晓萍，等：符号网络的局部标注特征与预测方法 ·439·
·440· 智能系统学报 第13卷 中均取得了很好的预测效果。 模型得到的符号预测结果为=(PQ)。因此，以 基本矩阵分解模型充分利用了邻接矩阵的全局 式(4)为目标函数的优化方法，不但考虑了符号网 低秩特性，但是，在被符号网络所代表的社会关系 的全局低秩特性还考虑了待预测边两端节点的局部 网中，不同节点的标注行为常常具有偏置现象：网 标注特征，与基本模型相似，添加了关于局部特征 络“喷子”也被称为Tro”的节点，该类节点为引起 项的正则化项Ui2+Ujm防止过拟合。 别人的注意会故意攻击其他人，“Troll'"节点会发出 损失函数I可以有多种选择，本文选择Square 比其余节点更多的负边；与此相对应的，有些节点 1oss为损失函数，于是优化目标函数可写成： 会收到低于平均水平的评价，它们可能受到网络欺 2 凌”，这一现象的社会心理学根源是“认知失调”，人 与-(b+∑P (5) 们通常为保持与他人态度的一致而调整自己的行为 (P++Uioor+Ujn2) 因此而攻击收到过负面评价的人。从真实符号网络 对式（⑤）给出的优化问题可以采用随机梯度下 的统计特征发现，这两类节点在符号网中确实存 降法进行求解，令=A-,+∑PQ通过求梯 在，虽然数量不多但其作用巨大。在符号预测问题 =1 中仅考虑平均后的全局特征并不能完全反映网络结 度以确定优化函数下降方向：那=-24,0+2P.。 ac 构特征，节点的局部标注特征需要在预测模型中得 ac 80: =-2eP:+2Q,同理也可求得目标函数对 以体现。现定义待预测边的局部标注特征为 b=μ+Uiout+Ujim (3) Ui、Ujim的偏导数，由于沿梯度方向相反的方向下 式中：μ为符号网络的平均标注倾向，当μ为负时说 降最快，于是得到如下迭代公式： 明网络用户更倾向于给其他用户以负面评价；μ为正 P:←-P:+a(eQj-AP) (6) Qi←Q1+a(eP:-Qi) (7) 时，则表示网络用户有给其他邻居以正面评价的倾 Uiout Uioat+a(eij-aUiou) (8) 向。设待预测边e(i,)两端的节点为i和j,Uio表示 Ujin -Ujin+a(eij-al jin) (9) 节点i发出的边符号的均值，Ui的值能够反映节 通过反复迭代并不断优化参数，使观测矩阵 点i对相邻节点的局部标注特征：若节点发出的负 A与分解后矩阵B+PQ间的误差小于设定的误差 边数大于正边数，表示节点i给邻居以负面评价的 值即最终收敛。其中α为学习速度，α越大下降就越 可能性大，e(i,)被预测为负的可能性就增加。同 快。随机梯度下降的时间复杂度为O(mk),t为迭代 理，Uj为j收到的边符号的均值，当Uj为负时表示 并收敛次数，m为节点个数，k为秩数。由于符号网 节点j收到了更多的负面评价，因此(i,)被预测为 络满足低秩特性，通常<值很小，且收敛较快，因此 负的可能性就增加。图3给出了符号网络标注的局 采用随机梯度下降法求解最小化问题速度较快。 部偏置示例，设μ=0.2，即符号网络全局有正面评价 的倾向，经计算可得：Uim=[(-1)+(-1)+1]/4=-1/4, 3实验结果与分析 Ujim=-1/4,于是b=-3/10,此时边e(,)的符号预 3.1数据集描述 测结果将向负偏斜。 实验中的3个真实大型社会网络数据来自于斯 坦福大学的SNAP2项目，Epinions给出了用户间 “who-trust-whom”的关系，Slashdot是一个技术相关 的新闻网站，允许用户根据自身观点标记其他用户 图3标注行为的偏置现象 为friend/foe,Wikipedia是维基百科申请管理员身 Fig.3 Bias behavior of signed edges 份的投票关系网，若一个用户被大多数其他用户同 b,的值能够很好地反映待预测边两端节点的局 意则当选为某一学科的管理员负责百科词条的维 部标注行为和行为偏好，将标注偏好反映在预测的 护，若该用户未受到大多数其他用户的赞成票则选 目标函数，得到较基本模型更为精细的预测模型： 举失败。表1给出了3个网络的统计特征。 rC=∑4y-b,+∑P.0u》t 表1的统计结果显示：3个符号网络中正边占 (4) 比均在75%以上，而负边占比较少，互惠边(recip a(lIP+lll+Uioor+Uj2) rocal edges)是指两用户间持有相同态度，这样的互 根据式(4)可知：节点i对节点j的符号可被预 惠边在网络中占有一定比例，且互惠边中正边居 测为=b+(PQ),而式(2)表示的基本矩阵分解 多，这与人们社会心理有关，当一个人讨厌另一个
中均取得了很好的预测效果。 基本矩阵分解模型充分利用了邻接矩阵的全局 低秩特性，但是，在被符号网络所代表的社会关系 网中，不同节点的标注行为常常具有偏置现象：网 络“喷子”也被称为“Troll”的节点，该类节点为引起 别人的注意会故意攻击其他人，“Troll”节点会发出 比其余节点更多的负边；与此相对应的，有些节点 会收到低于平均水平的评价，它们可能受到“网络欺 凌”，这一现象的社会心理学根源是“认知失调”，人 们通常为保持与他人态度的一致而调整自己的行为 因此而攻击收到过负面评价的人。从真实符号网络 的统计特征发现，这两类节点在符号网中确实存 在，虽然数量不多但其作用巨大。在符号预测问题 中仅考虑平均后的全局特征并不能完全反映网络结 构特征，节点的局部标注特征需要在预测模型中得 以体现。现定义待预测边的局部标注特征为 bi j = µ+Uiout +U jin (3) µ µ µ e(i, j) Uiout Uiout e(i, j) U jin j U jin j e(i, j) µ = 0.2 Uiout = [(−1)+(−1)+1] /4 = −1/4 U jin = −1/4 bi j = −3/10 e(i, j) 式中： 为符号网络的平均标注倾向，当 为负时说 明网络用户更倾向于给其他用户以负面评价； 为正 时，则表示网络用户有给其他邻居以正面评价的倾 向。设待预测边 两端的节点为 i 和 j， 表示 节点 i 发出的边符号的均值， 的值能够反映节 点 i 对相邻节点的局部标注特征：若节点发出的负 边数大于正边数，表示节点 i 给邻居以负面评价的 可能性大， 被预测为负的可能性就增加。同 理， 为 收到的边符号的均值，当 为负时表示 节点 收到了更多的负面评价，因此 被预测为 负的可能性就增加。图 3 给出了符号网络标注的局 部偏置示例，设 ，即符号网络全局有正面评价 的倾向，经计算可得： ， ，于是 ，此时边 的符号预 测结果将向负偏斜。 bi j 的值能够很好地反映待预测边两端节点的局 部标注行为和行为偏好，将标注偏好反映在预测的 目标函数，得到较基本模型更为精细的预测模型： min PT,Q∈Rk×n C = ∑ e(i, j)∈O l(Ai j −(bi j + ∑κ k=1 PikQk j))+ λ(∥P∥ 2 1 +∥Q∥ 2 1 +Uiout 2 +U jin 2 ) (4) rˆi j = bi j +(P TQ)i j 根据式 (4) 可知：节点 i 对节点 j 的符号可被预 测为 ，而式 (2) 表示的基本矩阵分解 rˆi j = (P TQ)i j Uiout 2 +U jin 2 模型得到的符号预测结果为 。因此，以 式 (4) 为目标函数的优化方法，不但考虑了符号网 的全局低秩特性还考虑了待预测边两端节点的局部 标注特征，与基本模型相似，添加了关于局部特征 项的正则化项 防止过拟合。 损失函数 l 可以有多种选择，本文选择 Square_ loss 为损失函数，于是优化目标函数可写成： min PT,Q∈Rk×n C = ∑ e(i, j)∈O Ai j −(bi j + ∑κ k=1 PikQk j) 2 + λ(∥P∥ 2 1 +∥Q∥ 2 1 +Uiout 2 +U jin 2 ) (5) ei j = Ai j −(bi j + ∑κ k=1 PikQk j) ∂C ∂Pi = −2ei jQj +2λPi ∂C ∂Qj = −2ei jPi +2λQj Uiout U jin 对式 (5) 给出的优化问题可以采用随机梯度下 降法进行求解，令 ，通过求梯 度以确定优化函数下降方向： ， ，同理也可求得目标函数对 、 的偏导数，由于沿梯度方向相反的方向下 降最快，于是得到如下迭代公式： Pi ← Pi +α(ei jQj −λPi) (6) Qj ← Qj +α(ei jPi −λQj) (7) Uiout ← Uiout +α(ei j −λUiout) (8) U jin ← U jin +α(ei j −λU jin) (9) B+ P TQ α α O(tmκ) t m κ κ 通过反复迭代并不断优化参数，使观测矩阵 A 与分解后矩阵 间的误差小于设定的误差 值即最终收敛。其中 为学习速度， 越大下降就越 快。随机梯度下降的时间复杂度为 ， 为迭代 并收敛次数， 为节点个数， 为秩数。由于符号网 络满足低秩特性，通常 值很小，且收敛较快，因此 采用随机梯度下降法求解最小化问题速度较快。 3 实验结果与分析 3.1 数据集描述 实验中的 3 个真实大型社会网络数据来自于斯 坦福大学的 SNAP2 项目，Epinions 给出了用户间 “who-trust-whom”的关系，Slashdot 是一个技术相关 的新闻网站，允许用户根据自身观点标记其他用户 为 friend/foe，Wikipedia 是维基百科申请管理员身 份的投票关系网，若一个用户被大多数其他用户同 意则当选为某一学科的管理员负责百科词条的维 护，若该用户未受到大多数其他用户的赞成票则选 举失败。表 1 给出了 3 个网络的统计特征。 表 1 的统计结果显示：3 个符号网络中正边占 比均在 75% 以上，而负边占比较少，互惠边 (reciprocal edges) 是指两用户间持有相同态度，这样的互 惠边在网络中占有一定比例，且互惠边中正边居 多，这与人们社会心理有关，当一个人讨厌另一个 i j ? + + − − − − e(i, j) 图 3 标注行为的偏置现象 Fig. 3 Bias behavior of signed edges ·440· 智 能 系 统 学 报 第 13 卷
第3期 苏晓萍，等：符号网络的局部标注特征与预测方法 ·441· 人反应的是不予理睬，“爱的反义词不是恨而是冷 式中：p:为第i个观测值，a为第i个真实值，RMSE 漠”。而一个人对另一个人的示好通常显示出“镜子 值越小预测误差越小。图4(a)、(b)、(c)给出了3个 效应”。统计结果还发现：发出50%以上负边的节 符号网络在不同抽样比率下的RMSE值。 点只占网络节点极少部分，且大部分的负边都是由 0.96 些特定节点发出的，这些节点充满反社会特征， MF-Bias 0.95 并通过攻击别人博取别人的关注，这些节点发出的 -ID 0.94◆0D 新边为负的可能性极大，而收到50%以上负边的节 0.93 点也的确存在，即“网络欺凌”是事实，存在“人云亦 0.92 云”的现象。统计结果还显示，符号网络中有一定比 0.91 例的节点无法构成三元组，此时基于结构平衡理论 0.90 的预测算法将失效。 0.89 表1数据集统计特征 0.8 0.1 0.20.30.40.50.60.70.80.9 Table 1 Statistics of datasets 训练集数据占比% 数据集 (a)数据集Epinions的预测精度 统计特征 Epinions Slashdot Wikipedia 0.90 -ME-Bias 节点数 13182882144 7118 0.884 边总数 841372549202104357 ◆OD 0.86 正边占比% 85.3 77.4 78.4 负边占比% 14.7 22.6 21.6 084 互惠正边占比% 30.2 17.0 5.1 0.82 互患负边占比% 0.30 0.31 0.28 0.80 发出50%以上负边占比% 7.9 6.7 16.9 收到50%以上负边占比% ，” 15.1 19.0 12.2 0.78 .10.20.30.40.50.60.70.80.9 非三元组边占比% 20.2 44.8 8.1 训练集数据占比% (b)数据集Slashdof的预测精度 3.2预测效果与分析 0.90. 为证明所提带有偏置的矩阵分解模型MF-Bias MF-Bias M (matrix factorization with bias)对符号预测问题的有 0.88 OD 效性，将它与以下基准预测算法进行比较。 0.86 l)OutDegree(简写为OD):若d()≥d,则被 0.84 预测边(i,)的符号为正，反之为负。 0.82 2)InDegree(简写为ID):若d()≥d),则被预 测边i,)的符号为正，反之为负。 0.80 3)LR(logistic regression)":将符号预测问题 0.78 0 .10.20.30.40.50.60.70.80.9 看作二值分类问题，采用逻辑回归模型训练分类 训练集数据占比% 器，得到了较高的预测精度。 (c)数据集Wikipedial的预测精度 4)Mf(matrix factorization)m:由Hsieh等提出 0.70 的基本矩阵分解模型。 0.65 3.2.1评价指标 0.60 I)均方根误差(RMSE) 它是衡量模型误差率的常用方法，反映了观测 值与真值偏差的平方和观测次数n比值的平方根， 050 0.45 -Bias 计算公式为 0.40 LR --ID OD (p-a)月 0.3 0.10.20.30.40.50.60.70.80.9 训练集数据占比% RMSE (10) (d数据集Epinions的预测误差
人反应的是不予理睬，“爱的反义词不是恨而是冷 漠”。而一个人对另一个人的示好通常显示出“镜子 效应”。统计结果还发现：发出 50% 以上负边的节 点只占网络节点极少部分，且大部分的负边都是由 一些特定节点发出的，这些节点充满反社会特征， 并通过攻击别人博取别人的关注，这些节点发出的 新边为负的可能性极大，而收到 50% 以上负边的节 点也的确存在，即“网络欺凌”是事实，存在“人云亦 云”的现象。统计结果还显示，符号网络中有一定比 例的节点无法构成三元组，此时基于结构平衡理论 的预测算法将失效。 3.2 预测效果与分析 为证明所提带有偏置的矩阵分解模型 MF-Bias (matrix factorization with bias) 对符号预测问题的有 效性，将它与以下基准预测算法进行比较。 d + out(i) ⩾ d − out e(i, j) 1) OutDegree(简写为 OD)：若 ，则被 预测边 的符号为正，反之为负。 d + in(j) ⩾ d − in(j) e(i, j) 2) InDegree(简写为 ID)：若 ，则被预 测边 的符号为正，反之为负。 3) LR (logistic regression)[11] ：将符号预测问题 看作二值分类问题，采用逻辑回归模型训练分类 器，得到了较高的预测精度。 4) MF(matrix factorization)[17] ：由 Hsieh 等提出 的基本矩阵分解模型。 3.2.1 评价指标 1) 均方根误差 (RMSE) 它是衡量模型误差率的常用方法，反映了观测 值与真值偏差的平方和观测次数 n 比值的平方根， 计算公式为 RMSE = vuuuuut∑n i=1 (pi −ai) 2 n (10) pi i ai 式中： 为第 个观测值， 为第 i 个真实值，RMSE 值越小预测误差越小。图 4(a)、(b)、(c) 给出了 3 个 符号网络在不同抽样比率下的 RMSE 值。 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.88 0.89 0.90 0.91 0.92 0.93 0.94 0.95 0.96 精确度/% 训练集数据占比/% (a) 数据集Epinions的预测精度 MF−Bias MF LR ID OD MF−Bias MF LR ID OD 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.78 0.80 0.82 0.84 0.86 0.88 0.90 训练集数据占比/% (b) 数据集Slashdo的预测精度 精确度/% MF−Bias MF LR ID OD 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.78 0.80 0.82 0.84 0.86 0.88 0.90 训练集数据占比/% (c) 数据集Wikipedia的预测精度 精确度/% MF−Bias MF LR ID OD 均方根误差 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.35 0.40 0.45 0.50 0.55 0.60 0.65 0.70 训练集数据占比/% (d) 数据集Epinions的预测误差 表 1 数据集统计特征 Table 1 Statistics of datasets 统计特征 数据集 Epinions Slashdot Wikipedia 节点数 131 828 82 144 7 118 边总数 841 372 549 202 104 357 正边占比/% 85.3 77.4 78.4 负边占比/% 14.7 22.6 21.6 互惠正边占比/% 30.2 17.0 5.1 互惠负边占比/% 0.30 0.31 0.28 发出 50% 以上负边占比/% 7.9 6.7 16.9 收到 50% 以上负边占比/% 15.1 19.0 12.2 非三元组边占比/% 20.2 44.8 8.1 第 3 期 苏晓萍，等：符号网络的局部标注特征与预测方法 ·441·
·442· 智能系统学报 第13卷 0.95 后使α值衰减（α*=0.9），目的是使算法尽快收敛，最 0.90 大迭代次数为30次。得到的预测结果是符号网上 0.85 两节点间以正或负的符号相连的倾向，这一预测值 并不是离散的±1而是连续的值，因此得到预测结果 会070 后需要对预测结果进行划分，划分方法有直接划 0.65 分、全局划分、局部划分、从众划分，本文采用直 0.60 接划分，即预测结果≥0则预测符号为正，否则为 0.5 负。以下通过均方根误差(RMSE)和预测精确性 0.10.20.30.40.50.60.70.80.9 训练集数据占比% (Accuracy)评价各算法的预测效果。 (e)数据集Slashdotf的预测误差 3.2.3实验结果及讨论 0.95 图4的实验结果显示：随着抽样数据的增加， 0.90 MF-Bias 预测误差(RMSE)减小，预测精确度增加。基于低 0.85 秩矩阵分解的方法（包括MF、MF-Bias)获得了比其 0.80 ◆OD 他算法更好的预测效果，这说明在符号网络中节点 标注的偏置现象确实存在，同时，由于MF-Bias充 0.65 分考虑了节点的局部偏置特性，得到了相较于基本 0.60 矩阵分解算法好的预测精度，例如：在数据集Epin- 0.5 ions上当训练集为90%时，预测精确度为95.04%， 0.10.20.30.40.50.60.70.80.9 训练集数据占比% 相较于基本矩阵分解方法提高了0.6%，LR方法提 (①数据集Vikipedia的预测误差 高了2.3%，在其他两个数据集上也得到了与图4a) 图43个符号网络的预测结果 相似的结果（见图4(b)~(c),RMSE误差分析结果 Fig.4 Three signed networks predicted results (见图4(d)(①)与预测精确度得到相似的结论：本文 2)精确性(Accuracy) 所提MF-Bias模型获得了最小预测误差。实验表 用于评价预测算法对符号预测的准确程度，精 明：带有偏置的矩阵分解方法能够很好地对抗数据 确性计算公式为 稀疏带来的问题并提高预测效果。尽管两种启发式 TP+TN Accuracy P+N (11) 算法(D和OD)的预测精度都低于矩阵分解模型 和逻辑回归模型，但是它们的特点是计算复杂度 式中：TP表示对符号为正的边的预测正确的数目， 低，因为它们仅仅使用待预测边两端节点的局部信 TN表示符号为负的预测正确的数目，P+N则是需 息且能在一定程度上反映数据的结构特性。不同数 要预测的边的总数。Accuracy的值越大表示预测 据集ID和OD的效果截然不同，在Slashdot上OD 成功的概率越高。图4(d)、(e)、()给出了3个符号 好于ID,在Wiki上ID好于OD,可见仅考虑出度 网络在不同抽样比率下的精确性实验结果。 或入度作为预测依据不够合理，用户在不同数据集 3.2.2实验参数设置 上的行为特征值得进一步思考。 给定部分观察的符号网络，符号推断的目标就 3.3秩与预测精度 是通过符号网中已知边符号推断出未知边的符号。 本文构建的符号网络模型为有向网络，需要说明的 根据1.3节可知，符号网络邻接矩阵的秩与弱 是，所提算法也适用于无向符号网络。实验采用随 平衡结构间存在必然联系：当符号网络满足k平衡 机抽样的方法将数据集分为训练集(training data 条件时，网络节点可以被分成k个子集，邻接矩阵具 set)和测试集(testing data set)。训练集被看作部分 有低秩性且矩阵的秩恰好等于k,而矩阵分解的本质 观测的符号网络，利用测试集训练模型，然后对测 是做降维操作，将会把邻接矩阵分解为2个k行列 试集中边符号进行预测：测试集分别为整个符号网 的矩阵，那么到底将邻接矩阵分解为多少行合适 络的15%，30%，，90%。对于MF和MF-Bias算 呢？本文分别令k=1、2、4、5、6、7、8、16、32,对两 法，首先需要对矩阵P、Q进行初始化，这里我们令其 种矩阵分解算法在3个数据集进行精确度测试，所 为全1矩阵，有时也将P、Q的初始值设为随机矩 有实验均取测试集为90%，其余各参数与3.2节相 阵。另外，模型还需要确定3个参数，即k、α和入，其 同。实验结果如图5所示，实验结果显示：相较于 中K为符号网络的秩，取k=5;入为惩罚因子，取 k=1,k=2时预测精度有大幅提高，这支持了1.4节 =0.12;α是学习速度，初始值取a=0.2,且每次迭代 所述结构平衡理论的正确性，k值从2~5预测精度
2) 精确性 (Accuracy) 用于评价预测算法对符号预测的准确程度，精 确性计算公式为 Accuracy = TP+TN P+N (11) TP TN P+N 式中： 表示对符号为正的边的预测正确的数目， 表示符号为负的预测正确的数目， 则是需 要预测的边的总数。Accuracy 的值越大表示预测 成功的概率越高。图 4(d)、(e)、(f) 给出了 3 个符号 网络在不同抽样比率下的精确性实验结果。 3.2.2 实验参数设置 ··· P Q P Q κ α λ κ κ λ λ α α 给定部分观察的符号网络，符号推断的目标就 是通过符号网中已知边符号推断出未知边的符号。 本文构建的符号网络模型为有向网络，需要说明的 是，所提算法也适用于无向符号网络。实验采用随 机抽样的方法将数据集分为训练集 (training data set) 和测试集 (testing data set)。训练集被看作部分 观测的符号网络，利用测试集训练模型，然后对测 试集中边符号进行预测；测试集分别为整个符号网 络的 15%，30%， ，90%。对于 MF 和 MF-Bias 算 法，首先需要对矩阵 、 进行初始化，这里我们令其 为全 1 矩阵，有时也将 、 的初始值设为随机矩 阵。另外，模型还需要确定 3 个参数，即 、 和 ，其 中 为符号网络的秩，取 = 5 ； 为惩罚因子，取 =0.12； 是学习速度，初始值取 =0.2，且每次迭代 后使α值衰减 (α*=0.9)，目的是使算法尽快收敛，最 大迭代次数为 30 次。得到的预测结果是符号网上 两节点间以正或负的符号相连的倾向，这一预测值 并不是离散的±1 而是连续的值，因此得到预测结果 后需要对预测结果进行划分，划分方法有直接划 分、全局划分、局部划分、从众划分[14] ，本文采用直 接划分，即预测结果≥0 则预测符号为正，否则为 负。以下通过均方根误差 (RMSE) 和预测精确性 (Accuracy) 评价各算法的预测效果。 3.2.3 实验结果及讨论 图 4 的实验结果显示：随着抽样数据的增加， 预测误差 (RMSE) 减小，预测精确度增加。基于低 秩矩阵分解的方法 (包括 MF、MF-Bias) 获得了比其 他算法更好的预测效果，这说明在符号网络中节点 标注的偏置现象确实存在，同时，由于 MF-Bias 充 分考虑了节点的局部偏置特性，得到了相较于基本 矩阵分解算法好的预测精度，例如：在数据集 Epinions 上当训练集为 90% 时，预测精确度为 95.04%， 相较于基本矩阵分解方法提高了 0.6%，LR 方法提 高了 2.3%，在其他两个数据集上也得到了与图 4(a) 相似的结果 (见图 4(b)~(c))，RMSE 误差分析结果 (见图 4(d)~(f)) 与预测精确度得到相似的结论：本文 所提 MF-Bias 模型获得了最小预测误差。实验表 明：带有偏置的矩阵分解方法能够很好地对抗数据 稀疏带来的问题并提高预测效果。尽管两种启发式 算法 (ID 和 OD) 的预测精度都低于矩阵分解模型 和逻辑回归模型，但是它们的特点是计算复杂度 低，因为它们仅仅使用待预测边两端节点的局部信 息且能在一定程度上反映数据的结构特性。不同数 据集 ID 和 OD 的效果截然不同，在 Slashdot 上 OD 好于 ID，在 Wiki 上 ID 好于 OD，可见仅考虑出度 或入度作为预测依据不够合理，用户在不同数据集 上的行为特征值得进一步思考。 3.3 秩与预测精度 κ κ κ κ n κ κ κ κ 根据 1.3 节可知，符号网络邻接矩阵的秩与弱 平衡结构间存在必然联系：当符号网络满足 -平衡 条件时，网络节点可以被分成 个子集，邻接矩阵具 有低秩性且矩阵的秩恰好等于 ，而矩阵分解的本质 是做降维操作，将会把邻接矩阵分解为 2 个 行 列 的矩阵，那么到底将邻接矩阵分解为多少行合适 呢？本文分别令 =1、2、4、5、6、7、8、16、32，对两 种矩阵分解算法在 3 个数据集进行精确度测试，所 有实验均取测试集为 90%，其余各参数与 3.2 节相 同。实验结果如图 5 所示，实验结果显示：相较于 =1， =2 时预测精度有大幅提高，这支持了 1.4 节 所述结构平衡理论的正确性， 值从 2~5 预测精度 ᵥ䄛ጚ 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.55 0.60 0.65 0.70 0.75 0.80 0.85 0.90 0.95 䃙㏯䯲ᢚࢌ%/a/c (e) ᢚ䯲Slashdot⮰䶰≷䄛ጚ MF−Bias MF LR ID OD ᵥ䄛ጚ 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 0.55 0.60 0.65 0.70 0.75 0.80 0.85 0.90 0.95 䃙㏯䯲ᢚࢌ%/a/c (f) ᢚ䯲Wikipedia⮰䶰≷䄛ጚ MF−Bias MF LR ID OD 图 4 3 个符号网络的预测结果 Fig. 4 Three signed networks predicted results ·442· 智 能 系 统 学 报 第 13 卷
第3期 苏晓萍，等：符号网络的局部标注特征与预测方法 ·443· 有较大幅度提高，大部分数据集在k=7时预测精度 提高运算速度，当然负面影响会带来一定预测效果 达到最优(Slashdot数据集在k=5时精确度最优)， 的下降。如何充分利用局部信息的研究还显得不 k≥7后预测精度变化不大。实验结果与Chiang等 足，如节点间除了出度和入度还有哪些连接特点能 在文献[13]中得到的结论一致，也证明符号网络邻 用结构平衡理论或地位理论来解释。当节点间的嵌 接矩阵的低秩特性明显。实验还发现：比起基本矩 入性很低时结构平衡等社会学理论将失效，怎样保 阵分解算法，带偏置的矩阵分解算法对x值更加鲁 证预测的精确度？ 棒，即随着x的变化符号预测的精确度变化不大，这 另外，还需进一步丰富符号网络结构的理论研 是因为在带偏置的矩阵分解模型中节点及其邻居的 究，目前用于符号预测的理论只有结构平衡理论和 特征与低秩特性共同决定模型的精确度，因此获得 地位理论，近年并未有较大突破。也就是说，对符 了较高的精确度，这也证明节点的局部特性对预测 号网络结构演化、动力学行为的分析仍然不能解释 效果有影响。 符号网络结构的形成，从而制约了符号预测方法的 0.96 进一步发展，根据33节的研究发现本文所提算法 0.94 对矩阵的秩鲁棒，及在秩取5和7时预测效果最 0.92 好，这一结果的深层社会学理论含义及其与符号网 0.90 络形成机制间的联系将另文讨论。这也是下一步将 =0.88 Epinions- 要研究的内容。 0.86 dot-SI-ME 符号网络作为近年来从基本复杂网络衍生出的 0.84 LB-ME 0.82 Wiki-s 新网络模型和符号预测问题作为新模型上的新问 1245678 16 题，人们对它们的理解还远远不够，符号网络的拓 矩阵秩 扑结构、动力学行为以及在个性化推荐、态度预测、 图5预测精度与矩阵的秩k间的关系 用户特征分析与聚类等方面的应用将会受到更多的 Fig.5 The relation between prediction accuracy and k 研究和关注。 4结束语 参考文献： 真实的复杂系统中对立关系普遍存在，利用符 []程苏琦，沈华伟，张国清，等.符号网络研究综述).软件学 号网络对这些复杂系统建模能够很好地表达节点间 报，2014,25(1)：1-15 的对立关系，符号属性对分析、理解复杂网络的拓 CHENG Suqi,SHEN Huawei,ZHANG Guoqing et al.Sur- 扑结构、功能、动力学行为具有十分重要的理论意 vey of signed network research[J].Journal of software, 义。要利用符号属性，首要的问题就是对未知边符 2014,25(1):1-15 号的正确预测。本文对已有的符号网络预测方法进 [2]TANG Jiliang,AGGARWAL C,LIU Huan.Recommenda- 行了分类和总结。为了同时利用节点的局部特征和 tions in signed social networks[Cl//Proceedings of the 25th 全局特征进行符号预测，在基于利用网络全局特征 International Conference on World Wide Web.Montreal 的低秩矩阵分解方法的基础上改写优化目标函数使 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,97):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. 展：1)进一步利用丰富的元数据信息，因为元数据 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 降低；2)降低模型复杂度以适应于数量巨大的在线 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
κ κ κ κ κ 有较大幅度提高，大部分数据集在 =7 时预测精度 达到最优 (Slashdot 数据集在 =5 时精确度最优)， ≥7 后预测精度变化不大。实验结果与 Chiang 等 在文献[13]中得到的结论一致，也证明符号网络邻 接矩阵的低秩特性明显。实验还发现：比起基本矩 阵分解算法，带偏置的矩阵分解算法对 值更加鲁 棒，即随着 的变化符号预测的精确度变化不大，这 是因为在带偏置的矩阵分解模型中节点及其邻居的 特征与低秩特性共同决定模型的精确度，因此获得 了较高的精确度，这也证明节点的局部特性对预测 效果有影响。 4 结束语 真实的复杂系统中对立关系普遍存在，利用符 号网络对这些复杂系统建模能够很好地表达节点间 的对立关系，符号属性对分析、理解复杂网络的拓 扑结构、功能、动力学行为具有十分重要的理论意 义。要利用符号属性，首要的问题就是对未知边符 号的正确预测。本文对已有的符号网络预测方法进 行了分类和总结。为了同时利用节点的局部特征和 全局特征进行符号预测，在基于利用网络全局特征 的低秩矩阵分解方法的基础上改写优化目标函数使 之能够描述待预测边两端节点的出度和入度局部特 征，给出了带有偏置的低秩矩阵分解方法。实验结 果证实：添加节点局部特征后的低秩矩阵分解方法 能够得到较其他基准算法好的预测效果，且互惠信 息能够进一步提高预测精度。 未来符号预测的研究方向会向两个不同方向发 展：1) 进一步利用丰富的元数据信息，因为元数据 蕴含了用户间的熟识度、声誉、语义与态度等重要 信息，元数据可以在缺少结构信息时保证预测精 度，当然付出的代价是模型复杂度升高，运算速度 降低；2) 降低模型复杂度以适应于数量巨大的在线 符号网络挖掘，此时基于网络局部信息的符号预测 方法具有优势，因为这类算法易于被并行化，从而 提高运算速度，当然负面影响会带来一定预测效果 的下降。如何充分利用局部信息的研究还显得不 足，如节点间除了出度和入度还有哪些连接特点能 用结构平衡理论或地位理论来解释。当节点间的嵌 入性很低时结构平衡等社会学理论将失效，怎样保 证预测的精确度？ 另外，还需进一步丰富符号网络结构的理论研 究，目前用于符号预测的理论只有结构平衡理论和 地位理论，近年并未有较大突破。也就是说，对符 号网络结构演化、动力学行为的分析仍然不能解释 符号网络结构的形成，从而制约了符号预测方法的 进一步发展，根据 3.3 节的研究发现本文所提算法 对矩阵的秩鲁棒，及在秩取 5 和 7 时预测效果最 好，这一结果的深层社会学理论含义及其与符号网 络形成机制间的联系将另文讨论。这也是下一步将 要研究的内容。 符号网络作为近年来从基本复杂网络衍生出的 新网络模型和符号预测问题作为新模型上的新问 题，人们对它们的理解还远远不够，符号网络的拓 扑结构、动力学行为以及在个性化推荐、态度预测、 用户特征分析与聚类等方面的应用将会受到更多的 研究和关注。 参考文献： 程苏琦, 沈华伟, 张国清,等. 符号网络研究综述[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. [1] 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. [2] LI Dong, XU Zhiming, CHAKRABORTY N, et al. Polarity related influence maximization in signed social networks[J]. PLoS one, 2014, 9(7): e102199. [3] EVERETT M G, BORGATTI S P. Networks containing negative ties[J]. Social networks, 2014, 38: 111–120. [4] HEIDER F. Attitudes and cognitive organization[J]. The Journal of psychology: interdisciplinary and applied, 1946, 21(1): 107–112. [5] 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. [6] CHU Lingyang, WANG Zhefeng, PEI Jian, et al. Finding gangs in war from signed networks[C]//Proceedings of the [7] 1 2 4 5 6 7 8 16 0.82 0.84 0.86 0.88 0.90 0.92 0.94 0.96 矩阵秩/k 精确度 Epinions−SLB−MF Epinions−SL−MF Slashdot−SLB−MF Slashdot−SL−MF Wiki−SLB−MF Wiki−SL−MF 图 5 预测精度与矩阵的秩κ间的关系 Fig. 5 The relation between prediction accuracy and κ 第 3 期 苏晓萍，等：符号网络的局部标注特征与预测方法 ·443·
·444· 智能系统学报 第13卷 22nd ACM SIGKDD International Conference on Know- Spectral analysis of signed graphs for clustering,predic- ledge Discovery and Data Mining.San Francisco,USA, tion and visualization[C]//Proceedings of the 2010 SIAM 2016:1505-1514. International Conference on Data Mining.Columbus,USA, [8]DAVIS J A.Clustering and structural balance in graphs[J]. 2010:559-570. Human relations,1967,20(2):181-187. [17]HSIEH C J,CHIANG K Y,DHILLON I S.Low rank mod- 9]LESKOVEC J,HUTTENLOCHER D,KLEINBERG J. eling of signed networks[C]//Proceedings of the 18th ACM Signed networks in social media[C]//Proceedings of the SIGKDD International Conference on Knowledge Discov- SIGCHI Conference on Human Factors in Computing Sys- ery and Data Mining.Beijing,China,2012:507-515. tems.Atlanta,USA,2010:1361-1370. [18]MENON A K,ELKAN C.Link prediction via matrix fac- [10]GUHA R,KUMAR R,RAGHAVAN P,et al.Propagation torization[C]//Proceedings of the 2011 European Confer- of trust and distrust[C]//Proceedings of the 13th Interna- ence on Machine Learning and Knowledge Discovery in tional Conference on World Wide Web.New York,USA, Databases.Athens,Greece,2011:437-452. 2004:403-412. [19]AGRAWAL P,GARG V K,NARAYANAM R.Link la- [11]LESKOVEC J,HUTTENLOCHER D,KLEINBERG J. bel prediction in signed social networks[Cl//Proceedings of Predicting positive and negative links in online social net- the 23rd International Joint Conference on Artificial Intelli- works[C]//Proceedings of the 19th International Confer- gence.Beijing,China,2013:2591-2597. ence on World Wide Web.Raleigh,USA,2010:641-650. [20]CARTWRIGHT D,HARARY F.Structural balance:a gen- [12]WANG Guannan,GAO Hui,CHEN Lian,et al.Predicting eralization of Heider's theory[J].Psychological review, positive and negative relationships in large social net- 1956,63(5):277-293 works[J.PLoS one,2015,10(6):e0129530. [21]CANDES E J,TAO T.The power of convex relaxation: near-optimal matrix completion[J].IEEE transactions on [13]CHIANG K Y,NATARAJAN N,TEWARI A,et al.Ex- information theory,2010,56(5):2053-2080. ploiting longer cycles for link prediction in signed net- works[Cl//Proceedings of the 20th ACM international Con- 作者简介： ference on Information and Knowledge Management.Glas- 苏晓萍，女，1971年生，教授，主 gow,Scotland,UK,2011:1157-1162. 要研究方向为复杂网络上动态信息传 [14纠蓝梦微，李翠平，王绍卿，等.符号社会网络中正负关系 播、信息检索。主持省部级项目2项， 预测算法研究综述).计算机研究与发展，2015,52(2)： 发表学术论文10余篇。 410-422 LAN Mengwei,LI Cuiping,Wang Shaoging,et al.Survey of sign prediction algorithms in signed social networks[J]. Journal of computer research and development,2015, 宋玉蓉，女，1971年生，教授，博 士生导师，博士，主要研究方向为复杂 52(2):410-422 网络上动态信息传播、网络控制与优 [15]SONG Dongjin,MEYER D A.Link sign prediction and 化。主持国家自然科学基金项目2项 ranking in signed directed social networks[J].Social net- 教育部人文社科项目1项，发表学术 work analysis and mining,2015,5:52 论文30余篇，被SCI、EI收录多篇。 [16]KUNEGIS J,SCHMIDT S,LOMMATZSCH A,et al
22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. San Francisco, USA, 2016: 1505–1514. DAVIS J A. Clustering and structural balance in graphs[J]. Human relations, 1967, 20(2): 181–187. [8] 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. [9] 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. [10] 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. [11] WANG Guannan, GAO Hui, CHEN Lian, et al. Predicting positive and negative relationships in large social networks[J]. PLoS one, 2015, 10(6): e0129530. [12] 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. [13] 蓝梦微, 李翠平, 王绍卿, 等. 符号社会网络中正负关系 预测算法研究综述[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. [14] SONG Dongjin, MEYER D A. Link sign prediction and ranking in signed directed social networks[J]. Social network analysis and mining, 2015, 5: 52. [15] [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. 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. [17] 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. [18] 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. [19] CARTWRIGHT D, HARARY F. Structural balance: a generalization of Heider’s theory[J]. Psychological review, 1956, 63(5): 277–293. [20] 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. [21] 作者简介： 苏晓萍，女，1971 年生，教授，主 要研究方向为复杂网络上动态信息传 播、信息检索。主持省部级项目 2 项， 发表学术论文 10 余篇。 宋玉蓉，女，1971 年生，教授，博 士生导师，博士，主要研究方向为复杂 网络上动态信息传播、网络控制与优 化。主持国家自然科学基金项目 2 项、 教育部人文社科项目 1 项，发表学术 论文 30 余篇，被 SCI、EI 收录多篇。 ·444· 智 能 系 统 学 报 第 13 卷