成雨蓉,王國仁,李博揚,袁 野

1(北京理工大學(xué) 計算機學(xué)院,北京 100081)

2(東北大學(xué) 計算機科學(xué)與工程學(xué)院,遼寧 沈陽 110819)

近年來,基于事件的社交網(wǎng)絡(luò)(event based social network)正逐步走入人們的生活.人們越來越喜歡用基于事件的社交網(wǎng)絡(luò)平臺來安排空閑時間,以參加一些自己感興趣的活動(即事件),從而充實自己的業(yè)余生活[1].常見的基于事件的社交網(wǎng)絡(luò)平臺有Meetup(http://www.meetup.com/),Plancast(http://plancast.com/)等.以Meeup為例,如圖1所示:圖1(a)為Meetup首頁,陳列用戶所在位置附近正在舉辦或即將舉辦的事件;圖1(b)為其中一個事件的簡介,包括事件的描述、參與人、舉辦人、舉辦地、舉辦時間等信息.可見基于事件的社交網(wǎng)絡(luò)可以為用戶提供一種從線上到線下(online to offline)的服務(wù),允許用戶在線上創(chuàng)建、管理以及加入不同的事件,并為用戶制定個性化的線下參與事件的計劃.截至2018年,僅Meetup一家網(wǎng)站就已經(jīng)擁有1 600萬用戶,平均每個月舉辦30萬個事件[2].

Fig.1 Homepage of Meetup and a brief introduction of an event圖1 Meetup首頁、事件基本信息及用戶基本信息

在基于事件的社交網(wǎng)絡(luò)中,一個經(jīng)典的問題是為用戶安排其感興趣的事件[2-6].用戶在注冊時會被要求選擇自己的興趣愛好,例如體育、音樂、編程等.如圖1(c)“Interests”欄中所有的標簽所示.每個事件在創(chuàng)建時,亦會要求利用一些標簽對其進行相應(yīng)的描述.如圖1(b)“We’re about”欄中所有的標簽所示.因此,可以用效用值(utility score)來衡量每個用戶對每個事件的感興趣程度,其計算方式為用戶興趣標簽欄和事件描述標簽欄中兩組標簽的相似度[2-6].該效用值越高,表示用戶對相應(yīng)的事件越感興趣.此外,在為用戶安排事件的時候,還應(yīng)該考慮二者位置之間的距離.為此,用戶可以提供一個行程預(yù)算值(travel budget),使得系統(tǒng)可以為其安排預(yù)算值之內(nèi)的事件來參加.更進一步,當基于事件的社交網(wǎng)絡(luò)平臺為用戶指定計劃時,還應(yīng)考慮到用戶可能參加多個事件,這些事件舉行的時間和地點彼此之間不應(yīng)有沖突.平臺整體的規(guī)劃目標為使所有計劃中的效用值之和最大.下面通過例1具體闡述現(xiàn)有工作[2-6]中的事件規(guī)劃問題.

例1:表1列出了基于事件社交網(wǎng)絡(luò)中的每個用戶對每個事件的效用值,以及每個事件的舉辦時間.

Table 1 Users’ utility to each event表1 用戶對每個事件的效用值

表1中事件e1與e3的舉辦時間有重疊,可見兩個事件是沖突的,不可被同時安排到同一個用戶的計劃中.表中用戶后邊附加的括號表示該用戶的行程預(yù)算值,每個事件后邊附加的括號表示每個事件參與人數(shù)的上限.所有用戶的所在位置和所有事件的舉辦地如圖2所示.圖中坐標表示其經(jīng)緯度,簡單起見,這里用自然數(shù)表示.任意兩個位置之間的距離以歐式距離計算.一個用戶的計劃是其從當前位置出發(fā),按照事件舉辦時間的順序依次經(jīng)過各個事件舉辦地,最后回到用戶所在位置的過程.例如:用戶u2的計劃即從u2所在地出發(fā),依次經(jīng)過e3和e2所在的位置,最后回到u2的初始所在地,如圖中紫色的折線所示.在該計劃中,用戶u2的總體距離開銷為,小于其預(yù)算值 30.圖2中所有折線表示計劃是文獻[2-6]中的算法得出的規(guī)劃方式,其總體效用值為0.9+0.5+0.9+0.9+0.9+0.5=4.6.

Fig.2 Location of users and events圖2 用戶所在位置及事件舉辦地點

現(xiàn)有的工作在為用戶制定計劃的過程中均忽略了一個重要的問題,那就是作為事件舉辦者,他們對不同質(zhì)量的用戶也是有偏向性和選擇性的.例如,有些用戶經(jīng)常缺席安排給他們的事件,這些經(jīng)常缺席的用戶會嚴重影響事件舉辦的效果.以一個參觀景區(qū)的事件為例,如果原計劃中的用戶大量缺席,會使得按時來參加該事件的用戶無法享受原定的折扣景區(qū)票價,從而降低按時參加事件的用戶的參與滿意度,影響事件舉辦者的信譽.久而久之,會影響平臺上事件舉辦者和參與者雙方對于參與事件的積極性,造成平臺的用戶流失.另一方面而言,對于事件舉辦者來說,他們也更喜歡請在社交媒體中影響力更大的用戶來參加他們的事件,從而擴大事件的影響力,促進事件長久高質(zhì)量地舉辦下去.因此,基于事件的社交網(wǎng)絡(luò)上規(guī)劃問題本質(zhì)上應(yīng)該是一個用戶和事件雙邊選擇的問題,所安排的計劃應(yīng)該令事件舉辦者和用戶雙方都盡量感到滿意,而現(xiàn)有的工作恰恰忽略了這一點.如果例1中的事件對用戶的偏好效用值見表2,則圖2所示的計劃中,安排給事件e1的用戶u1是其效用值最低的用戶;安排給事件e2的用戶u2和u4是其效用值最低的兩個用戶;而安排給事件e3的用戶除u5外,另兩個用戶u2和u3也是e3效用值最低的兩個用戶.可見,用現(xiàn)有工作[2-6]中的方法無法兼顧事件和用戶雙方的偏好效用.

Table 2 Events’ utility to each user表2 事件對每個用戶的效用值

根據(jù)上文所述,在基于事件的社交網(wǎng)絡(luò)規(guī)劃中,考慮事件與用戶雙邊偏好比只考慮用戶的單邊偏好的規(guī)劃在實際應(yīng)用中更合理.因此,如何定義一種新的能夠考慮用戶與事件雙邊偏好的規(guī)劃問題,是本文面臨的挑戰(zhàn)之一.另外,由于現(xiàn)有工作從未考慮過此類雙邊偏好的規(guī)劃問題,因此現(xiàn)有的考慮單邊規(guī)劃的算法能夠提供的參考性有限.而考慮雙邊偏好的規(guī)劃顯然比只考慮單邊偏好的規(guī)劃問題更復(fù)雜,約束條件更多,從而更加難以解決.為此,本文提出了基于事件的社交網(wǎng)絡(luò)上的雙邊偏好穩(wěn)態(tài)規(guī)劃問題,可以同時兼顧用戶和事件雙方對彼此之間的偏好效用,彌補現(xiàn)有工作的不足.本文提出了兩種基礎(chǔ)算法和一種改進算法,以解決該問題.最后,通過一些真實數(shù)據(jù)集上的實驗,驗證了本文提出方法的有效性和高效性.

本文第1節(jié)對基于事件的社交網(wǎng)絡(luò)上的雙邊偏好穩(wěn)態(tài)規(guī)劃問題進行定義.第2節(jié)對相關(guān)工作加以總結(jié).第3節(jié)詳細介紹兩種基礎(chǔ)算法,并分析其正確性和復(fù)雜度.第4節(jié)分析基礎(chǔ)算法的不足,并提出一種改進的方法.第5節(jié)通過真實數(shù)據(jù)集上的實驗驗證本文提出算法的高效性和有效性.第 6節(jié)對全文加以總結(jié),并提出對未來工作的設(shè)想.

1 問題定義

本節(jié)給出基于事件的社交網(wǎng)絡(luò)上的雙邊偏好穩(wěn)態(tài)規(guī)劃問題的正式定義.設(shè)基于事件的社交網(wǎng)絡(luò)平臺上的用戶集為U={ui},共包含n個用戶;事件集為E={ej},共包含m個事件.每個用戶ui∈U以二元組〈lui,Bi〉表示,其中,為向量,表示ui的當前位置,Bi為ui的行程預(yù)算值.每個事件ej∈E以四元組表示.其中,為向量,表示事件ej的舉辦地;ηj為事件ej參與人數(shù)的上界,即事件ej最多可以被分配多少人;表示事件ej舉辦的開始時間,表示結(jié)束時間.對于每一個用戶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.本文中,設(shè)定ui對每個事件的偏好順序是嚴格的,即沒有兩個效用值是相同的;同理,ej對每個用戶的偏好順序也是嚴格的.

當基于事件的社交網(wǎng)絡(luò)平臺為用戶制定計劃時,必須在一個特定時間段內(nèi)為用戶制定預(yù)計的行程計劃.為了簡單起見,本文假設(shè)該時間段為1天,即,本文所制定的計劃是為用戶提前制定一天的計劃.

設(shè)全局計劃P是為每個用戶制定一天個性化計劃的集合,即P={Pi:Pi?E,1≤i≤n}.每個用戶的計劃中不能包含彼此沖突的事件,也就是說,如果Pi中的一個事件ek在另一個事件eh之前開始,那么ek也要在eh開始之前結(jié)束.例如在例1中,事件e1和e3就是沖突的,因為e3在e1還沒有結(jié)束的時候就已經(jīng)開始了.如果事件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中,根據(jù)表1和表2,那么(u5,e2)就是一個阻塞對,因為u5比起計劃中的e3更喜歡e2,而e3比起計劃中的u3也更喜歡u5.

基于以上預(yù)備知識,現(xiàn)在對基于事件的社交網(wǎng)絡(luò)上雙邊偏好穩(wěn)態(tài)規(guī)劃問題進行定義.

定義2(基于事件的社交網(wǎng)絡(luò)上雙邊偏好穩(wěn)態(tài)規(guī)劃問題).在基于事件的社交網(wǎng)絡(luò)平臺上,雙邊偏好穩(wěn)態(tài)規(guī)劃問題是指找到一個滿足下列適當?shù)娜钟媱漃.

(2) 用戶的行程開銷要在其預(yù)算之內(nèi),即?i,Di≤Bi;

(3) 事件的參加人數(shù)要少于其人數(shù)上界,即?j|{Pi:ej∈Pi}≠ηj;

(4) P中不存在阻塞對.

根據(jù)定義2中的表述,最終的規(guī)劃中,用戶和事件雙方不會同時更喜歡另一個事件和用戶,會達到一個穩(wěn)定的狀態(tài).從經(jīng)濟學(xué)角度看,在存在競爭的關(guān)系中,穩(wěn)定平衡的狀態(tài)是最合理的,也是最符合事物發(fā)展規(guī)律的[7].

2 相關(guān)工作

本節(jié)從3個角度總結(jié)與本文相關(guān)的現(xiàn)有工作:(1) 基于位置的社交網(wǎng)絡(luò);(2) 基于事件的社交網(wǎng)絡(luò);(3) 穩(wěn)定婚姻問題及其變種.

2.1 基于位置的社交網(wǎng)絡(luò)

近年來,從線上到線下(online to offline)的服務(wù)逐步走入人們的日常生活,其中最火熱的一類服務(wù)就是基于位置的社交網(wǎng)絡(luò)[8-17].基于位置的社交網(wǎng)絡(luò)服務(wù)的現(xiàn)有工作也會推薦或安排用戶到各個事件(或地點,如旅店、商場等)中去,但這些工作更關(guān)注如何能夠使用戶各自的效用值最大,即面向用戶個人的推薦.而基于事件的社交網(wǎng)絡(luò)更關(guān)注于平臺上所有用戶和事件的總體效用值,即基于事件的社交網(wǎng)絡(luò)工作更關(guān)注于令平臺上所有用戶對計劃都很滿意.更進一步而言,現(xiàn)有的基于位置的社交網(wǎng)絡(luò)上的工作從未涉獵過事件與用戶之間的雙向選擇問題,僅僅是關(guān)注用戶單方面的偏好.

2.2 基于事件的社交網(wǎng)絡(luò)

基于事件的社交網(wǎng)絡(luò)首先由Liu等人在文獻[1]中分析了來自于兩個著名的基于事件的社交網(wǎng)絡(luò)平臺——Meetup和 Plancust數(shù)據(jù)的特征,并提出了基于事件的社交網(wǎng)絡(luò)數(shù)據(jù)模型及其相應(yīng)的性質(zhì).Zhang等人[14]和 Du等人[15]利用機器學(xué)習(xí)的方法,根據(jù)基于事件的社交網(wǎng)絡(luò)平臺上的歷史數(shù)據(jù),為用戶推薦相關(guān)的事件.Pham 等人在文獻[16]中提出了一種通用的異構(gòu)圖模型表示基于事件的社交網(wǎng)絡(luò)數(shù)據(jù),并提出了一種通用的訓(xùn)練方式解決基于事件的社交網(wǎng)絡(luò)上的3種推薦問題,即:為用戶推薦事件群組、為事件群組推薦標簽以及為事件推薦用戶.以上工作也均為關(guān)注用戶的個性化、個體化推薦,而不是平臺的全局規(guī)劃.此外,Feng等人在文獻[17]中提出了一個找到最有影響力的覆蓋集問題,即找到k用戶,他們所擁有技能的并集能夠覆蓋一個技能要求集合,并組織一個能夠使得在社交網(wǎng)絡(luò)上影響力最大的事件.從本質(zhì)上來說,該問題是解決最大影響力問題(influence maximization problem)[18]和團隊構(gòu)成問題(team formation problem)[19]所構(gòu)成的綜合問題.

一組更相關(guān)的基于事件的社交網(wǎng)絡(luò)的工作是關(guān)于社交事件組織問題(social event organization problem)[5]及其變種,它是指為一組用戶安排一系列事件,并能夠保證整個平臺的效用值是最大的.She等人在文獻[3,4]中考慮了事件之間的沖突情況,并做出了規(guī)避了沖突的事件安排;在文獻[6]考慮了用戶的行程預(yù)算問題,并從簡單將用戶和事件匹配起來的問題擴展到為用戶安排參與所有事件的合理行程.Cheng等人在文獻[2]中進一步考慮了事件的參與人數(shù)下界和動態(tài)的事件規(guī)劃問題.以上基于事件的社交網(wǎng)絡(luò)上的工作從未涉獵過事件與用戶之間的雙向選擇問題,僅僅是關(guān)注用戶單方面的偏好.

2.3 穩(wěn)定婚姻問題

穩(wěn)定婚姻問題是指:設(shè)有n個男人和n個女人,將這些男人和女人進行配對,使得該配對方案中沒有阻塞對(定義1).文獻[20,21]是兩篇非常不錯的相關(guān)綜述.最基礎(chǔ)的穩(wěn)定婚姻問題要求匹配雙方(男人和女人)的數(shù)量相同,且為一對一匹配.第1類變種為:可以允許男人和女人的偏好順序不是嚴格的,即,在某個男人(或女人)的偏好列表中,可以對某些女人(或男人)的喜好是相同的.第 2類變種將一對一匹配擴展為多對多匹配[22].這兩種變種與本文強相關(guān),但穩(wěn)定婚姻的基礎(chǔ)問題及此二變種問題,均不考慮匹配雙方(即本文中的用戶和事件)之間的相關(guān)時空信息限制(事件之間的時間沖突,事件與用戶的地理位置及用戶對行程的預(yù)算等).也就是說,以上問題是本文所研究問題的特例.因此,解決這些已有的穩(wěn)定婚姻及其變種問題的現(xiàn)有方法不能直接應(yīng)用來解決本文的問題.第3類變種為穩(wěn)定室友問題[23],即給定2n個人,他們對其他2n-1個人均給出一個偏好列表,穩(wěn)定室友問題是找到一種沒有阻塞對的穩(wěn)定匹配.該變種與本文的問題差別較大,因此亦不能用來解決本文的問題.

3 基礎(chǔ)算法

本節(jié)介紹雙邊偏好穩(wěn)態(tài)規(guī)劃問題的兩個基礎(chǔ)算法,分別是事件優(yōu)先的算法和用戶優(yōu)先的算法.

3.1 事件優(yōu)先的算法

事件優(yōu)先算法的主要思路是優(yōu)先考慮事件對用戶的偏好,讓每個事件ei優(yōu)先選擇其喜好的用戶,如果當前被選擇的用戶因與其現(xiàn)有事件(比如ej)沖突或預(yù)算不足的原因無法加入其計劃中,則要看用戶對事件ei和ej更偏好哪個,令其選擇他更偏好的那個事件,釋放另一個事件,以便于其他用戶可以對其選擇.該算法的偽代碼見算法1.

算法1.事件優(yōu)先算法.

輸入:事件對用戶的偏序PE,用戶對事件的偏序PU,事件集E,用戶集U;

輸出:全局用戶安排的事件P.

算法 1首先為每個事件設(shè)置一個是否活躍的狀態(tài):如果是活躍的,記為active,表示該事件依然可以被安排到用戶的計劃中;否則記為inactive,表示該事件已不可能被安排給任何用戶(第1行).只要有事件是active的,則通過第2行～第34行的方式對其進行用戶安排.每次取出一個active的事件,記為ei(第3行),根據(jù)其對事件的偏好列表PE(ei)來選擇用戶.PE(ei)已經(jīng)按照偏好效用值排序好,令偏好效用值高的用戶排在前端,每次選最前端的用戶uj進行處理(第4行).如果ei被安排的用戶數(shù)量已經(jīng)達到了其人數(shù)上界,則證明該事件無法被安排給更多的用戶,于是跳出循環(huán)(第5行～第7行);否則聲明一個集合conflict_events來存儲與ei沖突的事件,并初始化為空(第8行).對于ei選出的當前效用值最高的用戶uj,首先判斷P(uj)中是否有與ei沖突的事件,如果有(設(shè)為ek),則判斷在PU(uj)中uj更喜歡ei還是ek:如果用戶更喜歡ek,則證明ei無法加入到P(uj)中,并跳出循環(huán)(第10行～第13行);否則將ek從P(uj)中移除,并加入與ei沖突的conflict_events集合中,并將ek的狀態(tài)變回active(第14行～第16行).以上證明ei與P(uj)中的所有事件不沖突,于是將其加入P(uj)中(第17行).如果加入ei會使得P(uj)的行程開銷超過uj的行程預(yù)算,則不斷地刪除P(uj)偏好最差的事件(第18行～第24行).如果ei被從P(uj)中刪除,則證明ei不能加入P(uj)中,那么判斷conflict_events中的每個事件(依然按照效用值從大到小的順序)是否有合適的事件ek加入P(uj):如果可以,則加入ek并將其狀態(tài)更新為inactive(第 25行～第 32行).最后,將ei的狀態(tài)變位active(第 33行).下面用例2對算法1的過程進行說明.

例2:如例1中,事件和用戶的位置如圖2所示,用戶對事件的偏好效用值見表1,事件對用戶的偏好效用值見表2.根據(jù)算法1,所有用戶的初始狀態(tài)為active.事件e1首先選擇其最喜好的用戶u5,u5的計劃中目前還沒有事件,因此可以加入事件e1,此時e1達到其用戶數(shù)量上限,停止選擇,狀態(tài)變位inactive.之后,事件e2選擇其最喜歡的用戶u3,經(jīng)判斷,u3的計劃中可以加入e2.事件e2還可以有一個名額來選擇其第2喜歡的用戶u5,此時u5已經(jīng)參加了e1.由于e2與e1不沖突,且e2的加入不會超過u5的預(yù)算,因此e2可以加入u5的計劃中.事件e2選擇完畢,狀態(tài)變?yōu)閕nactive.事件e3進行選擇,首先選擇其最喜歡的用戶u5,但u5已經(jīng)參加了事件e1,與事件e3沖突.而在u5的偏好列表中,他更喜歡e3而不是e1,因此將e3加入其計劃中,把e1移除計劃,并將事件e1的狀態(tài)改回active.此時u5參加兩個事件e2和e3不會超過其行程預(yù)算.e3繼續(xù)考察第2喜歡的用戶u4,u4的行程預(yù)算不支持往返e3,因此不能將e3分配給u4.e3繼續(xù)考察第3喜歡的用戶u1,u1可以參加e3.e3繼續(xù)考察第4喜歡的用戶u3,u3的預(yù)算不支持同時參加e2和e3.e3繼續(xù)考察第 5喜歡的用戶u2,u2可以參加e3.此時e3的參與人數(shù)達到上界,狀態(tài)變位inactive.由于u5改去e3而放棄e1,因此e1現(xiàn)在是active的,因此令e1選擇當前最喜歡的用戶u4.u4可以參加e1,e1的參與人數(shù)達到上界,變?yōu)閕nactive.此時,所有的事件狀態(tài)均已變?yōu)閕nactive,算法結(jié)束.

算法正確性分析:算法在第 4行保障當前事件所選擇的用戶是其最喜歡的,而一旦事件不得不放棄選擇其最喜歡的用戶時,算法的第11行保障該用戶選擇到的事件是其最喜歡的.因此,至少保障用戶或事件一方滿足其最喜歡的選擇,因此不會出現(xiàn)阻塞對.同時,每當在計劃中加入一個事件或者用戶時,均會判斷是否滿足事件人數(shù)上界、用戶行程開銷、事件與計劃中是否存在沖突這些所有約束條件是否滿足.當且僅當所有的約束條件均滿足時,才會插入該事件或者用戶.因此,算法1可以滿足定義2中的所有條件,所以算法1是正確的.

算法復(fù)雜度分析:算法在第2行需要遍歷所有事件,時間復(fù)雜度為O(m);第4行～第16行需要每個事件遍歷O(n)個用戶,其余的計算復(fù)雜度為O(1).因此,算法的時間復(fù)雜度為O(mn).空間復(fù)雜度也為O(mn).

3.2 用戶優(yōu)先算法

用戶優(yōu)先算法的主要思路是:優(yōu)先考慮用戶對事件的偏好,讓每個用戶優(yōu)先選擇其喜好的事件,如果當前被選擇的事件因與其現(xiàn)有事件沖突或預(yù)算原因無法加入其計劃中,則放棄此事件.如果事件是由于參加人數(shù)已滿的原因而無法加入,則要看當前用戶在該事件已匹配的用戶的效用值是否是最低的:如果是,則放棄加入該事件;否則,用該用戶替換其計劃中效用值最低的用戶,并將其釋放另一個事件,以便其選擇其他事件.

該算法的偽代碼見算法2所示.

算法2.用戶優(yōu)先算法.

輸入:事件對用戶的偏序PE,用戶對事件的偏序PU,事件集E,用戶集U;

輸出:全局用戶安排的事件P.

算法 2首先為每個用戶設(shè)置一個是否活躍的狀態(tài):如果是活躍的,記為active,表示該用戶依然可以參加其他事件;否則記為inactive,表示該用戶已無法參加更多事件(第1行).只要有用戶是active的,則通過第2行～第19行的方式對其進行事件安排.每次取出一個active的用戶,記為ui(第3行),根據(jù)其對事件的偏好列表PU(ui)來選擇用戶.PU(ui)已經(jīng)按照偏好效用值排序好,令偏好效用值高的事件排在前端,每次選最前端的事件ej進行處理(第4行).如果加入ej會使得ui的當前行程已超過預(yù)算或與當前計劃中的事件沖突,于是跳出循環(huán)(第5行～第7行);否則,將ej加入到P(ui)中(第8行).如果加入事件ej后,ej中所安排的人數(shù)超過了其上限,則要看當前用戶在該事件已匹配用戶的效用值是否是最低的:如果是,則放棄加入該事件;否則,用該用戶替換其計劃中效用值最低的用戶,并將另一個事件釋放,以便其選擇其他事件(第 9行～第 16行).如此循環(huán)下去,直到P(ui)中無法再加入新的事件為止(第4行～第17行).此時,將ui的狀態(tài)變?yōu)閕nactive(第18行).當所有用戶的狀態(tài)均變?yōu)閕nactive時,算法結(jié)束.下面用例3對算法2的過程加以說明.

例 3:例 1中,事件和用戶的位置如圖2所示,用戶對事件的偏好效用值見表1,事件對用戶的偏好效用值見表2.根據(jù)算法 2,所有用戶的初始狀態(tài)為active.用戶u1首先選擇其最喜好的事件e1,將e1加入P(u1)中;其次是e2,將e2加入P(u1)中;之后考察e3,e3與e1沖突,因此不能將e3加入P(u1)中.u1選擇完畢,狀態(tài)變?yōu)閕nactive.用戶u2選擇事件,首先選擇其最喜歡的事件e3,將e3加入P(u2)中;其次是e2,將e2加入P(u2)中;之后考察e1,e1與e3沖突,因此不能將e3加入P(u2)中.u2選擇完畢,狀態(tài)變?yōu)閕nactive.用戶u3選擇事件,首先選擇其最喜歡的事件e3,將e3加入P(u3)中;其次是e1,e1與e3沖突,因此不能將e3加入P(u3)中;之后考察事件e2,加入e2會超過u3的預(yù)算,因此不能將e2加入P(u3)中.u3選擇完畢,狀態(tài)變?yōu)閕nactive.用戶u4選擇事件,首先選擇其最喜歡的事件e2,由于此時P(e2)中已經(jīng)有兩個用戶u1和u2,加入u4超過其人數(shù)上限,且在e2的偏好列表中u4的效用值比u1和u2都低,因此不能將e2加入P(u4)中;其次是e1,由于此時P(e1)中已經(jīng)有一個用戶u1,加入u4超過其人數(shù)上限,而e1比起u1更喜歡u4,因此將e1加入到u4中,并從P(u1)中刪除e1,將u1的狀態(tài)變?yōu)閍ctive;之后考察e3,e3與e1沖突,因此不能將e3加入P(u4)中.u4選擇完畢,狀態(tài)變?yōu)閕nactive.用戶u5選擇事件,首先選擇其最喜歡的事件e2,將e2加入P(u5)中;由于此時P(e2)中已經(jīng)有兩個用戶u1和u2,加入u5超過其人數(shù)上限,又因為其中e2最喜歡u5、最不喜歡u2,因此將e2加入到u5中,并從P(u2)中刪除e2,將u2的狀態(tài)變?yōu)閍ctive;其次是e3,將e1加入P(u5)中;之后考察e1,e1與e3沖突,因此不能將e1加入P(u5)中.u5選擇完畢,狀態(tài)變?yōu)閕nactive.此時,由于用戶u1和u2的狀態(tài)是active的,需要繼續(xù)考察.對于用戶u1而言,此時他最喜歡的事件是e3,但加入e3會超過u1的預(yù)算,因此不能將e3加入P(u1)中.u1選擇完畢,狀態(tài)變?yōu)閕nactive.對于用戶u2,還剩e1可供選擇,但e1與e3沖突,因此不能將e1加入P(u2)中.u2選擇完畢,狀態(tài)變?yōu)閕nactive.此時,所有用戶的狀態(tài)均為inactive,算法終止.

算法正確性分析:算法在第 4行保障當前用戶所選擇的事件是其最喜歡的,而一旦用戶不得不放棄選擇其最喜歡的事件時,算法的第 10行保障該事件選擇到的用戶是其當前最喜歡的.因此,至少保障用戶或事件一方滿足其最喜歡的選擇,因此不會出現(xiàn)阻塞對.同時,每當在計劃中加入一個事件或者用戶時,均會判斷是否滿足事件人數(shù)上界、用戶行程開銷、事件與計劃中是否存在沖突這些所有約束條件是否滿足.當且僅當所有的約束條件均滿足時,才會插入該事件或者用戶.因此,算法2可以滿足定義2中的所有條件,所以算法2是正確的.

算法復(fù)雜度分析:算法在第2行需要遍歷所有用戶,時間復(fù)雜度為O(n);第4行～第17行需要每個用戶遍歷O(m)個事件,其余的計算復(fù)雜度為O(1).因此,算法的時間復(fù)雜度為O(mn).空間復(fù)雜度也為O(mn).

4 改進算法

本節(jié)首先在第4.1節(jié)對基礎(chǔ)算法進行分析,指出基礎(chǔ)算法的缺點.針對該缺點提出改進算法,在第4.2節(jié)中對其加以詳述.

4.1 對基礎(chǔ)算法的分析

兩個基礎(chǔ)算法均從事件(或用戶的)單邊優(yōu)先的角度考慮,當遇到?jīng)_突或預(yù)算不足時,才通過考慮另一方的偏好來進行調(diào)整,以保證無阻塞對的出現(xiàn).但這樣可能會出現(xiàn)一種情況,即:用戶和事件雙方均沒有選到各自較為喜歡的事件和用戶,均以選擇相對不喜歡的事件或用戶從而達到穩(wěn)態(tài)(即無阻塞對的出現(xiàn)).這樣會使得雖然規(guī)劃滿足穩(wěn)態(tài)條件,但總體的效用值會變得較低.那么是否有一種方式,可以滿足時空約束條件、在達到穩(wěn)定狀態(tài)的前提下,得到盡可能高的效用值呢?本節(jié)便解決這一問題.其次,對于每個事件和用戶,都要存儲一個m×n的效用值表,當數(shù)據(jù)量大時,耗用大量的時間進行搜索,且需要大量內(nèi)存來存儲.因此,本節(jié)也介紹一種空間剪枝方法,來縮小效用值表格的存儲.

4.2 改進算法描述

改進算法的主要思路是:綜合了用戶和事件雙方對彼此的偏好,讓每個用戶(事件)優(yōu)先選擇其喜好的事件(用戶),如果當前被選擇的事件因與其現(xiàn)有事件沖突或預(yù)算原因無法加入其計劃中,則放棄此事件.如果事件是由于參加人數(shù)已滿的原因而無法加入,則要看當前用戶在該事件已匹配的用戶的效用值是否是最低的:如果是,則放棄加入該事件;否則,用該用戶替換其計劃中效用值最低的用戶,并將其釋放釋放另一個事件,以便其選擇其他事件.該算法的偽代碼見算法3.

算法3.改進算法.

輸入:事件對用戶的偏序PE,用戶對事件的偏序PU,事件集E,用戶集U;

輸出:全局用戶安排的事件P.

算法 3首先將所有可能的用戶和事件組合按照互相偏序加和,按照和的遞增排序,和越小意味著用戶和事件之間的偏好程度越高(第1行).按順序取出每一個組合,記(ei,uj)(第3行),如果ei被安排的用戶數(shù)量已經(jīng)達到了其人數(shù)上界且更偏好于當前被安排的用戶,則證明uj無法被安排到該事件,于是跳出循環(huán)(第3行～第5行);否則,聲明一個集合conflict_events來存儲與ei沖突的事件,并初始化為空(第6行).首先判斷P(uj)中是否有與ei沖突的事件,如果有(設(shè)為ek),則判斷在PU(uj)中uj更喜歡ei還是ek:如果用戶更喜歡ek,則證明ei無法加入到P(uj)中,并跳出循環(huán)(第8行～第10行);否則,將ek從P(uj)中移除,并加入與ei沖突的conflict_events集合中(第11行～第14行).以上證明ei與P(uj)中的所有事件不沖突,于是將其加入P(uj)中(第15行).如果加入ei會使得P(uj)的行程開銷超過uj的行程預(yù)算,則不斷的刪除P(uj)偏好最差的事件(第16行～第22行).如果ei被從P(uj)中刪除,則證明ei不能加入P(uj)中,那么判斷conflict_events中的每個事件(依然按照效用值從大到小的順序)是否有合適的事件ek加入P(uj):如果可以,則加入ek(第23行～第26行).最后,如果ei分配的用戶超過人數(shù)上界,則刪除ei中偏好程度最低的用戶,并將ei從P(uk)中刪除(第27行～第30行).下面用例4對算法3的過程加以說明.

例4:如例1中,事件和用戶的位置如圖2所示,用戶對事件的偏好效用值見表1,事件對用戶的偏好效用值見表2.根據(jù)算法3,所有用戶和事件的組合排序結(jié)果為(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的預(yù)算,所以e1無法加入到P(u5)中.接下來將e2加入到P(u3)中,將e2加入到P(u3)中.考察(e1,u3),e1已經(jīng)達到人數(shù)上界,且更偏愛u4,所以e1加入P(u3)中.考察(e2,u1),e2已經(jīng)達到人數(shù)上界,但e2更偏愛u1,將e2加入到P(u1)中,將e2從P(u3)中移除.下一組,將e3加入到P(u3)中.e3無法加入到P(u4)中,因為將超過u4的預(yù)算.e1無法加入到P(u1)中,因為e1更加偏愛當前的u4.同理,e2無法加入到P(u2)中.接下來考察(e3,u1),由于加入e3將超過u1的預(yù)算,所以e3無法加入到P(u1)中.將e3加入到P(u2)中.由于將會超過u4的預(yù)算,e3無法加入到P(u4)中.最后,e1無法加入到P(u3)中,因為e1更加偏愛當前的u3.此時,所有的組合遍歷完畢,算法終止.

算法正確性分析:算法在第 3行保障當前事件所選擇的用戶是其最喜歡的,而一旦事件不得不放棄選擇其最喜歡的用戶時,算法的第 9行保障該用戶選擇到的事件是其最喜歡的.因此,至少保障用戶或事件一方滿足其最喜歡的選擇,因此不會出現(xiàn)阻塞對.同時,每當在計劃中加入一個事件或者用戶時,均會判斷是否滿足事件人數(shù)上界、用戶行程開銷、事件與計劃中是否存在沖突這些所有約束條件是否滿足.當且僅當所有的約束條件均滿足時,才會插入該事件或者用戶.因此,算法3可以滿足定義2中的所有條件,所以算法3是正確的.

算法復(fù)雜度分析:算法在第2行需要遍歷所有可能組合,時間復(fù)雜度為O(mn);其余的計算復(fù)雜度為O(1).因此,算法的時間復(fù)雜度為O(mn).空間復(fù)雜度也為O(mn).

4.3 空間剪枝方法

不難發(fā)現(xiàn),對于任意一個用戶ui,他所能參加的最遠的事件,其舉辦地與ui所在位置的距離不能超過Bi/2.因此,ui可以參加的事件,其舉辦地必須在以ui所在位置為圓心、Bi/2為半徑所在的圓內(nèi).于是,在算法運行之前,可以對數(shù)據(jù)集進行預(yù)處理.對每個用戶ui來說,以為圓心、Bi/2為半徑畫一個圓,將lei不在圓內(nèi)的每個事件ej、彼此的效用值pu(ui,ej)和pe(ej,ui)均置為0,即從彼此效用值表中刪除.利用這種方法可以大量減少兩個效用值表的存儲,并節(jié)省算法在遍歷兩個效用值表時所用的時間.

5 實驗及分析

本節(jié)給出算法的實驗結(jié)果,包括實驗環(huán)境、算法的計算時間、內(nèi)存消耗、獲得的總體效用值.另外,將本文提出的穩(wěn)態(tài)規(guī)劃問題定義與現(xiàn)有工作[6]所提出的問題定義(即忽略定義2中的條件(4))及算法進行比較,證明本文提出問題定義及相應(yīng)算法的必要性.

5.1 數(shù)據(jù)集及實驗環(huán)境

本文算法用 C++及其 STL庫所實現(xiàn).實驗在一臺服務(wù)器上運行,該服務(wù)器的操作系統(tǒng)為 Linux Fedora 16(Linux3.6.11-4.fc16*86 62 GNOME 3.2.1),處理器為 Intel(R)Xeon(R) CPU E5-2620 0@2.00GHz,內(nèi)存 64GB.內(nèi)存開銷利用Linux系統(tǒng)函數(shù)進行測試.

本實驗所使用的數(shù)據(jù)集為Meetup數(shù)據(jù)集[1],數(shù)據(jù)集中,每個用戶有一個標簽文件和位置文件.標簽文件記錄用戶在平臺上注冊時所選擇的興趣標簽;位置文件記錄用戶位置的經(jīng)緯度坐標.對于每個事件,有一個位置文件以及一個事件群組文件.在 Meetup中,事件是由事件群所創(chuàng)建的,事件群文件記錄著包含在群中的事件,標簽文件記錄著每個群組的興趣標簽.位置文件記錄著每個事件舉辦地的經(jīng)緯度.利用用戶的表情文件、事件的標簽文件、群組的標簽文件,可以計算用戶對事件感興趣程度的效用值[1,3].事件對用戶的感興趣程度,由用戶參加事件的歷史記錄所計算.設(shè)e為用戶u參加過的歷史事件,e的標簽集為{L1,L2,…,Ln},則每個擁有{L1,L2,…,Ln}中至少其中一個表情的事件對u的好感度+1.統(tǒng)計所有歷史事件后,將每個事件對用戶的好感度進行歸一化.其他參數(shù)的產(chǎn)生方式與文獻[6]中相同.表3中總結(jié)了真實數(shù)據(jù)集中的各參數(shù),其中,n為數(shù)據(jù)集中的用戶數(shù)量,m為數(shù)據(jù)集中的事件數(shù)量,η為事件參與人數(shù)的上界,沖突率表示沖突事件占事件總數(shù)的百分比.

Table 3 Real datasets表3 真實數(shù)據(jù)集

為了測試算法的可擴展性,從溫哥華真實數(shù)據(jù)中截取了一定數(shù)量的用戶和事件,生成幾個合成數(shù)據(jù)集.表4列出了合成數(shù)據(jù)集中用戶數(shù)量和事件數(shù)量的變化情況,其中加粗的為默認值.

本實驗對比本文的算法1～算法3以及文獻[6]中的算法.以下,算法1記為事件穩(wěn)定規(guī)劃,算法2記為用戶穩(wěn)定規(guī)劃,算法3記為改進穩(wěn)定規(guī)劃,文獻[6]中的算法記為單邊規(guī)劃.算法1～算法3均經(jīng)過第4.3節(jié)空間剪枝方法的預(yù)處理.在真實數(shù)據(jù)集上,測試以上4個算法的總效用值、運行時間、所需內(nèi)存以及“單邊規(guī)劃”算法所得結(jié)果中阻塞對數(shù)量所占的百分比.在可擴展性測試中,測試以上4種算法在用戶數(shù)量n和事件數(shù)量m變化時,運行時間和總效用值的變化情況.在無特殊說明的情況下,n和m的值取默認值.參數(shù)名稱 設(shè)置值

Table 4 Synthetic datasets表4 合成數(shù)據(jù)集

5.2 真實數(shù)據(jù)集上的實驗結(jié)果

4種算法在真實數(shù)據(jù)集上的實驗結(jié)果見表5～表7.表5顯示各算法在真實數(shù)據(jù)集上獲得的總效用值.表6顯示單邊規(guī)劃算法在真實數(shù)據(jù)集上運行結(jié)果中阻塞對所占的百分比.表7顯示各算法在真實數(shù)據(jù)集上運行所需的時間開銷和內(nèi)存開銷.

Table 5 Results of total utility over real datasets表5 真實數(shù)據(jù)集上對總效用值的測試結(jié)果

Table 6 Results of percentage of block pairs over real datasets表6 真實數(shù)據(jù)集上單邊規(guī)劃阻塞對數(shù)量百分比

Table 7 Resultsof time and memory cost over real datasets表7 真實數(shù)據(jù)集上對時間和內(nèi)存開銷的測試結(jié)果

由表5可以看出:改進穩(wěn)定規(guī)劃算法所獲得的總效用值是最高的,在溫哥華數(shù)據(jù)集上,其效用值甚至比單邊規(guī)劃算法高出2倍以上.事件穩(wěn)定規(guī)劃算法和用戶穩(wěn)定規(guī)劃算法所獲得的總效用值在數(shù)據(jù)集北京、香港、新加坡上比單邊規(guī)劃低.這說明現(xiàn)有的單邊規(guī)劃算法不考慮事件與用戶雙方的效用偏好,它得到的總效用值是比較隨機的.而考慮了雙邊效用偏好的算法在大部分情況下,也可以獲得較高的效用值.事件穩(wěn)定規(guī)劃算法和用戶穩(wěn)定規(guī)劃兩個算法偶爾得到效用值低的情況,是它們在雙方均取較低效用值的情況下所達到的穩(wěn)態(tài)規(guī)劃.而改進算法較好地規(guī)避了這一情況,因此在保證穩(wěn)態(tài)規(guī)劃下,也可以獲得較高的總效用值,在數(shù)據(jù)量大的情況下尤為顯著.該實驗證明了本文提出穩(wěn)態(tài)規(guī)劃的合理性和必要性.

由表6可以看出:單邊規(guī)劃算法在真實數(shù)據(jù)集上所得到的計算結(jié)果中,阻塞對的數(shù)量不在少數(shù),在數(shù)據(jù)集奧克蘭和新加坡上,甚至高達61.14%和68.73%,在3個穩(wěn)態(tài)規(guī)劃算法中,阻塞對的數(shù)量為0.根據(jù)表5和表6二者綜合的結(jié)果可以看出:單邊規(guī)劃算法既不能保證事件和用戶雙方共同達到滿意,在總效用值上也不如考慮雙方偏好效用的穩(wěn)態(tài)算法.由此可以進一步的證明,本文提出的穩(wěn)態(tài)規(guī)劃問題的合理性和必要性.

由表7可以看出,單邊規(guī)劃算法和雙邊穩(wěn)態(tài)算法的內(nèi)存開銷差別不大.而在時間開銷上,雙邊穩(wěn)態(tài)規(guī)劃算法比單邊算法要高一些.這是因為,雙邊穩(wěn)態(tài)算法需要一定的時間來保障匹配結(jié)果中沒有阻塞對的存在,因此需要更多的時間開銷.另外,雖然本文提出的3種算法在時間復(fù)雜度上是一樣的,但平均來說,改進穩(wěn)態(tài)算法比兩個基礎(chǔ)算法所花費的時間要低一些.這是因為改進算法同時考慮雙方共同的選擇,因此當遇到阻塞對出現(xiàn)時,所需調(diào)整的空間就小一些.因此,改進算法在實驗中的時間開銷會比兩個基礎(chǔ)算法要小,但比單邊規(guī)劃算法要大一些.

5.3 合成數(shù)據(jù)集上的實驗結(jié)果

本節(jié)分析本文提出的 3種算法在合成數(shù)據(jù)集上的可擴展性,并與單邊規(guī)劃算法進行比較.實驗結(jié)果如圖3所示.當用戶數(shù)量n變化時,m取默認值5 000;當事件數(shù)量m變化時,n取默認值50.

圖3所示為單邊規(guī)劃算法在合成數(shù)據(jù)集上阻塞對所占的百分比,可以看出:隨著n與m變大,單邊規(guī)劃算法在合成數(shù)據(jù)集上阻塞對所占的百分比基本上在增高,當然也存在下降的情況.這是因為單邊規(guī)劃算法完全不考慮雙方穩(wěn)態(tài)平衡的問題,產(chǎn)生阻塞對的情況基本上是隨機的.而隨著數(shù)據(jù)量的增大,產(chǎn)生阻塞對的概率就會增大,因此阻塞對百分比基本會呈現(xiàn)上升趨勢.

Fig.3 Percentage of block pairs in the results of unilateral planning algorithms over synthetic datasets圖3 單邊規(guī)劃算法在合成數(shù)據(jù)集上阻塞對所占的百分比

圖4所示為時間開銷隨用戶數(shù)量和事件數(shù)量的變化情況,從圖中可以看出,4種算法的時間開銷均隨用戶數(shù)量和事件數(shù)量的增加而增加.該現(xiàn)象顯然是合理的,因為隨著數(shù)據(jù)量的增加,算法在檢索遍歷事件和用戶之間效用值的過程所耗費的時間就要增加.這是因為雙邊穩(wěn)態(tài)算法需要一定的時間來保障匹配結(jié)果中沒有阻塞對的存在,因此需要更多的時間開銷.另外,單邊規(guī)劃的時間開銷比較低,隨著用戶和事件數(shù)量的增大而增加的幅度也比較小.事件穩(wěn)態(tài)規(guī)劃和用戶穩(wěn)態(tài)規(guī)劃兩種基礎(chǔ)算法所耗費的時間最長,二者之間的差別不大.改進穩(wěn)態(tài)規(guī)劃的時間開銷介于單邊規(guī)劃和兩個基礎(chǔ)算法之間.這是因為改進算法同時考慮雙方共同的選擇,因此當遇到阻塞對出現(xiàn)時,所需調(diào)整的空間就小一些.

Fig.4 Time cost with reference to the number of users and events圖4 時間開銷隨用戶數(shù)量和事件數(shù)量的變化

圖5所示為4種算法的總效用值隨用戶數(shù)量和事件數(shù)量的變化情況,可以看出,4種算法的總效用值均隨用戶數(shù)量和事件數(shù)量的增加而增加.該現(xiàn)象顯然是合理的,因為隨著數(shù)據(jù)量的增加,形成匹配的用戶和事件的數(shù)量就會增加,因此總體的效用值必然增加.改進穩(wěn)定規(guī)劃算法所獲得的總效用值是最高的;事件穩(wěn)定規(guī)劃算法和用戶穩(wěn)定規(guī)劃算法所獲得的總效用值次之,但并不明顯;單邊規(guī)劃的總效用值最低.由此可見:現(xiàn)有的單邊規(guī)劃定義和算法無論在考慮事件和用戶的雙方滿意度上,還是總體效用值上,均不如考慮雙邊穩(wěn)態(tài)的定義和算法達到的效果好,因此也佐證了本文提出的雙邊穩(wěn)態(tài)問題的合理性.

Fig.5 Total utility with reference to the number of users and events圖5 總效用值隨用戶數(shù)量和事件數(shù)量的變化

6 結(jié)論及展望

本文重點研究社交網(wǎng)絡(luò)中為用戶規(guī)劃感興趣事件這一經(jīng)典問題,從用戶和事件兩個角度進行偏好考慮,提出一種雙邊偏好穩(wěn)態(tài)規(guī)劃算法,解決了社交網(wǎng)絡(luò)中這一雙向選擇難題.為了驗證該雙邊偏好算法的有效性,設(shè)計了兩種基礎(chǔ)算法與一種改進算法,并通過實驗進行了對比.實驗結(jié)果顯示,雙邊穩(wěn)態(tài)規(guī)劃對比現(xiàn)有的單邊規(guī)劃無論從總效用值上,還是滿足事件與用戶雙方偏好上,均沒有雙邊穩(wěn)態(tài)規(guī)劃的效果好.從而為主辦者和參與者提供了一種高效、高質(zhì)量的雙向匹配事件推送模式,有效解決了這一經(jīng)典問題中的雙向選擇難題,有助于提高社交平臺的用戶滿意度與價值提升.

未來工作中,可以考慮事件與用戶中各個參數(shù)的動態(tài)變化的可能,提供支持動態(tài)變化的雙邊穩(wěn)態(tài)規(guī)劃算法.