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