复杂网络是社会学、生物学和信息学领域研究复杂系统对立关系的重要方法之一。符号网络的正号“+”和负号“-”分别代表着个体或群体之间的积极和消极关系，预测符号网络的正负号能够推动个性化推荐、用户聚类、社区分割等方面的研究发展，因此吸引了国内外众多学者研究^[1]。

然而许多研究为增加预测的准确率，丰富了符号网络的符号预测算法。但在过渡强调准确率的同时，也较大地牺牲了算法的时间效率，使之难以实用。基于此，本文设计优化算法，首先得到不同条件下的预测准确度和时间复杂度，然后利用函数拟合方法，得到它们之间的关系并提出优化方案。

1 预备知识与相关工作分析 1.1 预备知识

为论文阐述之便，以下先对符号网络做简要介绍。

定义1 　符号网络是指图G=(V,E,Σ)，其中V={1, 2,…,n}为图中n个节点的集合，E={(i,j)|i,j∈V}为边集，映射Σ:E→{+1, –1}为边上的符号，可用s(i,j)=1或者s(i,j)= –1表示正号或者负号。

符号预测问题可以形式化描述如下。给定一个符号网络，利用除边(i,j)以外其他边的符号信息预测边(i,j)的符号s(i,j)^[1]。图1是一个简单的符号网络，只有节点i与节点j连边的符号未知，其他边的符号已知，目标是预测边(i,j)的符号s(i,j)。可以利用步长为2的路径i-b-j，步长为3的路径i-c-d-j，以及步长更长的路径信息来预测边(i,j)上的符号。

环是符号网络的重要的结构特征，很多学者都利用了这个结构特征来预测边的符号，例如Chiang等^[2]使用长度为k的环构建特征然后建立模型进行预测。实际上，待测边两端节点间的步长x(x≥2)对应待测边所在的长度为k=x+1的环。

定义2 　k-环为边的集合E={(i₁,i₂), (i₂,i₃),…, (i_k-1,i_k ), (i_k ,i₁)|i₁,i₂,…,i_k ∈V,k≥3}，其中, |E|=k。

定义3 　平衡环指k-环上所有边的符号乘积为正，即s(i₁,i₂)*s(i₂,i₃)*…s(i_k-1,i_k )*s(i_k ,i₁)=1, 其中,i₁,i₂,…,i_k ∈V。

1.2 相关工作

如上所述，由于符号网络能对社会网络的对立关系做形象且准确表示，因此被广泛用于关系预测，尤其是其中的符号预测研究。对于预测符号的研究，学者们有着各种不一样的预测算法。Leskovec等^[3]提出LOO-LR算法，利用两类特征：1)传统的节点局部特征测度，如出度、入度等；2)结构平衡理论和地位理论，然后运用逻辑回归模型对待预测边进行分类，发现符合结构平衡理论和地位理论的三元组对于待测边的符号预测起主要作用。Chiang等^[2]在Leskovec等^[3]的基础上提出HOC-k算法，利用k-环进行构建特征集，再利用逻辑回归模型进行符号预测，发现k的值从3到5时，预测准确度有所提高，但大于5时准确度变化不大。其算法时间复杂度为O(2^k nm)，其中，k是环的长度；n是数据集的节点数；m是数据集的边数；计算时需要消耗大量时间。

Papaoikonomou等^[4]利用了Chiang等^[2]的HOC-k算法的3-环和4-环的局部特征，提出了频繁子图发现(frequent subgraph discovery)算法，在拥有至少25个共同邻居的边上根据周围的连边情况构建自我图(ego graph)，然后在这些自我图里发现频繁子图，并在每个自我图里面利用频繁子图出现的次数构建特征集，最后使用支持向量机模型进行符号预测。他们使用ROC曲线下的面积评估模型，在至少25个共同邻居的条件下预测效果好，但是在其他条件下预测效果就差，而且时间复杂度较高。表1是3个常用数据集Epinions、Slashdot和Wikipedia^[5]上的不同算法的预测准确度。

在预测边的符号时，总会用到符号网络的局部特征信息，例如上述的k-环。在利用k-环的局部特征预测符号时，随着步长的增加，利用的路径信息越来越多，预测准确度必然越来越高，但是时间复杂度也越来越高。例如Chiang等^[2]提出的HOC-k算法，时间复杂度是O(2^knm)，是k的指数函数，后面的实验部分可以验证，这就是Papaoikonomou等^[4]的算法只利用3-环和4-环的原因。所以，本文为了降低时间复杂度并得到较高的预测准确度，设计了一个优化算法。首先得到不同步长的预测准确度和所需的时间，然后利用函数拟合的方法得到各自与步长的关系，最后分析算法性能和实验结果，并提出优化方案。

2 研究方法

在预测边(i,j)上的符号时，为了利用步长大于等于2上的路径信息，本文利用社会结构平衡理论中的结构平衡环来设计预测边符号的算法，即待测边(i,j)的符号s(i,j)能使待测边所在的k-环中，平衡环的个数最多。用公式表示为

$\quad\quad s(i,j) = \left\{ {\begin{array}{*{20}{l}}{{\rm sign}(\sum\limits_{n=3}^k {({p_n} - {q_n})} ),{p_n} \ne {q_n}{{\text{；}}}}\\{1,{p_n} = {q_n}{{\text{。}}}}\end{array}} \right.$

其中，假设s(i,j)=1时，p_n 是平衡k-环的个数，q_n 是不平衡k-环的个数。

利用上述预测算法，先通过实验测出每个步长对应的预测准确度，然后使用Matlab软件对数据进行曲线拟合。由于高斯函数应用广泛，在自然科学、数学等领域都可以用到，而且在Chiang等^[2]和Leskovec等^[3]的文章中看出预测准确度符合高斯分布，所以利用高斯函数进行拟合，预测准确度g(x)与步长x的函数为

$\quad\quad g(x) = a{{\rm{e}}^{ - {{(\frac{{x - b}}{c})}^2}}}{{\text{。}}}$

同时，对应每个步长得到的预测准确度，可以分别获得所需的时间，然后根据Chiang等^[2]得到的时间复杂度，利用指数函数对数据进行拟合得到运行时间f(x)与步长x的函数为

$\quad\quad f(x) = a{{\rm{e}}^{bx}}{{\text{。}}}$

这样得到的运行时间是预测每条边所需的时间，为了容易得到预测准确度与时间复杂度的关系，并且能够容易获得优化方案，本文首先利用函数

$\quad\quad f(t) = \frac{1}{t}{{\text{，}}}$

将时间数据进行转换，得到的是每秒可预测的边数，本文称为时间可接受度，值越大，表明时间复杂度越低，反之亦然。再对转换后的数据使用最小-最大规范化，

$\quad\quad h(t) = \frac{{f(t) - {{\min }f}}}{{{{\max }f} - {{\min }f}}}(1 - 0) + 0{{\text{。}}}$

将数据规范化到[0, 1]区间。这样最终得到的数据就可以和预测准确度进行比较。最后利用指数函数对数据进行拟合得到时间可接受度f_ac(x)与步长x的函数为

$\quad\quad {f_{{\rm{ac}}}}(x) = a{{\rm{e}}^{bx}}{{\text{。}}}$

最后，分别在3个数据集上，将函数g(x)与f_ac(x)进行作图对比，就可找到预测准确度与时间可接受度的相交点，并从中分析得到优化方案。优化算法如表2所示，在下一部分将结合实验，对算法性能进行分析与总结。

3 实验 3.1 数据集

使用了3个大型在线社交网络数据集Epinions、Slashdot和Wikipedia。3个数据集都是有向符号网络。由于在有向符号网络上进行实验的时间复杂度非常高，难度很大，所以本文对有向符号网络不考虑方向，对无向符号网络进行研究。经过数据预处理，如删除指向自身的边和空值记录等，各个数据集的统计信息如表3。

3.2 实验及结果分析

在3个数据集中，正边的比例都在76%以上，远大于负边的比例。这意味着一个总是把边的符号预测为正号的算法的预测准确度能达到76%以上，这样的数据会影响结果分析。所以，仿照Guha等^[6]设计的实验，设计一种平衡数据测试集，即测试集中正边数与负边数各占一半，这些正边和负边都是在原来数据集上随机选取的。根据表2的优化算法，分别在3个数据集上，对步长分别为2、3、4、5进行实验，结果如表4。

对表4中的时间和步长数据使用指数函数进行拟合，得到运行时间-步长函数f(x)，如表5。确定系数的值域是[0, 1]，值越大表示函数的拟合效果越好。因为3个数据集的确定系数的值均为1，所以能够验证时间复杂度是关于步长的指数函数。运行时间-步长的函数图如图2。

验证完毕后，继续对表4的数据使用函数拟合，得到3个数据集上的目标函数如表6和表7。在3个数据集上分别作图比较，如图3所示。从图3可以看出，3个数据集上的预测准确度曲线与时间可接受度曲线的交叉点的横坐标都在区间[2, 3]。在Epinions数据集上，对f_ac(x)分别进行一次求导和二次求导，得

$\quad\quad {f'_{{\rm{ac}}}}(x) = - 3.86 \times {10^4}{{\rm{e}}^{ - 4.53x}}{{\text{，}}}$

(1)

$\quad\quad {f''_{{\rm{ac}}}}(x) = 1.75 \times {10^5}{{\rm{e}}^{ - 4.53x}}{{\text{。}}}$

(2)

从式(1)可看出时间可接收度减小的速度非常快，从式(2)可看出减小的加速度也非常快。由于归一化后的时间可接收度趋向于0，所以没能很好地在图上表示出来。尽管根据高斯函数的性质知，g(x)最高点的横坐标是4.1，即步长为4的预测准确度最高，但是时间代价已经非常大了。在步长为2时，时间复杂度最低，但是预测准确度不高，只有67%，在步长为3时，预测准确度提高了约10%，但是时间复杂度也提高了91倍，在步长大于3时，预测准确度没有提高，而时间复杂度进一步提高，达254倍。在Slashdot和Wikipedia上的情况也是如此。据此，可以提出以下优化方案：综合考虑步长为2和3的路径信息可使预测准确度高而时间复杂度低，适用于稳定的符号网络，而只考虑步长为2的路径信息的时间复杂度低，适用于瞬时万变的符号网络。不必要考虑步长大于3的路径信息。

4 结论

在符号网络中，设计符号预测算法的研究者能够从本文得到启发，进而改进自己的算法。本文设计了一个优化算法，首先使用平衡环算法预测符号，利用函数拟合方法分别拟合预测准确度与步长、时间复杂度与步长的函数关系，然后研究随步长增加预测准确度与时间复杂度的关系并提出了优化方案。本文的优化算法能够有效获得预测准确度高和时间复杂度的关系。但是，本文只考虑无向符号网络，而且在利用局部特征信息时没有考虑节点和边的重要性，所以，在有向符号网络中考虑节点和边的重要性，更准确地找出预测准确度与时间复杂度的关系并提出优化方案是下一步的工作。