基于事件的社交网络上的双边偏好稳态规划∗

成雨蓉,王国仁,李博扬,袁 野

1(北京理工大学 计算机学院,北京 100081)

2(东北大学 计算机科学与工程学院,辽宁 沈阳 110819)

近年来,基于事件的社交网络(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].

Fig.1 Homepage of Meetup and a brief introduction of an event图1 Meetup首页、事件基本信息及用户基本信息

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

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

Table 1 Users’ utility to each event表1 用户对每个事件的效用值

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

Fig.2 Location of users and events图2 用户所在位置及事件举办地点

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

Table 2 Events’ utility to each user表2 事件对每个用户的效用值

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

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

1 问题定义

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

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

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

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

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

例如在例1中,如果M(u3,e3)在P中,根据表1和表2,那么(u5,e2)就是一个阻塞对,因为u5比起计划中的e3更喜欢e2,而e3比起计划中的u3也更喜欢u5.

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

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

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

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

(4) 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 事件优先的算法

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

算法1.事件优先算法.

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

输出:全局用户安排的事件P.

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

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

输出:全局用户安排的事件P.

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

例 3:例 1中,事件和用户的位置如图2所示,用户对事件的偏好效用值见表1,事件对用户的偏好效用值见表2.根据算法 2,所有用户的初始状态为active.用户u1首先选择其最喜好的事件e1,将e1加入P(u1)中;其次是e2,将e2加入P(u1)中;之后考察e3,e3与e1冲突,因此不能将e3加入P(u1)中.u1选择完毕,状态变为inactive.用户u2选择事件,首先选择其最喜欢的事件e3,将e3加入P(u2)中;其次是e2,将e2加入P(u2)中;之后考察e1,e1与e3冲突,因此不能将e3加入P(u2)中.u2选择完毕,状态变为inactive.用户u3选择事件,首先选择其最喜欢的事件e3,将e3加入P(u3)中;其次是e1,e1与e3冲突,因此不能将e3加入P(u3)中;之后考察事件e2,加入e2会超过u3的预算,因此不能将e2加入P(u3)中.u3选择完毕,状态变为inactive.用户u4选择事件,首先选择其最喜欢的事件e2,由于此时P(e2)中已经有两个用户u1和u2,加入u4超过其人数上限,且在e2的偏好列表中u4的效用值比u1和u2都低,因此不能将e2加入P(u4)中;其次是e1,由于此时P(e1)中已经有一个用户u1,加入u4超过其人数上限,而e1比起u1更喜欢u4,因此将e1加入到u4中,并从P(u1)中删除e1,将u1的状态变为active;之后考察e3,e3与e1冲突,因此不能将e3加入P(u4)中.u4选择完毕,状态变为inactive.用户u5选择事件,首先选择其最喜欢的事件e2,将e2加入P(u5)中;由于此时P(e2)中已经有两个用户u1和u2,加入u5超过其人数上限,又因为其中e2最喜欢u5、最不喜欢u2,因此将e2加入到u5中,并从P(u2)中删除e2,将u2的状态变为active;其次是e3,将e1加入P(u5)中;之后考察e1,e1与e3冲突,因此不能将e1加入P(u5)中.u5选择完毕,状态变为inactive.此时,由于用户u1和u2的状态是active的,需要继续考察.对于用户u1而言,此时他最喜欢的事件是e3,但加入e3会超过u1的预算,因此不能将e3加入P(u1)中.u1选择完毕,状态变为inactive.对于用户u2,还剩e1可供选择,但e1与e3冲突,因此不能将e1加入P(u2)中.u2选择完毕,状态变为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;

输出:全局用户安排的事件P.

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

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

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

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

4.3 空间剪枝方法

不难发现,对于任意一个用户ui,他所能参加的最远的事件,其举办地与ui所在位置的距离不能超过Bi/2.因此,ui可以参加的事件,其举办地必须在以ui所在位置为圆心、Bi/2为半径所在的圆内.于是,在算法运行之前,可以对数据集进行预处理.对每个用户ui来说,以为圆心、Bi/2为半径画一个圆,将lei不在圆内的每个事件ej、彼此的效用值pu(ui,ej)和pe(ej,ui)均置为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的标签集为{L1,L2,…,Ln},则每个拥有{L1,L2,…,Ln}中至少其中一个表情的事件对u的好感度+1.统计所有历史事件后,将每个事件对用户的好感度进行归一化.其他参数的产生方式与文献[6]中相同.表3中总结了真实数据集中的各参数,其中,n为数据集中的用户数量,m为数据集中的事件数量,η为事件参与人数的上界,冲突率表示冲突事件占事件总数的百分比.

Table 3 Real datasets表3 真实数据集

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

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

Table 4 Synthetic datasets表4 合成数据集

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

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

Table 5 Results of total utility over real datasets表5 真实数据集上对总效用值的测试结果

Table 6 Results of percentage of block pairs over real datasets表6 真实数据集上单边规划阻塞对数量百分比

Table 7 Resultsof time and memory cost over real datasets表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变大,单边规划算法在合成数据集上阻塞对所占的百分比基本上在增高,当然也存在下降的情况.这是因为单边规划算法完全不考虑双方稳态平衡的问题,产生阻塞对的情况基本上是随机的.而随着数据量的增大,产生阻塞对的概率就会增大,因此阻塞对百分比基本会呈现上升趋势.

Fig.3 Percentage of block pairs in the results of unilateral planning algorithms over synthetic datasets图3 单边规划算法在合成数据集上阻塞对所占的百分比

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

Fig.4 Time cost with reference to the number of users and events图4 时间开销随用户数量和事件数量的变化

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

Fig.5 Total utility with reference to the number of users and events图5 总效用值随用户数量和事件数量的变化

6 结论及展望

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

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