符号网络是边带有正负符号属性的社会网络^[1]，节点间的链接类型有正负两种。其中，正链接表示朋友、支持、喜欢等积极关系；负链接表示敌人、反对、讨厌等消极关系。有关符号网络的研究主要致力于其结构及演化分析，对社会网络演化过程研究的一个计算性问题就是链接预测，即通过对网络已知信息如节点属性、拓扑结构等进行分析，预测网络中尚不相连的节点间产生链接的可能性^[2]。链接预测是社会网络分析领域的热点话题，在信息领域的推荐系统、态度预测以及生物领域等有着广泛的理论研究价值及实践指导意义。例如，在人人网、合著网等社交网络中，通过链接预测可以分析两个用户在将来是否会形成某种关系，或者识别研究者在将来进行合作的可能性，从而进行朋友推荐。在淘宝、京东等电子商务平台中，通过链接预测可以分析用户的喜好和需求，预测其购买趋势，进而为其推荐感兴趣的产品，帮助网站提升销售量。在安全领域中，通过链接预测可以发现潜在的犯罪团伙之间的秘密关系，从而为控制犯罪行为的蔓延提供有力的决策支持。

在将负关系纳入信任传播模型之前，研究者主要关注仅包含单一正关系的边值模型，对同时包含正负链接的符号网络边值预测问题的研究相对较少。然而，Epinions等网站的实际经验表明用户间的负关系同样不容忽视^[3]。符号网络边值预测问题的研究有助于分析正负关系在符号网络中发挥的作用，推进社会网络中个性化推荐、异常用户识别、用户决策行为预测等多方面的研究发展及应用。于是，研究人员从不同角度设计了不同算法对符号网络正负关系预测问题进行了研究，主要分为两大类：基于矩阵的符号预测方法和基于分类的符号预测方法^[4]。

1）基于矩阵的符号预测方法。将符号网络视为矩阵，利用信任传播模型、矩阵分解或矩阵填充等进行符号预测。Agrawal等^[5]指出对矩阵进行奇异值分解、特征值分解或利用一些核函数的矩阵分解都可以有效预测未知的边的符号。Hsieh等^[6]将符号预测问题转化为低秩矩阵填充问题，用MC-SVP算法有效预测边的符号。此外，一些基于矩阵的符号预测方法将预测结果矩阵中的连续元素通过阈值转化为离散值±1，以获得最终的正负关系预测结果。上述基于矩阵的符号预测算法中矩阵分解和矩阵填充算法能够达到较高的预测准确率，但相关算法未能有效融合结构平衡理论，预测所得符号网络模型不能很好地体现结构平衡性。然而，大量实证分析表明结构平衡理论能够很好地捕获无向符号网络中节点间的相互作用模式，有助于符号网络的链接预测研究以及网络结构平衡性分析。且Leskovec等^[7]的研究发现，真实符号网络中符合结构平衡理论的三元环数目远大于不平衡的三元环数目。自此之后，研究人员开始结合结构平衡理论对符号网络中的符号预测问题进行研究。目前，结构平衡理论中的一些规律已被普遍应用于符号网络正负链接预测算法中。

2）基于分类的符号预测方法。将符号网络中正负链接预测视为二值分类问题，构建特征集，利用分类算法进行符号预测。根据构建特征集所用信息的不同，可分为基于网络结构信息的算法和基于网络上下文信息的算法。前者结合结构平衡理论，利用符号网络结构信息设计符号预测算法；后者利用上下文信息构建特征集，通过分类算法对边的符号进行预测。Leskovec等^[7]分析了真实符号网络中正负链接模型与预测的链接之间的区别，对无向符号网络中的边值演化问题进行了分析。随后，Leskovec等^[8]结合结构平衡理论，使用Epinions、Slashdot和Wikipedia这3个数据集通过有监督的机器学习，利用逻辑回归模型对潜在社会网络中的链接符号进行了预测，该方法准确度较高，但仅考虑了网络局部信息。Chiang等^[9]基于Katz指标提取网络中长度为 $ k $ 的环构建特征集，再通过逻辑回归模型进行符号预测。实验发现， $ k $ 从3增至5时，算法预测准确度有一定提高；但当 $ k >5$ 时，准确度变化却很小。该算法将视野从局部扩大到全局，考虑了网络整体结构特征与边的符号的关系。Ye等^[10]通过在大规模符号网络之间进行网络结构知识的迁移学习完成了符号预测。Yang等^[11]通过研究用户关系和用户间行为，提出能够无监督或半监督进行符号预测的模型，并融合结构平衡理论改进模型，进一步提高了预测准确率。Facchetti等^[12]分析了大规模符号网络的结构并对其全局平衡性进行了计算，得出结论目前绝大多数在线网络都体现出结构平衡性。Symeonidis等^[13]定义了基本节点相似度捕获符号图的局部特征，引入过渡节点相似度来挖掘图的全局特征，通过边的信息在符号网络中预测链接。Patidar等^[14]提出一种归纳学习框架，结合结构平衡理论使用C4.5算法预测朋友和敌人链接。佘宏俊^[15]提出改进的基于共同邻居的符号网络链接预测算法ICN，结合节点符号密度和网络拓扑特征进行预测，提高了负边的预测准确率。Zeng等^[16]提出了一种符号预测模型，通过挖掘基于特征聚类的元路径，有效利用了网络的局部和全局信息构建模型，并使用逻辑回归分类器训练模型，以此得到符号预测结果。

从总体研究现状而言，基于分类的符号预测方法虽涌现出不少优秀成果，但仍然存在一些问题，主要体现在以下两方面：

1）基于相似性的链接预测算法大多仅单一地考虑了网络图的局部或全局特性，在预测准确率和计算复杂度上难以均衡，且无法直接应用于包含正负二元边值关系的符号网络。研究发现，基于网络结构信息的特征比基于网络上下文信息的特征更重要^[17]，且大多数真实社会网络的上下文信息难以获取。因此，当前主流的链接预测算法是通过节点固有属性定义节点相似性，主要分为两类：一类是基于节点局部信息的相似性算法，主要利用了节点及邻居节点的度信息，如CN指标、Jaccard算法等。此类算法思路简单，容易实现，计算复杂度较低，但忽略了邻居节点间的联系，不能有效挖掘路径信息对节点间相似性的影响，针对不同的网络，预测精度不稳定。另一类是基于路径结构的相似性算法，主要利用了路径个数、路径长度以及路径上节点间的信息来定义相似性，如最短路径算法、Katz指标等。该类算法考虑了连接两节点的全部或部分路径对于节点的相似性贡献，预测准确率较高。但其忽略了路径上传输节点的局部相似度对于两节点的相似性影响，且没有区分相同长度的不同路径对于相似性的影响力。此外，计算两节点间所有路径信息的复杂度较高。因此，基于符号网络的结构特征，如何结合结构平衡理论，有效融合节点局部信息和路径结构信息来定义相似性，在提高预测准确率的同时有效降低计算复杂度是符号网络链接预测算法研究的重点之一。

2）已有符号预测算法仅能对已经存在但缺失链接类型的边的符号进行预测，无法同时实现未来边的链接预测和符号预测。主流的符号预测算法主要基于结构平衡理论和机器学习，该类算法往往假定边集固定不变，基于现有的节点集与边集，通过机器学习完成已有边的符号预测。该类算法没有考虑网络结构演变中未来链接的建立及其对网络结构平衡性的影响，而真正意义上的边值预测包括网络结构上的链接预测和符号预测，即要对符号网络中的已有链接、未来链接及其符号类型同时做出准确预测。因此，如何结合结构平衡理论构建特征集，或利用符号网络的拓扑结构信息完成未来边的链接预测和符号预测是值得深入探讨的问题。

鉴于以上问题，作者以符号网络在某一时刻的瞬时快照图为研究对象，以节点相似性度量为出发点，从符号网络结构特征入手，改进传统单一相似性指标的不足之处，定义融合节点局部属性相似性和全局路径结构相似性的度量指标，以提高预测准确率，降低计算复杂度。同时，在深入研究反映和影响符号形成因素的机制之上，基于结构平衡理论，设计融合多特征的符号预测算法。最后，构建融合相似性和结构平衡理论的符号网络边值预测算法（prediction for signed networks based on the balance and similarity，PSNBS）。

1 预备知识

Heider于1946年提出的结构平衡理论为符号网络结构分析提供了理论基础，它用一种平衡模型描述了用户间就正负向链接形成的关系的结构和冲突等的来源。随后，Cartwright和Harary将该理论推广至图论中，用数学语言将其形式化描述为符号网络。2010年，Leskovec等首次将结构平衡理论应用于符号预测问题^[7]。

1.1 结构平衡三角形

结构平衡理论是围绕三角形的平衡性分析开始的，考虑了3个节点组成的三元组所有可能的组合模式。在无向符号网络中这种组合模式共有4种，分别记为 $T_{0}$ 、 $T_{1}$ 、 $T_{2}$ 、 $T_{3}$ ，如图1所示， $T_i$ 代表该模式中正向链接数为 $ i $ 。根据结构平衡理论，三角形的结构平衡性可通过其3条边的符号之积判定：若三边符号之积为正，则该三角形是结构平衡的，否则是不平衡的。因此， $T_{1}$ 和 $T_{3}$ 是结构平衡的，而 $T_{0}$ 和 $T_{2}$ 则不平衡。

1.2 结构平衡环

上述三角形的结构平衡性判定方法可扩展至分析环的结构平衡性，即一个环是结构平衡的当且仅当环上所有边的符号之积为正，如图2所示。

1.3 符号网络平衡性分析

若无向符号网络中所有的环都是结构平衡环，则该网络是平衡网络。Anchuri等^[18]对大规模符号网络Epinions和Slashdot的平衡性进行了研究，结果如表1所示。

研究发现，这两个真实网络中符合结构平衡理论的三元环数远大于不平衡的三元环数。Hassan等^[19]的研究表明，在自动构建的符号网络中， $T_{3}$ 模式被充分表达， $T_{0}$ 和 $T_{2}$ 模式未被充分表达；且自动构建的网络与明确表示的符号网络都与结构平衡理论一致。此外，文献[20–22]的相关研究也发现，真实符号网络中符合结构平衡理论的三角形数远大于不平衡的三角形数，且随时间推移不平衡网络会朝着平衡网络的结构发展，进一步验证了结构平衡理论在衡量无向符号网络平衡性上的重要性。

2 主要思想

PSNBS算法的目标是对未来链接及其符号同时做出准确预测，也可对网络中已经存在但缺失符号类型的边的符号做出预测。算法的一个重要假设前提是两节点相似度越高，两者建立链接的可能性越大。

首先，鉴于局部特征和路径结构对相似性的影响，综合考虑了两节点间的所有路径以及路径上的中间节点对于两节点的相似性贡献。先提取连接两节点的长度为 $ L $ 的路径，有效结合该路径上节点的属性相似度和路径结构相似度。在度量节点自身属性对于两节点的相似性影响时，认为度数小的公共邻居比度数大的公共邻居对两节点的相似性贡献大。在度量路径结构对于两节点的相似性影响时，认为两节点间路径数越多，两者相似度越高；且短路径比长路径对于两节点的相似性贡献程度更大。

其次，考虑到未来链接对网络结构的平衡性影响，相似性指标的定义还要结合结构平衡理论，选取能从多角度反映符号形成机理的网络属性，以准确预测未来链接的符号类型。在度量未来链接对网络结构的平衡性影响时，将连接两节点的某条路径对于该未来链接的符号影响定义为该路径上所有已知边的符号乘积，以使未来链接所在的环是一个结构平衡环。

此外，张维玉等^[23]的研究表明，三角形结构平衡理论可以为符号预测提供重要支持，在引入四边形结构平衡特征后，其预测准确率与仅使用三角形结构平衡特征的相比有显著提高，这也进一步验证了适当扩大结构平衡环的长度可以为连边符号预测提供更多的信息。同时，Liu等所提出的STNMP算法^[24]中最优步长选择部分的实验结果也表明，提取连接两节点的步长大于3的路径计算相似度时，复杂度显著加大，预测准确率反而没有明显提高。鉴于此，结合相关研究成果，为降低复杂度，本文算法只考虑连接两节点的长度为2和3的路径对于相似性的影响，旨在达到较高预测准确率的同时保证算法效率。

最后，考虑到不同步长的路径对于两节点相似性以及未来链接符号的不同影响程度，对两种不同长度的路径赋予不同的可调步长影响因子。最终，用两节点基于步长为2和3的所有路径的相似性得分之和作为两节点基于相似性和结构平衡理论的边值预测得分。得分的绝对值度量了两节点的相似程度，即未来链接建立的概率；得分的正负即为未来链接的符号预测结果。

有一种特殊情况：若两节点的边值预测得分为0，则或许是因为连接两节点的步长为2和3的路径都不存在，又或者是两节点基于步长为2和步长为3的路径相似性得分的正负值相抵为0，导致无法获得未来链接的符号类型。此时，采用节点自身特征信息进行符号预测。引入负密度的概念，分析待测链接对应的两节点在网络中与其他节点的连边的符号倾向。当两节点的负密度都大于网络平均负密度时，表明这两个节点趋向于和其他节点建立负链接关系，此时，待测链接符号预测结果为负；否则，符号预测结果为正。

3 PSNBS算法 3.1 符号说明

为准确描述所提算法，给出如下符号变量定义及说明：

1） $ G =( V , E , S )$ 为无向无权符号网络图。

2） $ V =\{v_{1},v_{2},\cdots\!,v_{n}\}$ 为节点集，且 $| V |= n $ 。

3） $ E =\{ e (v_{i},v_{j})\}$ 为边集，且 $| E |= m $ 。其中， $ e (v_{i},v_{j})\in $ $ \{0,1\}$ 。若 $ e (v_{i},v_{j})\in E $ ，则 $ e (v_{i},v_{j})$ =1；否则 $ e (v_{i},v_{j})$ =0。 $\forall v_{i},v_{j}\in V $ 且 $ i \ne j $ ，都有 $ e (v_{i},v_{j})= e (v_{j},v_{i})$ 且 $ e (v_{i},v_{i})\notin E $ 。

4） $ S =\{ s (v_{i},v_{j})\}$ 为符号集。 $\forall v_{i},v_{j}\in V $ ， $ s (v_{i},v_{j})\in $ $ \{0,1,-1\}$ 。若节点对〈 $v_{i},v_{j}$ 〉间为正向链接，则 $ s (v_{i},v_{j})$ =1；若为负向链接，则 $ s (v_{i},v_{j})=-1$ ；若尚不存在链接，则 $ s (v_{i},v_{j})=0$ 。

5） $N_{1}(v_{i})$ 为节点 $v_{i}$ 的一级邻居节点集合。

6） $N_{2}(v_{i})$ 为节点 $v_{i}$ 的二级邻居节点集合。

7） $ k ^+(v_{i})$ 为节点 $v_{i}$ 的正度数，即与 $v_{i}$ 相连的正向链接数目。

8） $ k^- (v_{i})$ 为节点 $v_{i}$ 的负度数，即与 $v_{i}$ 相连的负向链接数目。

9） $ k (v_{i})$ 为节点 $v_{i}$ 的度数，即与 $v_{i}$ 相连的总边数，也即， $ k (v_{i})= k^+(v_{i})$ + $ k^-(v_{i})$ 。

3.2 相关定义 3.2.1 节点对的2-step相似性得分

设 $ G =( V , E , S )$ ， $\forall v_{i},v_{j}\in V $ 且 $ e (v_{i},v_{j})$ =0，将节点对〈 $v_{i},v_{j}$ 〉基于平衡论的2-step相似性得分定义为连接 $v_{i}$ 与 $v_{j}$ 的步长为2的所有路径对两者的相似性贡献总和，记作 $BS\!core_{2}(v_{i},v_{j})$ ，如下：

$\begin{gathered} BS\!cor{e_2}({v_i},{v_j}) = S\!core({v_i},{v_{tk}},{v_j}) = \hfill \\ \sum\limits_{k = 1}^{|{N_1}({v_i}) \cap {N_1}({V_j})|} {\frac{2}{{k({v_{tk}})}}} \cdot s({v_i},{v_{tk}})\cdot s({v_{tk}},{v_j}) \hfill \\ \end{gathered} $

(1)

式中， $v_{tk}\in V \cap N_{1}(v_{i})\cap N_{1}(v_{j})$ ， $ e (v_{i},v_{tk})=1$ ， $ e (v_{tk},v_{j})=1$ 。

3.2.2 节点对的3-step相似性得分

设 $ G =( V , E , S )$ ， $\forall v_{i},v_{j}\in V $ 且 $ e (v_{i},v_{j})=0$ ，将节点对〈 $v_{i},v_{j}$ 〉基于平衡论的3-step相似性得分定义为连接 $v_{i}$ 与 $v_{j}$ 的步长为3的所有路径对两者的相似性贡献总和，记作 $BS\!core_{3}(v_{i},v_{j})$ ，如下：

$\begin{aligned} & BS\!cor{e_3}({v_i},{v_j}) = S\!core({v_i},{v_{pk}},{v_{qk}},{v_j}) = \\ & \quad \sum\limits_{|{l_k}| = 3} {\frac{{3 \cdot s({v_i},{v_{pk}})\cdot s({v_{pk}},{v_{qk}})\cdot s({v_{qk}},{v_j})}}{{k({v_{pk}}) + k({v_{qk}}) - 1}}}\end{aligned} $

(2)

式中： $l_{k}=v_{i}e(v_{i},v_{pk}) v_{pk}e(v_{pk},v_{qk}) v_{qk}e(v_{qk},v_{j}) v_{j}$ 为连接 $v_{i}$ 与 $v_{j}$ 的第 $ k $ 条路径，且 $ e (v_{i},v_{pk})$ =1， $ e (v_{pk},v_{qk})$ =1， $ e (v_{qk},v_{j})$ =1； $|l_{k}|$ 表示路径 $l_{k}$ 的步长； $v_{pk}\in N_{1}(v_{i})\cap N_{2}(v_{j})$ ， $v_{qk}\in $ $N_{1}(v_{j})\cap N_{2}(v_{i})$ 。

3.2.3 节点对的边值预测得分

设 $ G =( V , E , S )$ ， $\forall v_{i},v_{j}\in V $ 且 $ e (v_{i},v_{j})$ =0，将节点对〈 $v_{i},v_{j}$ 〉基于相似性与结构平衡理论的边值预测得分定义为连接节点对〈 $v_{i},v_{j}$ 〉的步长为2和3的所有路径对于两节点的相似性贡献总和，记作 $BS\!core(v_{i},v_{j})$ ，如下：

$\begin{aligned} & BS\!core({v_i},{v_j}) = \lambda \cdot BS\!core_2({v_i},{v_j}) + \\&\;\;\;\;\quad (1 - \lambda )\cdot BS\!core_3({v_i},{v_j}) \end{aligned} $

(3)

式中， $\lambda $ 为可调步长影响因子，且考虑到3阶路径相似性影响程度小于2阶路径，故 $\lambda $ 取值范围设定为 $ [0.5,1.0]$ 。

3.2.4 节点负密度

设 $ G =( V , E , S )$ ， $\forall v_{i}\in V $ ，将节点 $v_{i}$ 的负密度定义为与 $v_{i}$ 相连的负向链接数同与 $v_{i}$ 相连的总链接数的比值，记作 ${D^ - }({v_i})$ ，如下：

${D^ - }({v_i}) = \frac{{{k^ - }({v_i})}}{{k({v_i})}}$

(4)

3.2.5 网络平均负密度

设 $ G =( V , E , S )$ ， $|V|=n$ ，将网络平均负密度定义为网络中所有节点负密度的平均值，记作 ${D^ - }(G)$ ，如下：

${D^ - }(G) = \frac{{\displaystyle\sum\limits_{i = 1}^n {{D^ - }({v_i})} }}{n}$

(5)

3.2.6 边值预测

将基于相似性与结构平衡理论结合的符号网络边值预测结果定义如下：

1）链接预测结果。节点对〈 $v_{i},v_{j}$ 〉边值预测得分的绝对值 $|BS\!core(v_{i},v_{j})|$ 为两节点的总相似度，度量了未来链接 $ e (v_{i},v_{j})$ 建立的概率。该值越大，两节点建立链接的可能性越大。

2）符号预测结果。若 $BS\!core(v_{i},v_{j})$ >0，则未来链接 $ e (v_{i},v_{j})$ 符号预测结果为正，两节点间建立正向链接的概率更大。若 $BS\!core(v_{i},v_{j})$ <0，则 $ e (v_{i},v_{j})$ 符号预测结果为负。若 $BS\!core(v_{i},v_{j})$ =0，则当 $ D ^-(v_{i})> D ^-( G )$ 且 $ D ^-(v_{j})> D ^-( G )$ 时， $ e (v_{i},v_{j})$ 符号预测结果为负；否则，为正。

3.3 算法描述

输入：图 $ G $ 的邻接矩阵 $ {{A}} $ ， $ A ( i , j )= s (v_{i},v_{j})$ 。

输出：待测边的符号预测结果及图 $ G $ 中最有可能建立的 $ k $ 个链接。

对于图 $ G $ 中的任意节点对〈 $v_{i},v_{j}$ 〉，若两节点的连边符号未知，或者两节点间尚不存在连接，则执行如下操作：

第1步：查找 $ G $ 中连接 $v_{i}$ 与 $v_{j}$ 的步长为2的所有路径，计算节点对的2-step相似性得分 $BS\!core_{2}(v_{i},v_{j})$ 并存至2-step相似性矩阵 ${{BS}}\!_{2}$ 中，其中， $ BS_{2}( i , j )= $ $BS\!core_{2}(v_{i},v_{j})$ 。

第2步：查找 $ G $ 中连接 $v_{i}$ 与 $v_{j}$ 的步长为3的所有路径，计算节点对的3-step相似性得分 $BS\!core_{3}(v_{i},v_{j})$ 并存至3-step相似性矩阵 ${{BS}}\!_{3}$ 中，其中， $ BS\!_{3}( i , j )= $ $BS\!core_{3}(v_{i},v_{j})$ 。

第3步：计算节点对的边值预测得分 $BS\!core(v_{i},v_{j})$ 并存至总相似性矩阵 ${{BSim}}$ 中，其中， $BS\!im( i , j )= $ $BS\!core(v_{i},v_{j})$ 。

第4步：进行链接预测。

1）对已存在的边进行符号预测

①若节点对边值预测得分不为0，则待测边符号类型与边值预测得分的符号类型相同。

②若节点对边值预测得分为0，则当两节点的负密度都大于网络平均负密度时，待测边的符号预测结果为负；否则，符号预测结果为正。

③对未来链接进行边值预测

将节点对的边值预测得分的绝对值降序排序，将前 $ k $ 个节点对对应的链接作为图 $ G $ 基于相似性与结构平衡理论的未来链接边值预测结果，链接的符号类型与节点对的边值预测得分的符号类型相同。

PSNBS算法实现过程如下：

1：ReadGraphFile

2：Initialize matrix $ {{A}}$

3：For each $ v_i, v_j \in V$ do

4：If $ e(v_i,v_j)=0$ or $ s(v_i,v_j)=0$

5：{ Find all $ l_2(v_i,v_j)$ , calculate $ BS\!core_2(v_i,v_j)$ and update matrix $ {{BS}}_2$

6：Find all $ l_3(v_i,v_j)$ , calculate $ BS\!core_3(v_i,v_j)$ and update matrix $ {{BS}}_3$

7：Compute $ BS\!core(v_i,v_j)$ and get matrix $ {{BSim}}$

8：If $ BS\!core(v_i,v_j)=0$

9：{Calculate $ D ^-(v_{i})$ , $ D ^-(v_{j})$ and $ D ^-( G )$

10：If $ D^-(v_i)> D^-(G)$ and $ D^-(v_j)> D^-(G)$ , $ s(v_i,v_j)=$ $-1$

11：Else $ s (v_{i},v_{j})$ =+1 }

12：Else if $ BS\!core(v_i,v_j)>0$ , $ s(v_i,v_j)=+1$

13：Else $ s(v_i,v_j)=-1$

14：Output $ s(v_i,v_j)$ } End for

15：Sort $|BS\!im(i,j)|$ and get top $ k $ 〈 $v_{i}, v_{j} $ 〉

4 实验与分析

首先，通过网络获取实验所需数据集，将实验过程分为训练验证和比较实验两个阶段。其次，针对符号网络拓扑特征，采用改进的适合于符号网络的链接预测准确率评价指标对所提算法边值预测准确率进行评估，验证算法的正确性。最后，将所提算法与经典的同类型的符号网络链接预测方法进行对比分析。

4.1 实验所用数据集

从http://snap.stanford.edu/下载获取3个经典的大规模真实符号网络数据集Epinions、Slashdot和Wikipedia，抽取得到其子集。本研究中忽略链接的方向，将这3个数据集转化为无向符号网络进行边值预测研究。各数据集拓扑信息见表2，详细信息如下：

1）Epinions。消费者评论网站，用户可在网站上查看其他用户对商品的评论等，并可创建有向符号链接表达对他人的信任或不信任。

2）Slashdot。技术博客网站，用户可对公布在该网站的新闻发表意见，同时可将其他用户添加至朋友或敌人列表。

3）Wikipedia。收集了维基百科用户对选举其管理员的投票信息构建所得的一个网络，用户可对候选人的晋升投支持票或反对票。

4.2 训练集与测试集的划分

为衡量算法预测结果的准确率，需将已知的边集 $ E $ 划分为训练集和测试集。作者采用常用的十折交叉法，针对每个数据集，随机从 $ E $ 中取10%的边作为测试集，记作 $E_{\rm{te}}$ ；剩下的90%的边作为训练集，记作 $E_{\rm{tr}}$ ；满足 $E_{\rm{te}}\cup E_{\rm{tr}}= E $ 且 $E_{\rm{te}}\cap E_{\rm{tr}} =\varnothing$ 。训练集中的信息看作是已知信息，测试集用于测试，验证算法预测结果的准确度。重复进行10次，基本保证所有样本数据既进行了训练也进行了测试验证。

4.3 评价指标的选取及改进

常用的评价链接预测算法精度的指标有 $AUC$ 、 $Precision$ 和 $Ranking S\!core$ ，然而，这些指标仅能单一地评价传统社会网络中链接预测的准确率或符号网络中符号预测的准确率。故对 $AUC$ 指标^[25]和 $Precision$ ^[26]进行改进，得到适合于符号网络链接预测准确率的衡量指标 $AUC_{\rm{BS}}$ 和 $Precision_{\rm{BS}}$ ，分别作为PSNBS算法边值预测和符号预测准确率的评估标准。

4.3.1 边值预测准确率评价指标 $AUC_{\rm{BS}}$

$AUC_{\rm{BS}}$ 指标用于对未来链接的边值预测准确率进行评估。本实验中，针对随机从测试集中所取的边和随机选择的不存在的边，需要保证两者预测得分符号相同时才能比较其绝对值以计算 $AUC$ 的值；否则，取消本次计算，重新选取下一对待测边开始新一次的比较计算。最终，将 $AUC_{\rm{BS}}$ 定义如下：

$AU{C_{^{{\rm{BS}}}}} = \frac{{n' + 0.5n''}}{n}$

(6)

与 $AUC$ 指标^[25]相比，式（6）中参数的含义因符号网络的特性也相应地做了调整。式中： $ n $ 代表独立实验的次数，本实验中设为20 000； $n'$ 为正边符号类型预测正确的数； $n''$ 为负边符号类型预测正确数。用 $ U $ 代表全集， $E_ {\rm{un}}=U-E$ 代表实际不存在的边集。在 $ n $ 次独立实验中，每次随机从 $E_{\rm{te}}$ 中选取一条边，再随机从 $E_ {\rm{un}}$ 中选取一条边，依据PSNBS算法计算所选两个链接对应节点对的边值预测得分。当两个得分都为正或都为负时，若 $E_{\rm{te}}$ 中所取边的得分绝对值大于 $E_ {\rm{un}}$ 中所取边的得分绝对值，则 $n'$ 加1；若两者得分绝对值相同，则 $n''$ 加1；否则，若两者边值预测得分符号不同，则重新选择待测边，开始下一次计算。

4.3.2 符号预测准确率评价指标 $Precision_{\rm{BS}}$

$Precision_{\rm{BS}}$ 指标用于对缺失符号的已有边的符号预测准确率进行评估。为验证所提算法符号预测的准确率，改进 $Precision$ 指标^[26]。针对符号类型已知的网络图在某个时刻的静态快照，每次随机从测试集中取出一条边作为待测边，假定该边不存在，基于现有符号网络图的边值信息，根据PSNBS算法计算该待测边对应的两节点的边值预测得分，将得分的正负与待测边原有真实的符号类型进行比对。在此，当预测得分为0时，通过待测边对应的两个节点的负密度获得待测边的符号类型。若预测所得的符号类型与待测边真实的符号类型相同，则表明算法对于待测边的符号预测结果正确；否则，符号类型预测错误。最终，将适合于符号网络符号预测准确率的评价指标定义为 $Precision_{\rm{BS}}$ ，公式如下：

$Precisio{n_{{\rm{BS}}}} = \frac{{{N_{{\rm{s\_correct}}}}}}{{{N_{{\rm{s\_total}}}}}}$

(7)

式中： $N_ {\rm{s\_total}}$ 表示实验中进行符号预测的链接总数，本实验中，该参数设定为10 000； $N_ {\rm{s\_correct}}$ 表示符号预测结果正确的链接数。

4.4 边值预测准确率评估

PSNBS算法引入可调步长影响因子 $\lambda $ ，以度量步长为2和3的不同长度的路径对于节点相似性贡献的不同程度。为减少计算次数，本实验中， $\lambda $ 分别取值0.5、0.6、0.7、0.8、0.9和1.0。表3给出了PSNBS算法针对不同数据集， $\lambda $ 取不同值时基于 $AUC_{\rm{BS}}$ 指标的预测准确率，其值是10次独立实验的平均值。

由表3可知，针对3个数据集，PSNBS算法预测准确率基本可达93%以上。实验结果显示了PSNBS算法对于大规模符号网络较为理想的边值预测效果。此外，针对实验所用数据集，算法在 $\lambda $ 分别取0.6、0.8、0.5时预测准确率达到了最高值。在拓扑性质不同的数据集中，连接两节点的步长为2和3的路径数不同时，对应的三元和四元结构平衡环对于未来链接及其符号的形成也起到了不同程度的作用。实际应用中，需根据网络具体的拓扑性质合理确定 $\lambda $ 的值，以达到最佳预测性能。

4.5 符号预测正确性验证

真实符号网路中，许多边的符号类型是未知的。比如，蛋白质相互作用网络中，酵母菌蛋白质之间80%的相互作用是不为人知的^[27]。针对此类缺失符号类型的符号网络，若先采用链接预测算法对未知的符号类型进行预测，在此基础上指导试验过程，便有可能大大减少试验次数，提高成功率，降低实验成本，加快人类对于网络中隐含的链接信息的认识。

为进一步验证所提算法对于未知的边的符号类型预测的有效性及正确性，后期实验中，采用 $Precision_{\rm{BS}}$ 指标对算法符号预测结果的准确度进行了评价分析。同时，为进一步验证第4.4节对于步长影响因子的选取是否合理，本实验中，仍然对 $\lambda $ 分别取0.5、0.6、0.7、0.8、0.9、1.0。针对不同的数据集和不同的步长影响因子，PSNBS算法符号预测准确率详细实验结果见表4，其值是10次独立实验的平均值。

从表4可知，PSNBS算法在3个数据集上均达到了较高的符号预测准确率。此外，比较表3和4可知，针对3个符号网络，采用 $AUC_{\rm{BS}}$ 对未来链接边值预测准确率进行评价以及采用 $Precision_{\rm{BS}}$ 对未知边的符号预测结果进行准确率评价时，两个评价指标随 $\lambda $ 的变化趋势基本一致，都在 $\lambda $ 取0.6、0.8和0.5时达到了最高值。图3和4分别给出了3个数据集下 $AUC_{\rm{BS}}$ 和 $Precision_{\rm{BS}}$ 随 $\lambda $ 的变化曲线。

4.6 与经典算法性能对比

PSNBS算法在扩展结构平衡环概念的基础上，通过定义基于节点局部信息和路径结构相结合的相似性度量实现了边值预测，在一定程度上达到预测准确率和计算复杂度较好的均衡。为进一步验证算法性能，将该算法与符号网络链接预测CN^[15]和改进的ICN^[15]算法进行了对比实验，同时，采用 $AUC$ 指标^[15]作为算法符号预测结果的评价指标，其定义中，实验次数 $ n $ 取值为数据集的总边数，正边符号类型预测正确量 $n'$ 的权值为1，负边符号类型预测正确数 $n''$ 的权值为0.5。此处，依据前文实验结果，针对3个数据集，PSNBS算法中 $\lambda $ 分别设定为0.6、0.8和0.5。表5给出了CN、ICN和PSNBS这3种算法在3个数据集上符号预测准确率的统计结果。

由表5可知，以 $AUC$ 指标^[15]作为符号预测准确率的评价指标时，PSNBS算法在不同数据集下仍然表现出良好的预测效果，具有一定的稳健性，且准确率明显高于CN和ICN算法。

5 结　论

提出基于相似性与结构平衡理论的符号网络边值预测算法PSNBS，综合考虑了节点自身属性和路径特征定义节点相似性度量，改进了已有相似度指标的不足之处；结合结构平衡理论预测符号类型，在提高准确率的同时，能够实现链接及其符号双重预测。采用 $AUC$ 、 $AUC_{\rm{BS}}$ 、 $Precision_{\rm{BS}}$ 为算法预测准确率的评价指标，在多个数据集上进行了实验，并与经典算法CN和ICN进行了对比分析，验证了所提算法对于已有边的符号类型和未来链接的边值预测的有效性及预测准确率较高。随着网络规模扩大，需进一步降低算法复杂度，提升其可扩展性及稳健性。此外，定性或定量分析步长影响因子的取值以更加准确有效地完成预测，也是下一步的研究内容。