近年来, 基于事件的社交网络(event based social network)正逐步走入人们的生活.人们越来越喜欢用基于事件的社交网络平台来安排空闲时间, 以参加一些自己感兴趣的活动(即事件), 从而充实自己的业余生活^[1].常见的基于事件的社交网络平台有Meetup(http://www.meetup.com/), Plancast(http://plancast.com/)等.以Meeup为例, 如图 1所示:图 1(a)为Meetup首页, 陈列用户所在位置附近正在举办或即将举办的事件; 图 1(b)为其中一个事件的简介, 包括事件的描述、参与人、举办人、举办地、举办时间等信息.可见基于事件的社交网络可以为用户提供一种从线上到线下(online to offline)的服务, 允许用户在线上创建、管理以及加入不同的事件, 并为用户制定个性化的线下参与事件的计划.截至2018年, 仅Meetup一家网站就已经拥有1 600万用户, 平均每个月举办30万个事件^[2].

在基于事件的社交网络中, 一个经典的问题是为用户安排其感兴趣的事件^[2-6].用户在注册时会被要求选择自己的兴趣爱好, 例如体育、音乐、编程等.如图 1(c)“Interests”栏中所有的标签所示.每个事件在创建时, 亦会要求利用一些标签对其进行相应的描述.如图 1(b)“We’re about”栏中所有的标签所示.因此, 可以用效用值(utility score)来衡量每个用户对每个事件的感兴趣程度, 其计算方式为用户兴趣标签栏和事件描述标签栏中两组标签的相似度^[2-6].该效用值越高, 表示用户对相应的事件越感兴趣.此外, 在为用户安排事件的时候, 还应该考虑二者位置之间的距离.为此, 用户可以提供一个行程预算值(travel budget), 使得系统可以为其安排预算值之内的事件来参加.更进一步, 当基于事件的社交网络平台为用户指定计划时, 还应考虑到用户可能参加多个事件, 这些事件举行的时间和地点彼此之间不应有冲突.平台整体的规划目标为使所有计划中的效用值之和最大.下面通过例1具体阐述现有工作^[2-6]中的事件规划问题.

例 1:表 1列出了基于事件社交网络中的每个用户对每个事件的效用值, 以及每个事件的举办时间.

表 1中事件e₁与e₃的举办时间有重叠, 可见两个事件是冲突的, 不可被同时安排到同一个用户的计划中.表中用户后边附加的括号表示该用户的行程预算值, 每个事件后边附加的括号表示每个事件参与人数的上限.所有用户的所在位置和所有事件的举办地如图 2所示.图中坐标表示其经纬度, 简单起见, 这里用自然数表示.任意两个位置之间的距离以欧式距离计算.一个用户的计划是其从当前位置出发, 按照事件举办时间的顺序依次经过各个事件举办地, 最后回到用户所在位置的过程.例如:用户u₂的计划即从u₂所在地出发, 依次经过e₃和e₂所在的位置, 最后回到u₂的初始所在地, 如图中紫色的折线所示.在该计划中, 用户u₂的总体距离开销为$ \sqrt {{3^2} + {3^2}} + $$ \sqrt {{{11}^2} + {1^2}} + \sqrt {{8^2} + {2^2}} = \sqrt {18} + \sqrt {122} + \sqrt {68} \approx 23.53 $, 小于其预算值30.图 2中所有折线表示计划是文献[2-6]中的算法得出的规划方式, 其总体效用值为0.9+0.5+0.9+0.9+0.9+0.5=4.6.

现有的工作在为用户制定计划的过程中均忽略了一个重要的问题, 那就是作为事件举办者, 他们对不同质量的用户也是有偏向性和选择性的.例如, 有些用户经常缺席安排给他们的事件, 这些经常缺席的用户会严重影响事件举办的效果.以一个参观景区的事件为例, 如果原计划中的用户大量缺席, 会使得按时来参加该事件的用户无法享受原定的折扣景区票价, 从而降低按时参加事件的用户的参与满意度, 影响事件举办者的信誉.久而久之, 会影响平台上事件举办者和参与者双方对于参与事件的积极性, 造成平台的用户流失.另一方面而言, 对于事件举办者来说, 他们也更喜欢请在社交媒体中影响力更大的用户来参加他们的事件, 从而扩大事件的影响力, 促进事件长久高质量地举办下去.因此, 基于事件的社交网络上规划问题本质上应该是一个用户和事件双边选择的问题, 所安排的计划应该令事件举办者和用户双方都尽量感到满意, 而现有的工作恰恰忽略了这一点.如果例1中的事件对用户的偏好效用值见表 2, 则图 2所示的计划中, 安排给事件e₁的用户u₁是其效用值最低的用户; 安排给事件e₂的用户u₂和u₄是其效用值最低的两个用户; 而安排给事件e₃的用户除u₅外, 另两个用户u₂和u₃也是e₃效用值最低的两个用户.可见, 用现有工作^[2-6]中的方法无法兼顾事件和用户双方的偏好效用.

根据上文所述, 在基于事件的社交网络规划中, 考虑事件与用户双边偏好比只考虑用户的单边偏好的规划在实际应用中更合理.因此, 如何定义一种新的能够考虑用户与事件双边偏好的规划问题, 是本文面临的挑战之一.另外, 由于现有工作从未考虑过此类双边偏好的规划问题, 因此现有的考虑单边规划的算法能够提供的参考性有限.而考虑双边偏好的规划显然比只考虑单边偏好的规划问题更复杂, 约束条件更多, 从而更加难以解决.为此, 本文提出了基于事件的社交网络上的双边偏好稳态规划问题, 可以同时兼顾用户和事件双方对彼此之间的偏好效用, 弥补现有工作的不足.本文提出了两种基础算法和一种改进算法, 以解决该问题.最后, 通过一些真实数据集上的实验, 验证了本文提出方法的有效性和高效性.

本文第1节对基于事件的社交网络上的双边偏好稳态规划问题进行定义.第2节对相关工作加以总结.第3节详细介绍两种基础算法, 并分析其正确性和复杂度.第4节分析基础算法的不足, 并提出一种改进的方法.第5节通过真实数据集上的实验验证本文提出算法的高效性和有效性.第6节对全文加以总结, 并提出对未来工作的设想.

1 问题定义

本节给出基于事件的社交网络上的双边偏好稳态规划问题的正式定义.设基于事件的社交网络平台上的用户集为U={u_i}, 共包含n个用户; 事件集为E={e_j}, 共包含m个事件.每个用户u_i∈U以二元组$\langle {\boldsymbol{l}_{{u_i}}}, {B_i}\rangle $表示, 其中, ${\boldsymbol{l}_{{u_i}}}$为向量, 表示u_i的当前位置, B_i为u_i的行程预算值.每个事件e_j∈E以四元组$\langle {\boldsymbol{l}_{{e_j}}}, {\eta _j}, t_j^s, t_j^t\rangle $表示.其中, ${\boldsymbol{l}_{{e_j}}}$为向量, 表示事件e_j的举办地; η_j为事件e_j参与人数的上界, 即事件e_j最多可以被分配多少人; $t_j^s$表示事件e_j举办的开始时间, $t_j^t$表示结束时间.对于每一个用户u_i而言, 他对每个事件e_j的感兴趣程度, 以一个效用值p_u(u_i, e_j)来表示; 对于每个事件e_j而言, 它对平台上的每个用户u_i亦有一个选择偏好, 以一个效用值p_e(e_j, u_i)来表示.p_u(u_i, e_j), p_e(e_j, u_i)∈[0, 1).如果p_u(u_i, e_j)=0, 表示该用户对该事件丝毫不感兴趣或无法参加该事件; 如果p_e(e_j, u_i)=0, 表示事件e_j的举办者已拉黑用户u_i.本文中, 设定u_i对每个事件的偏好顺序是严格的, 即没有两个效用值是相同的; 同理, e_j对每个用户的偏好顺序也是严格的.

当基于事件的社交网络平台为用户制定计划时, 必须在一个特定时间段内为用户制定预计的行程计划.为了简单起见, 本文假设该时间段为1天, 即, 本文所制定的计划是为用户提前制定一天的计划.

设全局计划$ \mathcal{P} $是为每个用户制定一天个性化计划的集合, 即$ \mathcal{P} $={P_i:P_i⊆E, 1≤i≤n}.每个用户的计划中不能包含彼此冲突的事件, 也就是说, 如果P_i中的一个事件e_k在另一个事件e_h之前开始, 那么e_k也要在e_h开始之前结束.例如在例1中, 事件e₁和e₃就是冲突的, 因为e₃在e₁还没有结束的时候就已经开始了.如果事件e_j被匹配给了用户u_i, 记为M(u_i, e_j); 此匹配中, M(u_i)=e_j, M(e_j)=u_i, u_i对e_j的偏好记做p_M(u_i), e_j对u_i的偏好, 记做p_M(e_j).

在某个用户的计划中, 可能会有多个事件, 那么这个用户参加该计划中的所有事件的总行程开销D_i是参加每个事件的行程之和.本文使用欧拉距离计算各个位置之间的距离.

定义 1(阻塞对). 对于一对用户或事件(u_i, e_j)中, 如果u_i和e_j不在$ \mathcal{P} $中, 而u_i比起$ \mathcal{P} $中的M(u_i)更喜欢e_j, 而e_j比起$ \mathcal{P} $中的M(e_j)更喜欢u_i, 那么就称(u_i, e_j)为$ \mathcal{P} $中(u_i, M(u_i))和(M(e_j), e_j)的阻塞对.

例如在例1中, 如果M(u₃, e₃)在$ \mathcal{P} $中, 根据表 1和表 2, 那么(u₅, e₂)就是一个阻塞对, 因为u₅比起计划中的e₃更喜欢e₂, 而e₃比起计划中的u₃也更喜欢u₅.

基于以上预备知识, 现在对基于事件的社交网络上双边偏好稳态规划问题进行定义.

定义 2(基于事件的社交网络上双边偏好稳态规划问题).在基于事件的社交网络平台上, 双边偏好稳态规划问题是指找到一个满足下列适当的全局计划$ \mathcal{P} $.

(1) 用户的计划中没有彼此冲突的事件, 即$\forall i\forall {e_k} \ne {e_h} \in {P_i}, t_{{e_k}}^s < t_{{e_h}}^s \Rightarrow t_{{e_k}}^t < t_{{e_h}}^t$;

(2) 用户的行程开销要在其预算之内, 即∀i, D_i≤B_i;

(3) 事件的参加人数要少于其人数上界, 即∀j|{P_i:e_j∈P_i}≠η_j;

(4) $ \mathcal{P} $中不存在阻塞对.

根据定义2中的表述, 最终的规划中, 用户和事件双方不会同时更喜欢另一个事件和用户, 会达到一个稳定的状态.从经济学角度看, 在存在竞争的关系中, 稳定平衡的状态是最合理的, 也是最符合事物发展规律的^[7].

2 相关工作

本节从3个角度总结与本文相关的现有工作:(1)基于位置的社交网络; (2)基于事件的社交网络; (3)稳定婚姻问题及其变种.

2.1 基于位置的社交网络

近年来, 从线上到线下(online to offline)的服务逐步走入人们的日常生活, 其中最火热的一类服务就是基于位置的社交网络^[8-17].基于位置的社交网络服务的现有工作也会推荐或安排用户到各个事件(或地点, 如旅店、商场等)中去, 但这些工作更关注如何能够使用户各自的效用值最大, 即面向用户个人的推荐.而基于事件的社交网络更关注于平台上所有用户和事件的总体效用值, 即基于事件的社交网络工作更关注于令平台上所有用户对计划都很满意.更进一步而言, 现有的基于位置的社交网络上的工作从未涉猎过事件与用户之间的双向选择问题, 仅仅是关注用户单方面的偏好.

2.2 基于事件的社交网络

基于事件的社交网络首先由Liu等人在文献[1]中分析了来自于两个著名的基于事件的社交网络平台——Meetup和Plancust数据的特征, 并提出了基于事件的社交网络数据模型及其相应的性质.Zhang等人^[14]和Du等人^[15]利用机器学习的方法, 根据基于事件的社交网络平台上的历史数据, 为用户推荐相关的事件.Pham等人在文献[16]中提出了一种通用的异构图模型表示基于事件的社交网络数据, 并提出了一种通用的训练方式解决基于事件的社交网络上的3种推荐问题, 即:为用户推荐事件群组、为事件群组推荐标签以及为事件推荐用户.以上工作也均为关注用户的个性化、个体化推荐, 而不是平台的全局规划.此外, Feng等人在文献[17]中提出了一个找到最有影响力的覆盖集问题, 即找到k用户, 他们所拥有技能的并集能够覆盖一个技能要求集合, 并组织一个能够使得在社交网络上影响力最大的事件.从本质上来说, 该问题是解决最大影响力问题(influence maximization problem)^[18]和团队构成问题(team formation problem)^[19]所构成的综合问题.

一组更相关的基于事件的社交网络的工作是关于社交事件组织问题(social event organization problem)^[5]及其变种, 它是指为一组用户安排一系列事件, 并能够保证整个平台的效用值是最大的.She等人在文献[3, 4]中考虑了事件之间的冲突情况, 并做出了规避了冲突的事件安排; 在文献[6]考虑了用户的行程预算问题, 并从简单将用户和事件匹配起来的问题扩展到为用户安排参与所有事件的合理行程.Cheng等人在文献[2]中进一步考虑了事件的参与人数下界和动态的事件规划问题.以上基于事件的社交网络上的工作从未涉猎过事件与用户之间的双向选择问题, 仅仅是关注用户单方面的偏好.

2.3 稳定婚姻问题

稳定婚姻问题是指:设有n个男人和n个女人, 将这些男人和女人进行配对, 使得该配对方案中没有阻塞对(定义1).文献[20, 21]是两篇非常不错的相关综述.最基础的稳定婚姻问题要求匹配双方(男人和女人)的数量相同, 且为一对一匹配.第1类变种为:可以允许男人和女人的偏好顺序不是严格的, 即, 在某个男人(或女人)的偏好列表中, 可以对某些女人(或男人)的喜好是相同的.第2类变种将一对一匹配扩展为多对多匹配^[22].这两种变种与本文强相关, 但稳定婚姻的基础问题及此二变种问题, 均不考虑匹配双方(即本文中的用户和事件)之间的相关时空信息限制(事件之间的时间冲突, 事件与用户的地理位置及用户对行程的预算等).也就是说, 以上问题是本文所研究问题的特例.因此, 解决这些已有的稳定婚姻及其变种问题的现有方法不能直接应用来解决本文的问题.第3类变种为稳定室友问题^[23], 即给定2n个人, 他们对其他2n-1个人均给出一个偏好列表, 稳定室友问题是找到一种没有阻塞对的稳定匹配.该变种与本文的问题差别较大, 因此亦不能用来解决本文的问题.

3 基础算法

本节介绍双边偏好稳态规划问题的两个基础算法, 分别是事件优先的算法和用户优先的算法.

3.1 事件优先的算法

事件优先算法的主要思路是优先考虑事件对用户的偏好, 让每个事件e_i优先选择其喜好的用户, 如果当前被选择的用户因与其现有事件(比如e_j)冲突或预算不足的原因无法加入其计划中, 则要看用户对事件e_i和e_j更偏好哪个, 令其选择他更偏好的那个事件, 释放另一个事件, 以便于其他用户可以对其选择.该算法的伪代码见算法1.

算法 1.事件优先算法.

输入:事件对用户的偏序PE, 用户对事件的偏序PU, 事件集E, 用户集U;

输出:全局用户安排的事件$ \mathcal{P} $.

1:  所有事件处于active状态;

2:  While (存在处于active状态的事件)

3:    取出active状态的事件e_i

4:    For(每一个在PE(e_i)的用户u_j)  //PE(e_i)已经按照其偏好对用户排序

5:      If(e_i被安排的用户等于人数上界)

6:        break;

7:      End If

8:      conflict_events=$\emptyset $;

9:      For(在$ \mathcal{P} $(u_j)中的每个事件e_k)

10:       If(e_i与e_k在时间上冲突)

11:         If(e_k在PU(u_j)的顺序优于e_i在PU(u_j)中的顺序)    //保障没有阻塞对

12:           break;

13:         Else

14:           将e_k从PU(u_j)中移除, 将e_k加入conflict_events, 将e_k的状态变为active;

15:       End If

16:     End For

17:     将e_i加入到$ \mathcal{P} $(u_j)中;

18:     While($ \mathcal{P} $(u_j)的行程开销超过u_j的行程预算)

19:   从$ \mathcal{P} $(u_j)中删除偏爱程度最差的事件e_k;

20:       If(e_i与e_k是同一个事件)

21:         Break;

22:       End

23:        将e_k加入conflict_events;

24:     End While

25:     If(e_i被从$ \mathcal{P} $(u_j)的行程中删除)

26:        For(在conflict_events中的每个事件e_k)

27:          If(加入e_k不会使$ \mathcal{P} $(u_j)的行程开销超过u_j的行程预算)

28:           将e_k加入$ \mathcal{P} $(u_j), 将e_k的状态变为inactive;

29:         End If

30:       End For

31:     End If

32:   End For

33:   将e_i的状态变为inactive;

34: End While

算法 1 首先为每个事件设置一个是否活跃的状态:如果是活跃的, 记为active, 表示该事件依然可以被安排到用户的计划中; 否则记为inactive, 表示该事件已不可能被安排给任何用户(第1行).只要有事件是active的, 则通过第2行~第34行的方式对其进行用户安排.每次取出一个active的事件, 记为e_i(第3行), 根据其对事件的偏好列表PE(e_i)来选择用户.PE(e_i)已经按照偏好效用值排序好, 令偏好效用值高的用户排在前端, 每次选最前端的用户u_j进行处理(第4行).如果e_i被安排的用户数量已经达到了其人数上界, 则证明该事件无法被安排给更多的用户, 于是跳出循环(第5行~第7行); 否则声明一个集合conflict_events来存储与e_i冲突的事件, 并初始化为空(第8行).对于e_i选出的当前效用值最高的用户u_j, 首先判断$ \mathcal{P} $(u_j)中是否有与e_i冲突的事件, 如果有(设为e_k), 则判断在PU(u_j)中u_j更喜欢e_i还是e_k:如果用户更喜欢e_k, 则证明e_i无法加入到$ \mathcal{P} $(u_j)中, 并跳出循环(第10行~第13行); 否则将e_k从$ \mathcal{P} $(u_j)中移除, 并加入与e_i冲突的conflict_events集合中, 并将e_k的状态变回active(第14行~第16行).以上证明e_i与$ \mathcal{P} $(u_j)中的所有事件不冲突, 于是将其加入$ \mathcal{P} $(u_j)中(第17行).如果加入e_i会使得$ \mathcal{P} $(u_j)的行程开销超过u_j的行程预算, 则不断地删除$ \mathcal{P} $(u_j)偏好最差的事件(第18行~第24行).如果e_i被从$ \mathcal{P} $(u_j)中删除, 则证明e_i不能加入$ \mathcal{P} $(u_j)中, 那么判断conflict_events中的每个事件(依然按照效用值从大到小的顺序)是否有合适的事件e_k加入$ \mathcal{P} $(u_j):如果可以, 则加入e_k并将其状态更新为inactive(第25行~第32行).最后, 将e_i的状态变位active(第33行).下面用例2对算法1的过程进行说明.

例 2:如例1中, 事件和用户的位置如图 2所示, 用户对事件的偏好效用值见表 1, 事件对用户的偏好效用值见表 2.根据算法1, 所有用户的初始状态为active.事件e₁首先选择其最喜好的用户u₅, u₅的计划中目前还没有事件, 因此可以加入事件e₁, 此时e₁达到其用户数量上限, 停止选择, 状态变位inactive.之后, 事件e₂选择其最喜欢的用户u₃, 经判断, u₃的计划中可以加入e₂.事件e₂还可以有一个名额来选择其第2喜欢的用户u₅, 此时u₅已经参加了e₁.由于e₂与e₁不冲突, 且e₂的加入不会超过u₅的预算, 因此e₂可以加入u₅的计划中.事件e₂选择完毕, 状态变为inactive.事件e₃进行选择, 首先选择其最喜欢的用户u₅, 但u₅已经参加了事件e₁, 与事件e₃冲突.而在u₅的偏好列表中, 他更喜欢e₃而不是e₁, 因此将e₃加入其计划中, 把e₁移除计划, 并将事件e₁的状态改回active.此时u₅参加两个事件e₂和e₃不会超过其行程预算.e₃继续考察第2喜欢的用户u₄, u₄的行程预算不支持往返e₃, 因此不能将e₃分配给u₄.e₃继续考察第3喜欢的用户u₁, u₁可以参加e₃.e₃继续考察第4喜欢的用户u₃, u₃的预算不支持同时参加e₂和e₃.e₃继续考察第5喜欢的用户u₂, u₂可以参加e₃.此时e₃的参与人数达到上界, 状态变位inactive.由于u₅改去e₃而放弃e₁, 因此e₁现在是active的, 因此令e₁选择当前最喜欢的用户u₄.u₄可以参加e₁, e₁的参与人数达到上界, 变为inactive.此时, 所有的事件状态均已变为inactive, 算法结束.

算法正确性分析:算法在第4行保障当前事件所选择的用户是其最喜欢的, 而一旦事件不得不放弃选择其最喜欢的用户时, 算法的第11行保障该用户选择到的事件是其最喜欢的.因此, 至少保障用户或事件一方满足其最喜欢的选择, 因此不会出现阻塞对.同时, 每当在计划中加入一个事件或者用户时, 均会判断是否满足事件人数上界、用户行程开销、事件与计划中是否存在冲突这些所有约束条件是否满足.当且仅当所有的约束条件均满足时, 才会插入该事件或者用户.因此, 算法1可以满足定义2中的所有条件, 所以算法1是正确的.

算法复杂度分析:算法在第2行需要遍历所有事件, 时间复杂度为O(m); 第4行~第16行需要每个事件遍历O(n)个用户, 其余的计算复杂度为O(1).因此, 算法的时间复杂度为O(mn).空间复杂度也为O(mn).

3.2 用户优先算法

用户优先算法的主要思路是:优先考虑用户对事件的偏好, 让每个用户优先选择其喜好的事件, 如果当前被选择的事件因与其现有事件冲突或预算原因无法加入其计划中, 则放弃此事件.如果事件是由于参加人数已满的原因而无法加入, 则要看当前用户在该事件已匹配的用户的效用值是否是最低的:如果是, 则放弃加入该事件; 否则, 用该用户替换其计划中效用值最低的用户, 并将其释放另一个事件, 以便其选择其他事件.

该算法的伪代码见算法2所示.

算法 2.用户优先算法.

输入:事件对用户的偏序PE, 用户对事件的偏序PU, 事件集E, 用户集U;

输出:全局用户安排的事件$ \mathcal{P} $.

1:  所有用户处于active状态;

2:  While (存在处于active状态的用户)

3:    取出active状态的用户u_i

4:    For(每一个在PU(u_i)的事件e_j)  //PU(u_i)已经按照其偏好对用户排序

5:     If(u_i的当前行程已超过预算或与当前计划中的事件冲突)

6:       break;

7:     End If

8:     事件e_j加入$ \mathcal{P} $(u_i)中;

9:     If(事件e_j的人数超过其上界)

10:      If(u_i在$ \mathcal{P} $(e_j)的偏好效用值是最低的)  //保障没有阻塞对

11:        break;

12:      Else If

13:        将$ \mathcal{P} $(e_j)中效用值最低的用户u_k移除;

14:        将u_k的状态变为active;

15:      End If

16:    End If

17:   End For

18:   将u_i的状态变为inactive;

19: End While

算法 2 首先为每个用户设置一个是否活跃的状态:如果是活跃的, 记为active, 表示该用户依然可以参加其他事件; 否则记为inactive, 表示该用户已无法参加更多事件(第1行).只要有用户是active的, 则通过第2行~第19行的方式对其进行事件安排.每次取出一个active的用户, 记为u_i(第3行), 根据其对事件的偏好列表PU(u_i)来选择用户.PU(u_i)已经按照偏好效用值排序好, 令偏好效用值高的事件排在前端, 每次选最前端的事件e_j进行处理(第4行).如果加入e_j会使得u_i的当前行程已超过预算或与当前计划中的事件冲突, 于是跳出循环(第5行~第7行); 否则, 将e_j加入到$ \mathcal{P} $(u_i)中(第8行).如果加入事件e_j后, e_j中所安排的人数超过了其上限, 则要看当前用户在该事件已匹配用户的效用值是否是最低的:如果是, 则放弃加入该事件; 否则, 用该用户替换其计划中效用值最低的用户, 并将另一个事件释放, 以便其选择其他事件(第9行~第16行).如此循环下去, 直到$ \mathcal{P} $(u_i)中无法再加入新的事件为止(第4行~第17行).此时, 将u_i的状态变为inactive(第18行).当所有用户的状态均变为inactive时, 算法结束.下面用例3对算法2的过程加以说明.

例 3:例1中, 事件和用户的位置如图 2所示, 用户对事件的偏好效用值见表 1, 事件对用户的偏好效用值见表 2.根据算法2, 所有用户的初始状态为active.用户u₁首先选择其最喜好的事件e₁, 将e₁加入$ \mathcal{P} $(u₁)中; 其次是e₂, 将e₂加入$ \mathcal{P} $(u₁)中; 之后考察e₃, e₃与e₁冲突, 因此不能将e₃加入$ \mathcal{P} $(u₁)中.u₁选择完毕, 状态变为inactive.用户u₂选择事件, 首先选择其最喜欢的事件e₃, 将e₃加入$ \mathcal{P} $(u₂)中; 其次是e₂, 将e₂加入$ \mathcal{P} $(u₂)中; 之后考察e₁, e₁与e₃冲突, 因此不能将e₃加入$ \mathcal{P} $(u₂)中.u₂选择完毕, 状态变为inactive.用户u₃选择事件, 首先选择其最喜欢的事件e₃, 将e₃加入$ \mathcal{P} $(u₃)中; 其次是e₁, e₁与e₃冲突, 因此不能将e₃加入$ \mathcal{P} $(u₃)中; 之后考察事件e₂, 加入e₂会超过u₃的预算, 因此不能将e₂加入$ \mathcal{P} $(u₃)中.u₃选择完毕, 状态变为inactive.用户u₄选择事件, 首先选择其最喜欢的事件e₂, 由于此时$ \mathcal{P} $(e₂)中已经有两个用户u₁和u₂, 加入u₄超过其人数上限, 且在e₂的偏好列表中u₄的效用值比u₁和u₂都低, 因此不能将e₂加入$ \mathcal{P} $(u₄)中; 其次是e₁, 由于此时$ \mathcal{P} $(e₁)中已经有一个用户u₁, 加入u₄超过其人数上限, 而e₁比起u₁更喜欢u₄, 因此将e₁加入到u₄中, 并从$ \mathcal{P} $(u₁)中删除e₁, 将u₁的状态变为active; 之后考察e₃, e₃与e₁冲突, 因此不能将e₃加入$ \mathcal{P} $(u₄)中.u₄选择完毕, 状态变为inactive.用户u₅选择事件, 首先选择其最喜欢的事件e₂, 将e₂加入$ \mathcal{P} $(u₅)中; 由于此时$ \mathcal{P} $(e₂)中已经有两个用户u₁和u₂, 加入u₅超过其人数上限, 又因为其中e₂最喜欢u₅、最不喜欢u₂, 因此将e₂加入到u₅中, 并从$ \mathcal{P} $(u₂)中删除e₂, 将u₂的状态变为active; 其次是e₃, 将e₁加入$ \mathcal{P} $(u₅)中; 之后考察e₁, e₁与e₃冲突, 因此不能将e₁加入$ \mathcal{P} $(u₅)中.u₅选择完毕, 状态变为inactive.此时, 由于用户u₁和u₂的状态是active的, 需要继续考察.对于用户u₁而言, 此时他最喜欢的事件是e₃, 但加入e₃会超过u₁的预算, 因此不能将e₃加入$ \mathcal{P} $(u₁)中.u₁选择完毕, 状态变为inactive.对于用户u₂, 还剩e₁可供选择, 但e₁与e₃冲突, 因此不能将e₁加入$ \mathcal{P} $(u₂)中.u₂选择完毕, 状态变为inactive.此时, 所有用户的状态均为inactive, 算法终止.

算法正确性分析:算法在第4行保障当前用户所选择的事件是其最喜欢的, 而一旦用户不得不放弃选择其最喜欢的事件时, 算法的第10行保障该事件选择到的用户是其当前最喜欢的.因此, 至少保障用户或事件一方满足其最喜欢的选择, 因此不会出现阻塞对.同时, 每当在计划中加入一个事件或者用户时, 均会判断是否满足事件人数上界、用户行程开销、事件与计划中是否存在冲突这些所有约束条件是否满足.当且仅当所有的约束条件均满足时, 才会插入该事件或者用户.因此, 算法2可以满足定义2中的所有条件, 所以算法2是正确的.

算法复杂度分析:算法在第2行需要遍历所有用户, 时间复杂度为O(n); 第4行~第17行需要每个用户遍历O(m)个事件, 其余的计算复杂度为O(1).因此, 算法的时间复杂度为O(mn).空间复杂度也为O(mn).

4 改进算法

本节首先在第4.1节对基础算法进行分析, 指出基础算法的缺点.针对该缺点提出改进算法, 在第4.2节中对其加以详述.

4.1 对基础算法的分析

两个基础算法均从事件(或用户的)单边优先的角度考虑, 当遇到冲突或预算不足时, 才通过考虑另一方的偏好来进行调整, 以保证无阻塞对的出现.但这样可能会出现一种情况, 即:用户和事件双方均没有选到各自较为喜欢的事件和用户, 均以选择相对不喜欢的事件或用户从而达到稳态(即无阻塞对的出现).这样会使得虽然规划满足稳态条件, 但总体的效用值会变得较低.那么是否有一种方式, 可以满足时空约束条件、在达到稳定状态的前提下, 得到尽可能高的效用值呢?本节便解决这一问题.其次, 对于每个事件和用户, 都要存储一个m×n的效用值表, 当数据量大时, 耗用大量的时间进行搜索, 且需要大量内存来存储.因此, 本节也介绍一种空间剪枝方法, 来缩小效用值表格的存储.

4.2 改进算法描述

改进算法的主要思路是:综合了用户和事件双方对彼此的偏好, 让每个用户(事件)优先选择其喜好的事件(用户), 如果当前被选择的事件因与其现有事件冲突或预算原因无法加入其计划中, 则放弃此事件.如果事件是由于参加人数已满的原因而无法加入, 则要看当前用户在该事件已匹配的用户的效用值是否是最低的:如果是, 则放弃加入该事件; 否则, 用该用户替换其计划中效用值最低的用户, 并将其释放释放另一个事件, 以便其选择其他事件.该算法的伪代码见算法3.

算法 3.改进算法.

输入:事件对用户的偏序PE, 用户对事件的偏序PU, 事件集E, 用户集U;

输出:全局用户安排的事件$ \mathcal{P} $.

1:  将所有用户和事件的组合按照偏好加和递增排序;

2:  For (每一个用户和事件的组合(e_i, u_j)

3:    If (事件e_i的人数超过其上界且事件e_i更偏爱当前分配的用户)

4:      break;

5:    End If

6:    conflict_events=$\emptyset $;

7:      For(在$ \mathcal{P} $(u_j)中的每个事件e_k)

8:        If(e_i与e_k在时间上冲突)

9:          If(e_k在PU(u_j)的顺序优于e_i在PU(u_j)中的顺序)  //保障没有阻塞对

10:         break;

11:   Else

12:           将e_k从$ \mathcal{P} $(u_j)中移除, 将e_k加入conflict_events;

13:       End If

14:     End For

15:     将e_i加入到$ \mathcal{P} $(u_j)中;

16:     While($ \mathcal{P} $(u_j)的行程开销超过u_j的行程预算)

17:     从$ \mathcal{P} $(u_j)中删除偏爱程度最差的事件e_k;

18:      If(e_i与e_k是同一个事件)

19:         Break;

20:       End If

21:      将e_k加入conflict_events;

22:     End While

23:     If(e_i被从$ \mathcal{P} $(u_j)的行程中删除)

24:       For(在conflict_events中的每个事件e_k)

25:        将e_k加入$ \mathcal{P} $(u_j), 将e_k的状态变为inactive;

26:       End For

27:     Else If(事件e_i的人数超过其上界)

28:     找到目前事件e_i偏好程度最低的用户u_k, 并将e_i从$ \mathcal{P} $(u_k)中删除;

29:   End If

30: End For

算法 3 首先将所有可能的用户和事件组合按照互相偏序加和, 按照和的递增排序, 和越小意味着用户和事件之间的偏好程度越高(第1行).按顺序取出每一个组合, 记(e_i, u_j)(第3行), 如果e_i被安排的用户数量已经达到了其人数上界且更偏好于当前被安排的用户, 则证明u_j无法被安排到该事件, 于是跳出循环(第3行~第5行); 否则, 声明一个集合conflict_events来存储与e_i冲突的事件, 并初始化为空(第6行).首先判断$ \mathcal{P} $(u_j)中是否有与e_i冲突的事件, 如果有(设为e_k), 则判断在PU(u_j)中u_j更喜欢e_i还是e_k:如果用户更喜欢e_k, 则证明e_i无法加入到$ \mathcal{P} $(u_j)中, 并跳出循环(第8行~第10行); 否则, 将e_k从$ \mathcal{P} $(u_j)中移除, 并加入与e_i冲突的conflict_events集合中(第11行~第14行).以上证明e_i与$ \mathcal{P} $(u_j)中的所有事件不冲突, 于是将其加入$ \mathcal{P} $(u_j)中(第15行).如果加入e_i会使得$ \mathcal{P} $(u_j)的行程开销超过u_j的行程预算, 则不断的删除$ \mathcal{P} $(u_j)偏好最差的事件(第16行~第22行).如果e_i被从$ \mathcal{P} $(u_j)中删除, 则证明e_i不能加入$ \mathcal{P} $(u_j)中, 那么判断conflict_events中的每个事件(依然按照效用值从大到小的顺序)是否有合适的事件e_k加入$ \mathcal{P} $(u_j):如果可以, 则加入e_k(第23行~第26行).最后, 如果e_i分配的用户超过人数上界, 则删除e_i中偏好程度最低的用户, 并将e_i从$ \mathcal{P} $(u_k)中删除(第27行~第30行).下面用例4对算法3的过程加以说明.

例 4:如例1中, 事件和用户的位置如图 2所示, 用户对事件的偏好效用值见表 1, 事件对用户的偏好效用值见表 2.根据算法3, 所有用户和事件的组合排序结果为(e₂, u₅), (e₃, u₅), (e₁, u₄), …, (e₁, u₃).因为e₂对u₅的偏序是2, u₅对e₂的偏序是1, 和为3, (e₂, u₅)排在最前面; (e₃, u₅)的和也为3, 但是e₃ > e₂, 所以排在第2个位置; (e₁, u₄)的和为4, 排在第3个位置; 以此类推, (e₁, u₃)的和为7, 排在最后一个.首先考察组合(e₂, u₅), 将e₂加入$ \mathcal{P} $(u₅)中.接下来分别考察(e₃, u₅)和(e₁, u₄), 分别将e₃和e₂加入$ \mathcal{P} $(u₅)和$ \mathcal{P} $(u₄)中.当考察(e₁, u₅)时, 将e₁加入$ \mathcal{P} $(u₅)中会超过u₅的预算, 所以e₁无法加入到$ \mathcal{P} $(u₅)中.接下来将e₂加入到$ \mathcal{P} $(u₃)中, 将e₂加入到$ \mathcal{P} $(u₃)中.考察(e₁, u₃), e₁已经达到人数上界, 且更偏爱u₄, 所以e₁加入$ \mathcal{P} $(u₃)中.考察(e₂, u₁), e₂已经达到人数上界, 但e₂更偏爱u₁, 将e₂加入到$ \mathcal{P} $(u₁)中, 将e₂从$ \mathcal{P} $(u₃)中移除.下一组, 将e₃加入到$ \mathcal{P} $(u₃)中.e₃无法加入到$ \mathcal{P} $(u₄)中, 因为将超过u₄的预算.e₁无法加入到$ \mathcal{P} $(u₁)中, 因为e₁更加偏爱当前的u₄.同理, e₂无法加入到$ \mathcal{P} $(u₂)中.接下来考察(e₃, u₁), 由于加入e₃将超过u₁的预算, 所以e₃无法加入到$ \mathcal{P} $(u₁)中.将e₃加入到$ \mathcal{P} $(u₂)中.由于将会超过u₄的预算, e₃无法加入到$ \mathcal{P} $(u₄)中.最后, e₁无法加入到$ \mathcal{P} $(u₃)中, 因为e₁更加偏爱当前的u₃.此时, 所有的组合遍历完毕, 算法终止.

算法正确性分析:算法在第3行保障当前事件所选择的用户是其最喜欢的, 而一旦事件不得不放弃选择其最喜欢的用户时, 算法的第9行保障该用户选择到的事件是其最喜欢的.因此, 至少保障用户或事件一方满足其最喜欢的选择, 因此不会出现阻塞对.同时, 每当在计划中加入一个事件或者用户时, 均会判断是否满足事件人数上界、用户行程开销、事件与计划中是否存在冲突这些所有约束条件是否满足.当且仅当所有的约束条件均满足时, 才会插入该事件或者用户.因此, 算法3可以满足定义2中的所有条件, 所以算法3是正确的.

算法复杂度分析:算法在第2行需要遍历所有可能组合, 时间复杂度为O(mn); 其余的计算复杂度为O(1).因此, 算法的时间复杂度为O(mn).空间复杂度也为O(mn).

4.3 空间剪枝方法

不难发现, 对于任意一个用户u_i, 他所能参加的最远的事件, 其举办地与u_i所在位置的距离不能超过B_i/2.因此, u_i可以参加的事件, 其举办地必须在以u_i所在位置${\boldsymbol{l}_{{u_i}}}$为圆心、B_i/2为半径所在的圆内.于是, 在算法运行之前, 可以对数据集进行预处理.对每个用户u_i来说, 以${\boldsymbol{l}_{{u_i}}}$为圆心、B_i/2为半径画一个圆, 将${\boldsymbol{l}_{{e_i}}}$不在圆内的每个事件e_j、彼此的效用值p_u(u_i, e_j)和p_e(e_j, u_i)均置为0, 即从彼此效用值表中删除.利用这种方法可以大量减少两个效用值表的存储, 并节省算法在遍历两个效用值表时所用的时间.

5 实验及分析

本节给出算法的实验结果, 包括实验环境、算法的计算时间、内存消耗、获得的总体效用值.另外, 将本文提出的稳态规划问题定义与现有工作^[6]所提出的问题定义(即忽略定义2中的条件(4))及算法进行比较, 证明本文提出问题定义及相应算法的必要性.

5.1 数据集及实验环境

本文算法用C++及其STL库所实现.实验在一台服务器上运行, 该服务器的操作系统为Linux Fedora 16 (Linux3.6.11-4.fc16^*86 62 GNOME 3.2.1), 处理器为Intel(R)Xeon(R) CPU E5-2620 0@2.00GHz, 内存64GB.内存开销利用Linux系统函数进行测试.

本实验所使用的数据集为Meetup数据集^[1], 数据集中, 每个用户有一个标签文件和位置文件.标签文件记录用户在平台上注册时所选择的兴趣标签; 位置文件记录用户位置的经纬度坐标.对于每个事件, 有一个位置文件以及一个事件群组文件.在Meetup中, 事件是由事件群所创建的, 事件群文件记录着包含在群中的事件, 标签文件记录着每个群组的兴趣标签.位置文件记录着每个事件举办地的经纬度.利用用户的表情文件、事件的标签文件、群组的标签文件, 可以计算用户对事件感兴趣程度的效用值^{[1, 3]}.事件对用户的感兴趣程度, 由用户参加事件的历史记录所计算.设e为用户u参加过的历史事件, e的标签集为{L₁, L₂, …, L_n}, 则每个拥有{L₁, L₂, …, L_n}中至少其中一个表情的事件对u的好感度+1.统计所有历史事件后, 将每个事件对用户的好感度进行归一化.其他参数的产生方式与文献[6]中相同.表 3中总结了真实数据集中的各参数, 其中, n为数据集中的用户数量, m为数据集中的事件数量, η为事件参与人数的上界, 冲突率表示冲突事件占事件总数的百分比.

为了测试算法的可扩展性, 从温哥华真实数据中截取了一定数量的用户和事件, 生成几个合成数据集.表 4列出了合成数据集中用户数量和事件数量的变化情况, 其中加粗的为默认值.

本实验对比本文的算法1~算法3以及文献[6]中的算法.以下, 算法1记为事件稳定规划, 算法2记为用户稳定规划, 算法3记为改进稳定规划, 文献[6]中的算法记为单边规划.算法1~算法3均经过第4.3节空间剪枝方法的预处理.在真实数据集上, 测试以上4个算法的总效用值、运行时间、所需内存以及“单边规划”算法所得结果中阻塞对数量所占的百分比.在可扩展性测试中, 测试以上4种算法在用户数量n和事件数量m变化时, 运行时间和总效用值的变化情况.在无特殊说明的情况下, n和m的值取默认值.

5.2 真实数据集上的实验结果

4种算法在真实数据集上的实验结果见表 5~表 7.表 5显示各算法在真实数据集上获得的总效用值.表 6显示单边规划算法在真实数据集上运行结果中阻塞对所占的百分比.表 7显示各算法在真实数据集上运行所需的时间开销和内存开销.

由表 5可以看出:改进稳定规划算法所获得的总效用值是最高的, 在温哥华数据集上, 其效用值甚至比单边规划算法高出2倍以上.事件稳定规划算法和用户稳定规划算法所获得的总效用值在数据集北京、香港、新加坡上比单边规划低.这说明现有的单边规划算法不考虑事件与用户双方的效用偏好, 它得到的总效用值是比较随机的.而考虑了双边效用偏好的算法在大部分情况下, 也可以获得较高的效用值.事件稳定规划算法和用户稳定规划两个算法偶尔得到效用值低的情况, 是它们在双方均取较低效用值的情况下所达到的稳态规划.而改进算法较好地规避了这一情况, 因此在保证稳态规划下, 也可以获得较高的总效用值, 在数据量大的情况下尤为显著.该实验证明了本文提出稳态规划的合理性和必要性.

由表 6可以看出:单边规划算法在真实数据集上所得到的计算结果中, 阻塞对的数量不在少数, 在数据集奥克兰和新加坡上, 甚至高达61.14%和68.73%, 在3个稳态规划算法中, 阻塞对的数量为0.根据表 5和表 6二者综合的结果可以看出:单边规划算法既不能保证事件和用户双方共同达到满意, 在总效用值上也不如考虑双方偏好效用的稳态算法.由此可以进一步的证明, 本文提出的稳态规划问题的合理性和必要性.

由表 7可以看出, 单边规划算法和双边稳态算法的内存开销差别不大.而在时间开销上, 双边稳态规划算法比单边算法要高一些.这是因为, 双边稳态算法需要一定的时间来保障匹配结果中没有阻塞对的存在, 因此需要更多的时间开销.另外, 虽然本文提出的3种算法在时间复杂度上是一样的, 但平均来说, 改进稳态算法比两个基础算法所花费的时间要低一些.这是因为改进算法同时考虑双方共同的选择, 因此当遇到阻塞对出现时, 所需调整的空间就小一些.因此, 改进算法在实验中的时间开销会比两个基础算法要小, 但比单边规划算法要大一些.

5.3 合成数据集上的实验结果

本节分析本文提出的3种算法在合成数据集上的可扩展性, 并与单边规划算法进行比较.实验结果如图 3所示.当用户数量n变化时, m取默认值5 000;当事件数量m变化时, n取默认值50.

图 3所示为单边规划算法在合成数据集上阻塞对所占的百分比, 可以看出:随着n与m变大, 单边规划算法在合成数据集上阻塞对所占的百分比基本上在增高, 当然也存在下降的情况.这是因为单边规划算法完全不考虑双方稳态平衡的问题, 产生阻塞对的情况基本上是随机的.而随着数据量的增大, 产生阻塞对的概率就会增大, 因此阻塞对百分比基本会呈现上升趋势.

图 4所示为时间开销随用户数量和事件数量的变化情况, 从图中可以看出, 4种算法的时间开销均随用户数量和事件数量的增加而增加.该现象显然是合理的, 因为随着数据量的增加, 算法在检索遍历事件和用户之间效用值的过程所耗费的时间就要增加.这是因为双边稳态算法需要一定的时间来保障匹配结果中没有阻塞对的存在, 因此需要更多的时间开销.另外, 单边规划的时间开销比较低, 随着用户和事件数量的增大而增加的幅度也比较小.事件稳态规划和用户稳态规划两种基础算法所耗费的时间最长, 二者之间的差别不大.改进稳态规划的时间开销介于单边规划和两个基础算法之间.这是因为改进算法同时考虑双方共同的选择, 因此当遇到阻塞对出现时, 所需调整的空间就小一些.

图 5所示为4种算法的总效用值随用户数量和事件数量的变化情况, 可以看出, 4种算法的总效用值均随用户数量和事件数量的增加而增加.该现象显然是合理的, 因为随着数据量的增加, 形成匹配的用户和事件的数量就会增加, 因此总体的效用值必然增加.改进稳定规划算法所获得的总效用值是最高的; 事件稳定规划算法和用户稳定规划算法所获得的总效用值次之, 但并不明显; 单边规划的总效用值最低.由此可见:现有的单边规划定义和算法无论在考虑事件和用户的双方满意度上, 还是总体效用值上, 均不如考虑双边稳态的定义和算法达到的效果好, 因此也佐证了本文提出的双边稳态问题的合理性.

6 结论及展望

本文重点研究社交网络中为用户规划感兴趣事件这一经典问题, 从用户和事件两个角度进行偏好考虑, 提出一种双边偏好稳态规划算法, 解决了社交网络中这一双向选择难题.为了验证该双边偏好算法的有效性, 设计了两种基础算法与一种改进算法, 并通过实验进行了对比.实验结果显示, 双边稳态规划对比现有的单边规划无论从总效用值上, 还是满足事件与用户双方偏好上, 均没有双边稳态规划的效果好.从而为主办者和参与者提供了一种高效、高质量的双向匹配事件推送模式, 有效解决了这一经典问题中的双向选择难题, 有助于提高社交平台的用户满意度与价值提升.

未来工作中, 可以考虑事件与用户中各个参数的动态变化的可能, 提供支持动态变化的双边稳态规划算法.