第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. Sur￾vey of signed network research[J]. Journal of software, 2014, 25(1): 1–15. [1] TANG Jiliang, AGGARWAL C, LIU Huan. Recommenda￾tions 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·