本发明属于通信网络领域，涉及一种基于链路预测的商业关系推测方法。
背景技术：
1、互联网是一个典型的复杂网络，由约11万个自治域(autonomous system，as)互连组成。as之间的连接是由决定流量交换的业务合同决定的。简化地说，业务合同通常由as之间的商业关系来表示，包括对等关系(peer-to-peer，p2p)和提供商到客户关系(provider-to-customer，p2c)。随着互联网规模和复杂性的快速增长，充分了解as之间的商业关系对于理解、运营和整合互联网非常重要。
2、商业关系通常被视为私有信息，自从2001年定义了商业关系以来，已经提出了许多从公开的bgp路由数据推测商业关系的算法。但由于as路由策略和bgp决策过程的复杂性，收集器无法收集到所有的bgp路由数据。尽管许多高级算法，如as-rank、problink等具有较高的推测准确率，但as级网络拓扑的不完整性导致推测的商业关系并不完整。为了提高as级网络拓扑的完整性，研究人员尝试部署更多的有利观测点(vantage point，vp)来收集更完整的bgp路由数据。然而，由于缺乏有效的指导，这些工作既不仔细选择vp的部署位置，也不仔细选择源/目标as，在消耗大量资源的同时也无法带来同等的拓扑完整性的提升。此外，也有一些研究人员专注于特定类型的as链路，以有效发现更多的链路。虽然可行，但上述工作是有限的，因为他们只能帮助发现特定类型的隐藏链路(例如ixp特定的as链路)。
3、针对上述方法中存在的问题，本发明提供一种基于链路预测的商业关系推测方法。在有限的观测数据下进行链路预测来提高as级网络拓扑的完整性，进而提高商业关系的完整性。
技术实现思路
1、本发明要解决的问题是基于有限的观测数据进行链路预测来提高as级网络拓扑的完整性，进而提高商业关系的完整性。考虑到节点重要性对链路预测的影响，在节点相似性的基础上加入节点重要性来计算隐藏链路存在的可能性；并且为了更好的捕捉自治域网络的特点，结合了三个自治域相关信息来进行链路预测。为了提高了商业关系推测的准确率，提取节点和边的六个特征并结合xgboost分类器对隐藏链路关系(p2c\c2p和p2p)进行分类。在有限的数据收集情况下，提出的发明在准确率和召回率上优于其他方法，且获取的商业关系更完整。
2、本发明的技术解决方案是：
3、本发明将as网络中的链路预测问题视为一个二分类问题，其主要任务是根据现有的网络结构预测一对节点之间是否存在链路。对于这一任务，节点相似性和节点重要性以及自治域相关信息被视为机器学习模型的特征，而模型本身则将这些特征组合在一起进行预测。对于隐藏链路上的商业关系推导，我们使用xgboost机器学习算法来训练一个分类器，该分类器根据一组节点对特征对as链路关系(p2c\c2p和p2p)进行分类。
4、其中，本发明提出的基于链路预测的商业关系推测方法详细步骤如下所示：
5、1)训练集和测试集划分
6、由于as级网络拓扑观测的不完整性主要是由于vp的稀缺造成的，为了模拟由于vp稀缺而导致的观测损失，我们将整个数据集随机分为d和s，每一部分都包含一半的vp报告的观测结果。为了评估方法的准确性，进一步将d中的数据按比例划分为训练集dt和测试集dv。对于网络中没有直连的节点对，我们无法判断它是不存在链路还是存在链路但未被观测到。为了解决这个问题，我们将s中存在d中不存的链路作为正样本加入到测试集dv中。
7、在as网络中，连接的节点对的数量远远低于未连接的节点对，如果我们考虑所有存在和不存在的边缘作为我们的数据集是高度不平衡的，如果我们将机器学习算法应用于这种不平衡的数据，可能会过度拟合负样本的数据集，即不存在的边缘，使预测结果变得毫无意义。因此，我们选择了集合dt和dv中的所有链路，然后随机提取相同数量的没有直连边的节点对作为负样本来平衡数据集，构成最后划分好的训练集dt和测试集dv。
8、2)构建数据集
9、这一步讨论了使用训练集和测试集分别创建用于训练和测试目的的标记良好的数据集的过程。这些数据集包含链路的特征以及它们在网络中对应的标签。链路的标签，表示链路的存在和不存在，存在为1，不存在为0。链路的特征根据各种节点相似性、节点重要性和as网络相关信息计算得到。接下来具体介绍节点相似性、节点重要性和as网络相关信息。
10、将所有观察到的as路径组成一个as级网络拓扑，在这个网络中，我们认为两个as之间存在链路的可能性，取决于一个节点对另一个节点的影响，即节点重要性和节点相似性。若两个节点间的得分越高，则两个节点间更有可能连接。现有的基于节点相似性的链路预测算法一般基于网络的局部、半局部或全局特征。但由于as网络拓扑规模较大，半局部和全局方法的特征提取能力下降，所以选取局部相似性指标进行链路预测。在局部相似性指标中，最基本、最广泛使用的指标是共同邻居指标cn。cn指标利用两个as之间公共邻居节点的数量来代表节点之间的相似性，公共邻居节点的数量越多，相似度就越高，就越有可能产生连边。urimoto等人也证实了在自治域网络中，两个as之间建立联系的可能性与两个as共同连接的as的百分比有关。但是仅使用cn指标表现并不好，因为局部方法的特征提取需要更好的集成才能进行正确的链路预测。因此选取了四个在cn上进行改进的指标：jaccard、ra、hpi、hdi。下面对这四个节点相似性指标进行了说明。
11、jaccard指标对公共邻居的数量进行归一化处理，不再是共同邻居的绝对数量，而是共同邻居占所有邻居数目的比例，算法如公式(1)所示。
12、
13、ra指标是受网络资源分配过程的启发，对于网络中没有直连的两个节点x和y，若x能传递一些资源到y，在这个过程中，他们的共同邻居就是传递的媒介。假设每个共同邻居都有一个单位的资源并平均分配给它的邻居，则节点x和y的相似度就可以定义为y可以接收到的资源数，算法如公式(2)所示。
14、
15、hpi指标在共同邻居的基础上定量刻画了每对节点的拓扑相似程度，算法公式如(3)所示。
16、
17、hdi指标与hpi算法相似，但分母取节点度的最大值，算法如公式(4)所示。
18、
19、节点重要性在一定程度上会影响链路存在的可能性，通过分析不同中心性对链路的影响，发现度中心性dc对链路存在性的影响最大，因此，本发明将节点对的度中心性作为节点重要性特征。度中心性表示在网络中，一个节点的度越大，就意味着这个节点的度中心性就越高，就说明在网络中这个节点越重要。算法如公式(5)所示。
20、
21、上面节点的相似性和节点重要性特征只反映了网络的拓扑结构。为了将链路预测方法更好的应用到自治域网络中，我们提取了三个与as相关的信息，例如as的地理位置、as拥有的provider、customer、peer的数量和as层次。这些信息对于发现as间的链路很有价值。互联网分为四个层次：包括clique层、高层、低层和stub层。as层次表示as在互联网层次结构中的位置。通常，相同或相似层中的as更容易建立链路。
22、每个as拥有的provider/customer/peer的数量是不同的，例如两个as都拥有大量的customer(客户)的话，这两个更有可能会建立连接，因为它们之间的对等连接有利于减少向provider(提供者)支付的中转费用，减少用户之间的通信延迟。
23、每个as属于不同的国家和组织，as的地理范围是否重叠，可能会影响as之间bgp连接的建立，同一组织或国家的不同as之间更有可能建立连接。
24、3)训练分类器并预测隐藏链路
25、在这步中，我们使用标记良好和平衡良好的训练数据集来训练我们的机器学习分类器，并使用测试数据集来测试分类器的预测能力。我们选取机器学习分类器xgboost进行链路预测。xgboost算法归根结底来说是boosting的一种实现方式，是以cart树为基学习器的极致梯度提升算法，主要目的是降低模型的误差。通过不断迭代，可以创建出一系列新的树，这些树的大小取决于上一棵树与预期值之间的差异，以此来减少模型的误差。这样就把一个个性能较差的弱学习器集成为强学习器，以达到更好的预测能力。
26、在训练并测试完分类器后，使用该分类器来预测整个网络中的隐藏链路。
27、4)对隐藏链路进行商业关系分类
28、当得到网络中的隐藏链路后，我们需要对隐藏链路上的商业关系(p2p，p2c\c2p)进行分类。
29、对于隐藏链路上的商业关系，toposcope结合as节点和节点之间的边提取特征，然后结合这些特征使用机器学习分类器xgboost对链路类型进行分类。在toposcope的基础上，我们增加了as到vp的距离、as链路的vp数量、共同邻居比率几个特征。
30、具体商业关系分类过程如下。首先，使用as rank来推导bgp路由数据集上的商业关系作为我们的真实as关系数据集t，对于t中的每条边，使用上面的特征计算它的特征值并按照每条边的类型赋予相对应的标签。然后将t按比例划分为训练集t1和测试集t2，训练集t1用于训练模型xgboost，测试集t2用于测试模型。最后将训练好的模型用于对隐藏链路进行商业关系分类。
1.一种基于链路预测的商业关系推测方法，其特征在于，包括以下步骤：
2.根据权利要求1所述的基于链路预测的商业关系推测方法，其特征在于，所述步骤s1具体为：将整个数据集随机分为d和s，并进一步将d中的数据按比例划分为训练集dt和测试集dv，同时将s中存在d中不存的链路作为正样本加入到测试集dv中。选择集合dt和dv中的所有链路，随机提取相同数量的没有直连边的节点对作为负样本来平衡数据集，构成最后划分好的训练集dt和测试集dv。
3.根据权利要求1所述的基于链路预测的商业关系推测方法，其特征在于，所述步骤s2具体为：使用训练集dt和测试集dv分别创建用于训练和测试目的的标记良好的数据集。这些数据集包含链路的特征以及它们在网络中对应的标签。链路的标签，表示链路的存在和不存在，存在为1，不存在为0。链路的特征根据各种节点相似性、节点重要性和as网络相关信息计算得到。
4.根据权利要求1所述的基于链路预测的商业关系推测方法，其特征在于，所述步骤s3具体为：使用标记良好和平衡良好的训练数据集来训练机器学习分类器xgboost，并使用测试数据集来测试分类器的预测能力。在训练并测试完分类器后，使用该分类器来预测整个网络中的隐藏链路。
5.根据权利要求1所述的基于链路预测的商业关系推测方法，其特征在于，所述步骤s4具体为：当得到网络中的隐藏链路后，我们需要对隐藏链路上的商业关系(p2p，p2c\c2p)进行分类。首先，使用as rank来推导bgp路由数据集上的商业关系作为我们的真实as关系数据集t，对于t中的每条边，计算它的特征值并按照每条边的类型赋予相对应的标签。然后将t按比例划分为训练集t1和测试集t2，训练集t1用于训练模型xgboost，测试集t2用于测试模型。最后将训练好的模型用于对隐藏链路进行商业关系分类。
