基于超图的EBSN个性化推荐及优化算法

近年来，随着Web2.0时代和O2O(online to offline)销售模式的不断发展，出现了一种新型社交网络，即基于事件的社交网(event-based social networks, EBSN)[1]，借助该应用平台，用户可以创建、发布和组织社交事件，比如组织学术会议、举行正式聚会、募集抗灾基金以及分发商品优惠券等.由于EBSN不仅包含传统社交网的线上交互(online interactions)操作，而且还包含颇具价值的线下交互(offline interactions)，因此使得虚拟与物理双重的社交交互变得易于融合.EBSN这一特色备受社交用户青睐，从而令EBSN变得越来越流行.

目前，典型的EBSN应用代表有：Meetup(meetup.com),Plancast(www.plancast.com),Groupon(www.groupon.com)和豆瓣(www.douban.com)等.在EBSN丰富异构信息中，包含着多种实体，比如用户(user)、事件(event)、地点(venues)、组(group)、标签(tag)和交互关系(interaction relationship)等，基于此，如何有效利用这些信息进行高质量个性化推荐是目前学术界和工业界共同关注的热点研究问题.

本文首次提出了利用超图(hypergraph)来解决EBSN下的推荐问题.超图节点可代表各类实体，超边则可代表相同或不同实体间的多元关系，因此超图相比于普通图能更准确地刻画异构图中各实体间的关系，信息密度较高，更适合解决推荐问题.在构建超图模型后，考虑到相比于基于欧氏距离的一般排序算法，流形排序算法(ranking of manifold)能更好体现对象间的拓扑结构，因此本文运用流行排序算法对EBSN超图模型进行排序，并将其命名为基于超图模型的EBSN个性化推荐(hypergraph-based personalized recommendation in EBSN, PRH)算法,该算法通过对超图模型运行流形排序及正则化计算，可以得到较准确推荐结果.另外，本文又立足于对查询向量设置方式进行改进和对不同类超边施以不同权重等角度，提出了一种推荐更为准确的优化PRH(optimized PRH, oPRH)算法.

1 EBSN特点概述

通过对EBSN进行深入研究，可以归纳出EBSN具有4个特点，其中后3个特点来源于文献[1]的总结(详细说明可参考文献[1]):

1) EBSN中的数据具有高维关系特征.

2) EBSN中的用户活动相比较于基于位置的社交网(location-based social networks, LBSN)具有更强的地域性[1].

3) 在EBSN中，用户和活动的分布满足重尾(heavy-tail)分布[1]而不是指数分布.

4) 用户间线上和线下行为具有正相关性，即线上行为相似的用户其线下行为也更相似，反之亦然.

首先，EBSN中的数据具有高维关系特征.在EBSN中一般存在着不同类别的实体，比如用户、事件、地点、用户组和标签等.各实体间也存在着各种联系，比如用户与事件间有关系、事件与地点有关系、事件和组有关系、用户和标签有关系等.实体是多元的，实体间的关系也是多元的，因此EBSN信息实体的异构性就有别于传统社交网，使得EBSN数据具有高维特质.目前，高维数据的处理仍是数据处理领域的一个挑战性难题，而降维技术则是处理高维数据的重要途径之一.研究表明：大部分的降维算法都可归结于图的构造及其嵌入方式，换句话说，就是可以用普通图来表示数据之间的关系，但缺陷在于，普通图只能表达2点之间的关系，却不能表达多点之间的关系.不同于简单图，超图则可以表达1对多和多对多关系，并且可以对多阶特征进行表示，因此运用超图模型来对EBSN中的实体和关系进行建模就再合适不过了.

其次，EBSN中的用户活动相比较于LBSN具有更强的地域性.EBSN中无论是用户参加的活动地点，还是该用户的好友所参加的活动地点，绝大多数都集中在该用户较近距离范围之内；而且，这种地域性在EBSN中相比较于LBSN体现得更为明显，因此，在对用户进行服务推荐时应该考虑用户的物理位置信息，即尽量将距离用户较近的事件推荐给用户.

在EBSN中用户和活动的分布满足重尾(heavy-tail)分布而不是指数分布.大部分事件的参与者是比较少的，拥有较多参与者的大型事件数量很少，这表现出一种重尾分布；同样，每个组的成员数量也具有非常类似的重尾分布特点.据此，在数据处理过程中，可以将用户规模太大的事件或者组去掉，从而得到更具有代表性的数据.

最后，用户间线上和线下行为具有正相关性.该特点体现在具有线上行为的用户间更有可能具有线下关系，反之亦然，这说明EBSN中的用户相比LBSN联系更加紧密，也更强调集体行为，往往以组(group)反映出来，而LBSN则强调个体行为.基于此，在为用户进行个性化推荐时，组和事件的关系作为精准推荐考虑要素之一需要格外关注，因为这种关联会直接影响事件的推荐效果.

2 相关工作

协同过滤作为推荐问题中最常用的一种方法可被普遍应用于EBSN中的推荐问题.Li等人[2]提出一种混合协同过滤模型来对EBSN下的社交影响进行预测.该算法的关注点集中在预测用户对EBSN中即将到来事件的影响，建立了一个基于用户和事件间社交影响的矩阵，矩阵中每个实体表示的是用户对事件的影响因子，基于此通过协同过滤来实现对用户及事件的推荐.Dong等人[3]提出一种针对训练数据的基于图的协同过滤推荐方法，主要思想是通过在时间上进行迭代来获得推荐结果.Ding等人[4]考虑了影响用户参加活动的主要因子，并在此基础上提出一种基于滑动窗口的机器学习模型来实现对用户的事件推荐.

Macedo等人[5]为克服冷启动问题，提出在推荐事件中，不仅应考虑用户参加的事件对结果的影响，还应同时考虑其他诸如组内成员、事件位置、时间等因素对结果的影响.在此基础上，他们提出一种基于多种信息的用户个性化事件推荐模型.文献[6]为了解决用户间隐式关系的挖掘，提出了基于EBSN的2阶段事件推荐模型(two-phase group event reco-mmendation, 2PGER).首先，利用EBSN的在线社交行为、用户事件参与记录、拓扑结构等信息，建立用户间的全局信任网络；然后，在预先构建的网络上为每个用户执行随机游走，以获取用户对未体验事件的预测偏好；最后，采用重启随机游走(RWR)方法对用户偏好进行聚合，并将前N个事件推荐给组.Pham等人[7]提出了一种基于普通图的推荐模型，他们主张应该考虑EBSN下各实体间的关系，并利用普通图来对各实体间的关系建模，通过机器学习得到最终推荐结果，该算法可以实现对用户进行组推荐、事件推荐，对组进行标签推荐等.这与本文要探讨的问题有相似之处，即同样都考虑到了各实体间的关系对推荐结果的影响，不同的是，本文提出利用超图来更好地对实体间的关系进行建模.

上述提到的EBSN推荐算法都是通过在普通图上建模来解决，其中文献[2-4]仅仅考虑了用户和事件对推荐结果的影响，通过加入一些影响因子或者对协同过滤算法进行一定改进来实现对用户的事件推荐，这些方法都忽略了EBSN中其他实体对推荐结果的影响.文献[5]和文献[7]考虑到了EBSN中不同类型的实体可能对推荐结果有一定影响，考虑相对来说更全面一些，推荐结果也相对更准确一些，但这些算法仍然是基于普通图来解决EBSN异构信息问题，因而可能导致数据在多维空间下的信息丢失问题.文献[6]尽管实现了用户偏好的预测及面向组的事件推荐，但依然没有摆脱利用简单图进行建模的局限性，即忽略了各实体间复杂关系建模的准确性会在很大程度上影响推荐结果质量的问题；Li等人在文献[8]中综合考虑了用户个人喜好和好友之间的影响，提出了如何对用户的活动进行最有效的规划和推荐；She等人[9]则提出一种在ESBN下进行活动安排的算法；文献[10]中提出了一种在普通图建模的基础上运行随机游走及熵的思路来解决EBSN下事件推荐；文献[11]中提出的算法也是一种运行普通图来对EBSN异构信息图下各种信息进行建模并进行事件推荐的算法.文献[12]中提出了一种基于用户潜在好友关系活动推荐算法.

目前超图学习在研究领域比较热门[13-17],Zhou等人[18]提出了一种流形排序算法将数据对象列为内在几何数据结构，首先将要排序的各个点根据欧氏距离进行连接构成一个连通图，之后通过迭代运算对图中每个节点进行扩展，重复迭代过程直至最终收敛状态，此时整个图中的对象达到最优相似性；Guan等人[19]提出了一种基于图的关联排序算法多类型对象；文献[20]介绍了超图聚类从中提取最大相干群的算法，使用高阶(而不是成对)相似性的一组对象；基于超图的个性化推荐也已经在各个领域具有很好的应用,并且取得了显著成果，如Bu等人[21]提出了基于超图的音乐个性化推荐、Li等人[22]提出基于超图的新闻个性化推荐等.

结合考虑上述算法优缺点后，本文首次提出用超图来对EBSN各实体间的关系进行建模，并利用超图模型通过流形排序解决EBSN下的推荐问题.

3 相关理论知识

本节简要介绍EBSN个性化推荐算法用到的一些理论基础和模型，给出超图定义及相关概念，介绍流形排序算法，描述了正则化运算的基本思路.本文用到的符号及其含义如表1所示:

3.1 超图的定义及概念

超图可以表示异构信息中各实体间的相互关联关系且不丢失信息，超图既可以表示1对多的关系也可以表示多对多的关系.

定义1. 超图.设V是一个有限集的对象，E是V中的子集的集合，即Ue∈E=V，称G=(V,E)是一个超图，其中V是点集合，E是边集合.

由定义1可知，当且仅当E中的每个元素e关联2个节点v时，超图退化为普通图.如果每个超边中包含点的个数相同，个数为k，则可称为k-均匀超图，普通图即为2-均匀超图.超图包含普通图，普通图为超图的特例.超图每条超边具有不同的权重，可用w(e)表示超边e的权重.超图可以表示为G=(V,E,w)，其中w表示权重，对应于超边e.

定义2. 关联矩阵.将超图表示为|V|×|E|的矩阵H，h(v,e)表示针对该矩阵的计算规则，如果某个节点v∈e，则称e附带v，在超图的矩阵中h(v,e)表示为1；否则，如果v∉e，则在超图的矩阵中h(v,e)表示为0.这时矩阵H称为关联矩阵.

图1给出了解释超图相关定义的一个例子.给定一个普通图，如图1(a)所示，其超图形式如图1(b)所示，关联矩阵图1(c)则表示了该超图中节点和超边的关系.

根据超图的关联矩阵(如图1(c)所示)及权重矩阵(如图2(a)所示)，计算超图节点的度d(v)和超边的度δ(e):

超图的每个顶点对应任意类的对象，而超边则被用于创建高阶关系，通过利用超图建模，可以充分挖掘出各不同实体间存在的关联关系，而不至于丢失信息.

3.2 流形排序

基于欧氏距离的排序只能简单地根据数据点与查询点间的欧氏距离进行排序，无法表示数据点之间内在的某种关联，而流形排序[18]则能够表示数据点间的内在关联，如图3所示(图3中“+”表示查询节点).很明显，图3(a)中的数据点分为2部分，即上半月牙和下半月牙，但传统基于欧氏距离的排序并不能体现出上半月牙内的点相较于下半月牙内的点与查询节点具有更紧密的关联性，如图3(b)所示.而在图3(c)中，通过流形排序可以更好地得到图的拓扑结构.这是由于上半月牙的某个点距离查询节点的距离更近，而上半月牙后面的点与距离查询节点近的上半月牙前面的点相比，显然要比下半月牙的点更近，那它们之间肯定会更相似.以此类推，可以得到整个上半月牙的点普遍比下半月牙的点要大，即上半月牙的点之间普遍与查询节点要更相似，这就更好地得到图了的拓扑关系.基于此，本文选择流形排作为超图模型的排序算法.

流形排序算法思路为：

给点集合χ={x1,x2,…,xq,xq+1,…,xn}⊂

m，前q个点是查询，剩下的点是通过与查询点的相关性来进行排序的点.

令d:χ×χ→

表示一个在χ上的度量标准，例如欧氏距离，设置每对点xi和xj的距离为d(xi,xj).

令f:χ→

表示一个排序函数来为每个点xi分配一个排序值fi，可以将f看作是一个向量f=(f1,f2,…,fn)T；同时，定义向量y=(y1,y2,…,yn)T，如果xi是一个查询的话，yi=1，否则yi=0.

流形排序算法步骤为：

1) 按照由小到大升序顺序，对成对关系的点的欧氏距离进行排序，然后根据得到的顺序，重复用边连接2个点，直至得到1个连通图.

2) 生成关联矩阵H，其中

如果在xi和xj之间存在1个边连接2个点.注意，Hii=0，因为图中没有环.

3) 通过

将H对称正规化，这里，D是对角矩阵，位于(i,i)处的元素等于矩阵H中第i行的元素和.

4) 迭代计算f(t+1)=α Sf(t)+(1-α)y，直至收敛，在这里α是一个介于[0,1)的参数.

5) 使

表示序列{fi(t)}的界限，根据每个点xi的排序得分

来对它们进行排序.

3.3 正则化运算

正则化代价函数w*可表示为

其中，m为样本数，第1项L(yi,f(xi;w))是平滑项，衡量模型第i个样本的预测值f(xi;w)和真实标签yi之间的误差.为让模型尽量拟合训练数据，即保证训练误差最小，要求这一项最小.此外，还希望模型测试误差也要小，因而需要加上第2项λΩ(w)，即正则项，它是参数w的正则化函数，用以约束模型尽量简单，其中λ为正则化因子.

机器学习中大部分带参模型都与代价函数比较相像，只是变换第1项和第2项而已.对于第1项loss函数，如果是square loss，那就是最小二乘；如果是hinge loss，那就是SVM；如果是exp-loss，那就是Boosting等.不同loss函数，具有不同拟合特性，本文中第1项为基于流形排序的loss函数.第2个正则项可分为L0,L1,L2范数和核范数正则化，为防止出现过拟合，提升模型泛化能力，本文采取L2范数正则化，即

4 PRH推荐算法和oPRH优化算法

本节介绍了基于超图模型的PRH推荐算法，然后在PRH算法基础上给出了2种优化策略，即oPRH算法.

4.1 PRH算法

PRH算法首先分析EBSN中实体间的关系，然后根据已得到的关系构建超图模型；接着构造超图的关联矩阵并设置超边权重，求得节点的度矩阵及超边的度矩阵；之后，根据查询目标点设置查询向量y，将y带入超图的流形排序正则化运算中，通过计算得到最终的结果向量f，最终根据要求取向量f中前k个标量作为推荐结果.下面详细阐述超图建模和超图的流形排序.

4.1.1 用超图对EBSN进行建模

本文选取Meetup应用作为分析EBSN的样例.通过分析，得到Meetup中的模式有6种关系：

1) 1个用户可以加入到多个事件，1个事件也可以有多个用户.如用户ui可以参加篮球、足球事件，而每个事件会有多个用户参与.

2) 1个用户可以加入多个组，1个组也可以有多个用户.如用户ui可以同时参加户外运动、音乐等多个社交组，并且每个社交组中也可以有多个用户参与.

3) 组可以组织各种事件，即1个组中可以有多个事件.如户外运动组可以组织爬山事件，还可以组织篮球比赛等.

4) 事件在1个地点举办，1个地点也可以有多个事件.如篮球比赛会在篮球场举办，同时篮球场可能还会举办诸如拔河等其他事件.

5) 用户可以同时具有活动、音乐、学习等多个标签.

6) 社交组可以同时具有艺术、音乐、美术等多个标签.

本文考虑了EBSN中5种实体类型和6种实体间关系类型.实体类型分别为：用户(U)、事件(A)、组(G)、地点(L)和标签(T).关系类型分别为：用户参加事件的关系R1、用户参加组的关系R2、用户组与事件的关系R3、事件和地点的关系R4、用户和标签的关系R5、用户组和标签的关系R6.

5种实体类型组成了超图的节点集合V，即V=U∪A∪G∪L∪T.6种超边，每一种超边对应一种实体间关系，如表2所示.定义超边集合为E(i)对应于Ri，i=1,2,…,6，6种超边类型构造为：

E(1)：构造一种用户参加活动的超边关系，并设置权重为1.

E(2)：对于每个组，构建了一种组内包含所有用户的超边，组本身也是超边的对象，设置权重为

表示为组内包含的用户个数，为了消除偏差，标准化后

可表示为

E(3)：对于每个组，构建了一种组内包含所有事件的超边，组本身也是超边的对象，设置权重为

表示为组内包含的事件个数，为了消除偏差，标准化后

可表示为

E(4)：事件与地点的关系作为一种超边，权重为1.

E(5)：用户与标签的关系作为一种超边，权重为1.

E(6)：用户组与标签的关系作为一种超边，权重为1.

另外，由分析可知，不同类超边关系对最终推荐结果的影响程度是不同的，因而根据每类超边对结果的影响程度，给关联矩阵中不同类超边关系加一个系数Ci，i=1,2,…,6，满足0<Ci<1并且

这点在oPRH算法中会有进一步说明.

4.1.2 超图流形排序

推荐问题进一步可以转换为与输入向量相似度高低的排序问题，排序问题需要找到最优解，如何找到最优解就需要构造一个代价函数：

其中,f为输入向量，正则化参数μ>0.

该代价函数的主要思想是对两两节点在所有包含它们的超边中求方差，即进行相似度比较.显然，如果2个节点在所有包含它们的超边中都更相似的话，那么说明两者一定存在更强的相似性，即两者间的方差和越小，说明2个节点更相似.另外，超边的度越大，两者在这种超边中的相似性越显得不重要.举个例子，现在有节点A,B,C,如果要给节点A推荐一个相似性更高的节点，那么可以看节点B,C所属的超边与节点A所属的超边的关系，如果节点B所在的超边与节点A所在的一模一样，而节点C只有部分所属的超边与节点A相同，那么显然节点B相较于节点C,A具有更高的相似性，就会选择将节点B推荐给节点A.进一步，对整个模型中所有两两节点求方差以得到方差和，当方差和达到最小时，对整个模型来说，达到了最好的相似性.对Q(f)加正则化约束项可使之更准确.当Q(f)最小时，即对Q(f)求导为0时，可以得到最优排序结果.通过对Q(f)表达式进行变形和化简，并依据流行排序公式，可以得到模型达到最优时的结果向量y.

最优排序结果是当Q(f)最小时实现f*:

在式(6)中，等式右侧的第1项可以改写为

定义一个矩阵A：

则L=I-A是超图的半正定拉普拉斯矩阵[16].

然后，可将代价函数写成矩阵形式:

要使代价函数最小，对Q(f)求导使其等于0，即：

通过一些简单的代数步骤，可以得到：

假设

注意到

是一个常数并不改变排序结果，可重写f*.

从式(10)可以发现矩阵I-αA是可逆的.注意矩阵I-αA是高度稀疏的，因此，计算效率非常高.

运算得到的f*为结果向量，对f*中各分量值进行排序，选取其中符合条件的前k个点实体作为推荐列表推荐给用户.

4.2 oPRH优化算法

实际上，可以从2个角度对PRH算法做推荐优化：1)通过改进设置查询向量方式;2)对不同类超边施以不同权重.下面，分别在4.2.1节和4.2.2节中加以阐述.

4.2.1 基于改进查询向量方式的oPRH算法

根据查询目标点，有3种设置查询向量方式，具体操作:

1) 设置查询向量y与查询目标用户的分量为1，其他分量为0.

2) 设置查询向量y与查询目标用户的分量为1，同时设置与查询用户相关的分量也为1，其他分量为0.

3) 设置查询向量y与查询目标用户的分量为1，同时设置与查询用户相关的分量为Au,v(0 < Au,v < 1)，Au,v主要根据各实体与查询用户的相关度设置，其他分量为0.

方式1没有考虑查询目标点与其他节点的关系，关联性差.方式2只是简单地将查询目标点与其他节点的关系设置为1，尽管考虑了关联性，但关系描述尚不够准确，因为查询目标点与其他节点的关联程度是不同的.基于上述2点，本文采取方法3设置查询向量方式，旨在进一步提升推荐结果的准确度.

4.2.2 基于不同类超边权重的oPRH算法

在4.1.1节中曾论述过，除了同类的各超边会对推荐结果有不同程度影响，不同类的超边也会对推荐结果有不同程度影响，为此，本文尝试通过对关联矩阵中不同类超边关系增加系数Ci的方法，分别从几何学、多元统计分析和线性回归3个角度，即基于单形的体积、散布矩阵的迹和线性重构误差，重新度量了点集合间的相似性，由此提出了3种超边加权方法.为阐述清晰，将其统称为oPRH算法，旨在进一步提升推荐精准度，具体细节为：

1) 基于单形体积的超边加权法

从几何学角度看，每个超边可以被看作一个单形，因此，从几何学来衡量点集合可以通过计算单形的体积来获得，因为一个小的单形体积意味着超边中的节点具有更紧密的集合关系，反之相反.

通过使用单形中的节点来计算它的体积

其中,det(·)是矩阵的行列式，k!是k的阶乘，G是定义的k×k阶的矩阵，其中列向量gi=(x0-xi).

在得到单形体积之后，与单形Ej相关联的超边ej可以表示为

其中，μ是一个正参数.

2) 基于散布矩阵迹的超边加权法

从多元统计分析和数据挖掘角度看，每个超边可以被看作为样例空间中的聚簇，因此可以使用散布矩阵来衡量超边聚簇的紧密型.定义k×d的矩阵X=(x1,x2,…,xk)为与k度超边ej节点相关联的样例矩阵.然后，散布矩阵S的计算：

其中，

是样例的平均值，

是d×k维向量，其中列全部为

可以设置超边ej的权重：

其中，tr(·)表示为矩阵的迹，μ是一个正参数.

3) 基于线性重构误差的超边加权法

受到在机器学习和计算机视觉方向线性回归的启发[23-26]，可以使用线性回归误差来衡量超边，因为重构误差在衡量同构体例子时会得到比异构体例子更小的值.在无向超图中，每个节点可以得到重构误差，假设k×d维的样例x1,x2,…,xk与在k度超边ej中有序节点相对应.样例xi的重构系数ci是用来最小化重构误差的，可以被当作一个最小二乘方问题来解决：

其中，Xt≠i,t∈ej是一个d×(k-1)维的矩阵，矩阵的第t列是xt,t≠i并且1≤t≤k.在得到ci后则可以得到相关重构误差ri：

对于一个无向超图来说，其一条超边的整个重构误差R可以灵活地表示为所有重构误差样例的平均值：

最终，可以得到超边ej的权重w(ej)：

其中，μ是一个正参数.

5 性能测试与分析

5.1 实验环境与实验数据

本文实验数据爬取自Meetup网站，采用MongoDB对爬取的数据进行存储，使用Java语言编程算法，并用Matlab实现矩阵的正则化运算.

设备相关参数包括处理器：Intel® CoreTM i7-6700；主频：2.8 GHz，4核；内存：16 GB；操作系统：Windows 10.

实验采用的数据集分为2种:1)2015年1～6月旧金山(SF)地区的Meetup数据；2)2015年1～6月洛杉矶(LA)地区的Meetup数据.这些数据都可以从Meetup API网站(1)https://www.meetup.com/meetup_api/自行爬取.

由第1节EBSN特性分析可知，实验中需要将用户数目过多的事件和组去掉，因此在实验中将用户规模大于200的事件和组筛选掉.同时，考虑到用户数目过少的事件和组对实验结果的影响也很微弱，因而将用户规模小于5的事件和组也筛选掉.接下来，在处理后的数据集中选取20%的数据作为测试数据，并去掉实验数据与测试数据之间的关联，之后对实验数据进行运算，并使用测试数据验证实验性能.实验数据中涉及到的对象和关系信息如表3～6所示:

5.2 性能评估指标

本文用准确率(precision, P)、召回率(recall, R)、F1值(F1 measure),PM,A(mean average precision)以及GN,D,C(normalize discounted cumulative gain)等评测指标来衡量算法性能.其中:

准确率=推荐准确的个数/推荐总个数，本文中准确率=推荐准确事件数/推荐总事件数：

召回率=推荐准确的个数/样本数目，本文中召回率=推荐准确事件数/用户参加事件数:

式(19)和式(20)中，R(u)表示对用户推荐的事件集合，T(u)表示用户参加过的事件集合.

F值是准去率和召回率的加权调和平均：

当参数α=1时，F就是F1：

PM,A指的是所有用户的平均准确率(average precision, PA)的平均值. PA指的是在推荐列表中，每个正确推荐项目点计算得到的准确率的平均值：

其中，N是推荐项目的数目，M为正确推荐项目的数目，Pi是在排序点i处的准确率，如果在i处的项目被准确推荐，那么Ci=0，否则Ci=1.

GN,D,C是衡量搜索引擎算法的指标，但它也可以作为衡量排序质量的指标.在n处GN,D,C：

其中，ri是排在i处的项目相关度程度，即排在i处的事件相关性程度.本文中，如果用户参加了该事件，则ri=1，否则ri=0.式(24)中，

其体现的主要思想是，如果在排序结果中，等级比较高的结果排名却比较靠后，那么在最终统计分数时，就应该对这个排序结果的得分进行打折.GI,D,C则是理想的GD,C，也就是排序中最好的状态.

5.3 PRH算法性能测试与分析

为检测PRH算法推荐效果，将其与6种算法进行了比较，6种算法分别为协同过滤(CF)、基于普通图的面向异构信息的EBSN推荐算法(HeteRS)[6]、不加影响因子的HeteRS算法(uni_HeteRS)[6]、基于随机游走的推荐算法(RWR)、基于普通图熵的推荐算法[9]以及基于多特征的事件推荐算法[10].

首先，针对2个不同数据集(SF和LA)，比较了6种算法在时间粒度分别为1个月、3个月、6个月下的准确率和召回率，实验结果如图4和图5所示:

从图4和图5中可以看到，随着时间粒度变大，算法的推荐准确性都会下降，因为用户的兴趣点可能会随时间流逝而发生变化，比如，用户会在这段时间内不断参加别的事件，因而可能会造成推荐结果的准确性下降.因此，要预测一个用户距现在较长时间可能感兴趣的事件是很困难的，这对选取多长时间粒度的数据提出了要求，数据时间粒度过小可能会造成数据信息不全面，进而影响推荐结果准确率，时间粒度过长的数据也同样可能造成推荐准确性下降.本文最终选取了时间粒度为6个月的数据，实验证明该时间粒度比较合理.

其次，针对2个不同数据集(SF和LA)，比较了7种算法在位置数N的准确率和召回率，实验结果如图6和图7所示.

从图6和图7可知，CF算法在位置数N的准确率和召回率相较于其他6种算法差距较大，因为CF算法相对来说比较简单，因而在推荐结果的准确性上可能比较欠缺，HeteRS是除本文提出的算法外表现最好的一种算法，SERGE和MHF算法推荐性能也不错，但由于跟HeteRS一样都是基于普通图对EBSN异构信息图进行建模，虽然考虑了事件推荐中其他各因素对推荐结果的影响，但由于普通图在对异构信息图进行的建模不如超图，所以本文中提出的基于超图建模的推荐方法在推荐性能上还是更优一些.7种算法的准确率都随着位置数N的变大而变小，与此相反，召回率都随着位置数N的变大而变大.

紧接着，针对2个不同数据集(SF和LA)，比较了各算法的PM,A,F1,GN,D,C指标，实验结果如表7～10所示.由表7～10可知，PRH算法在这4个指标上性能均优于其他推荐算法(PRH算法加以*表示).尤其是在位置数N较小时，这种优越性表现得更为明显，这是因为PRH算法是利用超图对高维数据进行建模，而其余集中算法都是基于普通图的基础上进行建模，PRH算法相较于其他算法性能更优，说明了利用超图对复杂的社交网络数据关系建模相较于普通图确实是一种更好的选择.同时，从实验结果中可以观察到，CF算法性能是最差的，这可能是CF算法没有考虑复杂的社交网络中各种实体都可能对推荐结果有一定影响的原因.

首先，利用准确率和召回率2个指标，验证不同查询向量设置方式对最终实验结果的准确性产生的影响，实验结果如图8所示.从图8(a)中可以发现，随着位置数N的上升，3种设置查询向量方式的准确率都会下降，而由图10(b)可以发现，随着位置数N的上升，召回率则都会上升.另外，从图8中还可以发现，方式3设置查询向量的方式不管是准确率还是召回率都要优于方式1、方式2，方式2则稍微比方式1要好一点.原因是，由于方式2只是简单地将与查询节点相关的点全部设置成1，所以对最终推荐结果的提升并不明显，而方式3则根据对象与查询节点相关程度的紧密性将向量设置为0～1之间的值，所以方式3要明显优于方式1、方式2.

5.4 oPRH算法性能测试与分析

为验证不同种类超边对最终推荐结果也确有不同影响，分别测试了PRH算法在不考虑系数和考虑系数情况下且处于位置数N的准确率和召回率.为避免混淆，将不考虑系数的PRH算法称为uni_PRH算法，而将考虑系数的PRH算法仍简称为PRH算法，实验结果如图9所示.

由图9可以看到，加系数的PRH算法其准确率和召回率曲线与坐标轴围成的面积要大于不加系数的uni_PRH算法，因而可以得到加系数的PRH算法的推荐准确性要好于不加系数的uni_PRH，这说明对超边加系数的方法确实可以提高推荐算法的性能.

进一步，为验证所提3种不同种类超边加权方法哪种能更有效提升推荐质量，又将原始未考虑系数的PRH算法与3种加权方法下的oPRH算法进行了准确率和召回率指标上的测试，结果如图10所示.由图10(a)可以看到，随着位置数N的增加，4种算法的推荐准确率都会随之下降，同时3种改进的加权方式在位置数N下得到的准确率都要高于原始PRH算法.除此之外，还可以发现加权方式1和加权方式3在准确率上要略差于加权方式2.同样，由图10(b)可以看到，随着位置数N的增加，4种算法召回率都会随之上升，而3种改进加权方式在位置数N的召回率也要高于原始PRH算法，另外加权方式2在召回率方面也要优于另外2种方式.接下来，基于上述实验分析，本文选择采用加权方式2，从而得到一个在推荐准确性上更加出色的优化算法oPRH，下文中将oPRH算法与PRH算法分别在SF数据集和LA数据集上进行了实验对比，测试结果如图11～12所示.从图11～12中可以看到，oPRH在位置数N处的准确率和召回率都要高于PRH，说明优化效果明显.

最后，针对2个不同数据集(SF和LA)，比较了各算法的PM,A,F1,GN,D,C指标，实验结果如表11～14所示.由表11～12可以观察到，在2个不同数据集下的PM,A值和F1值，oPRH算法都要高于PRH算法，说明优化措施确实可以提高算法推荐结果的准确性.另外，由表13～14可以观察到，PRH算法和oPRH算法在位置数N处的GN,D,C值基本相同，这是由于GN,D,C是用来衡量最终推荐结果中的排序效果的，而本节中采取的优化方法只能提高最终推荐结果的准确性，但不能提高最终推荐结果中的排序效果，因而表13和表14中实验结果相差无几是合理的.

6 总结

由于超图相比于普通图能更准确地刻画异构图中各实体间的关系，且信息不易丢失，本文首先开创性地将超图用于EBSN来解决异构实体网络的推荐问题，并在该超图模型下提出了面向EBSN的个性化推荐PRH算法.PRH算法主要利用了流行排序本身具有准确体现对象间拓扑结构的特点，经过正则化运算给出了较优的初始推荐结果.本文又从改进查询向量设置方式和对不同类超边施以不同权重等方面，对PRH算法进行了优化，继而提出了oPRH算法，进一步提高了推荐质量.实验结果表明，利用超图解决EBSN下的推荐问题相较于普通图方法确实更有效，而优化的oPRH算法在推荐效果上也比PRH算法更为精准.

[1]Liu Xingjie, He Qi, Tian Yuanyuan, et al. Event-based social networks: Linking the online and offline social worlds[C] //Proc of the 18th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2012: 1032-1040

[2]Li Xiao, Cheng Xiang, Su Sen, et al. A hybrid collaborative filtering model for social influence prediction in event-based social networks[J]. Neurocomputing, 2017, 230: 197-209

[3]Dong Cailing, Shen Yilin, Zhou Bin, et al. I2Rec: An iterative and interactive recommendation system for event-based social networks[C] //Proc of Int Conf on Social Computing, Behavioral-Cultural Modeling, and Prediction and Behavior Representation in Modeling and Simulation. Berlin: Springer, 2016: 250-261

[4]Ding Hao, Yu Chenguang, Li Guangyu, et al. Event participation recommendation in event-based social networks[C] //Proc of Int Conf on Social Informatics. Berlin: Springer, 2016: 361-375

[5]Macedo A Q, Marinho L B, Santos R L T. Context-Aware event recommendation in event-based social networks[C] //Proc of the 9th ACM Conf on Recommender Systems. New York: ACM, 2015: 123-130

[6]Liao Guoqiong, Huang Xiaomei, Mao Mingsong, et al. Group event recommendation in event-based social networks considering unexperienced events[J]. IEEE Access, 2019, 7: 96650-96671

[7]Pham T A N, Li Xutao, Cong Gao, et al. A general graph-based model for recommendation in event-based social networks[C] //Proc of the 31st IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2015: 567-578

[8]Li Keqian, Lu Wei, Bhagat S, et al. On social event organization[C] //Proc of the 20th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2014: 1206-1215

[9]She Jieying, Tong Yongxin, Chen Lei, et al. Confict-aware event-participant arrangement[C] //Proc of the 31st IEEE Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2015: 735-746

[10]Liu Shenghao, Wang Bang, Xu Minghua. SERGE: Successive event recommendation based on graph entropy for event-based social networks[J]. IEEE Access, 2017, 6: 3020-3030

[11]Cao Jiuxin, Zhu Ziqing, Shi Liang, et al. Multi-feature based event recommendation in event-based social network[J]. International Journal of Computational Intelligence Systems, 2018, 11(1): 618-633

[12]Yu Yaxin, Zhang Haijun. Activity recommendation algorithm based on latent friendships in EBSN[J]. Computer Science, 2018, 45(3): 196-203 (in Chinese)(于亚新, 张海军. EBSN中基于潜在好友关系的活动推荐算法[J]. 计算机科学, 2018, 45(3): 196-203)

[13]Agarwal S. Ranking on graph data[C] //Proc of the 23rd Int Conf on Machine Learning. New York: ACM, 2006: 25-32

[14]Agarwal S, Branson K, Belongie S. Higher order learning with graphs[C] //Proc of the 23rd Int Conf on Machine Learning. New York: ACM, 2006: 17-24

[15]Sun Liang, Ji Shuiwang, Ye Jieping. Hypergraph spectral learning for multi-label classification[C] //Proc of the 14th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2008: 668-676

[16]Zhou Dengyong, Huang Jiayuan, Schölkopf B. Learning with hypergraphs: Clustering, classification, and embedding[C] //Advances in Neural Information Processing Systems. Cambridge, MA: The MIT Press, 2007: 1601-1608

[17]Chen Shouchun, Wang Fei, Zhang Changshui. Simultaneous heterogeneous data clustering based on higher order relationships[C] //Proc of the 7th IEEE Int Conf on Data Mining Workshops. Piscataway, NJ: IEEE, 2007: 387-392

[18]Zhou Dengyong, Weston J, Gretton A, et al. Ranking on data manifolds[C] //Advances in Neural Information Processing Systems. Cambridge, MA: The MIT Press, 2004: 169-176

[19]Guan Ziyu, Bu Jiajun, Mei Qiaozhu, et al. Personalized tag recommendation using graph-based ranking on multi-type interrelated objects[C] //Proc of the 32nd Int ACM SIGIR Conf on Research and Development in Information Retrieval. New York: ACM, 2009: 540-547

[20]Bulò S R, Pelillo M. A game-theoretic approach to hypergraph clustering[C] //Advances in Neural Information Processing Systems. Cambridge, MA: The MIT Press, 2009: 1571-1579

[21]Bu Jiajun, Tan Shulong, Chen Chun, et al. Music recommendation by unified hypergraph: Combining social media information and music content[C] //Proc of the 18th ACM Int Conf on Multimedia. New York: ACM, 2010: 391-400

[22]Li Lei, Li Tao. News recommendation via hypergraph learning: Encapsulation of user behavior and news content[C] //Proc of the 6th ACM Int Conf on Web Search and Data Mining. New York: ACM, 2013: 305-314

[23]Yu Jun, Rui Yong, Tang Yuanyan, et al. High-order distance-based multi view stochastic learning in image classification[J]. IEEE Transactions on Cybernetics, 2014, 44(12): 2431-2442

[24]Li Xi, Hu Weiming, Shen Chunhua, et al. Context-aware hypergraph construction for robust spectral clustering[J]. IEEE Transactions on Knowledge & Data Engineering, 2014, 26(10): 2588-2597

[25]Agarwal S, Branson K, Belongie S. Higher order learning with graphs[C] //Proc of the 23rd Int Conf on Machine Learning. New York: ACM, 2006: 17-24

[26]Rodriguez J A. On the Laplacian spectrum and walk-regular hypergraphs[J]. Linear and Multilinear Algebra, 2003, 51(3): 285-297