第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·