地理-社会网络中最大化推荐方案MRG的制作方法

由天下分享时间：2024/12/25 17:57:53 加入收藏我要投稿点赞

图片简介:

本技术介绍了一种地理社会网络中最大化推荐方案MRG，MRG针对最大化推荐问题，首先根据被推荐的位置r对周围欲进行推荐的节点进行环状区域划分，剔除对周围节点具有负影响的负面节点，再利用剩下所有的节点根据其相互之间的影响值建立位置社会网络并计算加权影响值，挑选出用户所需的k个加权影响值最高的节点进行推荐。从而有效的降低了推荐的成本，提高了推荐的效果。同时，MRG考虑了负面影响，提高了推荐的效率。实验证明本文方法比目前大多数方法在最大化推荐领域具有更好的性能。

技术要求

1.一种地理-社会网络中最大化推荐方案MRG，其特征在于，该方法包括，首先根据被推荐的位置r对周围欲进行推荐的节点进行环状区域划分，剔除掉对周围

骤包括：

响的负面节点，再利用剩下所有的节点根据其相互之间的影响值建立位置-社会网络并计算出其加权影响值，挑选出用户所需的k个加权影响值最高的节点进

MRG把一个位置-社会网络定义为一个有向图G＝(U,E)，U表示一组节点即用户，E表示G的边集合即用户之间的关系，每个节点u∈U都有一个地理位置(x,y)，

表示u的经度和纬度，权重函数定义如公式(1)所示：

f:U×r→F (1)公式(1)中，U表示一组节点即用户，r是一个需要推荐的位置，F是一组权重，公式(1)表示在二维空间中赋予每个节点u一个与给定位置r对应的权重

给定一条边∈E，则说uj是ui的出邻，ui是uj的进邻，或ui指向uj，或ui能影响到uj；

MRG的目标是在成本用户数量k固定的基础上，选取最有影响力的k个成本节点，为此给出如下定义；

定义1.影响值，给定一个位置-社会网络G＝(U,E)，假定每条边∈E有独立的影响值h∈[＝1,1]，其中正数表示正向影响，负数表示负面影响，0表

即如果h＝0，则这条边不需要画出来，显然，如果ui和uj是很好的朋友，这个影响值可能就是1或-1，而如果ui和uj只是普通朋友，这个影响值可果只是发个朋友圈，发个微信，这个影响值甚至可能是0；

定义2.加权影响WeightedInfluence，给定一个位置-社会网络G＝(U,E)，一个阈值δ和一个在二维空间中的推广位置r，一个节点u在G中对其他节点产生的加权影

Ir(u)，计算过程如公式(2)所示：

其中f(u,r)是u关于r的权值，h(u,ui)是u对ui的影响值；

MRG认为只有当Ir(u)>δ的时候，用户u才具有足够的影响力，可以被认为是一个候选的成本节点。

技术说明书

一种地理-社会网络中最大化推荐方案MRG技术领域

本技术涉及信息技术，具体涉及一种地理-社会网络中最大化推荐方案MRG，即一种地理-社会网络中最大化推荐方案MRG，(Maximum recommendation schem

in Geo-social network，MRG)针对最大化推荐问题，有效的降低了推荐的成本，提高了推荐的效果，同时，该方法考虑了负面影响，提高了推荐的效率。

背景技术

随着地理-社会网络技术的进步和地理-社会媒体平台的发展，越来越多的公司利用地理-社会网络平台推广他们的产品。因此，现实中相关的商业程序也变得越来越有必要。

给定一个地理-社会网络G，一个正整数k和一个被推荐的位置r。目标是找出G中对r具有最大推荐效果的k个节点，从而达到最大的推荐效果。

在现有的相关技术中，有通过自适应方式选择种子用户的策略。提供了一种有效的启发式算法来实现更好的可扩展性、有通过对部分社区的探索，提出了一个实用的框架。该框架最大限度地减少了观察到的拓扑和实际网络之间的可能差异、有通过分析了贪婪算法效率低下的原因,提出了一种降阶搜索进化算法

(DDSE)，消除了贪婪算法的耗时仿真，因此具有比贪婪算法更高的效率。但是现有的相关技术在应用上仍存在一些问题，具体如下：(1)没有考虑推荐最大化

问题。这些方法考虑的是影响最大化(IM：InfluenceMaximization)问题。这个问题的核心是尽量减少被评估的节点数量n(即候选集的数量)，确定被评估的范围

最大化的影响被评估范围内的节点。至于这个节点数量n与公司预期投入的成本数量k之间是没有关系的，因此，面对推荐最大化应用场景，现有方法会浪费

一些公司的成本。(2)没有考虑负面影响。例如餐馆老板提供了免费的餐券，但是有的顾客吃完觉得并不好吃，可能就不但不会向他的朋友推荐这个餐馆，还

会劝阻朋友来消费。因此，将负面影响加入到推荐最大化模型中是很有必要的。但是现有方法均未考虑这种负面影响。综上可知在实际应用中目前的最大化推荐方法存在浪费成本和推荐效果损失等问题，因此开展这方面的研究很有实际意义。技术内容

本技术其目的就在于提供一种地理-社会网络中最大化推荐方案MRG，该方案考虑了负面节点，去除了推荐系统中的负面影响，同时，针对推荐最大化问题，提出了一种高效的推荐模型，该模型可以有效的降低公司的推荐成本，提高推荐效果，从而可以提高推荐最大化系统的可用性。

为实现上述目的而采取的技术方案是，一种地理-社会网络中最大化推荐方案MRG，该方法包括，首先根据被推荐的位置r对周围欲进行推荐的节点进行环状

域划分，剔除掉对周围节点具有负影响的负面节点，再将剩下所有的节点根据其相互之间的影响值建立位置-社会网络并计算出其加权影响值，挑选出用户所需的k个加权影响值最高的节点进行推荐，具体步骤包括：

MRG把一个位置-社会网络定义为一个有向图G＝(U,E)，U表示一组节点即用户，E表示G的边集合即用户之间的关系，每个节点u∈U都有一个地理位置(x,y)，

其中x和y分别表示u的经度和纬度，权重函数定义如公式(1)所示。

f:U×r→F (1)

公式(1)中，U表示一组节点即用户，r是一个需要推荐的位置，F是一组权重，公式(1)表示在二维空间中赋予每个节点u一个与给定位置r对应的权重f∈F。给定一条边∈E，则说uj是ui的出邻，ui是uj的进邻，或ui指向uj，或ui能影响到uj。

MRG的目标是在成本用户数量k固定的基础上，选取最有影响力的k个成本节点，为此给出如下定义。

定义1.影响值，给定一个位置-社会网络G＝(U,E)，假定每条边∈E有独立的影响值h∈[-1,1]，其中正数表示正向影响，负数表示负面影响，0表示

没有影响，即如果h＝0，则这条边不需要画出来，显然，如果ui和uj是很好的朋友，这个影响值可能就是1或-1，而如果ui和uj只是普通朋友，这个影响值可能只是0.1，如果只是发个朋友圈，发个微信，这个影响值甚至可能是0，

定义2.加权影响Weighted Influence，给定一个位置-社会网络G＝(U,E)，一个阈值δ和一个在二维空间中的推广位置r，一个节点u在G中对其他节点产生的加权影响表示为Ir(u)，计算过程如公式(2)所示，

其中f(u,r)是u关于r的权值，h(u,ui)是u对ui的影响值。

MRG认为只有当Ir(u)>δ的时候，用户u才具有足够的影响力，可以被认为是一个候选的成本节点。

有益效果

与现有技术相比本技术具有以下优点。

1.提出了一种新的推荐最大化模型，该模型旨在根据公司预期投入的成本数量k，找出具有最大化推荐效果的k个节点，从而节省公司的推荐成本，提高推荐

率。

2.将负面影响加入了推荐模型，一旦MRG发现负面节点，就会将负面节点剔除出地理-社会网络，使得负面节点无法进一步破坏推荐模型，因此降低了地理-社

验证明本技术方法比目前大多数方法在最大化推荐领域具有更好的性能。附图说明

会网络的负面影响，提高了推荐效率。另外，如果地理-社会网络数据更新了，由于该节点已经不存在，因此不需要再次计算这个节点，减少了更新代价。实

以下结合附图对本技术作进一步详述。图1是动机示例图；

图2是处于时间戳1的推荐模型图；图3是处于时间戳2的推荐模型图；图4是处于时间戳3的推荐模型图；图5是不同环数下内存消耗对比图；图6是不同节点数下内存消耗对比图；图7是索引构建对比图；

图8是不同成本节点数下推荐效率对比图；图9是不同推荐环数下推荐效率对比图；图10是不同推荐环内节点数下效率对比图；图11是推荐效果对比图。具体实施方式

一种地理-社会网络中最大化推荐方案MRG，该方法包括，首先根据被推荐的位置r对周围欲进行推荐的节点进行环状区域划分，剔除对周围节点具有负影响

负面节点，再利用剩下所有的节点根据其相互之间的影响值建立位置-社会网络并计算出其加权影响值，挑选出用户所需的k个加权影响值最高的节点进行推荐，具体步骤包括：

MRG把一个位置-社会网络定义为一个有向图G＝(U,E)，U表示一组节点即用户，E表示G的边集合即用户之间的关系，每个节点u∈U都有一个地理位置(x,y)，

其中x和y分别表示u的经度和纬度，权重函数定义如公式(1)所示。

f:U×r→F (1)

公式(1)中，U表示一组节点即用户，r是一个需要推荐的位置，F是一组权重，公式(1)表示在二维空间中赋予每个节点u一个与给定位置r对应的权重f∈F，给定一条边∈E，则说uj是ui的出邻，ui是uj的进邻，或ui指向uj，或ui能影响到uj，

MRG的目标是在成本用户数量k固定的基础上，选取最有影响力的k个成本节点，为此给出如下定义。

定义1.影响值，给定一个位置-社会网络G＝(U,E)，假定每条边∈E有独立的影响值h∈[-1,1]，其中正数表示正向影响，负数表示负面影响，0表示

没有影响，即如果h＝0，则这条边不需要画出来，显然，如果ui和uj是很好的朋友，这个影响值可能就是1或-1，而如果ui和uj只是普通朋友，这个影响值可能只是0.1，如果只是发个朋友圈，发个微信，这个影响值甚至可能是0。

定义2.加权影响(Weighted Influence)，给定一个位置-社会网络G＝(U,E)，一个阈值δ和一个在二维空间中的推广位置r，一个节点u在G中对其他节点产生的加权影响表示为Ir(u)，计算过程如公式(2)所示。

其中f(u,r)是u关于r的权值，h(u,ui)是u对ui的影响值。

MRG认为只有当Ir(u)>δ的时候，用户u才具有足够的影响力，可以被认为是一个候选的成本节点。

实施例

一种地理-社会网络中最大化推荐方案MRG。

如果节点u对位置-社会网络G中其他人的影响是负面的(h(u,ui)<0)，则从G中将u去掉。否则计算u的加权影响Ir(u)。

以一个地理-社会网络，预期投资的成本节点数量k，一个阈值和拟推荐的位置r为输入，以推荐效果最好的k个成本节点为输出。

假如u的加权影响大于预先设定的阈值，说明u是有影响力的节点，可以将其作为候选成本节点。在找出k个候选节点以后，MRG方法会将剩下节点的加权影响

与进行对比，找出k个加权影响最大的节点，凡是出现外面的节点要大于中加权影响最小的节点，就将两个节点互换一下。以此类推，从里到外地对每个推荐环进行筛选，直至找出加权影响最大的k个节点。

本技术提出一种地理-社会网络中最大化推荐方案MRG(Maximum recommendationscheme in Geo-social network，MRG)针对最大化推荐问题，首先根据被推荐的

位置r对周围欲进行推荐的节点进行环状区域划分，剔除掉对周围节点具有负影响的负面节点，再将剩下所有的节点根据其相互之间的影响值建立位置-社会网络并计算出其加权影响值，挑选出用户所需的k个加权影响值最高的节点进行推荐。从而节约了推荐成本并且提高了推荐效率。

MRG把一个位置-社会网络定义为一个有向图G＝(U,E)，U表示一组节点(用户)，E表示G的边集合(用户之间的关系)。每个节点u∈U都有一个地理位置(x,y)其中x和y分别表示u的经度和纬度。权重函数定义如公式(1)所示。f:U×r→F (1)

公式(1)中，U表示一组节点(用户)，r是一个需要推荐的位置，F是一组权重。公式(1)表示在二维空间中赋予每个节点u一个与给定位置r对应的权重f∈F。给定一条边∈E，则说uj是ui的出邻，ui是uj的进邻。也可以理解成，ui指向uj，或者说，ui能影响到uj。

例如，用户ui觉得商店r的东西好吃，因此大力推荐，则ui对其他用户产生的影响是正向影响。而用户uj觉得不好吃，或者太贵，因此大力抨击r，因此u

用户产生的影响是负面影响。定义被商店r提供一些免费的餐券和VIP卡等推销的用户称为成本用户(即成本节点)。这些用户是需要商店r付出一定成本的，本

关键是找出最有价值的k个成本节点。将会产生负面影响的用户称为负面用户(即负面节点)，一般来说，一个人对某个商店产生的印象不会随便改动，例如用

户A不可能和用户B贬低商店r，但是却和用户C夸奖商店r。而且，一旦用户A对商店r产生了不好的映像，那么想要改变他的看法就会很困难。因此，推荐模型中凡是出现负面用户，必须剔除掉。显然，MRG的目标是在成本用户数量k固定的基础上，选取最有影响力的k个成本节点。为此给出如下定义。

定义1.影响值。给定一个位置-社会网络G＝(U,E)，假定每条边∈E有独立的影响值h∈[-1,1]。其中正数表示正向影响，负数表示负面影响，0表示没有影响(即如果h＝0，则这条边不需要画出来)。

显然，如果ui和uj是很好的朋友，这个影响值可能就是1或-1。而如果ui和uj只是普通朋友，这个影响值可能只是0.1。如果只是发个朋友圈，发个微信响值甚至可能是0。

定义2.加权影响(Weighted Influence)。给定一个位置-社会网络G＝(U,E)，一个阈值δ和一个在二维空间中的推广位置r。一个节点u在G中对其他节点产生的加权影响表示为Ir(u)，计算过程如公式(2)所示。

其中f(u,r)是u关于r的权值，h(u,ui)是u对ui的影响值。

换言之，MRG认为只有当Ir(u)>δ的时候，用户u才具有足够的影响力，可以被认为是一个候选的成本节点。

以下结合附图和实例对本技术作进一步说明，参见图1～11。图1为该技术的动机示例图。如图1所示，在北京有一个新开的餐馆“Cinky”位于r位置。老板希望通过使用地理-社会网络平台来推广他的餐厅(例如Facebook，微信，QQ等)。他打算向一些有影响力的客户支付一些推荐费用(例如免费的餐券，上门送

餐，VIP打折卡等)。支付推荐费用的目的是希望这些有影响力的客户能通过社会网络传播关于这家餐馆的信息。“Cinky”的老板的资金有限，不可能向太多的

人支付推荐费用，因此他只能设定一个k值，拟向k个有影响力的客户支付推荐费用。直观地，如果没有提供关于用户的其他信息，在餐厅附近的用户将更可能成为潜在顾客。

本技术的推荐方案中，接近推广位置r的用户应该优先被考虑。因此，与u和r之间的距离是成反比的。换言之，节点u与位置r离的越近，越大；反之，越小。

因此本文以r为中心，画出多个圆环，在第一环内的是最先被考虑的用户，这组用户的权重最大。一个商店不可能将全球的人都变成推荐用户，因此最外围的圆环不是无限的。MRG将一个商店能推销的最外围区域作为最外层圆环，此时，最外层圆环内的用户权重最小。

图1是一个处于时间戳0的推荐模型，此时，任何一个用户都没有被r选中作为成本用户。而MRG的推荐模型是从内向外，从权重最高的用户向权重最低的用户

逐步蔓延。为了清楚的描述本文的推荐模型，下面给出一个处于时间戳1的例子如图2所示。图2中，位于1环内的用户的权重最大，都是3。二环内的用户都是

2。三环内的用户权重最小，都是1。并且用户对其他用户是负面影响。而用户和对其他用户产生的是正面影响。

下面以图2为例对加权影响力进行说明。

首先对最内层位于1环内的用户{u1,u2,u3}进行判断是否是具有足够影响力的成本节点。

(1)判断u1。计算影响值。h＝-1.0，因此将u1从地理-社会网络G中去掉。

(2)判断u2。Ir(u2)＝h(u2,u3)×f(u2,r)+h(u2,u7)×f(u2,r)+h(u2,u8)×f(u2,r)+h(u2,u9)×f(u2,r)+h(u2,u19)×f(u2,r)＝(+1.0)×3+(+0.9)×3+(+0.8)×3+(+0.5)×3+(+0.3)×3＝10.5。假

设δ＝2，k＝3。显然u2满足条件，是一个具有足够影响力的节点，可以作为候选成本节点。

同理，Ir(u3)＝+2.4，也满足条件。此时，推荐模型如图3所示。第一环判断完后，开始判断第二环(p＝2)。经过判断以后，发现u10需要去掉。Ir(u4)＝+1<δ，

不能作为候选成本节点。Ir(u8)＝3.2>Ir(u3)。Ir(u9)＝3.6>Ir(u3)，且k＝3，只能返回3个加权影响最大的节点。因此，需要将u3去掉。所以，执行完第二环以后的候选成本集Ek＝{u2,u8,u9}。此时，推荐模型如图4所示。在以上的例子之中，推荐环的序号最大是3，即p＝3。当p＝4的时候，计算结束。

由于PRI方法与本技术方法MRG最相关，并且PRI算法是目前最经典的相关方法。因此，为了证明本技术方法的高效性和实用性，这个部分将PRI与本技术方法

MRG进行对比。

每个影响值随机在区间中进行选取。权重由节点u所处的环数p决定。例如，总共有5个推荐环，那么最外层圆环上面的权重是1，最内层就是5，以此类推。拟

推荐的位置r是固定的，其他节点的位置、数量是随机的。阈值δ是所有正加权影响的平均值。负面节点的数量不会超过10％。PRI与MRG进行对比时总是处于同一个数据集的状态下。

系统中成本节点数量k从10到50，一个推荐环上面节点数量的最大值m从1T到5T(T表示千：Thousand)。推荐环的数量(Number of recommended rings)p从2到10。具体参数如表1所示。表1试验参数

k10，20，30，40，50

m1T，2T，3T，4T，5Tp

2，4，6，8，10

本技术的推荐模型其实就是一个索引，由于索引要常驻内存，因此第一个实验用于测试MRG与PRI两种方法的内存消耗。影响内存消耗的有两个参数：推荐环数p和一个推荐环上面节点数量的最大值m。

为此，实验结果如图5、6所示。其中纵坐标是内存消耗，单位是M。图5的横坐标表示推荐环数p，图6的横坐标表示一个推荐环上面节点数量的最大值m。图

5。当推荐环数p从2增长到10的时候，本技术的方法MRG随着订阅数量的增长消耗的内存缓慢增长，而PRI消耗的内存是MRG的1.65倍。由于在推荐环数量增

长以后，负面节点能影响到的节点会越来越多，而MRG考虑了负面节点，因此去除掉了负面节点。而PRI并未考虑负向节点。因此MRG消耗的内存显著低于