一种社交网络中的链接预测方法

摘要

本发明公开了一种社交网络中的链接预测方法，属于数据挖掘领域，包括预处理、构建上下文感知嵌入、构建链接预测候选集以及将下文感知嵌入与链接预测候选集结合进行相似度计算，本发明中，通过构建上下文感知嵌入找到用户具有相似行为模式的上下文情景，从而捕获了之前传统方法所遗漏的信息，将潜在的社会影响力实例化，提高了社交网络中链接预测的准确性，并将其与节点结构信息，得到了用户在社交网络中精确表示，提高了社交网络链路预测的准确性和性能，解决了传统的方法只考虑节点与相邻节点之间的影响力交互，并没有从整张社交网络的层面挖掘隐藏的社会影响力信息的问题。

说明书

技术领域

本发明涉及数据挖掘技术领域，具体为一种社交网络中的链接预测方法。

背景技术

随着社交网络的普及与发展，诸如Facebook、Twitter、微博等社交网络在人们的生活中扮演着越来越重要的角色，人们的社交方式和沟通理念也因此随之改变；社交网络中蕴含着大量的信息，给研究人员提供了一个前所未有的机会去探索人类的行为模式；对社交网络的研究，一直都是数据挖掘领域的热门；不同于一般的数据挖掘，社交网络中的数据具有其异构多样的特点，例如大部分人都只有很少的链接，但是有一小部分人他们的链接数量远多于其他人；又例如社群结构，社交网络里面会存在很多个小群体。

链接预测作为社交网络的基本研究问题，是为了从现有的网络中寻找潜在的链接，或者预测未来网络可能出现或断开的链接；它在许多领域可以得以应用，最典型的如推荐系统：社交网络中的好友推荐、在线购物网站的商品推荐、音乐应用中的歌曲推荐等。显然有效的链接预测，可以提升用户体验，提高用户对于应用的粘性，增加用户对社交网络的忠诚度。

传统的链接预测方法有基于相似性的方法，其主要是通过计算每对节点的相似度，以确定它们是否存在连接；这种方法的一个重要前提就是相似度越高的节点对，越倾向于存在链接；相似度主要可以分为两种，一种是通过节点的属性来度量，例如位置、年龄和性别等；另一种是通过拓扑特征来度量的相似性，例如共同邻居数量；这些方法基于这样的原理，即具有较大相似性的节点对往往更倾向于具有潜在的关系；这种方法的计算较为简单，可以快速推断出潜在的联系；但是，这些方法存在着明显的缺陷；首先，它将节点属性和拓扑特征视为独立，因此而缺乏一致性以及一个合适的能够同时使用这两种类型的相关特征来定义相似性的方法；其次，由于节点不同，模型的预测能力可能会有很大差异。

为了克服这一缺点，一些基于概率的策略方法被提出，这些方法将节点属性和拓扑特征属性作为随机变量，以从观测的网络中学习链接的概率分布，并利用假设的潜在结构来估算链接关系；但是这种方法的计算复杂，且在现实应用中很难事先获得基于概率模型所非常必要的链接分布情况，所以急需一种社交网络中的链接预测方法来解决上述问题。

发明内容

本发明提供一种结合用户节点的上下文情景信息以及节点结构信息，提高了社交网络链路预测的准确性和性能的社交网络中链接预测的方法。

为实现上述目的，本发明提供如下技术方案：一种社交网络中的链接预测方法，包括如下步骤：

S1、对社交网络进行预处理，移除社交网络中的明显噪点和未执行过任何动作的节点，并对社交网络中的缺失值进行补全；

S2、在预处理过的社交网络中构建节点对应的动作序列，形成数据集，其中，动作序列中的每个动作包括用户标识、动作项、动作主题和动作时间戳；

S3、构建上下文感知嵌入，具体为：

a、从数据集中获取用户节点对应的动作序列，计算各主题下每条边的影响因子，并结合单个用户节点的动作序列计算各主题影响标识；

b、利用各主题的影响标识的嵌入，计算对应的用户节点社交活动上下文中心嵌入；

c、基于欧氏距离模型原理构建上下文中心嵌入与主题影响标识嵌入的距离模型，根据距离模型对上下文进行聚类，将聚类结果构建成上下文感知嵌入；

S4、构建链接预测候选集，具体为：

a、通过GNN模型从数据集中获取用户关注节点的结构嵌入；

b、通过对节点与其相邻节点结构聚类，构建基于注意力的节点关注权重以及关注半径；

c、利用节点关注权重以及关注半径与社交网络中的节点进行初步结构性相似度比对，通过节点结构差异性获得候选节点对，并构建链接预测候选集；

S5、将候选集与上下文感知嵌入结合，对候选集中的节点对进行上下文情景嵌入的相似度计算，并选取Top-K候选节点对子集作为链接预测结果。

根据上述技术方案，在步骤S2中，动作序列中的每个动作标识都带有相应的主题以及对应的动作时间戳，动作项表示为：

根据上述技术方案，在所述步骤S3中，边的影响因子是通过计算对应边所连接两个节点之间的社交活动影响频率，其中，当边的两个节点都在同一主题下产生了动作，并且尾节点动作时间在头结点动作时间之后，则影响频率增加。

根据上述技术方案，在所述步骤S3中，主题影响标识计算公式为：

其中，

根据上述技术方案，在所述步骤S3中，距离模型的计算公式为：

根据上述技术方案，在步骤S4中，节点结构聚类过程中，采用了最速梯度下降优化方法，通过最小化节点与其相邻节点结构之间的差异性，得到节点相应的节点关注权重以及关注半径，其中，关注半径公式为

根据上述技术方案，在步骤S5中，相似度计算公式为：

与现有技术相比，本发明的有益效果：

1、本发明中，通过构建上下文感知嵌入找到用户具有相似行为模式的上下文情景，从而捕获了之前传统方法所遗漏的信息，将潜在的社会影响力实例化，提高了社交网络中链接预测的准确性，并将其与节点结构信息，得到了用户在社交网络中精确表示，提高了社交网络链路预测的准确性和性能，解决了传统的方法只考虑节点与相邻节点之间的影响力交互，并没有从整张社交网络的层面挖掘隐藏的社会影响力信息的问题。

2、在构建链接预测候选集时，通过社交网络本身的结构信息来进行节点聚类，既保留关键信息，又能保证预测效果，同时减少了计算成本；且本发明主要关注社交网络中用户行为本身，而不需要获取大量的社交网络用户隐私信息来进行预测，从而保障了用户的隐私。

3、本发明对社交网络进行预处理，移除没有任何社会活动节点，提高后期预测的准确性以及效率，同时对于明显噪点采用直接移除的方法，确保了方法的鲁棒性。

附图说明

附图用来提供对本发明的进一步理解，并且构成说明书的一部分，与本发明的实施例一起用于解释本发明，并不构成对本发明的限制。

在附图中：

图1是本发明链接预测方法流程框图。

具体实施方式

以下结合附图对本发明的优选实施例进行说明，应当理解，此处所描述的优选实施例仅用于说明和解释本发明，并不用于限定本发明。

实施例：如图1所示，一种社交网络中的链接预测方法，包括如下步骤：

S1、对社交网络进行预处理，移除社交网络中的明显噪点和未执行过任何动作的节点，并对社交网络中的缺失值进行补全；

S2、在预处理过的社交网络中构建节点对应的动作序列，形成数据集，其中，动作序列中的每个动作包括用户标识、动作项、动作主题和动作时间戳，其中，动作序列中的每个动作标识都带有相应的主题以及对应的动作时间戳，动作项表示为：

S3、构建上下文感知嵌入，具体为：

a、从数据集中获取用户节点对应的动作序列，计算各主题下每条边的影响因子，边的影响因子是通过计算对应边所连接两个节点之间的社交活动影响频率，其中，当边的两个节点都在同一主题下产生了动作，并且尾节点动作时间在头结点动作时间之后，则影响频率增加，并通过如下公式计算各主题影响标识：

其中，

b、利用各主题的影响标识的嵌入，计算对应的用户节点社交活动上下文中心嵌入；

c、基于欧氏距离模型原理构建上下文中心嵌入与主题影响标识嵌入的距离模型，其中，距离模型的计算公式为：

S4、构建链接预测候选集，具体为：

a、通过GNN(图神经网络)利用节点以及相邻节点之间的信息传递，在传播层稳定的情况下，获得节点的结构嵌入；

b、通过对节点与其相邻节点结构聚类，其中，采用了最速梯度下降优化方法，通过最小化节点与其相邻节点结构之间的差异性，得到节点相应的节点关注权重以及关注半径，注半径公式为

c、利用节点关注权重以及关注半径与社交网络中的节点进行初步结构性相似度比对，通过节点结构差异性获得候选节点对，并构建链接预测候选集；

S5、将候选集与上下文感知嵌入结合，对候选集中的节点对进行上下文情景嵌入的相似度计算，其中，相似度计算公式为：

在一具体实施中，环境配置如下：Linux中的Ubuntu系统，CPU主频3.40GHZ，以及内存8G，编程语言为Python 3.6.5，并在集成开发环境PyCharm下完成；

其中，使用的数据来自Digg社交网络，数据集主要包括用户集合、用户社交集合、社交活动集合以及项目集合，Digg数据集是高度连接的社交网络，平均每个用户有43个邻居，只有一小部分用户有超过100个邻居，基本符合正态分布特征，且社交网络中的用户社交活动也十分频繁，平均每个用户有930个动作，然而每个用户的动作执行数呈指数分布，通过上述方式对原始数据集进行清洗处理，保证数据集的真实性以及有效性，在数据预处理层去除任何头尾节点都没有执行任何动作的边，且当没有任何用户对某一主题动作执行任何操作，那么这一主题的所有动作也会被删除，本实施例中，将数据集所有时间戳格式统一；

在构建上下文感知嵌入时，对K＝4、6、8、10学习各自上下文，当K＝4 时，上下文情景分类不够清晰，粒度比较大，主要分为一个大的上下文情景，三个小的上下文情景，其中,在Digg社交网络中一个上下文情景包括婴儿、教育、购物以及政治新闻，婴儿和教育以及购物具有关联性，因为大多数关注婴儿的用户大多也会对教育以及购物感兴趣，此外，由于Digg用户大多是年龄在 25-35之间的女性，他们作为母亲以及家庭主妇需要关注婴儿以及孩子的教育还要关注购物，以及拥有大量闲暇时光浏览新闻关注政治信息；因为Digg网络中大多数社交活动都是这一组用户产生的；对于K＝6，上下文情景划分变得清晰；当K＝8时，上下文情景划分变得进一步清晰，并且每个上下文情景大小合适；当K＝10时，上下文情景基本趋于稳定，同时出现异常类别一些主题(例如：体育、科技和政治新闻)分成一个单独上下文情景；

在构建链接预测候选集时，首先计算分析了通过单一的节点嵌入相似性进行链路预测的效果，并与基于传统拓扑结构度量方法(公共邻居、Jaccard coefficient、Adamicscore、Preferential attachment、Resource allocation、 Salton index)的结果进行对比，对比结果表明采用GNN方法效率高，在有效性上远远超过传统拓扑结构度量方法，且链路预测的top-500准确性达到了 67.8％几乎达到了基于传统拓扑结构算法的两倍，链路预测AUC score也比其他方法高出至少15％，所以采用GNN对Digg数据集中的社交网络节点进行了嵌入，并在构建每个节点的关注半径时，引入腐蚀参数对关注半径进行一定软化以此来保证发明的有效性；

如下表所示，是不同K和δ不同参数值下的平均召回率：以下表格是不同K和δ不同参数值下的平均召回率：

由表可得，当K＝8，GNN嵌入维度10，腐蚀参数5％并且加入注意力机制的配置下链路预测效果达到了最优，AUC Score为0.895，Top-500准确度为 91.28％。

最后应说明的是：以上所述仅为本发明的优选实例而已，并不用于限制本发明，尽管参照前述实施例对本发明进行了详细的说明，对于本领域的技术人员来说，其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。