一种基于长期收益的动态社交网络中的链接推荐方法

摘要

本发明涉及一种基于长期收益的动态社交网络中的链接推荐方法，对链接推荐问题上进行了更进一步的思考，提出了如何更有效地在动态社交网络中面向长期收益的链接推荐的技术方案。本方法将网络中个体选择与其他节点建立链接的过程视作一种在社交网络中“投资”的过程，在有限的代价预算下，为目标节点进行链接推荐以获取长期的社会资本收益，也即对于网络中目标节点，期望通过链接推荐挖掘出一些推荐节点，使得目标节点在当下选择与这些个体建立链接也许并不会带来最高的直接收益，随着网络的动态演化，能够获得更高的长远收益，最终在网络中处于更加优势的社会地位。

说明书

技术领域

本发明涉及一种基于长期收益的动态社交网络中的链接推荐方法，属于网络分析技术领域。

背景技术

随着网络的发展和普及，以及大数据时代的到来，在线社交网络受到越来越多用户的青睐。

在线社交网络，是指由成千上万的互联网用户通过自组织方式构建关系而组成的集合，也是真实物理世界的社交网络在虚拟网络世界的一种映射，其本质是人与人之间的关系网络。社交网络逐渐在连接真实社交世界和网络虚拟信息世界中发挥关键的桥梁作用，在人们的生活中扮演着一个重要的角色，它能够赋予我们从人群中获取或是分享更多信息及资源的能力，对个体的成长是至关重要的。

近年来，社交网络应用不断发展，利用社交网络产生的数据进行信息挖掘处理，如影响力最大化、链接预测和推荐、隐私安全等研究方向，在学术界和工业界引起广泛关注。

然而，随着互联网的迅速扩张，以及网络用户规模的日渐增长，网络中存在的海量信息会带来“信息过载”的现象，使得网络用户常常难以直接找到感兴趣或需要的各种资源。为了带来更好的用户体验，帮助用户融入不同网络社区，线上社交网络常常会有链接推荐功能，以此来为用户建立社交关系提供帮助，更好地满足用户的社交需求。

在对链接推荐问题的研究中，研究人员大多数关注的是目标用户会喜欢什么样的用户，更可能与什么样的用户建立链接，并致力于提升推荐算法的准确性。例如，在“用户-用户”网络或是“用户-物品”网络中，链接推荐的主要目的是准确地找到目标节点可能交互的其他节点或感兴趣的物品。

但是，社交网络中的节点可以通过其社会关系借用或获取其他的资源，例如财富、权力或声誉，为自身带来回报利益。因此，在很多真实的社交网络场景中，如合作关系网络、职场人脉关系网络、好友关系网络或是信息发布平台网络，其中的用户社交需求并不只是想要与“可能认识的人”或“可能感兴趣的人”建立链接。在这样的场景中，链接建立往往存在一定的目的性。用户期望获取更大的影响力，更多的信息资源，更中心的网络地位等社会资本收益，这便让链接推荐问题可以具有不同目的。因此，逐渐有部分方法考虑通过链接推荐给目标用户带来收益，例如：最小化最短路径长度，最大化中心度，最大化节点影响力等。

现有的推荐方法均是对收益的考虑局限于网络某时刻的静态的快照中。社交网络通常是一个复杂且动态变化的网络，网络会随着时间的变化，由于网络中节点的交互过程而不断演进。当网络中个体与其他个体建立链接，不仅会在当下时刻获得静态的即时收益，同时会随着网络的演化会在未来获得长远的收益。例如，在职场关系网络中的用户建立链接时会更加关注其人脉关系在长期时间内为其带来的资源和支持作用，在合作关系网络中建立链接时用户会关注长期时间下其网络中声望和地位的提升，乃至在国家间关系网络中，长远视角下的网络地位提升也对国家发展尤为重要。

发明内容

本发明的目的是针对现有的链接推荐方法缺少对网络动态性、链接建立代价以及链接建立收益考虑的缺陷，为了更加有效地在动态社交网络中面向长期收益的链接推荐，创造性地提出一种基于长期收益的动态社交网络中的链接推荐方法。

本发明的创新点在于：第一，将链接推荐能够给网络中节点带来的社会资本收益纳入考虑。第二，立足于动态网络视角，通过链接推荐给用户带来更长远的收益，突破了现有技术仅仅关注静态网络中即时收益反馈的局限，使得随着网络的演化，目标个体能够从推荐链接中获得更高的长期社会资本收益，在网络中最终长期处于更加优势的地位。第三，在链接建立模型中，引入链接代价模型以及有限代价预算来模拟真实的社交关系建立，符合有限管理关注限制。

在本发明方法中，将网络中个体选择与其他节点建立链接的过程视作一种在社交网络中“投资”的过程，在有限的代价预算下，为目标节点进行链接推荐以获取长期的社会资本收益，即，对于网络中目标节点，期望通过链接推荐挖掘出若干推荐节点，使得目标节点在当下选择与个体建立链接，也许并不会带来最高的直接收益，但随着网络的动态演化，能够获得更高的长远收益，最终在网络中处于更加优势的社会地位。

有益效果

本发明方法，对比现有技术，具有以下优点：

1.本方法将长期社会资本收益纳入考虑，能够帮助目标用户从推荐链接中获取长期的社会资本收益，让目标用户在网络中占据优势地位，对资源有更好的掌控与运用能力，从而获取回报利益。

2.本方法立足于动态网络的视角，考虑通过链接推荐给用户带来更长远的收益，突破了仅关注静态网络中即时收益反馈的局限，使得随着网络的演化，目标个体能够从推荐链接中获得更高的长期社会资本收益，在网络中最终长期地处于更加优势的地位。

3.本方法引入了链接代价模型以及有限的代价预算来模拟真实的社交关系建立，符合有限管理关注限制原则。

4.本方法利用动态社交网络中的历史演化进程数据来模拟动态网络演化，解决动态网络中没有先验的演化结果以及在推荐策略比较时无法在真实世界的时间中等待网络演化来观察推荐策略效果的困难。

附图说明

图1是动态社交网络在时间步序列上的表示示意图；

图2是动态社交网络中利用历史演化进程数据的长期收益评估方法说明；

图3是基于邻居惠利指标的邻居惠利推荐策略(NBS)计算说明图；

图4是部分不同推荐策略在为目标节点推荐社会关系之后，目标节点的社会收益变化示意图；

图5是NBS、GFPS及基线比较策略AA策略的在动态网络中不同的代价预算下，对不同目标节点执行链接推荐所带来的社会资本收益提升示意图；

图6是NBS、GFPS及基线比较策略AA策略的在动态网络中不同的代价预算下，对不同目标节点执行链接推荐所带来的社会地位提升示意图；

图7是NBS、GFPS及基线比较策略在不同的动态网络中在不同的推荐时刻下，对不同目标节点执行链接推荐所带来的社会资本收益提升示意图；

图8是NBS、GFPS及基线比较策略在不同的动态网络中在不同的推荐时刻下，对不同目标节点执行链接推荐所带来的社会地位提升示意图。

具体实施方式

下面结合附图和实施例对本发明方法做进一步详细说明。

一种基于长期收益的动态社交网络中的链接推荐方法，包括以下步骤：

将静态社交网络看作是一个没有多重边、也没有自连边的无向图G

由链接(u，v)直接连接的两个节点u、v称作邻接，用N(v)表示与节点u邻接的节点(邻居)的集合。网络中的路径用节点序列v

dist

步骤1：首先从社交网络社会理论中的社会资本效益角度和链接建立代价的限制出发，确定衡量长期社会资本收益以及链接代价模型，帮助目标用户在动态网络中从推荐链接中获取长期的社会资本，使其在网络中占据优势地位，对资源有更好的掌控与运用能力，从而获取回报利益。

具体地：

步骤1.1：利用网络中的接近中心性能够衡量节点对网络中其他节点的可达性的特性，结合社会资本概念和定义,衡量节点在网络中某时刻的社会资本 cl(G,v)：

其中，由G＝{V,E}表示一个网络图，v∈V,u∈V\{v}，n是节点v可达的节点数量，N是图中的节点总数。

步骤1.2：计算节点在动态网络中不同时刻的社会资本的差值，代表用户节点在社交网络演化中所取得的长期社会资本收益。

节点v从时间步t到时间步t+k之间所获取的长期收益为：

LtB

其中,G

链接推荐结果给节点带来的长期社会资本收益表示为：

LtB

其中，对于一个动态的社交网络，用一个按时间顺序标注的静态网络快照序列表示，即

步骤1.3：计算节点在不同时刻的社会资本衡量值在网络所有节点中的排序比例，代表节点在社交网络中的社会地位：

rank

其中，rank

同时，利用链接预测算法，建立链接建立代价的模型：

其中，一个链接预测算法视作一个计算网络中节点对的得分函数

步骤1.4：令B为链接代价预算，面向长期收益的链接推荐问题最终目标为：

其中，在一个动态社交网络

步骤2：在动态网络中，利用真实动态网络演化的历史演化进程数据模拟网动态网络的实际演化过程，并在模拟演化过程中实施链接推荐，分析和评估不同推荐策略的推荐效果，从而解决动态网络中没有先验演化结果、以及在推荐策略比较时无法在真实世界的时间中等待网络演化来观察推荐策略效果的困难。

具体地：

设有记录完整历史演化进程数据的动态网络

首先，在动态网络

然后，假设在目标节点v采纳了推荐链接，在网络中与结果节点集S中的全部节点建立链接关系，使得网络小范围变化之后，整个动态网络后续的演化进程保持不被影响，即，忽略目标节点建立链接的行动所带来的“蝴蝶效应”。设原网络在推荐时刻t

在网络

进一步地，重复利用网络演化中的历史演化进程数据，遵循上述步骤，选取不同的推荐时刻、评估时刻及目标节点，应用不同的推荐策略进行重复实验，以便进行对比分析。

步骤3：在链接建立模型中，引入链接代价模型和有限代价预算，对面向长期收益的链接推荐策略以及评价对比方法进行研究，设计了贪婪即时利益策略 (GFPS)和基于邻居惠利指标(NBS)策略的两个链接推荐算法。利用步骤2中的方法，利用历史数据来模拟演化进程。最后在生成网络数据集和真实网络数据集中对不同策略进行了实验比较和分析。

贪婪即时利益策略(GFPS)模拟社会中人们对利益的追求心理，即目标用户总是优先与当前网络中给自身带来即时收益高的节点连接。对目标节点v及其邻居以外的其他节点u，只考虑其在当下时刻与目标节点建立链接能够给目标节点v带来的社会资本回报，即

进一步地，GFPS推荐算法具体描述如下：

首先，利用步骤1所述方法，为目标节点计算出中心性和链接代价。随后，通过计算目标节点与其他节点建立链接能够为目标节点当前的社会资本带来的提升，在有限链接代价预算下为目标节点选取候选链接节点。

然后，利用步骤2所述方法，利用历史数据来模拟演化进程，观察目标节点的社会资本变化。

最后，在评估时间步，对目标节点评估长期社会资本收益。

不同于传统的链接推荐，在面向长期收益的链接推荐问题中，由于考虑了社会资本的长期收益，将链接的推荐选择看作是在当前网络中的一种投资活动，以有限的链接代价预算来获得最高的长期社会资本收益。因此，对于此问题的链接推荐进行了以下考虑：

1.由于想要在未来的时间里获取社会资本的提升，理应利用动态网络中过往的历史数据，在其中挖掘提取出能够评估候选节点的信息。

2.与资本经济中的股票投资相似，用户希望能够在所有提供的可选投资组合中获得投资回报。起初人们没有其他信息渠道时，通常会采取一种等待并观察的态度，通过观察其他人通过投资、持有特定的股票获得的利益情况，并决定是否跟进投资。相似地，在人际关系这种社会关系投资上，我们也可以将每一个候选节点视作提供给目标节点的“股票”。对于目标节点，通过评估各支“股票”可能为其他人带来的收益情况做出比较和选择。

为此，本发明提出了一个新的评估指标——邻居惠利指标(Neighbor-Beneficial Score,NBS)。

邻居惠利指标(NBS)用于衡量一个节点能够给它的邻居带来的收益程度，象征节点的邻居通过与该节点建立链接所获得的长期回报收益期望。基于NBS 的策略利用NBS，为目标节点推荐可能为其带来较高长期社会资本收益的目标节点。

本方法希望利用邻居惠利指标提取计算出节点u作为节点s的邻居，给节点s 带来的长期收益的可量化数值。对于节点s，节点u能够为其带来的长期收益为：

其中，用t

当计算出节点u的各个邻居可以从节点u获得的收益后，进一步考虑对于推荐的目标节点v，节点u能够给其带来多大程度的期望收益。如果节点 v也投资节点u，与其建立链接关系，则需要计算一个指标代表节点u对节点v的价值。NBS策略进一步计算节点u的各个邻居节点s相对于目标节点v的相似程度，认为与节点v越相似的邻居节点s，节点u能给节点v 带来的收益应该越近似于节点u给该邻居s带来的收益。同时，从时间跨度角度考虑，节点u给节点s带来长期收益的时间跨度也同样应该贡献于最终收益值。本策略假设带来的长期收益预期在时间上是稳定的。最终，将节点u 的邻居获益指标定义为：

其中，w

NBS策略推荐算法的具体描述如下：

实施例1

本实施例详细阐述了本发明方法的具体实施过程，给出了在3个真实动态社交网络中的固定推荐时刻下不同代价预算时开展链接推荐的效果展示。

本实施例中，首先由真实的动态社交网络数据集Hypertext2009、SFHH和CollegeMessage进行预处理，得到它们的动态演化历史数据集。

在数据集中，对目标节点推荐时给出不同的合适代价预算值B。在每一组实施实验中，首先，对各推荐策略在给出的有限代价预算下对不同的目标节点进行链接推荐。

图4展示了部分实验过程的案例，表现了在进行推荐策略对比过程中，节点在推荐时刻过后的社会资本的变化情况。这些例子从在Hypertext2009数据集推荐时刻在网络历史时间步的50％处，B＝4和SFHH数据集推荐时刻在网络历史时间步25％处，B＝4中的实验中选取的部分实验案例，图中，横坐标是时间步 (以坐标起点0表示推荐时刻)，纵坐标是节点在网络中的社会资本。

可以看出，在这些例子中，在经过推荐之后GFPS策略和NBS策略都使得节点的社会资本超过了传统链接预测推荐AA策略，同时，NBS策略对比GFPS 策略，往往是在推荐时刻节点采纳推荐后，对于目标节点从当下即时的社会资本收益角度来看，经过NBS策略推荐的结果往往低于或等同于经过GFPS策略的推荐结果。而后，随着网络的演化，经过NBS推荐策略推荐的链接优势慢慢出现，最终在距离推荐时刻的一段时间之后，经过NBS推荐策略的目标节点的社会资本收益超过了GFPS策略，表现出了更好的长期收益效果。这些案例表明 NBS策略能够在面对长期收益的问题场景之时表现出更好的效果。

图5和图6展示了NBS、GFPS及基线比较策略AA策略的在动态网络中不同的代价预算下，对不同目标节点执行链接推荐所带来的社会资本收益和社会地位提升示意。

在真实世界的社交网络数据集下，在相同推荐时刻，给与不同的链接代价预算，让推荐策略为不同的目标节点做出推荐，从整体实验数据中推荐策略给目标节点带来的长期社会资本收益的平均来看，NBS策略在不同的代价预算下，平均带来的社会资本收益基本上均超过了AA以及GFPS策略，对比GFPS策略平均有8％左右的提升，对比AA推荐策略平均提高18％以上。从社会地位排序提升来看，NBS策略给目标节点带来更高的社会资本的同时，也给网络中的节点地位排名带来了更高的提升，大部分情况下NBS相对于GFPS平均都有5％以上的提升，而相对AA平均有10％左右提升。可以说，在真实世界的社交网络中，NBS推荐方法表现优于其他两个策略。也意味着，在更加复杂的真实世界的社交网络模型中，面向长期收益的链接推荐问题，NBS策略能够更好地挖掘到能够在整个网络中给用户带来长远收益的其他用户。

实施例2

本实施例详细阐述了本发明方法具体实施时，在3个真实动态社交网络中的不同的推荐时刻开展链接推荐的效果展示。

在本实施例中，在评估方法框架下，在网络数据集演化的不同阶段实施推荐策略，并分析推荐时间对于推荐的影响。具体地，本实施例在真实的动态社交网络数据集Hypertext2009、SFHH和CollegeMessage进行了预处理得到它们的动态演化历史数据集，选取分别位于网络历史演化进程中的前期，中期和后期(分别对应在网络演化总时间步的25％，37.5％，50％，72.5％和75％处)的推荐时刻来进行推荐。

在不同的推荐时刻推荐，一方面是在网络演化的不同阶段，网络的状态不同，越早期的网络，其中的节点与社会关系相对更少，网络的整体结构可能尚未定型，例如网络的整体中心边缘结构还没有十分明显。另一方面，在网络的越早期推荐，到达最终评估时刻的网络演化时间越长，相对来说推荐策略在长期收益上的“长期”表现更加明显。

图7和图8展示了NBS、GFPS及基线比较策略在不同的动态网络中在不同的推荐时刻下，对不同目标节点执行链接推荐所带来的社会资本收益和社会地位提升效果。

从整体上看，NBS策略在不同网络推荐时刻，均有更优的表现。在网络演化的前期，中期和偏后期，NBS策略表现均超过了GFPS和AA策略，平均有 6％和16％左右的提升。在网络的前期时刻进行网络推荐时，最终NBS策略的表现相较GFPS和AA策略，提升的幅度要大一些。而随着推荐时刻的后移，NBS 策略相对GFPS策略的优势更不明显，在网络相对较后(75％以后)的时刻开始推荐，GFPS策略的带来的平均提升有些情况相对NBS策略的更优。在动态网络的前期阶段，网络的结构相对更简单，NBS策略通过对历史中的邻居惠利性进行分析，相比只面对当前网络的即时收益的GFPS，NBS策略能够更好地挖掘到能够最终给目标节点带来长远利益的节点。而到网络的后期时刻，网络已经比较成型，GFPS策略在此时直接找到当下收益较高的节点，而此时相对地距离评估时刻时间也已经不再那么“长期”了，NBS策略挖掘的链接效果不一定能够赶上GFPS策略，优势也相对不那么明显。

以上两个实施例展示了基于长期收益的动态社交网络中的链接推荐方法框架在动态网络链接推荐问题中的有效性，以及NBS和GFPS推荐策略在面向长期收益的链接推荐场景下的有效性。