一种链路预测方法和装置

摘要

本发明公开了一种链路预测方法和装置，涉及计算机技术领域。该方法的一具体实施方式包括：根据现有关系网络数据生成第一训练集，所述第一训练集包括现有关系网络的各条边的类别标签，其中，边表示关系网络中两个用户间的关系，所述边的类别标签指示两个用户间的关系是否存在；对选定模型进行参数优化，利用参数优化后的选定模型修正所述第一训练集中各条边的类别标签，以得到第二训练集；利用所述第二训练集训练链路预测模型；使用训练后的链路预测模型对输入的关系网络数据进行链路预测。该实施方式能够提高链路预测的准确性，改善关系网络数据挖掘的效果。

权利要求

1.一种链路预测方法，其特征在于，包括：根据现有关系网络数据生成第一训练集，所述第一训练集包括现有关系网络的各条边的类别标签，其中，边表示关系网络中两个用户间的关系，所述边的类别标签指示两个用户间的关系是否存在；

对选定模型进行参数优化，利用参数优化后的选定模型修正所述第一训练集中各条边的类别标签，以得到第二训练集；对选定模型进行参数优化的步骤，包括：初始化所述选定模型的多组参数；在所述选定模型的每组参数下，利用所述选定模型修正所述第一训练集中各条边的类别标签，以得到第三训练集，并利用所述第三训练集对链路预测模型执行第一训练，使用第一训练后的链路预测模型对预先生成的测试集进行链路预测，并根据预测结果计算该组参数下链路预测模型的预测准确度；根据所述多组参数和各组参数下链路预测模型的预测准确度，建立选定模型参数与链路预测模型的预测准确度之间的函数关系式；利用遗传算法优化所述函数关系式中的选定模型参数，得到所述参数优化后的选定模型的参数；

利用所述第二训练集训练链路预测模型；

使用训练后的链路预测模型对输入的关系网络数据进行链路预测。

2.根据权利要求1所述的方法，其特征在于，所述选定模型用于生成所述各条边的预测值，

修正所述第一训练集中各条边的类别标签，包括：将所述第一训练集中各条边的类别标签替换为所述各条边的预测值。

3.根据权利要求1所述的方法，其特征在于，根据现有关系网络数据生成第一训练集的步骤，包括：

根据现有关系网络数据，按照预设指标计算所述现有关系网络的各条边的特征集；

根据所述各条边的特征集和所述各条边的类别标签得到数据集；

将所述数据集按照预设比例划分为两部分，以其中一部分作为所述第一训练集；

所述测试集通过如下方式生成：

将所述数据集中除所述第一训练集之外的部分作为第一测试集；

对所述第一测试集进行多次采样，直到累计采样得到的样本总数量与所述第一测试集中样本数量相同时停止采样，将所有采样得到的样本的集合作为所述测试集。

4.根据权利要求1所述的方法，其特征在于，利用遗传算法优化所述函数关系式中的选定模型参数，得到所述参数优化后的选定模型的参数的步骤，包括：初始化种群，该种群中每一染色体通过将所述选定模型的一组参数值的二进制编码首尾连接得到；

对初始化的种群，计算种群中每个染色体对应的预测准确度，并判断其中的最高预测准确度是否达到预设要求，若是，则将对应最高预测准确度的染色体的二进制编码还原为一组十进制参数，作为所述参数优化后的选定模型的参数；若否，则对种群进行染色体选择、交叉和变异操作，以得到新的种群，并不断重复上述过程，直到某次得到的最新种群中染色体对应的最高预测准确度达到所述预设要求时，将对应最高预测准确度的一染色体的二进制编码还原为一组十进制参数，作为所述参数优化后的选定模型的参数；其中，染色体对应的预测准确度为将组成该染色体的二进制编码还原为所述选定模型的一组参数后，该组参数下链路预测模型的预测准确度，根据所述函数关系式计算所述染色体对应的预测准确度。

5.根据权利要求1所述的方法，其特征在于，所述选定模型为逻辑回归模型或前馈神经网络模型。

6.一种链路预测装置，其特征在于，包括：第一训练集生成模块，用于根据现有关系网络数据生成第一训练集，所述第一训练集包括现有关系网络的各条边的类别标签，其中，边表示关系网络中两个用户间的关系，所述边的类别标签指示两个用户间的关系是否存在；

第二训练集生成模块，用于对选定模型进行参数优化，利用参数优化后的选定模型修正所述第一训练集中各条边的类别标签，以得到第二训练集；其中，所述第二训练集生成模块包括参数优化子模块，用于：初始化所述选定模型的多组参数；在所述选定模型的每组参数下，利用所述选定模型修正所述第一训练集中各条边的类别标签，以得到第三训练集，并利用所述第三训练集对链路预测模型执行第一训练，使用第一训练后的链路预测模型对预先生成的测试集进行链路预测，并根据预测结果计算该组参数下链路预测模型的预测准确度；根据所述多组参数和各组参数下链路预测模型的预测准确度，建立选定模型参数与链路预测模型的预测准确度之间的函数关系式；利用遗传算法优化所述函数关系式中的选定模型参数，得到所述参数优化后的选定模型的参数；链路预测模型训练模块，用于利用所述第二训练集训练链路预测模型；

链路预测模块，用于使用训练后的链路预测模型对输入的关系网络数据进行链路预测。

7.一种电子设备，其特征在于，包括：一个或多个处理器；

存储器，用于存储一个或多个程序，当所述一个或多个程序被所述一个或多个处理器执行时，使得所述一个或多个处理器实现如权利要求1-5中任一所述的方法。

8.一种计算机可读介质，其上存储有计算机程序，其特征在于，所述程序被处理器执行时实现如权利要求1-5中任一所述的方法。

说明书

一种链路预测方法和装置

技术领域

[0001] 本发明涉及计算机技术领域，尤其涉及一种链路预测方法和装置。

背景技术

[0002] 链路预测(Link Prediction)，属于网络数据挖掘，是指利用已经表现出来的社交联系、金融交易关系等，挖掘或预测出用户尚未表现出来的社交等关系(这种关系也称作连
边)，链路预测技术广泛应用于社交好友推荐、异常交易监测等领域。

[0003] 现有技术大多基于已经观察到的邻接矩阵，将邻接矩阵中为0的边认为不存在，邻接矩阵中为1的边认为存在，在此基础上对边进行预测。但是现实的网络中并不能完整且正
确地观察到所有边，例如，虽然当前没有观测到，但是某一连边可能真实存在，或者，虽然观
察到该边存在，但是该边是虚假的，这些情况使得判定准确度大幅度下降。

[0004] 在实现本发明过程中，发明人发现现有技术中至少存在如下问题：

[0005] 现有链路预测方案的链路预测的准确性较低。

发明内容

[0006] 有鉴于此，本发明实施例提供一种链路预测方法和装置，能够提高链路预测的准确性，改善关系网络数据挖掘的效果。

[0007] 为实现上述目的，根据本发明实施例的一个方面，提供了一种链路预测方法。

[0008] 一种链路预测方法，包括：根据现有关系网络数据生成第一训练集，所述第一训练集包括现有关系网络的各条边的类别标签，其中，边表示关系网络中两个用户间的关系，所
述边的类别标签指示两个用户间的关系是否存在；对选定模型进行参数优化，利用参数优
化后的选定模型修正所述第一训练集中各条边的类别标签，以得到第二训练集；利用所述
第二训练集训练链路预测模型；使用训练后的链路预测模型对输入的关系网络数据进行链
路预测。

[0009] 可选地，对选定模型进行参数优化的步骤，包括：初始化所述选定模型的多组参数；在所述选定模型的每组参数下，利用所述选定模型修正所述第一训练集中各条边的类
别标签，以得到第三训练集，并利用所述第三训练集对所述链路预测模型执行第一训练，使
用第一训练后的链路预测模型对预先生成的测试集进行链路预测，并根据预测结果计算该
组参数下链路预测模型的预测准确度；根据所述多组参数和各组参数下链路预测模型的预
测准确度，建立选定模型参数与链路预测模型的预测准确度之间的函数关系式；利用遗传
算法优化所述函数关系式中的选定模型参数，得到所述参数优化后的选定模型的参数。

[0010] 可选地，所述选定模型用于生成所述各条边的预测值，修正所述第一训练集中各条边的类别标签，包括：将所述第一训练集中各条边的类别标签替换为所述各条边的预测
值。

[0011] 可选地，根据现有关系网络数据生成第一训练集的步骤，包括：根据现有关系网络数据，按照预设指标计算所述现有关系网络的各条边的特征集；根据所述各条边的特征集
和所述各条边的类别标签得到数据集；将所述数据集按照预设比例划分为两部分，以其中
一部分作为所述第一训练集；所述测试集通过如下方式生成：将所述数据集中除所述第一
训练集之外的部分作为第一测试集；对所述第一测试集进行多次采样，直到累计采样得到
的样本总数量与所述第一测试集中样本数量相同时停止采样，将所有采样得到的样本的集
合作为所述测试集。

[0012] 可选地，利用遗传算法优化所述函数关系式中的选定模型参数，得到所述参数优化后的选定模型的参数的步骤，包括：初始化种群，该种群中每一染色体通过将所述选定模
型的一组参数值的二进制编码首尾连接得到；对初始化的种群，计算种群中每个染色体对
应的预测准确度，并判断其中的最高预测准确度是否达到预设要求，若是，则将对应最高预
测准确度的染色体的二进制编码还原为一组十进制参数，作为所述参数优化后的选定模型
的参数；若否，则对种群进行染色体选择、交叉和变异操作，以得到新的种群，并不断重复上
述过程，直到某次得到的最新种群中染色体对应的最高预测准确度达到所述预设要求时，
将对应最高预测准确度的一染色体的二进制编码还原为一组十进制参数，作为所述参数优
化后的选定模型的参数；其中，染色体对应的预测准确度为将组成该染色体的二进制编码
还原为所述选定模型的一组参数后，该组参数下链路预测模型的预测准确度，根据所述函
数关系式计算所述染色体对应的预测准确度。

[0013] 可选地，所述选定模型为逻辑回归模型或前馈神经网络模型。

[0014] 根据本发明实施例的另一方面，提供了一种链路预测装置。

[0015] 一种链路预测装置，包括：第一训练集生成模块，用于根据现有关系网络数据生成第一训练集，所述第一训练集包括现有关系网络的各条边的类别标签，其中，边表示关系网
络中两个用户间的关系，所述边的类别标签指示两个用户间的关系是否存在；第二训练集
生成模块，用于对选定模型进行参数优化，利用参数优化后的选定模型修正所述第一训练
集中各条边的类别标签，以得到第二训练集；链路预测模型训练模块，用于利用所述第二训
练集训练链路预测模型；链路预测模块，用于使用训练后的链路预测模型对输入的关系网
络数据进行链路预测。

[0016] 可选地，所述第二训练集生成模块包括参数优化子模块，用于：初始化所述选定模型的多组参数；在所述选定模型的每组参数下，利用所述选定模型修正所述第一训练集中
各条边的类别标签，以得到第三训练集，并利用所述第三训练集对所述链路预测模型执行
第一训练，使用第一训练后的链路预测模型对预先生成的测试集进行链路预测，并根据预
测结果计算该组参数下链路预测模型的预测准确度；根据所述多组参数和各组参数下链路
预测模型的预测准确度，建立选定模型参数与链路预测模型的预测准确度之间的函数关系
式；利用遗传算法优化所述函数关系式中的选定模型参数，得到所述参数优化后的选定模
型的参数。

[0017] 可选地，所述选定模型用于生成所述各条边的预测值，修正所述第一训练集中各条边的类别标签，包括：将所述第一训练集中各条边的类别标签替换为所述各条边的预测
值。

[0018] 可选地，所述第一训练集生成模块还用于：根据现有关系网络数据，按照预设指标计算所述现有关系网络的各条边的特征集；根据所述各条边的特征集和所述各条边的类别
标签得到数据集；将所述数据集按照预设比例划分为两部分，以其中一部分作为所述第一
训练集；所述装置还包括测试集生成模块，用于通过如下方式生成所述测试集：将所述数据
集中除所述第一训练集之外的部分作为第一测试集；对所述第一测试集进行多次采样，直
到累计采样得到的样本总数量与所述第一测试集中样本数量相同时停止采样，将所有采样
得到的样本的集合作为所述测试集。

[0019] 可选地，所述参数优化子模块包括参数优化执行单元，用于：初始化种群，该种群中每一染色体通过将所述选定模型的一组参数值的二进制编码首尾连接得到；对初始化的
种群，计算种群中每个染色体对应的预测准确度，并判断其中的最高预测准确度是否达到
预设要求，若是，则将对应最高预测准确度的染色体的二进制编码还原为一组十进制参数，
作为所述参数优化后的选定模型的参数；若否，则对种群进行染色体选择、交叉和变异操
作，以得到新的种群，并不断重复上述过程，直到某次得到的最新种群中染色体对应的最高
预测准确度达到所述预设要求时，将对应最高预测准确度的一染色体的二进制编码还原为
一组十进制参数，作为所述参数优化后的选定模型的参数；其中，染色体对应的预测准确度
为将组成该染色体的二进制编码还原为所述选定模型的一组参数后，该组参数下链路预测
模型的预测准确度，根据所述函数关系式计算所述染色体对应的预测准确度。

[0020] 可选地，所述选定模型为逻辑回归模型或前馈神经网络模型。

[0021] 根据本发明实施例的又一方面，提供了一种电子设备。

[0022] 一种电子设备，包括：一个或多个处理器；存储器，用于存储一个或多个程序，当所述一个或多个程序被所述一个或多个处理器执行时，使得所述一个或多个处理器实现本发
明提供的链路预测方法。

[0023] 根据本发明实施例的又一方面，提供了一种计算机可读介质。

[0024] 一种计算机可读介质，其上存储有计算机程序，所述程序被处理器执行时实现本发明提供的链路预测方法。

[0025] 上述发明中的一个实施例具有如下优点或有益效果：根据现有关系网络数据生成第一训练集，第一训练集包括现有关系网络的各条边的类别标签；对选定模型进行参数优
化，利用参数优化后的选定模型修正第一训练集中各条边的类别标签，以得到第二训练集；
利用第二训练集训练链路预测模型；使用训练后的链路预测模型对输入的关系网络数据进
行链路预测。能够提高链路预测的准确性，改善关系网络数据挖掘的效果。

[0026] 上述的非惯用的可选方式所具有的进一步效果将在下文中结合具体实施方式加以说明。

附图说明

[0027] 附图用于更好地理解本发明，不构成对本发明的不当限定。其中：

[0028] 图1是根据本发明实施例的链路预测方法的主要步骤示意图；

[0029] 图2是根据本发明实施例的链路预测流程示意图；

[0030] 图3是根据本发明实施例的链路预测装置的主要模块示意图；

[0031] 图4是本发明实施例可以应用于其中的示例性系统架构图；

[0032] 图5是适于用来实现本发明实施例的终端设备或服务器的计算机系统的结构示意图。

具体实施方式

[0033] 以下结合附图对本发明的示范性实施例做出说明，其中包括本发明实施例的各种细节以助于理解，应当将它们认为仅仅是示范性的。因此，本领域普通技术人员应当认识
到，可以对这里描述的实施例做出各种改变和修改，而不会背离本发明的范围和精神。同
样，为了清楚和简明，以下的描述中省略了对公知功能和结构的描述。

[0034] 本领域技术技术人员知道，本发明的实施方式可以实现为一种系统、装置、设备、方法或计算机程序产品。因此，本公开可以具体实现为以下形式，即：完全的硬件、完全的软
件(包括固件、驻留软件、微代码等)，或者硬件和软件结合的形式。

[0035] 链路预测是指利用已经表现出来的社交联系、金融交易关系等，挖掘或预测出用户尚未表现出来的社交等关系，这种关系也称作连边。如在社交关系挖掘中，如果用户A与
用户B为好友关系，B与C为好友关系，则关系挖掘的目的是研究A与C是否有机会成为好友关
系。

[0036] 图1是根据本发明实施例的链路预测方法的主要步骤示意图。

[0037] 如图1所示，本发明实施例的链路预测方法主要包括如下的步骤S101至步骤S104。

[0038] 步骤S101：根据现有关系网络数据生成第一训练集。

[0039] 现有关系网络数据可以为网络数据图或邻接矩阵，获取用户之间关系的网络图，该网络图由节点(Node)与边(Edge)组成，其中节点代表用户，边代表关系网络中两个用户
间的关系，如果观察到两个用户间存在关系，则对应该条边存在，记为1，如未观察到该条
边，表示两个用户之间不存在关系，则记为0，从而将用户间的关系转换为网络数据图或邻
接矩阵，为方便计算，现有关系网络数据通常采用邻接矩阵的形式。

[0040] 在邻接矩阵中，例如如下形式(以用户数＝3为例，1表示边存在，0表示边不存在)：

[0041] 0 1 0

[0042] 1 0 1

[0043] 0 1 0

[0044] 根据现有关系网络数据，按照预设指标计算现有关系网络的各条边(包括观察到的边和未观察到的边)的特征集。计算现有关系网络的每条边的上述指标，组织成适合于链
路预测模型训练的数据格式，数据具体由行和列组成，其中每一行代表一条边，例如网络中
有3个用户，则对应会产生C32条边，每一列代表对应于该条边的一个特征，每个特征即上述
计算的一个指标值，每条边的指标值的集合构成该条边的特征集，从而得到现有关系网络
的各条边的特征集。

[0045] 每条边有各自的类别标签，边的类别标签指示两个用户间的关系是否存在，类别标签为1表示两个用户之间存在关系，类别标签为0表示两个用户之间不存在关系。

[0046] 根据现有关系网络的各条边的特征集和各条边的类别标签得到数据集，数据集的最后一列为各条边的类别标签，之前的各列为各条边的特征集。

[0047] 将该数据集按照预设比例划分为两部分，以其中一部分作为第一训练集、另一部分作为第一测试集。第一训练集即包括现有关系网络的各条边的特征集和类别标签，每一
行表示一条边，每条边对应的各列(最后一列除外)为该条边的特征，最后一列为该条边的
类别标签。

[0048] 上述预设指标可以采用共同邻居(CN)、平均通勤时间(ACT)、有重启的随机游走指标(RWR)、偏好连接相似性(PA)、局部路径指标(LP)、Katz指标等指标。其中，关系网络中某
个节点的邻居数是指与该节点相连接的其他节点的数目。两个节点如果有更多的共同邻
居，则它们更倾向于连边，例如A与B有一条连边，B与C有一条连边，则A与C的共同邻居为B。
定义平均首达时间m(x,y)为一个随机游走粒子从节点vx到节点vy平均需要的步数，那么节
点vx和vy的平均通勤时间n(x,y)＝m(x,y)+m(y,x)。局部路径指标(LP)是在共同邻居指标的
基础上考虑三阶邻居(即经过三条边连接两节点的路径)的贡献。Katz指标考虑的是连接两
个节点的所有可能的路径数。偏好连接相似性(PA)是指在关系网络中，一条即将加入的新
边连接到节点x的概率正比于节点x的度k(x)，因此新边连接节点x和y的概率正比于两节点
度的乘积，节点的度即节点的邻居数。有重启的随机游走指标(RWR)假设随机游走粒子在每
一步的时候都以一定概率返回初始位置，由此可以得到从某一节点开始游走的粒子在t步
到达每个节点的可能性。

[0049] 步骤S102：对选定模型进行参数优化，利用参数优化后的选定模型修正第一训练集中各条边的类别标签，以得到第二训练集。

[0050] 选定模型用于生成第一训练集中各条边的预测值，即对第一训练集中的每一行特征生成一个预测值(0或1)并且不进行任何训练。

[0051] 选定模型具体可以选择逻辑回归模型或前馈神经网络模型。

[0052] 对选定模型进行参数优化后，将优化后的选定模型参数代入选定模型，以利用参数优化后的选定模型对第一训练集中各条边重新预测，生成各条边的预测值，使用该预测
值替代第一训练集中各条边的类别标签后，得到的训练集即第二训练集。

[0053] 对选定模型进行参数优化的步骤，具体可以包括：初始化选定模型的多组参数；在选定模型的每组参数下，利用选定模型修正第一训练集中各条边的类别标签，以得到第三
训练集，并利用第三训练集对链路预测模型执行第一训练，使用第一训练后的链路预测模
型对预先生成的测试集进行链路预测，并根据预测结果计算该组参数下链路预测模型的预
测准确度；根据多组参数和各组参数下链路预测模型的预测准确度，建立选定模型参数与
链路预测模型的预测准确度之间的函数关系式；利用遗传算法优化该函数关系式中的选定
模型参数，得到参数优化后的选定模型的参数。

[0054] 修正第一训练集中各条边的类别标签，具体包括：将第一训练集中各条边的类别标签替换为各条边的预测值。在给定选定模型的参数后，选定模型可以为第一训练集中的
边生成新的类别标签，并可以组成新的训练集(即第三训练集)。

[0055] 链路预测模型可以采用机器学习模型，例如支持向量机模型、GBDT(梯度提升树)、随机森林等模型，还可以采用深度学习模型。

[0056] 使用第一训练后的链路预测模型对预先生成的测试集进行链路预测时，该测试集通过对第一测试集采样而生成，具体地，对第一测试集进行多次采样，直到累计采样得到的
样本总数量与第一测试集中样本数量相同时停止采样，将所有采样得到的样本的集合作为
该测试集。

[0057] 根据预测结果计算该组参数下链路预测模型的预测准确度，具体地，将预测结果与测试集的类别标签比对，根据比对一致的数量与预测结果总数量的比值得到该组参数下
链路预测模型的预测准确度。

[0058] 通过上述内容可知，给定选定模型的一组参数值f(x1,x2...)，(x1,x2...)为选定模型参数值，f表示选定模型，就可以得到对应该参数值下的预测准确度(记作y)，根据多组
参数值和对应的预测准确度可以得到选定模型参数与链路预测模型的预测准确度之间的
函数关系式：y＝g(f(x1,x2...))，其中g为准确度函数，该函数由选定模型与预测准确度的
度量方法两部分组成，该函数由于不可微分，所以无法使用传统的优化方法得到参数值，本
发明实施例将该步骤包装为函数形式，函数的输入值为选定模型参数，输出值为预测准确
度。

[0059] 上述利用遗传算法优化该函数关系式中的选定模型参数的步骤，可以包括：初始化种群，该种群中每一染色体通过将选定模型的一组参数值的二进制编码首尾连接得到；
对初始化的种群，计算种群中每个染色体对应的预测准确度，并判断其中的最高预测准确
度是否达到预设要求，若是，则将对应最高预测准确度的染色体的二进制编码还原为一组
十进制参数，作为参数优化后的选定模型的参数；若否，则对种群进行染色体选择、交叉和
变异操作，以得到新的种群，并不断重复上述过程，直到某次得到的最新种群中染色体对应
的最高预测准确度达到预设要求时，将对应最高预测准确度的一染色体的二进制编码还原
为一组十进制参数，作为参数优化后的选定模型的参数；其中，染色体对应的预测准确度为
将组成该染色体的二进制编码还原为选定模型的一组参数后，该组参数下链路预测模型的
预测准确度，根据函数关系式计算所述染色体对应的预测准确度。

[0060] 利用遗传算法优化该函数关系式中的选定模型参数之前，预先选定精度、区间和编码方式，具体地，可以取选定模型参数精度为小数点后3位，参数区间取[-1,1]，这代表所
有参数都将在这个区间中，编码方式选择二进制编码，具体地，采用区间划分，通过将有限
区间划分为小段，如[0,1]以0.1为精度划分为10段，则这10段区间可以用2^4>10，即4位二
进制数表示。例如0.637197可以编码为1000101110110101000111。

[0061] 初始化的种群中染色体数量可以设定为50个，即随机初始化50组选定模型参数值。对每一组参数值进行二进制编码并首尾连接。以一组参数的随机初始化值是
[0.637197,0.637197]为例，首先进行二进制编码为[1000101110110101000111,
1000101110110101000111]，随后将二进制编码首尾连接为：

[0062] 10001011101101010001111000101110110101000111，

[0063] 并将该连接后的值称为染色体，连接之前的每一个二进制编码，即1000101110110101000111称为基因。按照该方法，通过对50组参数，分别将每组参数值的二
进制编码收尾连接，生成50个连接后的值，并将该50组值的集合称为初始化的种群。

[0064] 计算种群中每个染色体对应的预测准确度，具体地，可以将每条染色体拆分为基因片段(即基因)后，对基因片段进行二进制到十进制的还原，即可得到十进制下的参数值，
将该参数值代入选定模型参数与链路预测模型的预测准确度之间的函数关系式，即可得到
对应于该参数值下的预测准确度，50组参数值对应50个染色体，50个染色体相应可得到50
个预测准确度。

[0065] 对种群进行染色体选择时，根据计算得到的种群中每个染色体对应的预测准确度，选择一定数量的染色体。预测准确度高的染色体有更高的被选择概率，例如有两个染色
体，对应的预测准确度为[0.6,0.3]，则第一个染色体被选择的概率为0.6/(0.3+0.6)＝
0.66，第二个染色体被选择概率为0.3/(0.3+0.6)＝0.34，则可以根据该选择概率进行采
样，概率大的染色体有更高的概率被选中，例如可以从50个染色体中选择25个染色体。

[0066] 对经染色体选择所选出的染色体进行染色体交叉操作，具体地，对选出的染色体，每次选用两个染色体进行交叉，得到两条新染色体，直到交叉得到的新染色体数量与种群
中原染色体数量相同，例如选出的25个染色体经25次交叉操作后，得到50个新染色体。

[0067] 以如下两个染色体为例说明染色体的交叉操作，交叉前：

[0068] 0000 1100 1101

[0069] 0011 0101 0101

[0070] 交叉后：

[0071] 0000 0101 1101

[0072] 0011 1100 0101

[0073] 其中，加黑部分(即染色体12位编码的中间4位)为交叉部分，将“1100”与“0101”交叉后，得到两条新的染色体。

[0074] 对经交叉操作后得到的新染色体进行变异操作，具体地，对交叉后得到的新染色体的每一条染色体选择任意m(m的取值由人工提前设置)个小节点进行变异操作，变异操作
即将原始节点“1”变成“0”、将原始节点“0”变成“1”。例如变异前：

[0075] 0001 0110 0101

[0076] 变异后：

[0077] 0001 0111 0101

[0078] 对加黑的节点(即第8个节点)进行变异后，将该原始节点“0”变为“1”。

[0079] 通过对当前种群中染色体进行选择、交叉和变异之后，可以得到新的种群，对新的种群再计算每个染色体对应的预测准确度，并判断其中的最高预测准确度是否满足预设要
求，若不满足预设要求，则以该新的种群作为当前种群，继续进行染色体选择、交叉和变异，
再得到新的种群，如此循环，直到某次得到的最新种群中染色体的最高预测准确度满足预
设要求时，停止循环，并输出参数优化后的选定模型的参数，参数优化后的选定模型的参数
通过将对应最高预测准确度的染色体的二进制编码还原为十进制而得到。

[0080] 其中，在满足如下条件时可以视为上述最高预测准确度满足预设要求：当前种群的最高预测准确度在之后的n次(n的取值根据需要设定)优化过程中仍然是最高的；或者，
如果当前种群中有某一个染色体对应的预测准确度达到了预设的准确度值。

[0081] 步骤S103：利用第二训练集训练链路预测模型。

[0082] 第二训练集包括现有关系网络的各条边的特征集和修正后的类别标签。以现有关系网络的各条边的特征集为链路预测模型的输入，并以该修正后的类别标签为训练目标，
训练链路预测模型，得到训练后的链路预测模型。

[0083] 步骤S104：使用训练后的链路预测模型对输入的关系网络数据进行链路预测。

[0084] 根据输入的关系网络数据，按照预设指标可以计算输入的关系网络的各条边(包括观察到的边和未观察到的边)的特征集。将输入的关系网络的各条边的特征集输入训练
后的链路预测模型，以确定该关系网络的各条边(用户间关系)是否存在。

[0085] 本发明实施例使得在关系网络的链路预测中，如果存在大量无法观察到却真实存在的边和虚假边，链路预测效果相较于现有技术有明显地提升。

[0086] 图2是根据本发明实施例的链路预测流程示意图。

[0087] 本实施例中，选定模型为逻辑回归模型、链路预测模型为支持向量机模型。

[0088] 在许多链路预测的应用场景中，存在大量的节点之间的关系无法被观察到，或者节点之间存在的关系是虚假的。例如在用户间的金融关系中，存在用户A、B、C，其中可以通
过用户的转账数据发现用户A、B之间存在转账关系，但是B、C之间则通过现金交易，并且无
法观察到该关系。现有技术则认为B、C间既然没有观察到，则B、C间不存在任何金融关系，从
而导致挖掘关系的模型效果受到影响。本实施例利用逻辑回归模型调整此类错误的关系，
在调整之后进行建模，从而提高最后的支持向量机模型的链路预测效果。

[0089] 如图2所示，本发明实施例的链路预测流程包括如下的步骤S201至步骤S208。

[0090] 步骤S201：获取用户之间关系的网络图，将用户间的关系转换为邻接矩阵。

[0091] 步骤S202：根据邻接矩阵计算现有关系网络的各条边的共同邻居(CN)、平均通勤时间(ACT)、有重启的随机游走指标(RWR)、偏好连接相似性(PA)、局部路径指标(LP)、Katz
指标等指标，以得到各条边的特征集。

[0092] 步骤S203：生成适合链路模型训练的数据格式的数据集。

[0093] 数据集包括现有关系网络的各条边的特征集和各条边的类别标签。

[0094] 步骤S204：初始化逻辑回归模型和初始化支持向量机模型，并将数据集划分为第一训练集和第一测试集，以建立输入为逻辑回归参数、输出为支持向量机模型的预测准确
度的函数形式。

[0095] 具体地，初始化逻辑回归模型的多组参数(即多组逻辑回归参数)，在每组参数下，利用逻辑回归模型修正第一训练集中各条边的类别标签，以得到第三训练集，并利用第三
训练集对初始化的支持向量机模型执行第一训练，使用第一训练后的支持向量机模型对预
先生成的测试集进行链路预测，并根据预测结果计算该组参数下支持向量机模型的预测准
确度；根据多组参数和各组参数下支持向量机模型的预测准确度，建立逻辑回归参数与支
持向量机模型的预测准确度之间的函数关系式，该函数形式的输入为逻辑回归参数、输出
为支持向量机模型的预测准确度。其中，测试集根据第一测试集生成，具体生成方法上文已
经介绍，此处不再赘述。

[0096] 步骤S205：使用遗传算法对函数形式中的逻辑回归参数进行优化。

[0097] 具体包括，初始化种群，该种群中每一染色体通过将逻辑回归模型的一组参数值的二进制编码首尾连接得到；对初始化的种群，计算种群中每个染色体对应的预测准确度，
并判断其中的最高预测准确度是否达到预设要求，若是，则将对应最高预测准确度的染色
体的二进制编码还原为一组十进制参数，作为参数优化后的逻辑回归参数；若否，则对种群
进行染色体选择、交叉和变异操作，以得到新的种群，并不断重复上述过程，直到某次得到
的最新种群中染色体对应的最高预测准确度达到预设要求时，将对应最高预测准确度的一
染色体的二进制编码还原为一组十进制参数，作为参数优化后的逻辑回归参数；其中，染色
体对应的预测准确度为将组成该染色体的二进制编码还原为逻辑回归模型的一组参数后，
该组参数下支持向量机模型的预测准确度，根据函数关系式计算染色体对应的预测准确
度。

[0098] 步骤S206：在优化后的逻辑回归参数下，利用逻辑回归模型对第一训练集中各条边重新预测，生成各条边的预测值，并使用该预测值替代第一训练集中各条边的类别标签，
得到第二训练集。

[0099] 步骤S207：使用第二训练集训练支持向量机模型。

[0100] 步骤S208：将一关系网络的各条边的特征集输入训练后的支持向量机模型，以确定该关系网络的各条边是否存在。

[0101] 该关系网络的各条边的特征集由输入的关系网络数据，按照预设指标计算得到。

[0102] 本实施例将支持向量机的预测准确度设计成函数模块，并使得该函数模块可以通过遗传算法进行优化，使用优化后的函数模块以提高链路预测的准确性，解决了当网络中
存在大量无法观察到却真实存在的边与虚假边时关系网络数据挖掘的效果差的缺陷。

[0103] 图3是根据本发明实施例的链路预测装置的主要模块示意图。

[0104] 如图3所示，链路预测装置300主要包括：第一训练集生成模块301、第二训练集生成模块302、链路预测模型训练模块303、链路预测模块304。

[0105] 第一训练集生成模块301，用于根据现有关系网络数据生成第一训练集，第一训练集包括现有关系网络的各条边的类别标签，其中，边表示关系网络中两个用户间的关系，边
的类别标签指示两个用户间的关系是否存在。

[0106] 第一训练集生成模块具体可以用于：根据现有关系网络数据，按照预设指标计算现有关系网络的各条边的特征集；根据该各条边的特征集和各条边的类别标签得到数据
集；将数据集按照预设比例划分为两部分，以其中一部分作为第一训练集。

[0107] 链路预测装置300还可以包括测试集生成模块，用于通过如下方式生成测试集：将数据集中除第一训练集之外的部分作为第一测试集；对第一测试集进行多次采样，直到累
计采样得到的样本总数量与第一测试集中样本数量相同时停止采样，将所有采样得到的样
本的集合作为测试集。

[0108] 第二训练集生成模块302，用于对选定模型进行参数优化，利用参数优化后的选定模型修正第一训练集中各条边的类别标签，以得到第二训练集。

[0109] 选定模型用于生成各条边的预测值。具体可以为逻辑回归模型或前馈神经网络模型。

[0110] 修正第一训练集中各条边的类别标签，包括：将第一训练集中各条边的类别标签替换为各条边的预测值。

[0111] 第二训练集生成模块302可以包括参数优化子模块，用于：初始化选定模型的多组参数；在选定模型的每组参数下，利用选定模型修正第一训练集中各条边的类别标签，以得
到第三训练集，并利用第三训练集对链路预测模型执行第一训练，使用第一训练后的链路
预测模型对预先生成的测试集进行链路预测，并根据预测结果计算该组参数下链路预测模
型的预测准确度；根据多组参数和各组参数下链路预测模型的预测准确度，建立选定模型
参数与链路预测模型的预测准确度之间的函数关系式；利用遗传算法优化函数关系式中的
选定模型参数，得到参数优化后的选定模型的参数。

[0112] 参数优化子模块可以包括参数优化执行单元，用于：初始化种群，该种群中每一染色体通过将选定模型的一组参数值的二进制编码首尾连接得到；对初始化的种群，计算种
群中每个染色体对应的预测准确度，并判断其中的最高预测准确度是否达到预设要求，若
是，则将对应最高预测准确度的染色体的二进制编码还原为一组十进制参数，作为参数优
化后的选定模型的参数；若否，则对种群进行染色体选择、交叉和变异操作，以得到新的种
群，并不断重复上述过程，直到某次得到的最新种群中染色体对应的最高预测准确度达到
预设要求时，将对应最高预测准确度的一染色体的二进制编码还原为一组十进制参数，作
为参数优化后的选定模型的参数；其中，染色体对应的预测准确度为将组成该染色体的二
进制编码还原为选定模型的一组参数后，该组参数下链路预测模型的预测准确度，根据函
数关系式计算染色体对应的预测准确度。

[0113] 链路预测模型训练模块303，用于利用第二训练集训练链路预测模型；

[0114] 链路预测模块304，用于使用训练后的链路预测模型对输入的关系网络数据进行链路预测。

[0115] 另外，在本发明实施例中链路预测装置的具体实施内容，在上面所述链路预测方法中已经详细说明了，故在此重复内容不再说明。

[0116] 图4示出了可以应用本发明实施例的链路预测方法或链路预测装置的示例性系统架构400。

[0117] 如图4所示，系统架构400可以包括终端设备401、402、403，网络404和服务器405。网络404用以在终端设备401、402、403和服务器405之间提供通信链路的介质。网络404可以
包括各种连接类型，例如有线、无线通信链路或者光纤电缆等等。

[0118] 用户可以使用终端设备401、402、403通过网络404与服务器405交互，以接收或发送消息等。终端设备401、402、403上可以安装有各种通讯客户端应用，例如购物类应用、网
页浏览器应用、搜索类应用、即时通信工具、邮箱客户端、社交平台软件等(仅为示例)。

[0119] 终端设备401、402、403可以是具有显示屏并且支持网页浏览的各种电子设备，包括但不限于智能手机、平板电脑、膝上型便携计算机和台式计算机等等。

[0120] 服务器405可以是提供各种服务的服务器，例如对用户利用终端设备401、402、403所浏览的购物类网站提供支持的后台管理服务器(仅为示例)。后台管理服务器可以对接收
到的产品信息查询请求等数据进行分析等处理，并将处理结果(例如目标推送信息、产品信
息--仅为示例)反馈给终端设备。

[0121] 需要说明的是，本发明实施例所提供的链路预测方法一般由服务器405执行，相应地，链路预测装置一般设置于服务器405中。

[0122] 应该理解，图4中的终端设备、网络和服务器的数目仅仅是示意性的。根据实现需要，可以具有任意数目的终端设备、网络和服务器。

[0123] 下面参考图5，其示出了适于用来实现本申请实施例的终端设备或服务器的计算机系统500的结构示意图。图5示出的终端设备或服务器仅仅是一个示例，不应对本申请实
施例的功能和使用范围带来任何限制。

[0124] 如图5所示，计算机系统500包括中央处理单元(CPU)501，其可以根据存储在只读存储器(ROM)502中的程序或者从存储部分508加载到随机访问存储器(RAM)503中的程序而
执行各种适当的动作和处理。在RAM 503中，还存储有系统500操作所需的各种程序和数据。
CPU 501、ROM 502以及RAM 503通过总线504彼此相连。输入/输出(I/O)接口505也连接至总
线504。

[0125] 以下部件连接至I/O接口505：包括键盘、鼠标等的输入部分506；包括诸如阴极射线管(CRT)、液晶显示器(LCD)等以及扬声器等的输出部分507；包括硬盘等的存储部分508；
以及包括诸如LAN卡、调制解调器等的网络接口卡的通信部分509。通信部分509经由诸如因
特网的网络执行通信处理。驱动器510也根据需要连接至I/O接口505。可拆卸介质511，诸如
磁盘、光盘、磁光盘、半导体存储器等等，根据需要安装在驱动器510上，以便于从其上读出
的计算机程序根据需要被安装入存储部分508。

[0126] 特别地，根据本发明公开的实施例，上文参考流程图描述的过程可以被实现为计算机软件程序。例如，本发明公开的实施例包括一种计算机程序产品，其包括承载在计算机
可读介质上的计算机程序，该计算机程序包含用于执行流程图所示的方法的程序代码。在
这样的实施例中，该计算机程序可以通过通信部分509从网络上被下载和安装，和/或从可
拆卸介质511被安装。在该计算机程序被中央处理单元(CPU)501执行时，执行本申请的系统
中限定的上述功能。

[0127] 需要说明的是，本发明所示的计算机可读介质可以是计算机可读信号介质或者计算机可读存储介质或者是上述两者的任意组合。计算机可读存储介质例如可以是——但不
限于——电、磁、光、电磁、红外线、或半导体的系统、装置或器件，或者任意以上的组合。计
算机可读存储介质的更具体的例子可以包括但不限于：具有一个或多个导线的电连接、便
携式计算机磁盘、硬盘、随机访问存储器(RAM)、只读存储器(ROM)、可擦式可编程只读存储
器(EPROM或闪存)、光纤、便携式紧凑磁盘只读存储器(CD-ROM)、光存储器件、磁存储器件、
或者上述的任意合适的组合。在本申请中，计算机可读存储介质可以是任何包含或存储程
序的有形介质，该程序可以被指令执行系统、装置或者器件使用或者与其结合使用。而在本
申请中，计算机可读的信号介质可以包括在基带中或者作为载波一部分传播的数据信号，
其中承载了计算机可读的程序代码。这种传播的数据信号可以采用多种形式，包括但不限
于电磁信号、光信号或上述的任意合适的组合。计算机可读的信号介质还可以是计算机可
读存储介质以外的任何计算机可读介质，该计算机可读介质可以发送、传播或者传输用于
由指令执行系统、装置或者器件使用或者与其结合使用的程序。计算机可读介质上包含的
程序代码可以用任何适当的介质传输，包括但不限于：无线、电线、光缆、RF等等，或者上述
的任意合适的组合。

[0128] 附图中的流程图和框图，图示了按照本申请各种实施例的系统、方法和计算机程序产品的可能实现的体系架构、功能和操作。在这点上，流程图或框图中的每个方框可以代
表一个模块、程序段、或代码的一部分，上述模块、程序段、或代码的一部分包含一个或多个
用于实现规定的逻辑功能的可执行指令。也应当注意，在有些作为替换的实现中，方框中所
标注的功能也可以以不同于附图中所标注的顺序发生。例如，两个接连地表示的方框实际
上可以基本并行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能而定。也要
注意的是，框图或流程图中的每个方框、以及框图或流程图中的方框的组合，可以用执行规
定的功能或操作的专用的基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组
合来实现。

[0129] 描述于本发明实施例中所涉及到的模块可以通过软件的方式实现，也可以通过硬件的方式来实现。所描述的模块也可以设置在处理器中，例如，可以描述为：一种处理器包
括第一训练集生成模块、第二训练集生成模块、链路预测模型训练模块、链路预测模块。其
中，这些模块的名称在某种情况下并不构成对该模块本身的限定，例如，第一训练集生成模
块还可以被描述为“用于根据现有关系网络数据生成第一训练集的模块”。

[0130] 作为另一方面，本发明还提供了一种计算机可读介质，该计算机可读介质可以是上述实施例中描述的设备中所包含的；也可以是单独存在，而未装配入该设备中。上述计算
机可读介质承载有一个或者多个程序，当上述一个或者多个程序被一个该设备执行时，使
得该设备包括：根据现有关系网络数据生成第一训练集，所述第一训练集包括现有关系网
络的各条边的类别标签，其中，边表示关系网络中两个用户间的关系，所述边的类别标签指
示两个用户间的关系是否存在；对选定模型进行参数优化，利用参数优化后的选定模型修
正所述第一训练集中各条边的类别标签，以得到第二训练集；利用所述第二训练集训练链
路预测模型；使用训练后的链路预测模型对输入的关系网络数据进行链路预测。

[0131] 根据本发明实施例的技术方案，根据现有关系网络数据生成第一训练集，第一训练集包括现有关系网络的各条边的类别标签；对选定模型进行参数优化，利用参数优化后
的选定模型修正第一训练集中各条边的类别标签，以得到第二训练集；利用第二训练集训
练链路预测模型；使用训练后的链路预测模型对输入的关系网络数据进行链路预测。能够
提高链路预测的准确性，改善关系网络数据挖掘的效果。

[0132] 上述具体实施方式，并不构成对本发明保护范围的限制。本领域技术人员应该明白的是，取决于设计要求和其他因素，可以发生各种各样的修改、组合、子组合和替代。任何
在本发明的精神和原则之内所作的修改、等同替换和改进等，均应包含在本发明保护范围
之内。