# Incremental Bilateral Preference Stable Planning over Event Based Social Networks

Authors: Boyang Li; Yurong Cheng; Guoren Wang; Yongjiao Sun
Journal: Complexity
 (2019)

---

## Abstract

In recent years, Event Based Social Networks (EBSNs) appear in people’s daily life and are becoming increasing popular. In EBSNs, one typical task is to make personalized plans for users. Existing studies only consider the preference of users. They make plans by selecting interesting events for users. However, for organizers of events, they also would like more high-quality users to participate in their events, which may make the events more exciting. Existing studies are user-centered and ignore the requirement of organizers. What is more, organizers are allowed to modify their events dynamically before they are held. The platforms should be able to dynamically adjust the schedules of users. Therefore, we identify a new Incremental Bilateral Preference Stable Planning (IBPSP) problem over EBSNs and propose several solutions to deal with different situations. We conduct extensive experiments to verify the efficiency and effectiveness of the proposed algorithms.


---

## Body

## 1. Introduction

In recent years, Event Based Social Networks (EBSNs) [1] have experienced rapid development and attracted much attention from both industry and academia fields. EBSNs, such as Meetup (https://www.meetup.com/) and Plancast (http://plancast.com/), link the online social groups and the offline events. Taken Meetup(https://www.meetup.com/) as an example, it has attracted more than 16 million users with more than 300 thousand events held each month.In EBSNs, one typical task is to select suitable events and make personalized plans for users to participate in according to the labels that users select as their interested points. Therefore, we can evaluate the interest of users to events based on the similarity of labels of users and events, called utility score [2–6]. The higher the utility score is, the more interested the user is to the event. Besides, the spatial distance is another import factor in personalized planning; the total travel cost of a plan should not be more than the travel budget of the user. Moreover, a user may participate in more than one events; the platform should guarantee that the time periods of events that the user participate in are not overlapped. Therefore, the goal is to make plans for all the users to maximize the utility score where the travel cost of each user cannot be more than his budget and events in the same plan do not conflict with each other.Example 1.
Suppose we have 5 users and 3 events, and details are shown in Table1. The first row describes users and their travel budget, and the first column gives the events and the upper user bound. The last column is the time period when each event is held, and the time period of e2 and e3 are overlapped. It means that users cannot participate in both e1 and e3. The other columns are the utility scores of each user. The locations of users and events are shown in Figure 1. The locations are described in a 2D space and the distance between any two locations is Euclidean distance. For a user, he starts from his current location, participates in each event in his plan one by one, and goes back to his start location. For example, the purple lines are the plan of u2. He starts from (8,2), participates in e3 and e1, and go back to (8,2) at last. The travel cost is 16.9, which is no more than the travel budget. The total utility of all users whose plans are shown in Figure 1 is 3.7.Table 1
Users’ utility to each event.
u 1 ( 40 ) u 2 ( 40 ) u 3 ( 10 ) u 4 ( 52 ) u 5 ( 18 ) Time e 1 ( 3 ) 0.6 0.3 0.4 0.5 0.2 12:30-14:00 e 2 ( 1 ) 0.1 0.4 0.8 0.6 0.7 10:00-12:00 e 3 ( 2 ) 0.1 0.7 0.9 0.2 0.9 09:00-12:00Figure 1
The location of users and events.Existing studies [2–6] only focus on the utility of users. However, the event organizers also have preference towards users for holding the event successfully. For example, organizers prefer users who are more influential in the social network to participate in their events, which may improve the quality of the events. Therefore, the personalized planning problem over EBSNs should be a bilateral planning problem among users and events. The existing techniques cannot give plans that satisfy both users and event organizers. For Example 1, we give the utility scores of events to users in Table 2. u1, u2, and u4 are the worst three users of e1. e2 prefers u4 than u5. u2 and u3 are not the best users of e3. Through analysis, these methods cannot consider the preference of both users and events at the same time.Table 2
Events’ utility to each user.
e 1 ( 3 ) e 2 ( 1 ) e 3 ( 2 ) u 1 ( 12 ) 0.3 0.4 0.8 u 2 ( 40 ) 0.1 0.8 0.7 u 3 ( 10 ) 0.6 0.4 0.6 u 4 ( 52 ) 0.2 0.7 0.5 u 5 ( 10 ) 0.9 0.5 0.9Based on the aforementioned example, it is more reasonable to consider bilateral preference of users and events than to only consider the preference of users in real applications. Moreover, the events may be modified for some reasons; the plans for users should be updated quickly once it happens. Therefore, we formally define a new personalized planning problem in EBSNs. Different from existing studies, this problem is a bilateral planning problem which considers the preference of both users and events instead of only considering the preference of user and the attributes of user and events change dynamically. In summary, to solve this problem, we make the following contributions:(i)
We identify a new Incremental Bilateral Preference Stable Planning (IBPSP) problem over EBSNs, which aims to dynamically make plans satisfying both users and event organizers.(ii)
We present solutions to give stable plans in different situations as the attributes of users and events change.(iii)
We verify the effectiveness and efficiency of the proposed methods with extensive experiments on real dataset.The rest of this paper is organized as follows. Section2 briefly introduces some basic concepts and formalizes the problem. In Section 3, we give the solutions for different conditions. Extensive experiments are conducted on a series of real-life datasets and the performance is evaluated in Section 4. Section 5 discusses the related works. Finally, we give our conclusion in Section 6.


## 2. Problem Statement

In this section, we introduce some basic concepts of EBSNs firstly. And then, we formally define the Incremental Bilateral Preference Stable Planning (IBPSP) problem. Symbols used in our paper are shown in Table3.Table 3
Summary of symbols used in our paper.
Symbol Description E The event set e An event U The user set u A user l u i Location ofui B i The travel cost budget ofui l e j Location ofej η j The largest number of participants ofej t j s The start time ofej t j e The end time ofej D i The travel cost ofui p u ( u i , e j ) The utility score ofui to ej p e ( e j , u i ) The utility score ofej to ui P U ( u i ) The preference rank ofui to all the events P E ( e j ) The preference rank ofej to all the users P The global plan P ( u i ) The set of events thatui will participate in P ( e j ) The set of users who will participate inejGiven an event based social network withn users and m events, we denote U as the user set and E as the event set. Each user ui∈U is described by a 2-tuple  lui,Bi, where lui is the location of ui in a 2D space, and Bi is the travel cost budget. Each event ej∈E is described by a 4-tuple lej,ηj,tjs,tje, where lej is the location of ej in a 2D space, ηj is the largest number of participants, and tjs and tje are the start time and end time of ej. For user ui, the utility score to event ej is denoted as pu(ui,ej), and the utility score of ej to ui is denoted as pe(ej,ui), where pu(ui,ej), peej,ui∈[0,1]. We denote the preference rank of ui is PEui, and the preference rank of ej is PE(ej). The order of utility scores is strict; that is, no two utility scores are equal.A global planP is a set of plans for all the users in the platform, denoted as P={ui,ej∣1≤i≤n,1≤j≤m}. Events in each user’s plan cannot conflict with each other. In other words, for two events ek and eh in the same user’s plan, if ek starts before eh, ek should end earlier than eh. A user may participate in several events according to his plan; the travel cost is the sum of the distance that he travels. The distance between users and events is Euclidean distance.Definition 2 (blocking pair).
For a userui and an event ej, where ui,ej∉P and the travel budget is enough to participate in ej, if ui prefers ej to at least one event in his plan and ej prefers ui to at least one user that will participate in ej, then (ui,ej) is ablocking pair.Due to the existing of travel budget, the travel cost may be larger than the budget ofui after the platform arrangements ui participate in ej. In this case, (ui,ej) is not a blocking pair.Back to Example1, according to the plans in Figure 1 and the utility scores in Tables 1 and 2, (u4,e2) is a blocking pair. The reason is that u4 prefers e2 to e1, and e2 prefers u4 to u5. (u5,e3) is not a blocking pair. The reason is that the travel budget of u5 is not enough to travel to e3, though they prefer each other. Figure 2 shows planning results without the blocking pairs.Figure 2
A planning without blocking pairs.After defining the above concepts, we next introduce the IBPSP problem as follows.Definition 3 (IBPSP problem).
Given a set of usersU, a set of events E, the preference rank PE, and PU over an EBSN platform, which allows the attributes of users and events change dynamically, the IBPSP problem is to find a global plan P for all the users such that the following constraints are satisfied:(i)
Events in the same user’s plan do not conflict with each other, where∀i∀ek≠eh∈Pui,teks<tehs⇒teke<tehe.(ii)
The travel cost of users is not more than their travel budget, where∀iDi≤Bi.(iii)
The number of participants is not more than the upper bound of events, where∀j{(ui,ej)∈P,1≤i≤n}≤ηj.(iv)
The global plan does not contain any blocking pairs.(v)
The plan is updated when the attributes change.
In the IBPSP problem, both users and events do not prefer other events and users that are out of the plan, it will reach a stable state. From the perspective of economics, in the existence of competitive relations, the stable state is the most reasonable and the most consistent with the law of development of things [7]. In practice, information of events and profiles of users are subject to change. Thus, a reasonable event planning system should support incremental updates.


## 3. Solutions to IBPSP Problem

In this section, we first introduce which attributes of users and events may change. And then, we propose several solutions to deal with the changes and update the plans that are made based on the former attributes.


### 3.1. Changes Caused by Users and Events

Travel Budget of Users. Users can modify their travel budget according to their own intentions. For example, if a user has enough to enjoy the events, he may increase the travel budget to travel further or participate in more events. A user may also travel a shorter distance or even cancel the travel plan due to the bad weather or fall ill.Participation Upper Bounds of Events. The maximum capacity of the events is limited by a number of factors. For example, if the event is more popular than expected, the organizers may choose a larger venue and increase the upper bound of participations. The opposite, however, is also possible. If a tourism interest group organizes a visit to a scenic spot, the organizer may reduce the number of people due to the restricted traffic conditions of the scenic spot.Start Times and Times of Events. The organizer may modify the start or end time if the venue is occupied during the time period when the event will be held or some important guests cannot participate in the event on time.Events Are Added or Cancelled. In EBSNs, new events will be added at any time. When a new event is added, the platform needs to arrange suitable users to participate in this event. The planned events can also be cancelled for all kinds of reasons. When it happens, the platform needs to arrange users to participate in other events that are suitable for them.


### 3.2. Solutions

In this section, suppose the platform has made plans for users. And then, the changes which are introduced above come. We provide solutions on how to solve the changes when the changes happen.


#### 3.2.1.Bi Is Decreased

When the travel budget of a user decreases, it may lead to that he cannot participate in some events that are planned by the platform for him. The platform needs to remove some events from his plan until the total travel cost is no more than the budget. What is more, the plans also need to be adjusted to make sure that there are no blocking pairs in the new plan.The pseudocode is illustrated in Algorithm1. When the travel budget of ui changes, we first initialize a set Eac as an empty set (Line 2). Eac stores the events that are affected by the change. While the travel cost is larger than the travel budget, we find an event ej in P(ui) whose utility score is the lowest in PU(ui), remove it from P(ui), and put it into Eac (Lines 3-6). After this step, we make sure that the travel cost is not greater than the new travel budget. Since ui cannot participate in some events, there may be blocking pairs in the plans of these events. Finally, Algorithm 2 is called to update the plans of events in Eac.Algorithm 1:Budget decreasing algorithm.
Input: PE, PU, E, U, Pold, ui Output: P 1  P ← P o l d 2  E a c ← ∅ 3  While(Di>Bi) 4  e j ← event with the worst utility score in P(ui) 5 Put ej into Eac, remove ej, ui from P(ui), P(ej) 6  EndWhile 7  ReturnUpdate_event_plan(PE, PU, E, U, Pold, Eac)Algorithm 2:Update_event_plan.
Input: PE, PU, E, U, Pold, Eac Output: P 1  P ← P o l d 2  While(Eac≠∅) 3 Pop ej from Eac 4  u h ← user with the worst utility in P(ej) 5  Foreach (ui after uh in PEej⋀ the number of participants does not exceed ηj) 6  c o n f l i c t _ e v e n t s  = ϕ 7  If(∃ek∈P(uj) that conflicts with ej) 8  continue 9  EndIf 10  Foreach(ek∈P(uj)) 11 Remove ek from P(ui), put ek into conflict_events, put ek into Eac 12  EndFor 13 Put ej into P(uj) 14  While(Di>Bi) 15 Remove the worst event ek from P(ui) 16  If(ej is removed) 17  break 18  EndIf 19 Put  ek into conflict_events, put ek into Eac 20  EndWhile 21  If(ej has been removed from P(ui)) 22  Foreach(ek∈conflict_events) 23 Put ek back to P(ui), remove ek from Eac 24  EndFor 25  EndIf 26  EndFor 27  Endwhile 28  Return PAlgorithm2 terminates until Eac is empty and returns a new global plan. In each loop, we pop an event ej from Eac (Line 3) and start to enumerate each user ui whose utility is not greater than the lowest utility in current plan P(ej) until the number of participants equals ηj (Lines 4-5). If ej conflicts with ek that has a higher utility in (uj), then we start again from the next user (Lines 7-9). Otherwise, we remove the events whose utility is less than ej from P(ui) and put them in a conflict set and they are also put into Eac (Lines 10-12). Then we can add ej to P(uj) (Line 13). If the travel cost is greater than the travel budget, we remove some events and put them into the conflict set and Eac (Lines 14-20). If ej is also removed in the former step, it means ej is too fat for uj to participate in, and P(ui) is rehabilitated (Lines 21-25).Example 4.
Based on the planning of Figure2, suppose that the travel budget of u1 decreases to 5. Then, e3 is removed from P(u1) and put into Eac. We pop e3 from Eac, and u3 can participate in it; a new stable planning is constructed.


#### 3.2.2.ηj Is Decreased

Whenη decreases, the number of participants may exceeds the new upper bound in current plans. The platform needs to remove some participants and adjust the plans of these participants.The pseudocode is illustrated in Algorithm3. When ηj changes, we first initialize a set Uac as an empty set (Line 2). Uac stores the users that are affected by the change. While the number of participants is larger than the new upper bound, we find a user ui in P(ej) whose utility score is the lowest in PE(ej), remove him from P(ej), and put it into Uac (Lines 3-6). After this step, we make sure that the new η is satisfied. Finally, Algorithm 4 is called to update the plans of users in Uac.Algorithm 3: η decreasing algorithm.
Input: PE, PU, E, U, Pold, ej Output: P 1  P ← P o l d 2  U a c ← ∅ 3  While(|P(ej)|>ηj) 4  u i ← user with the worst utility score in P(ej) 5 Put ui into Uac, remove ej, ui from P(ui), P(ej) 6  Endwhile 7  ReturnUpdate_user_plan(PE, PU, E, U, Pold, Uac)Algorithm 4:Update_user_plan.
Input: PE, PU, E, U, Pold, Uac Output: P 1  P ← P o l d 2  While(Uac≠∅) 3 Pop ui from Uac 4  e k ← event with the worst utility in P(ui) 5  Foreach (ej after ek in PU(ui)) 6  If(∃eh∈P(ui) conflicts with ej) 7  break 8  EndIf 9 Add ej, ui into P(ui), P(ej) 10  If(the number of participants exceeds ηj) 11  If(ui is the worst user in P(ej)) 12 Remove ej, ui from P(ui), P(ej) 13  break; 14  ElseIf 15 Remove the worst user uk from Pej 16 Put uk into Uac 17  EndIf 18  EndIf 19  EndFor 20  Endwhile 21  Return PAlgorithm4 terminates until Uac is empty and return a new global plan. In each loop, we pop a user ui from Uac (Line 3) and start to enumerate each event ej whose utility are not greater than the lowest utility in current plan P(ui) (Lines 4-5). If ej conflicts with ek that has a higher utility in P(ui), then we start again from the next event (Lines 6-8). Otherwise, add ej, ui into P(ui), Pej (Line 9). If the number of participants exceeds ηj, we remove the user with the lowest utility in P(ej) and put the user into Uac if he is not ui (Lines 9-18).Finally the new global plan P is returned (Line 21).Example 5.
Based on the planning of Figure2, suppose that the participant bound of e3 decreases to 1. Then, e3 is removed from the planning of u2, and u2 is put into Uac. We pop u2 from Uac, then e2 is removed from the planning of u4 and u4 is put into Uac. u4 cannot participate in other events; a new stable planning is constructed.


#### 3.2.3.tjs or tje Is Changed

If the start or end time changes, it may cause many conflicts in the original planP. There are four kinds of cases that the global plan needs to be updated: (1) the new event conflicts with events that with higher utility scores in users’ plans, (2) the event does not conflict with events with higher utility scores in the same plan, however, some events with lower utility scores that conflict with it, (3) the original event conflicts with some events in the users’ plan but the conflicts do not exist after the change, and (4) some events out of users’ conflict with the original event but the conflicts do not exist after the change.The pseudocode is illustrated in Algorithm5. We initialize Uac and Eac at first (Line 1). And then, we find all the users whose plans are affected by the change, remove ej from their plans, and put them into Uac (Lines 3-5). The plan of ej is cleared and needs to be replanned (Line 6). For users in Uac and events in Eac, we call Algorithms 2 and 3 to update their plans (Lines 7-12).Algorithm 5: t j s or tje changing algorithm.
Input: PE, PU, E, U, Pold, ej Output: P 1  U a c = ϕ ,  E a c = ∅ 2  P ← P o l d 3  Foreach(ui∈P(ej)) 4 Remove ej from P(ui), put ui into Uac 5  EndFor 6 Empty P(ej), put ej into Eac 7  If(Uac≠∅) 8  P ←Update start users(PE, PU, E, U, P, Uac) 9  EndIf 10  If(Eac≠∅) 11  P ←Update start events(PE, PU, E, U, P, Eac) 12  EndIf 13  Return P


#### 3.2.4. The Other Situations

We discuss how to solve the other situations, based on the above algorithms.B i Is Increased. When the travel budget of a user increases, the user can participate in more events. We can update his plan by putting him into Uac and calling Algorithm 4. However, we need to make a small change to Algorithm 4. We cannot enumerate events starting from whose utility is not greater than the lowest utility in current plan; it will result in blocking pairs. The user may participate in events with higher utility than events in the current plan, because his travel budget may be large enough to travel to the locations of these events. Therefore, we enumerate events starting from whose utility is the largest and add them into the plan if possible.η j Is Increased. When η increases, the event can accommodate more participants; we then put it into Eac and call Algorithm 2 to update the plans. Note that if the number of participants is less than the original upper bound, the plans need not to be update.


#### 3.2.5. Multiple Changes in One Run

We consider a more complex case in which multiple changes come at the same time. As introduced above, all the changes can be solved by two basic algorithms. The main idea is that we find the events and users whose plans need to be updated and conduct Algorithms2 and 4 to update their plans.The pseudocode is illustrated in Algorithm6. We initialize Uac and Eac at first (Line 1). While the travel cost is larger than the travel budget, we find an event ej in P(ui) whose utility score is the lowest in PU(ui), remove it from P(ui), and put it into Eac (Lines 3-6). And then, we find all the users whose plans are affected by the change, remove ej from their plans, and put them into Uac (Lines 7-9). The plan of ej is cleared and needs to be replanned (Line 10). For users in Uac and events in Eac, we call Algorithms 2 and 3 to update their plans (Lines 11-17).Algorithm 6:Multiple changes in one run.
Input: PE, PU, E, U, Pold, ej, ui Output: P 1  U a c = ϕ ,  E a c = ∅ 2  P ← P o l d 3  While(Di>Bi) 4  e j ← event with the worst utility score in P(ui) 5 Put ej into Eac, remove ej, ui from P(ui), P(ej) 6  Endwhile 7  Foreach(ui∈P(ej)) 8 Remove ej from P(ui), put ui into Uac 9  EndFor 10 Empty P(ej), put ej into Eac 11  If(Uac≠∅) 12  P ←Update start users(PE, PU, E, U, P, Uac) 13  EndIf 14  If(Eac≠∅) 15  P ←Update start events(PE, PU, E, U, P, Eac) 16  EndIf 17  Return P


## 3.1. Changes Caused by Users and Events

Travel Budget of Users. Users can modify their travel budget according to their own intentions. For example, if a user has enough to enjoy the events, he may increase the travel budget to travel further or participate in more events. A user may also travel a shorter distance or even cancel the travel plan due to the bad weather or fall ill.Participation Upper Bounds of Events. The maximum capacity of the events is limited by a number of factors. For example, if the event is more popular than expected, the organizers may choose a larger venue and increase the upper bound of participations. The opposite, however, is also possible. If a tourism interest group organizes a visit to a scenic spot, the organizer may reduce the number of people due to the restricted traffic conditions of the scenic spot.Start Times and Times of Events. The organizer may modify the start or end time if the venue is occupied during the time period when the event will be held or some important guests cannot participate in the event on time.Events Are Added or Cancelled. In EBSNs, new events will be added at any time. When a new event is added, the platform needs to arrange suitable users to participate in this event. The planned events can also be cancelled for all kinds of reasons. When it happens, the platform needs to arrange users to participate in other events that are suitable for them.


## 3.2. Solutions

In this section, suppose the platform has made plans for users. And then, the changes which are introduced above come. We provide solutions on how to solve the changes when the changes happen.


### 3.2.1.Bi Is Decreased

When the travel budget of a user decreases, it may lead to that he cannot participate in some events that are planned by the platform for him. The platform needs to remove some events from his plan until the total travel cost is no more than the budget. What is more, the plans also need to be adjusted to make sure that there are no blocking pairs in the new plan.The pseudocode is illustrated in Algorithm1. When the travel budget of ui changes, we first initialize a set Eac as an empty set (Line 2). Eac stores the events that are affected by the change. While the travel cost is larger than the travel budget, we find an event ej in P(ui) whose utility score is the lowest in PU(ui), remove it from P(ui), and put it into Eac (Lines 3-6). After this step, we make sure that the travel cost is not greater than the new travel budget. Since ui cannot participate in some events, there may be blocking pairs in the plans of these events. Finally, Algorithm 2 is called to update the plans of events in Eac.Algorithm 1:Budget decreasing algorithm.
Input: PE, PU, E, U, Pold, ui Output: P 1  P ← P o l d 2  E a c ← ∅ 3  While(Di>Bi) 4  e j ← event with the worst utility score in P(ui) 5 Put ej into Eac, remove ej, ui from P(ui), P(ej) 6  EndWhile 7  ReturnUpdate_event_plan(PE, PU, E, U, Pold, Eac)Algorithm 2:Update_event_plan.
Input: PE, PU, E, U, Pold, Eac Output: P 1  P ← P o l d 2  While(Eac≠∅) 3 Pop ej from Eac 4  u h ← user with the worst utility in P(ej) 5  Foreach (ui after uh in PEej⋀ the number of participants does not exceed ηj) 6  c o n f l i c t _ e v e n t s  = ϕ 7  If(∃ek∈P(uj) that conflicts with ej) 8  continue 9  EndIf 10  Foreach(ek∈P(uj)) 11 Remove ek from P(ui), put ek into conflict_events, put ek into Eac 12  EndFor 13 Put ej into P(uj) 14  While(Di>Bi) 15 Remove the worst event ek from P(ui) 16  If(ej is removed) 17  break 18  EndIf 19 Put  ek into conflict_events, put ek into Eac 20  EndWhile 21  If(ej has been removed from P(ui)) 22  Foreach(ek∈conflict_events) 23 Put ek back to P(ui), remove ek from Eac 24  EndFor 25  EndIf 26  EndFor 27  Endwhile 28  Return PAlgorithm2 terminates until Eac is empty and returns a new global plan. In each loop, we pop an event ej from Eac (Line 3) and start to enumerate each user ui whose utility is not greater than the lowest utility in current plan P(ej) until the number of participants equals ηj (Lines 4-5). If ej conflicts with ek that has a higher utility in (uj), then we start again from the next user (Lines 7-9). Otherwise, we remove the events whose utility is less than ej from P(ui) and put them in a conflict set and they are also put into Eac (Lines 10-12). Then we can add ej to P(uj) (Line 13). If the travel cost is greater than the travel budget, we remove some events and put them into the conflict set and Eac (Lines 14-20). If ej is also removed in the former step, it means ej is too fat for uj to participate in, and P(ui) is rehabilitated (Lines 21-25).Example 4.
Based on the planning of Figure2, suppose that the travel budget of u1 decreases to 5. Then, e3 is removed from P(u1) and put into Eac. We pop e3 from Eac, and u3 can participate in it; a new stable planning is constructed.


### 3.2.2.ηj Is Decreased

Whenη decreases, the number of participants may exceeds the new upper bound in current plans. The platform needs to remove some participants and adjust the plans of these participants.The pseudocode is illustrated in Algorithm3. When ηj changes, we first initialize a set Uac as an empty set (Line 2). Uac stores the users that are affected by the change. While the number of participants is larger than the new upper bound, we find a user ui in P(ej) whose utility score is the lowest in PE(ej), remove him from P(ej), and put it into Uac (Lines 3-6). After this step, we make sure that the new η is satisfied. Finally, Algorithm 4 is called to update the plans of users in Uac.Algorithm 3: η decreasing algorithm.
Input: PE, PU, E, U, Pold, ej Output: P 1  P ← P o l d 2  U a c ← ∅ 3  While(|P(ej)|>ηj) 4  u i ← user with the worst utility score in P(ej) 5 Put ui into Uac, remove ej, ui from P(ui), P(ej) 6  Endwhile 7  ReturnUpdate_user_plan(PE, PU, E, U, Pold, Uac)Algorithm 4:Update_user_plan.
Input: PE, PU, E, U, Pold, Uac Output: P 1  P ← P o l d 2  While(Uac≠∅) 3 Pop ui from Uac 4  e k ← event with the worst utility in P(ui) 5  Foreach (ej after ek in PU(ui)) 6  If(∃eh∈P(ui) conflicts with ej) 7  break 8  EndIf 9 Add ej, ui into P(ui), P(ej) 10  If(the number of participants exceeds ηj) 11  If(ui is the worst user in P(ej)) 12 Remove ej, ui from P(ui), P(ej) 13  break; 14  ElseIf 15 Remove the worst user uk from Pej 16 Put uk into Uac 17  EndIf 18  EndIf 19  EndFor 20  Endwhile 21  Return PAlgorithm4 terminates until Uac is empty and return a new global plan. In each loop, we pop a user ui from Uac (Line 3) and start to enumerate each event ej whose utility are not greater than the lowest utility in current plan P(ui) (Lines 4-5). If ej conflicts with ek that has a higher utility in P(ui), then we start again from the next event (Lines 6-8). Otherwise, add ej, ui into P(ui), Pej (Line 9). If the number of participants exceeds ηj, we remove the user with the lowest utility in P(ej) and put the user into Uac if he is not ui (Lines 9-18).Finally the new global plan P is returned (Line 21).Example 5.
Based on the planning of Figure2, suppose that the participant bound of e3 decreases to 1. Then, e3 is removed from the planning of u2, and u2 is put into Uac. We pop u2 from Uac, then e2 is removed from the planning of u4 and u4 is put into Uac. u4 cannot participate in other events; a new stable planning is constructed.


### 3.2.3.tjs or tje Is Changed

If the start or end time changes, it may cause many conflicts in the original planP. There are four kinds of cases that the global plan needs to be updated: (1) the new event conflicts with events that with higher utility scores in users’ plans, (2) the event does not conflict with events with higher utility scores in the same plan, however, some events with lower utility scores that conflict with it, (3) the original event conflicts with some events in the users’ plan but the conflicts do not exist after the change, and (4) some events out of users’ conflict with the original event but the conflicts do not exist after the change.The pseudocode is illustrated in Algorithm5. We initialize Uac and Eac at first (Line 1). And then, we find all the users whose plans are affected by the change, remove ej from their plans, and put them into Uac (Lines 3-5). The plan of ej is cleared and needs to be replanned (Line 6). For users in Uac and events in Eac, we call Algorithms 2 and 3 to update their plans (Lines 7-12).Algorithm 5: t j s or tje changing algorithm.
Input: PE, PU, E, U, Pold, ej Output: P 1  U a c = ϕ ,  E a c = ∅ 2  P ← P o l d 3  Foreach(ui∈P(ej)) 4 Remove ej from P(ui), put ui into Uac 5  EndFor 6 Empty P(ej), put ej into Eac 7  If(Uac≠∅) 8  P ←Update start users(PE, PU, E, U, P, Uac) 9  EndIf 10  If(Eac≠∅) 11  P ←Update start events(PE, PU, E, U, P, Eac) 12  EndIf 13  Return P


### 3.2.4. The Other Situations

We discuss how to solve the other situations, based on the above algorithms.B i Is Increased. When the travel budget of a user increases, the user can participate in more events. We can update his plan by putting him into Uac and calling Algorithm 4. However, we need to make a small change to Algorithm 4. We cannot enumerate events starting from whose utility is not greater than the lowest utility in current plan; it will result in blocking pairs. The user may participate in events with higher utility than events in the current plan, because his travel budget may be large enough to travel to the locations of these events. Therefore, we enumerate events starting from whose utility is the largest and add them into the plan if possible.η j Is Increased. When η increases, the event can accommodate more participants; we then put it into Eac and call Algorithm 2 to update the plans. Note that if the number of participants is less than the original upper bound, the plans need not to be update.


### 3.2.5. Multiple Changes in One Run

We consider a more complex case in which multiple changes come at the same time. As introduced above, all the changes can be solved by two basic algorithms. The main idea is that we find the events and users whose plans need to be updated and conduct Algorithms2 and 4 to update their plans.The pseudocode is illustrated in Algorithm6. We initialize Uac and Eac at first (Line 1). While the travel cost is larger than the travel budget, we find an event ej in P(ui) whose utility score is the lowest in PU(ui), remove it from P(ui), and put it into Eac (Lines 3-6). And then, we find all the users whose plans are affected by the change, remove ej from their plans, and put them into Uac (Lines 7-9). The plan of ej is cleared and needs to be replanned (Line 10). For users in Uac and events in Eac, we call Algorithms 2 and 3 to update their plans (Lines 11-17).Algorithm 6:Multiple changes in one run.
Input: PE, PU, E, U, Pold, ej, ui Output: P 1  U a c = ϕ ,  E a c = ∅ 2  P ← P o l d 3  While(Di>Bi) 4  e j ← event with the worst utility score in P(ui) 5 Put ej into Eac, remove ej, ui from P(ui), P(ej) 6  Endwhile 7  Foreach(ui∈P(ej)) 8 Remove ej from P(ui), put ui into Uac 9  EndFor 10 Empty P(ej), put ej into Eac 11  If(Uac≠∅) 12  P ←Update start users(PE, PU, E, U, P, Uac) 13  EndIf 14  If(Eac≠∅) 15  P ←Update start events(PE, PU, E, U, P, Eac) 16  EndIf 17  Return P


## 3.2.1.Bi Is Decreased

When the travel budget of a user decreases, it may lead to that he cannot participate in some events that are planned by the platform for him. The platform needs to remove some events from his plan until the total travel cost is no more than the budget. What is more, the plans also need to be adjusted to make sure that there are no blocking pairs in the new plan.The pseudocode is illustrated in Algorithm1. When the travel budget of ui changes, we first initialize a set Eac as an empty set (Line 2). Eac stores the events that are affected by the change. While the travel cost is larger than the travel budget, we find an event ej in P(ui) whose utility score is the lowest in PU(ui), remove it from P(ui), and put it into Eac (Lines 3-6). After this step, we make sure that the travel cost is not greater than the new travel budget. Since ui cannot participate in some events, there may be blocking pairs in the plans of these events. Finally, Algorithm 2 is called to update the plans of events in Eac.Algorithm 1:Budget decreasing algorithm.
Input: PE, PU, E, U, Pold, ui Output: P 1  P ← P o l d 2  E a c ← ∅ 3  While(Di>Bi) 4  e j ← event with the worst utility score in P(ui) 5 Put ej into Eac, remove ej, ui from P(ui), P(ej) 6  EndWhile 7  ReturnUpdate_event_plan(PE, PU, E, U, Pold, Eac)Algorithm 2:Update_event_plan.
Input: PE, PU, E, U, Pold, Eac Output: P 1  P ← P o l d 2  While(Eac≠∅) 3 Pop ej from Eac 4  u h ← user with the worst utility in P(ej) 5  Foreach (ui after uh in PEej⋀ the number of participants does not exceed ηj) 6  c o n f l i c t _ e v e n t s  = ϕ 7  If(∃ek∈P(uj) that conflicts with ej) 8  continue 9  EndIf 10  Foreach(ek∈P(uj)) 11 Remove ek from P(ui), put ek into conflict_events, put ek into Eac 12  EndFor 13 Put ej into P(uj) 14  While(Di>Bi) 15 Remove the worst event ek from P(ui) 16  If(ej is removed) 17  break 18  EndIf 19 Put  ek into conflict_events, put ek into Eac 20  EndWhile 21  If(ej has been removed from P(ui)) 22  Foreach(ek∈conflict_events) 23 Put ek back to P(ui), remove ek from Eac 24  EndFor 25  EndIf 26  EndFor 27  Endwhile 28  Return PAlgorithm2 terminates until Eac is empty and returns a new global plan. In each loop, we pop an event ej from Eac (Line 3) and start to enumerate each user ui whose utility is not greater than the lowest utility in current plan P(ej) until the number of participants equals ηj (Lines 4-5). If ej conflicts with ek that has a higher utility in (uj), then we start again from the next user (Lines 7-9). Otherwise, we remove the events whose utility is less than ej from P(ui) and put them in a conflict set and they are also put into Eac (Lines 10-12). Then we can add ej to P(uj) (Line 13). If the travel cost is greater than the travel budget, we remove some events and put them into the conflict set and Eac (Lines 14-20). If ej is also removed in the former step, it means ej is too fat for uj to participate in, and P(ui) is rehabilitated (Lines 21-25).Example 4.
Based on the planning of Figure2, suppose that the travel budget of u1 decreases to 5. Then, e3 is removed from P(u1) and put into Eac. We pop e3 from Eac, and u3 can participate in it; a new stable planning is constructed.


## 3.2.2.ηj Is Decreased

Whenη decreases, the number of participants may exceeds the new upper bound in current plans. The platform needs to remove some participants and adjust the plans of these participants.The pseudocode is illustrated in Algorithm3. When ηj changes, we first initialize a set Uac as an empty set (Line 2). Uac stores the users that are affected by the change. While the number of participants is larger than the new upper bound, we find a user ui in P(ej) whose utility score is the lowest in PE(ej), remove him from P(ej), and put it into Uac (Lines 3-6). After this step, we make sure that the new η is satisfied. Finally, Algorithm 4 is called to update the plans of users in Uac.Algorithm 3: η decreasing algorithm.
Input: PE, PU, E, U, Pold, ej Output: P 1  P ← P o l d 2  U a c ← ∅ 3  While(|P(ej)|>ηj) 4  u i ← user with the worst utility score in P(ej) 5 Put ui into Uac, remove ej, ui from P(ui), P(ej) 6  Endwhile 7  ReturnUpdate_user_plan(PE, PU, E, U, Pold, Uac)Algorithm 4:Update_user_plan.
Input: PE, PU, E, U, Pold, Uac Output: P 1  P ← P o l d 2  While(Uac≠∅) 3 Pop ui from Uac 4  e k ← event with the worst utility in P(ui) 5  Foreach (ej after ek in PU(ui)) 6  If(∃eh∈P(ui) conflicts with ej) 7  break 8  EndIf 9 Add ej, ui into P(ui), P(ej) 10  If(the number of participants exceeds ηj) 11  If(ui is the worst user in P(ej)) 12 Remove ej, ui from P(ui), P(ej) 13  break; 14  ElseIf 15 Remove the worst user uk from Pej 16 Put uk into Uac 17  EndIf 18  EndIf 19  EndFor 20  Endwhile 21  Return PAlgorithm4 terminates until Uac is empty and return a new global plan. In each loop, we pop a user ui from Uac (Line 3) and start to enumerate each event ej whose utility are not greater than the lowest utility in current plan P(ui) (Lines 4-5). If ej conflicts with ek that has a higher utility in P(ui), then we start again from the next event (Lines 6-8). Otherwise, add ej, ui into P(ui), Pej (Line 9). If the number of participants exceeds ηj, we remove the user with the lowest utility in P(ej) and put the user into Uac if he is not ui (Lines 9-18).Finally the new global plan P is returned (Line 21).Example 5.
Based on the planning of Figure2, suppose that the participant bound of e3 decreases to 1. Then, e3 is removed from the planning of u2, and u2 is put into Uac. We pop u2 from Uac, then e2 is removed from the planning of u4 and u4 is put into Uac. u4 cannot participate in other events; a new stable planning is constructed.


## 3.2.3.tjs or tje Is Changed

If the start or end time changes, it may cause many conflicts in the original planP. There are four kinds of cases that the global plan needs to be updated: (1) the new event conflicts with events that with higher utility scores in users’ plans, (2) the event does not conflict with events with higher utility scores in the same plan, however, some events with lower utility scores that conflict with it, (3) the original event conflicts with some events in the users’ plan but the conflicts do not exist after the change, and (4) some events out of users’ conflict with the original event but the conflicts do not exist after the change.The pseudocode is illustrated in Algorithm5. We initialize Uac and Eac at first (Line 1). And then, we find all the users whose plans are affected by the change, remove ej from their plans, and put them into Uac (Lines 3-5). The plan of ej is cleared and needs to be replanned (Line 6). For users in Uac and events in Eac, we call Algorithms 2 and 3 to update their plans (Lines 7-12).Algorithm 5: t j s or tje changing algorithm.
Input: PE, PU, E, U, Pold, ej Output: P 1  U a c = ϕ ,  E a c = ∅ 2  P ← P o l d 3  Foreach(ui∈P(ej)) 4 Remove ej from P(ui), put ui into Uac 5  EndFor 6 Empty P(ej), put ej into Eac 7  If(Uac≠∅) 8  P ←Update start users(PE, PU, E, U, P, Uac) 9  EndIf 10  If(Eac≠∅) 11  P ←Update start events(PE, PU, E, U, P, Eac) 12  EndIf 13  Return P


## 3.2.4. The Other Situations

We discuss how to solve the other situations, based on the above algorithms.B i Is Increased. When the travel budget of a user increases, the user can participate in more events. We can update his plan by putting him into Uac and calling Algorithm 4. However, we need to make a small change to Algorithm 4. We cannot enumerate events starting from whose utility is not greater than the lowest utility in current plan; it will result in blocking pairs. The user may participate in events with higher utility than events in the current plan, because his travel budget may be large enough to travel to the locations of these events. Therefore, we enumerate events starting from whose utility is the largest and add them into the plan if possible.η j Is Increased. When η increases, the event can accommodate more participants; we then put it into Eac and call Algorithm 2 to update the plans. Note that if the number of participants is less than the original upper bound, the plans need not to be update.


## 3.2.5. Multiple Changes in One Run

We consider a more complex case in which multiple changes come at the same time. As introduced above, all the changes can be solved by two basic algorithms. The main idea is that we find the events and users whose plans need to be updated and conduct Algorithms2 and 4 to update their plans.The pseudocode is illustrated in Algorithm6. We initialize Uac and Eac at first (Line 1). While the travel cost is larger than the travel budget, we find an event ej in P(ui) whose utility score is the lowest in PU(ui), remove it from P(ui), and put it into Eac (Lines 3-6). And then, we find all the users whose plans are affected by the change, remove ej from their plans, and put them into Uac (Lines 7-9). The plan of ej is cleared and needs to be replanned (Line 10). For users in Uac and events in Eac, we call Algorithms 2 and 3 to update their plans (Lines 11-17).Algorithm 6:Multiple changes in one run.
Input: PE, PU, E, U, Pold, ej, ui Output: P 1  U a c = ϕ ,  E a c = ∅ 2  P ← P o l d 3  While(Di>Bi) 4  e j ← event with the worst utility score in P(ui) 5 Put ej into Eac, remove ej, ui from P(ui), P(ej) 6  Endwhile 7  Foreach(ui∈P(ej)) 8 Remove ej from P(ui), put ui into Uac 9  EndFor 10 Empty P(ej), put ej into Eac 11  If(Uac≠∅) 12  P ←Update start users(PE, PU, E, U, P, Uac) 13  EndIf 14  If(Eac≠∅) 15  P ←Update start events(PE, PU, E, U, P, Eac) 16  EndIf 17  Return P


## 4. Performance Evaluation

In this section, we provide an empirical evaluation of our proposed algorithms, including the experimental environment, algorithm running time, memory cost, and the total sum of utility scores of users.


### 4.1. Experiment Environment and Dataset

We conduct our algorithms over a real-life dataset, the Meetup dataset [1], which is a popular event based social network. The dataset records the locations of users and the tags that indicate the interesting points of the users. It also records the locations of events where they are held. The events are held by interesting groups; therefore, the tags of events are the tags of whom hold them. The utility scores are calculated as the method in [1]. We extract six datasets of different cities according to the longitude and latitude and generate other parameters, summarized in Table 4. We also use a synthetic dataset to test the scalability of our algorithms, shown in Table 5.Table 4
Real datasets.
City U E Mean ofη Conflict ratio Beijing 113 16 50 0.25 Auckland 569 37 50 0.25 Hawaii 2967 817 50 0.25 Hong Kong 3528 1324 50 0.25 Singapore 9893 4257 50 0.25 Vancouver 16095 11536 50 0.25Table 5
Synthetic datasets.
Value | U | 200, 500, 1000,5000 | E | 200, 500,1000, 5000The algorithms are implemented in Visual C++ 2017, and the experiments are conducted in a Windows 10 machine with Intel(R) Core(TM) i5-6500 3.20GHz CPU and 16GB main memory. When the changes come, we treat all the events as new added and get a global plan as the contrast experiment, named Re-Plan. In each experiment, we repeat 10 times and report the average results.


### 4.2. Results on Real Dataset

In this section, we test the performance of our algorithms, denoted asB-De, η-De, ts-te, and Mul, on Meetup datasets. For each algorithm, we randomly select several users to decrease their travel budget and several events to decrease their upper bound of participations one by one. For the multiple case, we randomly select some users and events of the three kinds of changes.The experiment results are shown in Tables6–9. The utility scores of B-De are the same as Re-Plan. The reason is that B-De conducts the same algorithm to update the plans of events as Re-Plan. In other cases, the algorithms are similar with Re-Plan. η-De is better than Re-Plan on Hawaii and Vancouver, ts-te is better on Hawaii and Hong Kong, and Mul is better on Singapore and Vancouver. In IBPSP problem, the stable plan is not unique; we can find different stable plans through different algorithms. Though the utility scores are not the same, the plans are still stable. In all the algorithms, the running time is much smaller than the Re-Plan; the reason is that the incremental algorithms only adjust the plans of users and events that are affected by the changes, but the Re-Plan makes plans for all the users and events over again. The running time increases as the data size increases. The incremental algorithms cost the similar memory as Re-Plan due to the fact that they all need memory to store the preference and the final plans. Mul costs a bit more memory than others due to size of Uac and Eac is larger than others.Table 6
Results ofB-De on real datasets.
City Re-Plan B-De Utility Time(s) Memory(MB) Utility Time(s) Memory(MB) Beijing 218.94 0.81 0.78 218.94 0.01 0.78 Auckland 2443.73 4.62 2.71 2443.73 0.07 2.69 Hawaii 12469.67 56.19 166.58 12469.67 1.81 160.73 Hong Kong 18898.82 293.87 366.07 18898.82 6.35 370.36 Singapore 52753.51 11442.20 2902.35 52753.51 29.79 2900.78 Vancouver 70732.40 86492.48 12908.62 70732.40 103.67 13001.34Table 7
Results ofη-De on real datasets.
City Re-Plan η-De Utility Time(s) Memory(MB) Utility Time(s) Memory(MB) Beijing 215.77 0.77 0.78 208.78 0.01 0.78 Auckland 2394.26 3.65 2.89 2244.57 0.08 2.75 Hawaii 12489.57 60.78 170.86 12604.53 2.35 177.75 Hong Kong 18796.87 301.78 359.17 18702.48 7.56 388.47 Singapore 52766.12 11304.18 2801.87 52689.48 26.88 2857.44 Vancouver 70655.31 86677.14 12944.63 70689.14 99.57 12903.78Table 8
Results ofts-te on real datasets.
City Re-Plan t s - t e Utility Time(s) Memory(MB) Utility Time(s) Memory(MB) Beijing 221.07 0.97 0.78 211.77 0.01 0.79 Auckland 2507.47 5.21 2.67 2487.45 0.08 3.04 Hawaii 11847.70 55.78 150.43 12078.8 2.02 184.48 Hong Kong 19752.41 321.47 397.15 19987.56 7.59 394.51 Singapore 52078.86 11648.67 2784.45 51978.07 33.48 2875.43 Vancouver 71097.98 87124.35 13478.74 70988.46 112.78 13998.47Table 9
Results ofMul on real datasets.
City Re-Plan M u l Utility Time(s) Memory(MB) Utility Time(s) Memory(MB) Beijing 202.17 1.21 0.81 198.45 0.01 0.78 Auckland 2378.47 5.14 2.07 2245.87 0.07 2.88 Hawaii 11987.78 60.74 152.78 11624.47 1.75 187.57 Hong Kong 18048.14 318.45 401.65 17956.24 5.33 407.98 Singapore 52417.64 11620.78 2788.79 52745.78 38.78 2998.47 Vancouver 70574.78 87144.54 13407.55 70741.34 121.52 14002.46


### 4.3. Results on Synthetic Datasets

In this section, we test the scalability of the proposed algorithms on synthetic datasets. We first setU as 5000 and change E from 200 to 5000. Then, we set E as 1000 and change U from 200 to 5000.The results of efficiency are shown in Figure3. The total utility increases as the data size increases. The total utility of B-De is still as same as Re-Plan as shown in Figures 3(a) and 3(b). η-De is better than Re-Plan as E increases. ts-te and Mul are better than Re-Plan as U and E increase.Figure 3
Efficiency on synthetic datasets.
(a)
Total utility versusE (b)
Total utility versus|U| (c)
Total utility versus|E| (d)
Total utility versus|U| (e)
Total utility versus|E| (f)
Total utility versus|U| (g)
Total utility versus|E| (h)
Total utility versus|U|The results of effectiveness are show in Figure4. Both the running time and memory cost increase as |E| and |U| increase. ts-te and Mul cost more time than the others, the reason is that the plans adjusted in the two algorithms are more than the others. B-De runs faster than η-De when |E| increases but runs the slowest when |U| increases. The reason is that B-De needs to enumerate users while adjusting plans of events; the increasing of |U| affects the running time. To the contrary, η-De needs to enumerate events while adjusting plans of users; the running time increases faster as |E| increases.Figure 4
Effectiveness on synthetic datasets.
(a)
Running time versusE (b)
Running time versusU (c)
Memory cost versusE (d)
Memory cost versusU


## 4.1. Experiment Environment and Dataset

We conduct our algorithms over a real-life dataset, the Meetup dataset [1], which is a popular event based social network. The dataset records the locations of users and the tags that indicate the interesting points of the users. It also records the locations of events where they are held. The events are held by interesting groups; therefore, the tags of events are the tags of whom hold them. The utility scores are calculated as the method in [1]. We extract six datasets of different cities according to the longitude and latitude and generate other parameters, summarized in Table 4. We also use a synthetic dataset to test the scalability of our algorithms, shown in Table 5.Table 4
Real datasets.
City U E Mean ofη Conflict ratio Beijing 113 16 50 0.25 Auckland 569 37 50 0.25 Hawaii 2967 817 50 0.25 Hong Kong 3528 1324 50 0.25 Singapore 9893 4257 50 0.25 Vancouver 16095 11536 50 0.25Table 5
Synthetic datasets.
Value | U | 200, 500, 1000,5000 | E | 200, 500,1000, 5000The algorithms are implemented in Visual C++ 2017, and the experiments are conducted in a Windows 10 machine with Intel(R) Core(TM) i5-6500 3.20GHz CPU and 16GB main memory. When the changes come, we treat all the events as new added and get a global plan as the contrast experiment, named Re-Plan. In each experiment, we repeat 10 times and report the average results.


## 4.2. Results on Real Dataset

In this section, we test the performance of our algorithms, denoted asB-De, η-De, ts-te, and Mul, on Meetup datasets. For each algorithm, we randomly select several users to decrease their travel budget and several events to decrease their upper bound of participations one by one. For the multiple case, we randomly select some users and events of the three kinds of changes.The experiment results are shown in Tables6–9. The utility scores of B-De are the same as Re-Plan. The reason is that B-De conducts the same algorithm to update the plans of events as Re-Plan. In other cases, the algorithms are similar with Re-Plan. η-De is better than Re-Plan on Hawaii and Vancouver, ts-te is better on Hawaii and Hong Kong, and Mul is better on Singapore and Vancouver. In IBPSP problem, the stable plan is not unique; we can find different stable plans through different algorithms. Though the utility scores are not the same, the plans are still stable. In all the algorithms, the running time is much smaller than the Re-Plan; the reason is that the incremental algorithms only adjust the plans of users and events that are affected by the changes, but the Re-Plan makes plans for all the users and events over again. The running time increases as the data size increases. The incremental algorithms cost the similar memory as Re-Plan due to the fact that they all need memory to store the preference and the final plans. Mul costs a bit more memory than others due to size of Uac and Eac is larger than others.Table 6
Results ofB-De on real datasets.
City Re-Plan B-De Utility Time(s) Memory(MB) Utility Time(s) Memory(MB) Beijing 218.94 0.81 0.78 218.94 0.01 0.78 Auckland 2443.73 4.62 2.71 2443.73 0.07 2.69 Hawaii 12469.67 56.19 166.58 12469.67 1.81 160.73 Hong Kong 18898.82 293.87 366.07 18898.82 6.35 370.36 Singapore 52753.51 11442.20 2902.35 52753.51 29.79 2900.78 Vancouver 70732.40 86492.48 12908.62 70732.40 103.67 13001.34Table 7
Results ofη-De on real datasets.
City Re-Plan η-De Utility Time(s) Memory(MB) Utility Time(s) Memory(MB) Beijing 215.77 0.77 0.78 208.78 0.01 0.78 Auckland 2394.26 3.65 2.89 2244.57 0.08 2.75 Hawaii 12489.57 60.78 170.86 12604.53 2.35 177.75 Hong Kong 18796.87 301.78 359.17 18702.48 7.56 388.47 Singapore 52766.12 11304.18 2801.87 52689.48 26.88 2857.44 Vancouver 70655.31 86677.14 12944.63 70689.14 99.57 12903.78Table 8
Results ofts-te on real datasets.
City Re-Plan t s - t e Utility Time(s) Memory(MB) Utility Time(s) Memory(MB) Beijing 221.07 0.97 0.78 211.77 0.01 0.79 Auckland 2507.47 5.21 2.67 2487.45 0.08 3.04 Hawaii 11847.70 55.78 150.43 12078.8 2.02 184.48 Hong Kong 19752.41 321.47 397.15 19987.56 7.59 394.51 Singapore 52078.86 11648.67 2784.45 51978.07 33.48 2875.43 Vancouver 71097.98 87124.35 13478.74 70988.46 112.78 13998.47Table 9
Results ofMul on real datasets.
City Re-Plan M u l Utility Time(s) Memory(MB) Utility Time(s) Memory(MB) Beijing 202.17 1.21 0.81 198.45 0.01 0.78 Auckland 2378.47 5.14 2.07 2245.87 0.07 2.88 Hawaii 11987.78 60.74 152.78 11624.47 1.75 187.57 Hong Kong 18048.14 318.45 401.65 17956.24 5.33 407.98 Singapore 52417.64 11620.78 2788.79 52745.78 38.78 2998.47 Vancouver 70574.78 87144.54 13407.55 70741.34 121.52 14002.46


## 4.3. Results on Synthetic Datasets

In this section, we test the scalability of the proposed algorithms on synthetic datasets. We first setU as 5000 and change E from 200 to 5000. Then, we set E as 1000 and change U from 200 to 5000.The results of efficiency are shown in Figure3. The total utility increases as the data size increases. The total utility of B-De is still as same as Re-Plan as shown in Figures 3(a) and 3(b). η-De is better than Re-Plan as E increases. ts-te and Mul are better than Re-Plan as U and E increase.Figure 3
Efficiency on synthetic datasets.
(a)
Total utility versusE (b)
Total utility versus|U| (c)
Total utility versus|E| (d)
Total utility versus|U| (e)
Total utility versus|E| (f)
Total utility versus|U| (g)
Total utility versus|E| (h)
Total utility versus|U|The results of effectiveness are show in Figure4. Both the running time and memory cost increase as |E| and |U| increase. ts-te and Mul cost more time than the others, the reason is that the plans adjusted in the two algorithms are more than the others. B-De runs faster than η-De when |E| increases but runs the slowest when |U| increases. The reason is that B-De needs to enumerate users while adjusting plans of events; the increasing of |U| affects the running time. To the contrary, η-De needs to enumerate events while adjusting plans of users; the running time increases faster as |E| increases.Figure 4
Effectiveness on synthetic datasets.
(a)
Running time versusE (b)
Running time versusU (c)
Memory cost versusE (d)
Memory cost versusU


## 5. Related Work

In this section, we review related works from two categories, event based social networks (EBSNs) and stable matching problem.Studies on EBSNs. By analyzing Meetup and Plancust, X. Liu et al. [1] firstly proposed the concept of EBSN and received more and more attention [8–17]. On the event recommendation problem, Zhang et al. [9] predicted whether a user will participate in some events by learning the historical events that the user participated in. Cao et al. [18] scored users based on location information, attributes, and relations and built a Bayesian model to recommend events. Wang et al. [19] proposed a context-enhanced method to recommend events to users. However, the method relies too much on social information and geographical information; the lack and inaccuracy of data will seriously affect the accuracy. On the event organization problem, Shen et al. [3, 4] considered the conflict between events and made arrangements for users that avoid conflicts. Authors of [6] took into account the users’ travel budget and extended the problem from simply matching the users with events to scheduling reasonable travels for users to participate in events. Cheng et al. [2] further considered the lower bound of the number of participants in the events and the issue of dynamic planning. The existing works only considered the preference of users, none of them studied on the bilateral preference stable planning problem. The authors of [20] studied a kind of stable matching problem over EBSNs; however, our work studies an incremental problem which is different from it.Studies on Stable Matching Problem. The stable marriage (SM) problem was first proposed by Gale and Shapley [21] in 1962. Suppose a set of man and a set of woman with the same size; a stable marriage for these men and women is that everyone is matched with a partner and there are no such two couples that the man and the woman prefer each other than his/her partner. Reference [22] proved that the stable marriage always exists. There are some extensions of stable marriage problem, SM with incomplete preference lists, SM with preference lists with ties, and SM with incomplete preference lists with ties. In SM with incomplete preference lists, each person’s preference list may be incomplete. Authors of [23] partitioned the set of men (women) into two sets: one is the set of men (women) who have partners in all stable matching, and the other is the set of men (women) who are single in all stable matching. In SM with preference lists with ties, one can include two or more persons with the same preference in a tie. Authors of [24] found a weakly stable matching in polynomial time. The last extension allows both incompleteness and ties in preference list. There series of approximation algorithm [25–28] and the approximation ratio reached 1.8 in [28]. The definition of stable matching problem is different from ours and the attributes are not changed dynamically; the existing studies cannot be applied.


## 6. Conclusions

In this paper, we define the Incremental Bilateral Preference Stable Planning (IBPSP) problem, which dynamically make plans for all the users to participate in suitable events. In this problem, we consider the upper bound of participants, event time conflicts, and the travel budget of users and dynamically update the plans when the constraints change. We propose several algorithms to update the plans when the changes come. We verify the effectiveness, efficiency, and scalability of the proposed methods through extensive experiments on both read and synthetic datasets.



---

*Source: 1532013-2019-04-16.xml*