基于支持向量机的链路预测优化方案

（一）单个特征输入模型结果

以八个相似性指标分别作为单独特征输入，以支持向量机算法为模型，核函数选定径向基核函数（RBF），沿线国家航空的链路预测结果如图9-3-3所示，沿线机场航空网络预测结果如图9-3-4所示。

图9-3-3　基于向量机“一带一路”沿线国家航空网络链路预测结果

图9-3-3　基于向量机“一带一路”沿线国家航空网络链路预测结果（续）

以八个相似性指标分别作为单独特征输入，以支持向量机算法为模型，核函数选定径向基核函数（RBF），沿线机场航空网络预测结果如下图9-3-4所示。

图9-3-4　基于向量机“一带一路”沿线机场航空网络链路预测结果

图9-3-4　基于向量机“一带一路”沿线机场航空网络链路预测结果（续）

经计算，基于向量机“一带一路”沿线国家航空网络、沿线机场网络链路预测各指标如表9-3-2、表9-3-3所示。

表9-3-2　“一带一路”沿线国家航空网络链路预测结果

表9-3-3　“一带一路”沿线机场航空网络链路预测结果

根据表9-3-2，基于支持向量的链路预测算法，在“一带一路”沿线国家航空网络中的预测精度都很高，全部高于0.9。与基于相似性链路预算法结论相似的是，表格后半部分的相似性指标预测效果要高于前半部分也就是基于共同邻居信息的几个指标，即重点关注公共邻居节点度的指标预测效果不如关注全局网络路径的预测效果。

根据表9-3-3，基于支持向量机的链路预测算法在“一带一路”沿线机场航空网络中的表现，两极分化很严重。以支持向量机为模型，共同邻居的相似性指标为输入的模型预测性能比较差，只比0.5高一点；其余指标的预测性能比较高，高于9甚至接近1。这与“一带一路”沿线国家航空网络的预测结果相差非常多。对比两个层面航空网络的结构特征，我们发现机场航空网络的簇系数相较于国家航空网络比较低，这可能就是使得模型预测结果比较差的原因。该链路预测算法可能不适合网络密度和簇系数较低的网络，具体原因还需要进一步深入研究。

两个表格从整体上看，基于支持向量机的链路预测算法中，国家层面的航空网络也就是“一带一路”沿线国家航空网络的预测精确度，要高于机场层面的航空网络，尤其是以共同邻居指标CN、AA、RA作为特征输入时。越宏观层面的合作网络，预测精确度越高。基于支持向量机的链路预测算法中，以全局信息为特征输入时的预测精确度要高于以其他局部信息输入的结果。

（二）特征选择后输入模型的结果

与网络结构相似性有关的特征有七个，每个特征单独作为模型输入的时候，预测精度都较高，其中以基于全局信息的相似性特征预测精度最高。如果将7个相似性特征全部作为模型输入，那么等于考虑了基于网络结构相似性的全部信息。但是这七个特征都是从不同的角度描述网络结构的相似性，所包含的网络结构相似性信息存在重复的可能性。这就需要在模型输入前进行特征选择，以选择出包含几乎全部网络结构相似性信息的特征组合，来减少计算复杂度，提高预测精度。

1.特征选择结果(www.xing528.com)

特征选择算法主要有三大类：过滤式特征选择、包裹式特征选择、嵌入式特征选择。过滤式特征选择是在用相关系数或者卡方检验等方法从相关性角度对各个特征进行评分，然后选择分数较高的特征进行机器学习。包裹式特征选择主要是基于机器学习的预测效果评分，每次排除或者选择特征。嵌入式特征选择是使用一些机器学习算法计算各个特征的权值系数，根据权值系数选择特征。嵌入式与过滤式方法类似，但是是用训练的方法判断特征的优劣。由于决策树特征选择算法能够直观地比较各个特征的优劣，本部分将采用决策树ID3算法进行特征选择。它利用贪心算法思想，能够在进行节点分裂时能够分裂出具有最优分裂结构的属性。

图9-3-5　国家航空网络特征选择结果

图9-3-6　机场航空网络特征选择结果

根据图9-3-5和图9-3-6结果所示，无论是在“一带一路”国家航空网络还是机场航空网络，Katz相似性指标特征重要性最高，也就是Katz指标对于“一带一路”航空网络而言包含的有用信息很多。基于共同邻居的相似性指标特征重要性普遍较低，而特征重要性代表了该特征所包含的能够预测正确结果的信息完整度，这也就能解释为什么基于共同邻居的相似性指标预测精确度普遍比较低的原因；基于全局性的指标重要性最高，同时预测精确度也是最高的。

2.特征组合后输入模型结果

将以上特征重要性较高的前4个特征进行特征组合，重新输入模型测验模型精度。特征组合方式如表9-3-4所示。

表9-3-4　特征组合方式

每个模型的预测结果如表9-3-5和图9-3-7所示。

表9-3-5　特征组合预测结果

图9-3-7　特征选择后的链路预测结果

根据上述几种特征组合后的预测结果，可以看出：

（1）对比在基于支持向量机链路预测部分使用单个指标进行预测的结果，可以看出组合特征后的模型预测精确度更高。但注意，并不是包含的特征越多，该模型预测结果的精确度就越高。

（2）在基于支持向量机链路预测部分中，Katz指标不光涵盖了大部分“一带一路”网络链路预测的有用信息，且其他七个指标相对于Katz指标来说涵盖的信息是重复和微不足道的。对比单独考虑Katz指标和进行特征组合后的预测结果，我们认为只需要Katz指标基于支持向量机进行链路预测，预测精确度是最高的。

此外，以八个网络结构相似性的链路预测指标，分别输入以传统链路预测模型和支持向量分类机模型中进行预测分析，结果发现：

（1）对于“一带一路”沿线国家航空网络，也就是国家层面的“一带一路”航空网络，基于支持向量分类的链路预测模型精确度要优于传统模型。但对于机场层面的“一带一路”航空网络，只有当以全局和半局域信息作为特征输入的支持向量分类机模型，精确度才高于传统模型。这可能是因为，机场层面的跨国机场航空网络稀疏，各个机场之间由于地理距离等问题共同邻居数量很少，而以共同邻居信息为相似性指标作为输入时，相似性分值非常接近，以至于无法划分出一个分类性能优异的超平面。

（2）基于支持向量机的“一带一路”沿线国家航空网络链路预测精确度要高于“一带一路”沿线机场航空网络。这表示在“一带一路”航空网络中，网络越宏观，预测精确度越高。

（3）在“一带一路”沿线国家和机场航空网络中，基于支持向量机进行链路预测时，Katz指标几乎涵盖了所有能够预测链路的信息。相较于其他七个指标和组合指标，它有最高的预测精确度，是一个比较重要且具有代表性的指标。该指标不仅包含了路径相似的信息，同时也考虑进了共同邻居的数量。节点间的路径距离越短，共同邻居数量越多，则两个节点在结构上越相似、越可能产生连接。