Science, Faculty of
Computer Science, Department of
DSpace
UBCV
Li, Keqian
Master of Science - MSc
University of British Columbia
Online platforms, such as Meetup and Plancast, have recently become popular for planning gatherings and event organization. However, there is a surprising lack of studies on how to effectively and efficiently organize social events for a large group of people through those platforms. This thesis provides the first systematic study on key computational problem involved in organization of social events. We understand the Social Event Organization problem as assigning a set of events for a group of users to attend, where the users are socially connected with each other and have innate levels of interest in those events. We then introduce a set of formal definition of a restricted version of the problem and show that it is NP-hard and is hard to approximate. We propose efficient heuristic algorithms that improve upon simple greedy algorithms by incorporating the notion of phantom events and by using look-ahead estimation. Using synthetic datasets and three real datasets including those from the platforms Meetup and Plancast, we experimentally demonstrate that our greedy heuristics are scalable and furthermore outperform the baseline algorithms significantly in terms of achieving superior social welfare.
On Social Event OrganizationbyKeqian LiB. Science, Tsinghua University, 2013A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of ScienceinFACULTY OF GRADUATE AND POSTDOCTORAL STUDIES(Computer Science)The University of British Columbia(Vancouver)April 2016c© Keqian Li, 2016AbstractOnline platforms, such as Meetup and Plancast, have recently become popular forplanning gatherings and event organization. However, there is a surprising lackof studies on how to effectively and efficiently organize social events for a largegroup of people through those platforms. This thesis provides the first systematicstudy on key computational problem involved in organization of social events. Weunderstand the Social Event Organization problem as assigning a set of events fora group of users to attend, where the users are socially connected with each otherand have innate levels of interest in those events. We then introduce a set of formaldefinition of a restricted version of the problem and show that it is NP-hard and ishard to approximate. We propose efficient heuristic algorithms that improve uponsimple greedy algorithms by incorporating the notion of phantom events and by us-ing look-ahead estimation. Using synthetic datasets and three real datasets includ-ing those from the platforms Meetup and Plancast, we experimentally demonstratethat our greedy heuristics are scalable and furthermore outperform the baselinealgorithms significantly in terms of achieving superior social welfare.iiPrefaceThis dissertation is the result of collaborative research based on a publication [17]in the 2014 KDD Conference, a joint work with Prof. Lakshmanan, Dr. Wei Lu,Dr. Smriti Bhagat, Prof. Cong Yu. I developed the theory and conducted theexperiments under their guidance, with the help from them for paper presentationand introducing the problem as constrained optimization problem.iiiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 Social event organization . . . . . . . . . . . . . . . . . . . . . . . . 103.1 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . . 103.2 Hardness results . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 Proposed solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164.1 Baselines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174.2 Greedy with look ahead estimation . . . . . . . . . . . . . . . . . 215 Experimental analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 265.1 Experiments on synthetic datasets . . . . . . . . . . . . . . . . . 275.2 Experiments on real event datasets . . . . . . . . . . . . . . . . . 30iv6 Conclusions and future work . . . . . . . . . . . . . . . . . . . . . . 33Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37vList of TablesTable 2.1 Innate affinity for Example 3 . . . . . . . . . . . . . . . . . . 7Table 5.1 Running time (in seconds) of PADG and PCADG . . . . . . . 29Table 5.2 Running time (in seconds) of all algorithms with 10K users and100 events . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29viList of FiguresFigure 5.1 Effects of parameter choices on the performance of PADG andPCADG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27Figure 5.2 Distributions of social affinity values . . . . . . . . . . . . . . 28Figure 5.3 Improvement of social welfare yielded by various algorithmsover Random . . . . . . . . . . . . . . . . . . . . . . . . . . 29Figure 5.4 CDF showing regret ratio ρ for different algorithms. . . . . . 30viiAcknowledgmentsThank my advisor Professor Laks V.S. Lakshmanan who supervises my thesis re-search and my collaborator Mr. Wei Lu, Dr. Smriti Baghat, Dr. Cong Yu who gavetremendous helpful suggestions and helped with paper presentation and finally myfamily for their everlasting love and support.viiiChapter 1IntroductionThe problem of organizing social events for a large group of people can resonatewith the academic community: we are all familiar with the “canned” social eventsoffered by conference organizers, which are often a simple list of activities tochoose from and attendance at each event is organically decided by people at theconference based on who they know and how interested they are in the events.More broadly, event organization is one of the most important social activi-ties online, with many companies, established giants and startups alike, such asMeetup1 and Plancast2, offering platforms for their users to plan and organizeevents. The social networks data and the data indicating the interests of the userson these platforms offer a rich setting in which events can be organized effectivelyand efficiently. Existing academic studies on this topic only focuses on specificarea such as event detection through time series analysis (e.g., burst detection). Thegoal of this thesis is to provide a first systematic study on the problem of SocialEvent Organization, provide principled definitions and a platform of algorithmicsolutions for addressing this problem.The tasks of organizing various social events share many common characteris-tics. First, each individual user often has his or her unique preference for the eventsbeing offered, a numerical measure which we call a user’s innate affinity towardsan event. Innate affinities can be stated explicitly. For example, a user can mark his1http://www.meetup.com2http://www.plancast.com1preference for a game of chess as 9 out of 10. Or they can be categorically stated bythe users and computed by the organizer. For example, a user can list outdoor ac-tivities in her profile and the organizer can deduce that she will likely prefer hikingto playing chess. Finally, they can be computed based on the past events that theuser has participated in and enjoyed. Regardless of how innate affinities are com-puted, they are one of the two key ingredients for users’ happiness, for purposes ofsuccessful organization of social events.The other key ingredient is the social connections among users – individualsoften enjoy an activity more if they attend it along with their friends or otherswhom they would like to be around with. This connection is often defined betweena pair of users and we call this pairwise social affinity. Similar to innate affinities,social affinities can be stated explicitly by the users. For example, users on socialnetworks explicitly provide their friendship connections. They can also be deducedbased on users’ interests or past activities. For instance, two users who share lotsof interests and past activities are more likely to enjoy each other’s company. Thus,similar to innate affinity, social affinity is represented by a numerical measure.Importantly, in real world situations, events typically come with natural car-dinality constraints. For example, most sports activities need a certain number ofparticipants: two or four for tennis, two for chess, and two to nine for poker games.We illustrate aforementioned characteristics more concretely through the fol-lowing motivating examples.Example 1 (Convention Social Events). Academic conferences and business con-ventions often provide networking opportunities for attendees by offering socialevents. Planning them involves gathering individuals with similar interests to fa-cilitate interactions as well as ensuring that they have a good time. The currentpractice is to offer these events as a “canned” list of options: e.g., everybody se-lects from a small set of event choices based on their interests, perhaps uses adhoc conversations among friends for coordination. Being able to automatically as-sign people to events from a large list of options, in a centralized manner, basedon users’ interests and friendships will likely lead to people enjoying those eventsmore.Example 1 illustrates the core technical challenge inherent in event organiza-2tion, viz., the assignment problem, where the system has to assign a given setof users to events, with the goal of making users happy. Other examples in thiscategory include organization activities at a reunion party, corporate activity day,community fund raising, or volunteering gatherings. Event organization is by nomeans restricted to conventions, as the next example illustrates.Example 2 (Wide Area Events). In event organization platforms like Plancast andMeetup, users across a wide area register their interests in themes or topics. Users’social information is also available, e.g., their friendships in popular social net-works can be supplied to these platforms. Events are started by end users throughthe specification of the activity, capacity, etc. The platforms use known metadatato make ad hoc recommendations of events to users. As the platforms get utilized,information from past event attendance can be leveraged to estimate user’s interestin future ones. In place of ad hoc recommendations, these platforms can makecentralized assignments for all events planned in a local wide area (e.g., a city), tomaximize the “social welfare” of users.As the first systematic study towards Social Event Organization, we understandthe problem on the assignment procedure illustrated by the two examples above.Specifically, we are given a set of users, who are socially connected and have in-herent interests in the events being offered. We need to assign users to events so asto maximize the “overall happiness” of the users, while respecting the event car-dinality constraints (minimum and maximum). In event organization over a widearea, in addition to cardinality constraints, time and location also play a role. E.g.,user’s proximity to the event’s location may affect the user’s innate affinity for theevent. A similar remark holds for the time at which the event is organized. In orderto allow us to focus on the key technical problem of assignment, we assume thatusers’ proximity to the location of events as well as availability of users for theevents are factored in while determining the innate affinity of a user to an event.Consequently, our focus is squarely on finding good assignments of users to eventsas opposed to scheduling of events.One critical aspect of the solution is to define the overall happiness as a com-bination innate and social affinities. We provide an intuitive definition of socialwelfare, which is the sum of the total innate affinities enjoyed by the users to the3events they are assigned, and the aggregate social affinities enjoyed by pairs ofusers who are assigned to the same event. The exact definition will be providedlater. This focus allows us to cast the Social Event Organization problem as aconstrained discrete optimization problem, for which we can explore algorithmicsolutions.Our event organization problem has close connections with several major bod-ies of work generalized assignment problem (GAP) [8, 9, 15, 25], a family oftwo-sided matching problems including the National Resident Matching Problem(NRMP) [24], and community-search problems [26]. We depart from them bytaking both innate and social affinities into account and solving the event organiza-tion problem under a unified framework. A detailed comparison with these relatedworks appears in Chapter 2.Our event organization problem has close connections with two major bod-ies of work—generalized assignment problem (GAP) and a family of two-sidedmatching problems including the so-called college admission problem and the Na-tional Resident Matching Problem (NRMP) . While a detailed comparison withthis and other related work appears in , we note here that in all these problems so-cial affinity is not a concern. Taking social affinity into account raises a significantcomputational challenge as we shall show.Specifically, we make the following contributions.• We formally define social event organization as a constrained discrete opti-mization problem that asks for an assignment with maximum social welfarewhile respecting cardinality constraints of events (Chapter 3.1).• The problem is shown to be NP-hard. Given this, we analyze its approx-imability: we establish close connections between restricted versions of ourproblem and the SUBSET-SUM problem and DENSE k-SUBGRAPH prob-lem. We exploit these connections to offer strong evidence that the problemis hard to approximate (Chapter 3.2).• We then develop several heuristics including a greedy hill-climbing strat-egy and several improvements. Our improvements are based on a notion of“phantom events” which refer to tentatively scheduled events which have yet4to meet their lower cardinality constraint, and a look-ahead based technique(Chapter 4).• We conduct a comprehensive experimental study on both synthetic and realdata sets from Plancast, Meetup and SIGCOMM 2009. Our results show thatour methods with look ahead estimation far exceed the baseline methods inthe value of social welfare attained. Furthermore, our most sophisticatedalgorithm completes event assignments on a dataset consisting of 100,000users and 500 events in under 17 minutes (Chapter 5).Finally, Chapter 6 concludes the thesis and summarizes interesting directionsfor future work.5Chapter 2Related workOur event organization framework coincides with two traditional research directionon the general problem of assigning elements to a number of sets. One of the majordirection on this area is the generalized assignment problem (GAP) [8, 9, 15, 25],which generalizes knapsack and bin packing problems: there are multiple binswith capacity (maximum size) constraints, multiple objects with a size and a profitfor placing an object in a bin; the problem is to find an assignment of objects tobins respecting capacity such that the total profit is maximized. In a special case,all objects have the same size and capacity is replaced by (maximum) cardinal-ity. There are two major differences between GAP and event organization. Firstly,events typically also have lower bound constraints on their cardinality. For exam-ple, a game of Mahjong cannot be played by fewer than four people. Those lowerand upper cardinality constraints must be respected by the solutions we propose.Very recently, lower bound constraints have been studied in the context of GAP[15], and the precise relationship between event organization and GAP with lowerbound constraints will be made clear in Section 3.2. Secondly, social affinity isnot considered in GAP, whereas it is one of the key ingredients in social eventorganization.The other major research direction on the assignment problem is the NationalResident Matching Problem (NRMP) and the related two-sided matching prob-lems such as college admissions [6, 10, 11, 24], where medical school graduatesare matched with medical residency programs offered by hospitals throughout the6Tennis MovieAlice 1 5Bob 5.01 2.01Charlie 5.02 1.02Denny 5.03 1.03Eddie 3.01 3Table 2.1: Innate affinity for Example 3United States, and subsequently adopted by other countries. The differences withevent organization are three-fold. First, graduates choose residency programs as in-dividuals, and social affinity is almost never a concern, except in rare cases wheretwo graduates are a couple. Second, in NRMP, every graduate provides a rank or-der list of programs she’d like to join and and every program has its own preferencelist over graduates. Stability is an important concern. A matching is stable if thereis not a pair of a graduate and a resident program such that they both prefer eachother over the resident program or graduate they are currently assigned to. Such apair is called a blocking pair. When stable matchings exist, they focus on finding anoptimal stable matching where no graduate is worse off than she would be in anyother stable matching. When stable matchings don’t exist as in [6, 11], they focuson finding matchings that minimize the number of blocking pairs. While stabilityis similar in spirit to avoiding regrets (i.e., assigning a user to an event she doesnot enjoy) in event organization, the notion of “stability” in event organization isnot important as events treat all users alike! Third, in contrast to the objectivesin NRMP and college admissions, our goal is to maximize the social welfare (de-fined in Section 3.1) of the assignment, taking both innate and social affinities intoaccount, while respecting the cardinality constraints of events.We use a concrete example to illustrate the difference between the our socialevent organization (SEO) problem, the GAP problem and the NRMP problem.Example 3 (SEO, GAP and NRMP). Imagine a scenario of 5 people decidingbetween 2 events, where the innate affinity between each person and each eventsare shown in Table 2.1, and each event, happens to have the lower bound capacityconstraint of 2 and upper bound capacity constraint of 3, the social affinity betweeneach pair of persons are 0 except good friends Alice and Bob, who have an affin-7ity value of 10. The SEO, GAP and NRMP treats this scenario in distinct ways.Starting with the simple one, the GAP would only consider the innate affinity andcapacity constraint, assigning Alice and Eddie to Movie and the others to Tennis.The NRMP is also ignorant to social affinity between Alice and Bob, creating a as-signment the same as above. The above scenario is ”stable” in the sense that Movieevent would prefer to leave the 3 spots to Bob, Charlie, Denny since they enjoy itmore than the other two, leaving Alice and Eddie to the Tennis event, would hap-pens to prefer them over the rest 3. Finally, the SEO problem, taking account intoboth the innate affinity and the social affinity between Alice and Bob, would gen-erate an ideal assignment where Alice and Bob happily stay togther for Movie, andthe rest three go the Tennis, which they would also enjoy very much, achieving anoptima in a globale sense.In Section 4, we adapt the NRMP solution to solve our problem, and empiri-cally compare it in Section 5.Beyond the traditional research In a sense, event organization can be seen asbeing akin to group recommendations: so long as we know which set of userswill attend the same event, i.e., group memberships, but not which one, we can, inprinciple, determine that event using group recommendations [2]. However, we donot know these groups and part of the challenge is to determine them. Besides, ourassignment of users (and hence of groups) to events is more “holistic” in taking notjust innate affinity, but also social affinity into account. It is their combination thatdrives our assignment. Thus, group recommendations cannot handle our problem.In team formation in social networks [3, 16], they assume that for each user aset of skills is available and additionally, a measure of compatibility between pairsof users is also known. The problem is to put together teams that satisfy the skillrequirements of a given task while minimizing the communication overhead ofthe team, e.g., the diameter or weight of the minimum spanning tree of the graphof the formed team. Variants of the problem include ones where different costmodels are used and ones where the tasks arrive online and the team formationhas to keep the workload of users balanced. The problem is NP-hard and manyof the works resort to approximation algorithms. Superficially, the team formationproblem seems similar to ours. However, while social affinity has a counterpart8in compatibility, there is no direct innate affinity between users and tasks, exceptindirectly via skills. Furthermore, and more important, cardinality constraints inevent organization make the problem significantly more challenging. Finally, auser may be assigned to more than one task whereas users are assigned to at mostone event in our problem.Also relevant to our work is the community search problem [26], where given aset of query nodes, the task is to find a community containing the query nodes thatmaximizes the overall social affinity, subject to a maximum cardinality constraint.However, there is no notion of events, nor users innate affinities towards events in[26]. In contrast, our problem involves a combination of social and innate affinitiesand thus a holistic approach is needed which at once pays attention to the innateaspect (matching quality) and the social aspect. There have also been studies ongeo-social query processing [4]. Though both our problem and theirs considersocial effects, the SEO problem is inherently an assignment problem and cannot besolved by issuing queries.Yet another related research direction is social graph partition and more for-mally ”Uniform Metric Labeling”[5, 14], which is an optimization problem thatassigns group labels to nodes in the graph to minimize, incorporating both the”innate affinity”, the cost of assigning specific labels to nodes, and the ”socialaffinity”, the cost of assigning friends to different groups. Similarly to the teamformation problem, social graph partition does not consider cardinality constraintsin event organization, which is one of central element of hardness results and algo-rithm design.9Chapter 3Social event organizationIn this chapter, we formulate the assignment variant of the Social Event Organiza-tion problem, the focus of our research, and study its hardness and approximation.3.1 Problem definitionConsider a setting where organizers of a large gathering (e.g., an international con-ference or a company-wide retreat) are planning social activities for the conferenceattendees. Or a scenario in which or an event planning platform (e.g., Meetup) isbeing used to plan social events for its users over a wide local area such as a city.In both cases, there is a set of users U who must be assigned to events or activitiesfrom a given set of possible events A. We assume the presence of a social network,through which the friendships among those users can be obtained. Let G = (U,E)be the friendship graph induced on U . Each event a ∈ A is associated with a min-imum cardinality bound γa and a maximum cardinality bound δa, as motivated inSection 1.There is a function σ : U ×A→ R+ such that for each user u and event a,σ(u,a) models the user’s innate affinity for the event. We often denote σ(u,a) asσu,a for simplicity. As mentioned in the introduction, we assume that the innateaffinity σu,a factors in u’s proximity to a’s location and u’s availability w.r.t. thetime at which a is held. In addition to their innate affinity to events, users have pair-wise social affinity with each other, and we capture this by a function w : U×U →R+, such that w(u,v) is the social affinity between u and v. Both innate affinity10to events and social affinity to other users attending the same event contribute to auser’s sense of “utility” for attending an event. Note that as discussed in Section 1,social affinity is important because an individual may enjoy an event more whenshe is joined by her friends. We assume in this paper that social affinity is non-negative and that social affinity values are symmetric, i.e., w(u,v) = w(v,u), for allu,v ∈U .Suppose a set of users S⊂U is assigned to an event a∈ A. We define the utilityof this assignment as:µ(S,a) = ∑u∈Sσu,a+ ∑u,v∈S,u6=vw(u,v). (3.1)That is, the overall utility of the set of participants of an event is the sum of thetotal innate affinity of the participants for the event and the total social affinity ofall pairs of participants. As a special case, we define µ( /0,a) = 0: when nobody isassigned to an event, it results in zero utility. As mentioned in the introduction, bothinnate affinity σu,a and social affinity w(u,v) can be provided by the users explicitlythrough stated interests and friendships. However, in case such explicit informationis not available, those values can be estimated from a user’s implicit interests andpast activities. For example, social affinity can be computed using well-studiedsocial distance measures (e.g., graph distance, Katz, or hitting time) [18]. We deferthe details to Section 5.An assignment is a (possibly partial) function M : U → A. For a ∈ A, we de-note by M−1(a) the (possibly empty) subset of users assigned to a, i.e., M−1(a) ={u ∈ U | M(u) = a}. An assignment M is said to be feasible provided all car-dinality constraints are satisfied, i.e., ∀a ∈ A for which M−1(a) 6= /0, we haveγa ≤ |M−1(a)| ≤ δa, in words, for all events to which at least one user is assigned,the number of users assigned to that event lies within its lower and upper bounds.Notice that owing to the cardinality constraints and the number of users and eventsin an instance of the assignment problem, it may not be possible to find a feasibleassignment that covers all users: e.g., we may have 10 users and 1 event such thatthe event can accommodate at most 5 people. This is the reason we allow partialfunctions above. Similarly, not all events may be scheduled by an assignment, i.e.,M need not be onto. We define the social welfare of a feasible assignment M as11ω(M) = ∑a∈Aµ(M−1(a),a). (3.2)The overall social welfare of an assignment is thus determined by the sum ofutilities of the assignments made to each event. Our objective is to find a feasibleassignment that maximizes the overall social welfare. Our definition of overall so-cial welfare reflects the following intuition. A user’s personal utility for an assign-ment increases with her innate affinity for the event, as well as the social affinityshe has toward other users attending the same event. Besides, the more such fellowattendees, the higher her utility. The definition of overall social welfare is a simpleextension of this intuition. Note that other definitions of social welfare, using otheraggregate functions, are possible: we prefer to use a simple definition here thatcaptures the intuition above. We formally define the Social Event Organization(SEO) problem as follows.Problem 1 (Social Event Organization (SEO)). Given a set U of users and theinduced social graph G=(U,E), a set A of events where each a∈A has a minimumand maximum cardinality bound, denoted γa ∈ N and δa ∈ N respectively (γa ≤δa), innnate affinity function σ(·, ·), and social affinity function w(·, ·), produce afeasible assignment of M : U → A that has the maximum overall social welfareω(M), i.e., findM∗ = arg max{ω(M) |M is feasible}.The number of scheduled events (i.e., those have at least one user assigned andcardinality constraints satisfied) is not fixed in advance, but rather determined bythe solution, in which some events may receive zero users. However, the cardi-nality constraints for each event that has non-zero participants assigned must berespected. It is possible to have multiple groups performing the same event, e.g.,there may be four groups of two participants each that are suggested the event ofplaying chess. This is easily handled by technically treating different instances ofa given event as different events. We can consider weighting the two termsin Eq. 3.1, corresponding to the innate and social contributions to social welfare,differently. Our results in the next section show that the problem remains hard12regardless of the weights chosen.3.2 Hardness resultsNot surprisingly, our first result is that Social Event Organization is NP-hard. Ourreduction is from the recently studied Seminar Assignment Problem (SAP). SAP isobtained by adding lower bound constraints to a restricted version of GAP whereall objects have the same size, and is formally stated as follows. Given a set of nstudents and and a set of m seminars with maximum cardinality B1,B2, . . . ,Bm ∈Nand minimum cardinality q1,q2, . . . ,qm ∈ N, qi ≤ Bi, a profit pi, j ∈ N by assigningstudent i to seminar j, we want to find an assignment of students to seminars thatsatisfies the cardinality constraints and maximizes the total profit. Krumke andThielen [15] recently showed that this problem is NP-hard. We have the followingeasy result:Theorem 1. The decision version of Social Event Organization is NP-complete.Proof. Clearly, SAP is isomorphic to a restricted version of SEO where all innateaffinities are natural numbers and all social affinities are zero. The NP-hardnessof SEO follows from this. Membership in NP is straightforward: given an assign-ment, both checking its feasibility and whether its social welfare exceeds a giventhreshold can be done in polynomial time.Next, we analyze how hard it is to approximate SEO. Our analysis involves twospecial cases of the problem, one with only innate affinities (which is isomorphicto the SAP problem) and the other with only social affinity.Special Case 1: Innate Utility Only. In this case, we only consider probleminstances of which w(u,v) = 0, for all users u and v. Thus, the problem is to find afeasible assignment M : U → A that maximizes the social welfare, which is solelydetermined by innate affinities. We call this restricted version SEO-Innate.Theorem 2. It is NP-hard to approximate SEO-Innate within a factor of (1−1/n+ε) (∀ε > 0) in polynomial time, where n is the number of users.Proof. We prove the result by showing that if such an algorithm existed, it couldsolve the SUBSET-SUM problem, an NP-complete problem, in polynomial time.13Since this is impossible unless P = NP, the theorem follows. Consider an arbitraryinstanceI of SUBSET-SUM consisting of a set of integers T = {t1, t2, . . . , tN} anda target number τ . We must find out if there is a subset of T whose elements sumto exactly τ . AlgorithmB first creates an instanceJ of the SEO problem with τusers and N events, and for each event a∈ [1,N], it sets γa = δa := ta. Also, σu,a = 1for all u ∈U,a ∈ A and w(u,v) = 0 for all u,v ∈U . Then B runs A on J , andoutputs YES (indicating there is a subset of T summing to exactly τ) if and only ifA outputs an assignment with social welfare τ . We next prove that algorithm Bcan correctly distinguish between the YES- and NO-instances of SUBSET-SUM.If I is a YES-instance, then by the above reduction, OPTJ = τ , i.e., themaximum possible social welfare of any feasible assingment on instance J is τ .By assumption, A will output an assignment with welfare ≥ (1− 1/τ + ε)τ >τ−1. Since all utility values are 1, the output of A will be exactly τ , and thusBanswers correctly: YES.If I is a NO-instance, then for J , by construction, not all users can be fitinto an event, implying OPTJ < τ . Since the output of A is always ≤ OPTJ ,it will be surely < τ . Again, algorithm B answers correctly: NO. This was to beshown.We note that complementarily, Krumke and Thielen [15] show that it is NP-hard to approximate SAP within a factor of 1− ε0/3 even when all profits arein {0,1}, where ε0 > 0 is a constant associated with the hardness gap of the 3-Bounded 3-Dimensional Matching problem [21]. As a consequence, they showthat SAP does not admit PTAS (polynomial time approximation scheme). Thishardness is clearly inherited by SEO-Innate as well. Note that both 1− ε0/3 and(1−1/n) are close to 1 (the latter when n is large). This raises the question whethercoarser approximations exist for SEO. Our result in the next section suggests it isunlikely.Special Case 2: Pair-wise Affinity Only. In this case, we restrict attention toinstances of SEO where σu,a = 0 for all users and all events. We refer to thisrestricted version of SEO as SEO-Social. We show that this restricted problem ishard to approximate within any constant factor under hardness assumptions aboutcertain combinatorial problems. Specifically, our result is achieved by a reduction14from the DENSE k-SUBGRAPH problem. That problem, given a graph G= (V,E)and a parameter k, asks to find a subgraph G′ of G induced by k nodes such thataverage degree of nodes in G′ is maximum. The average degree of a node in G′ =(V ′,E ′) is given by 2|E ′|/|V ′|. By assuming the hardness of a conjecture knownas Unique Games with Small Set Expansion Conjecture [13], Raghavendra andStreurer [23] show that DENSE k-SUBGRAPH is hard to approximate within anyconstant factor. We “lift” this to show a similar hardness of approximation of SEO-Social. For lack of space, we refer the reader to [23] for details and history of thisconjecture.Theorem 3. Assuming the Unique Games with Small Set Expansion Conjecture,it is NP-hard to approximate SEO-Social within any constant factor in polynomialtime.Proof. Given an instanceI of DENSE k-SUBGRAPH defined by G = (V,E) anda positive integer k, create an SEO instance J by setting A = {a}, γa = δa = k,and U = V . That is, there is just one event whose lower and upper bound oncardinality is k and there is a user corresponding to each node of G. For all u ∈U ,set σu,a = 0, and for all u,v∈U , w(u,v)= 1. By construction, OPTI =OPTJ , thatis, the maximum social welfare of a feasible assignment on instanceJ is identicalto the maximum average degree of a k-vertex induced subgraph of G in instanceI . Suppose there is a polynomial-time algorithm A approximating SEO within afactor of c ∈ (0,1). Then, B can approximate DENSE k-SUBGRAPH within thesame factor by converting I to J as above, running A on J , and outputtingthe nodes corresponding to the users chosen by A to attend event a. This is notpossible unless the Unique Games with Small Set Expansion Conjecture does nothold.To conclude this section, not only is SEO NP-complete, it is also made up oftwo hard subproblems. Our results show that it is unlikely to be approximablewithin any constant factor in polynomial time, unless some hardness assumptionsabout important combinatorial problems break down. By Theorems 2 and 3, thisstatement is obvious regardless of the weights chosen for the two terms in Eq. 3.1.15Chapter 4Proposed solutionsGiven that SEO is NP-hard to even approximate, we propose a variety of heuristicsthat give emphasis to different aspects of the problem, such as the social affinity,the innate affinity, and the cardinality constraints. Before diving into the details ofthe algorithms, it is important to first understand what constitutes a feasible (valid)solution to the SEO problem.Characterizing Feasible Solutions. For any event, if the event has reached itsminimum cardinality, we refer to it as a real event; otherwise, we call it a phan-tom event. For example, a tennis or chess game with only one player is a phantomevent, that will become real only after one other person is assigned to the event.An event is open and can accept more participants if the maximum cardinality hasnot been reached yet, otherwise it is declared closed. By definition, all phantomevents are open. However, a real event can be either open or closed. A user u isavailable if u has not been assigned to a real event yet. A user-event assignmentis valid if it involves an available user and an open event. During the assignmentprocess, if the event to which a user was assigned becomes real, then the user’s as-signment is fixed, and she is marked unavailable. Consequently, all other previousand future assignments involving that particular user are deemed invalid. Recallthat the final solution must be feasible, i.e., respect cardinality constraints. Asshown in Section 3, in some instances it is not possible to find an assignment forevery user, so the assignment function may be partial. In practice, we can deal withthis by supposing that there are sufficiently many events with large capacity such16as movies or theatrical shows to which users left unassigned by the algorithm maybe assigned.Notice that each assignment decision impacts the utility received from futureassignments, due to the coupling effect with other users in the form of social affin-ity. Therefore, it is non-trivial to achieve a (feasible) solution to SEO that achievesa high social welfare.Solution Template. In the remainder of this chapter we discuss a variety of al-gorithms. At a high level, each algorithm (except Random and NRMP+) followsthe following template. First, a sorted list L of potential assignments of users toevents is generated. The additional contents of the list may vary depending on thealgorithm. This list may be updated and re-ordered several times during a run of thealgorithm. Second, users are assigned to events by making one pass on this list, andthe “state” of users (available, unavailable), and events (phantom, real open, realclosed) is updated appropriately. In particular, it marks an event a as “real” whenit reaches its minimum cardinality γa, and “closed” when it reaches its maximumcardinality δa. These assignments are tentative and are recorded by membership inthe “S” sets, e.g., u ∈ Sa means u is tentatively assigned to event a, and possiblyto other events. All events are “open” and “phantom” to start with. Once an eventa becomes real, the users in the set Sa are marked “unavailable” for future assign-ments and we set M(u) = a,∀u ∈ Sa. Additionally, the algorithm invalidates anyprevious and future assignments of each user u∈M−1(a), by cleaning up other “S”sets as needed. Finally, the algorithm performs post-processing to ensure that theoutput is a feasible solution, i.e., no phantom events are left behind.4.1 BaselinesIn this section, we present a set of intuitive baseline solutions, in increasing levelof sophistication. We build on these baselines and present our proposed algorithmsin Section 4.2.RandomOur first baseline is called Random, which randomly assigns users to events whilerespecting the cardinality constraints. Specifically, the algorithm first shuffles the17Algorithm 1 Dynamic Greedy (U,A,σ ,w)1: M(u)←⊥,∀u ∈U ; Sa← /0,∀a ∈ A2: for all (u,a) ∈U×A s.t. σu,a > 0 do3: g(u,a | Sa)← σu,a4: L .insert(〈u,a,g(u,a | Sa)〉)5: while 〈u,a,g(u,a | Sa)〉 ←L .pop() do6: if M(u) =⊥ and |Sa|< δa then7: Sa← Sa∪{u}8: if |Sa|> γa then9: M(u)← a10: for all a′ ∈ A s.t. a′ 6= a∧u ∈ Sa′ do11: Sa′ ← Sa′−{u}12: if |Sa|= γa then13: for all v ∈ Sa do14: M(v)← a15: for all a′ ∈ A s.t. a′ 6= a∧ v ∈ Sa′ do16: Sa′ ← Sa′−{v}17: for all v : (w(u,v)> 0∧M(v) =⊥) do18: L .update(〈v,a,g(v,a | Sa)〉) // Using Equation 4.119: Reassign available users {u|M(u) =⊥}20: return Mlist L containing tuples 〈u,a〉 of user-event pairs randomly. It then traverses thelist and at each tuple 〈u,a〉 assigns user u to event a if u is available and a is open. Itappropriately marks an event as real when it reaches its minimum cardinality con-straint. Clearly, this is a “straw man” approach, which does not take into accountthe “utility” of any assignment.NRMP+Given the connection between SEO and NRMP, a natural question is whether wecan leverage algorithms developed for NRMP. We next describe an adaptation ofthe NRMP algorithm [10] for handling the lower bound constraints present in SEO.In this adaptation, called NRMP+, we cast SEO in the NRMP framework by asso-ciating a preference list of events for each user, ordered by the innate affinity, and18a preference list of users for each event, ordered by the innate affinity.1NRMP+ repeats the following procedure until each user is either “accepted”by an event or is “rejected” by all events she applied to. Initially, all users areunassigned and no acceptance or rejection has been made yet. In each round,each unassigned user “applies” to the most preferred event that has not rejectedher. Each event a then picks the δa most preferred users who applied to it, or allapplicants if there are fewer than δa of them, and puts them on a waiting list. Userswho failed to get on the waiting list are rejected and are thus unassigned after thisround. After this iterative process stops, we check if there exists any phantomevent. If yes, redistribute users assigned to phantom events to existing real openevents in a greedy manner, based on innate affinity. After that, either no user is leftunassigned or there are no real events to which unassigned users can be assigned,and we stop.It is unclear how NRMP can be directly adapted to take social affinity intoaccount in deciding acceptances. In Section 5, we empirically compare NRMP+with the more sophisticated baselines we develop next, as well as with our mainalgorithm.Static Pairwise GreedyOur next baseline, called Static Pairwise Greedy (SG), assigns pairs of users toevents, taking into account both innate event and pairwise social affinities. Specifi-cally, a sorted listL containing tuples 〈u,v,a〉 representing potential assignment ofpairs of users to events is generated. The list is ordered by non-increasing potentialgain (of “utility”), defined asg((u,v),a) = σu,a+σv,a+2 ·w(u,v).The list is traversed and at each tuple 〈u,v,a〉 users u and v are assigned to eventa if both users are available, and a is open with at least two spots. User and eventstates are appropriately updated. Finally, any users that are in phantom events atthe end of one pass over the list L are redistributed greedily among remainingopen events. We call this a static approach as the function g is computed only1Events don’t have independent preference lists: we do this for the sake of simulation of NRMP.19once. Therefore, the partial ordering of theL is static, and it only incurs deletions(with some assignments being invalidated). Therefore, the assignment of a pair ofusers to an event is oblivious to which users are already assigned to that event.Dynamic GreedyOur next algorithm, called Dynamic Greedy (DG), is more sophisticated. It updatesits estimation of the “utility” a user will attain from an assignment, based on thecurrent set of assignments. To achieve this, the algorithm updates the list L ateach assignment, whereL is composed of tuples 〈u,a,g(u,a|Sa)〉, Sa = /0 initially,and the potential gain g isg(u,a | Sa) = σu,a+ ∑v∈Saw(u,v). (4.1)Clearly, when no users are assigned to an event a, g(u,a | /0) = σu,a. Algorithm 1presents the pseudocode for the DG method. At each step, the assignment thatgives the largest potential gain g(.) is performed. Let Nu be the set of users v:wu,v > 0. Now, whenever a user u is assigned to an event a, we need to recomputethe potential gain g(v,a | Sa) for all neighbors v∈Nu of user u in the network, sincetheir utility for event a increases after the assignment of u to that event. In practice,the algorithm maintains the list L as a priority queue of tuples in non-increasingorder of g(u,a | Sa). We use the notation M(u) = ⊥ to denote that the user u isavailable. We remark that the update operation (line 18) is in charge of not onlyupdating the existing entries in the priority queue but also checking whether thepair (v,a) is already in the heap and if not, adding it.The post-processing in Line 19 is done in a greedy manner. Let A′ be the setof currently open real events, i.e., A′ = {a | γa ≤ |Sa| < δa} and U ′ be the set ofusers assigned to phantom events. The list L is re-constructed with users fromU ′ and events from A′, and we rerun the DG algorithm over this list. This processcan be repeated as needed. The post-processing stops when either all users areassigned or there are not enough real events (i.e., all real events are closed). In thelatter case, from a practical perspective, the remaining users may be assigned tonew events with a large capacity, e.g., watching a movie or a theatrical show.20Implementation Notes and Time and Space Complexity. We remark that in ourimplementation, we optimize the algorithm for better performance. In particular,we tune our implementation to suit a Fibonacci heap based realization of the pri-ority queue. Specifically, we commit to making an assignment for new users rightafter line 7. This allows us to avoid assigning users to multiple phantom events.Thus, when the priority queue is updated, “decrease key” operation will not beneeded, permitting us to implement the priority queue using a Fibonacci heap. Wenote, however, in this case the assignment function M no longer corresponds toonly real events since some phantom events may be left behind by the algorithm attermination. For ease of exposition, we have chosen to present our algorithm in aconceptually simpler way.When the priority queue L is implemented using a Fibonacci heap, then foreach assignment (u,a), the algorithms performs O(|Nu|) update operations (Line 18),each of which is constant time. Summing over all users, the total running time ofall update operations is O(|E|), where E is the edge set of the social network ofusers, or more precisely the set of pairs (u,v) with wuv > 0. Next, since the numberof all possible (u,a) pairs is bounded by |L |, we need at most that many pop oper-ations, which in total takes O(|L | log(|L |)) time. In addition, insertion is constanttime for Fibonacci heaps so the initialization step takes O(|L |). Hence, the totaltime complexity for Dynamic Greedy is O(|L | log(|L |)+ |E|). Finally, the spacecomplexity is Ω(|L |+ |E|).4.2 Greedy with look ahead estimationThe Dynamic Greedy algorithm is intuitive: it tries to make assignments based onthe largest estimated gain, given the current state of the assignment. However, ithas its limitations: (i) it is oblivious to which events a user’s friends are likely tobe assigned; (ii) the first pass may result in a large number of phantom events as itis ignorant of which events are likely to materialize. To address these limitations,we propose the Phantom- and Community-Aware Dynamic Greedy or PCADG. Akey feature of this algorithm is that it looks ahead at the forthcoming assignmentsto inform the decision at each step.Community Awareness. The earlier algorithms do not take into account the po-21Algorithm 2 Phantom- and Community-Aware Dynamic Greedy (U,A,σ ,w)1: M(u)←⊥,∀u ∈U ; Sa← /0,∀a ∈ A;P ← /02: deficit← 0; V ←U3: for each (u,a) ∈U×A s.t. σu,a > 0 do4: g(u,a | Sa)← σu,a5: L .insert(〈u,a,g(u,a | Sa)〉)6: while 〈u,a,g(u,a | Sa)〉 ←L .pop() do7: if M(u) =⊥ and |Sa|< δa then8: if |Sa|= 0 then9: if deficit+ γa ≤ |V | then10: deficit← deficit+ γa−111: P ←P ∪{a}12: else13: continue14: else15: if a ∈P then16: deficit← deficit−117: Sa← Sa∪{u}18: V ←V \{u}19: if |Sa|> γa then20: M(u)← a21: for all a′ ∈ A s.t. a′ 6= a∧u ∈ Sa′ do22: Sa′ ← Sa′−{u}23: if |Sa|= γa then24: P ←P \{a};25: for all v ∈ Sa do26: M(v)← a27: for all a′ ∈ A s.t. a′ 6= a∧ v ∈ Sa′ do28: Sa′ ← Sa′−{v}29: for all v : (w(u,v)> 0∧M(v) =⊥) do30: L .update(〈v,a,g(v,a | Sa)〉) // Using Equation 4.231: return Mtential gain that future assignments of friends to an event may bring to a user. Inour Phantom- and Community-Aware Dynamic Greedy algorithm, the awarenessof friends’ potential assignments is incorporated into the decision making process.22More specifically, here, the potential gain g is defined asg(u,a|Sa) =σu,a+ ∑v∈Saw(u,v)+(δa−|Sa|)∑v∈Vw(u,v)/(|V |−1). (4.2)Notice that the first two terms in this equation are identical to the two terms inEquation 4.1 of the Dynamic Greedy method. The third term corresponds to the“look-ahead” whereby it is optimistically assumed that the remaining spots in theevent a will be filled with friends of u, with an average social affinity toward u.The average is computed over users who are not assigned to any event yet. Whilethe first two terms are based on the current membership of Sa, the third term isbased on anticipation. Thus, this algorithm gives equal importance to both innateaffinity and social affinity in gauging the potential gain that could come from anassignment. Other variants can be easily designed to weigh the importance of theinnate and social affinities differently.Phantom Awareness. Another observation about Dynamic Greedy is that it tendsto be somewhat indiscriminate in the creation of phantom events: it never restrictsthe creation of new events as the condition |Sa| < δa (line 6 of Algorithm 1) willalways be true for new events, for which |Sa|= 0 by definition. All phantom eventsthat are left behind after a pass over the listL have to be cleaned up later. PCADGtries to limit the creation of phantom events, by employing a stronger conditionfor phantom event creation. Accordingly, it keeps track of phantom events as itproceeds, and procrastinates on creating new events if the number of unassignedusers is less than the currently unfilled spots in existing phantom events that need tobe filled in order for the events to materialize. To this end, the algorithm maintainsa variable called deficit, computed as,deficit= ∑a∈P(γa−|Sa|).where P is the set of phantom events and Sa is the set of users assigned to eventa. In addition, the algorithm maintains the set of users V that have not yet been23assigned to any event, phantom or real. Specifically,V = {u | u ∈U ∧M(u) =⊥∧u 6∈⋃a∈ASa}.The pseudocode for Phantom- and Community-Aware Dynamic Greedy is pre-sented in Algorithm 2. At the beginning of the algorithm, whenP = /0, deficit=0 and V =U . The size of V is non-increasing throughout the algorithm. For anyassignment being considered 〈u,a,g(u,a | Sa)〉 for an available user u and openevent a, if a is a new event with no users, i.e., if |Sa|= 0, deficit is incrementedby γa− 1, else deficit is decremented by 1. Furthermore, u is removed fromV , if u ∈ V before this assignment. Using deficit and V , the algorithm limitsthe creation of new phantom events. If deficit> |V |, there will be at least onephantom event at the end of one pass over L , thus requiring reassignment. Thealgorithm performs an assignment based on a list tuple 〈u,a,g(.)〉 only if it doesnot push deficit over |V | (Line 9). If the condition is not met, it continues tothe next tuple from the listL .It is worth noting that PCADG may consider user-event combinations for whichthe innate affinity may be zero, as this assignment may potentially result in a largegain owing to the social affinity with other users assigned to this event, as per Equa-tion 4.2. This is in keeping with our stated objective of maximizing social welfare.Therefore, it is possible that some users may be assigned to low innate affinityevents as a result. We measure this tradeoff empirically in Section 5 by measuringthe “regret ratio” (defined in Section 5) of the assignment returned by the variousalgorithms.In order to explicitly study the impact of community and phantom awareness,we will compare PCADG with a lesser variant called Phantom-Aware DynamicGreedy (PADG) that only takes into account phantom awareness. As such, thePADG algorithm is identical to Algorithm 2, with the one change that the potentialgain is defined using Equation 4.1 instead of Equation 4.2. In Section 5, we com-pare the running times and scalability of different proposed algorithms, in additionto comparing them on their quality.We close this section by noting that the time and space complexity of thePCADG algorithm is the same as that of DG (and PADG) except that the size24of the list L may potentially become O(|U |× |A|) in the worst case. Also, whileDG may incur multiple iterations owing to redistribution, the two algorithms havethe same worst case time complexity.25Chapter 5Experimental analysisWe evaluate our Phantom- and Community-Aware Dynamic Greedy (PCADG)method against Phantom-Aware variant (PADG) and the baselines described inSection 4.1, i.e., Random, NRMP+, Static Greedy (SG) and Dynamic Greedy(DG).Evaluation Metrics. The most natural evaluation metric is the total social wel-fare, ω(M) defined in Equation (3.2). In addition, since optimal or near-optimalsolution cannot be found in polynomial time, we measure the effectiveness of eachalgorithm “indirectly” by comparing the utility a user gets against a coarse upperbound, which is the maximum utility she could have enjoyed by going to her fa-vorite event with her best friends. Formally, we define the regret ratio for a user u,denoted ρ(u), to beρ(u) = 1−σu,M(u)+∑v∈SM(u) w(u,v)maxa∈A(σu,a+∑v∈Bu w(u,v)) , (5.1)where M is the assignment made by an algorithm, and Bu⊆Nu is the set of top-Ku,afriends of u in terms of social affinity w(u,v), and Ku,a = min{|Nu|,δa−1}.Ideally an algorithm that performs well w.r.t. this metric should assign users toevents in such a way that many users experience low regret in the assignment made.Note that ∑u∈U maxa∈A(σu,a+∑v∈Bu w(u,v))is guaranteed to be greater than theoptimal social welfare, except when the favorite event of all users are the same,in which case the optimal welfare reaches this quantity. Moreover, ρ is a very26pessimistic ratio, as the denominator is an upper bound on the maximum possibleutility that the user can achieve. Also, it is worth pointing out that our algorithmsare not designed to directly minimize individual regrets of users, but rather socialwelfare that is the overall utility enjoyed by all users. The purpose here is to gainsome insights about to what extent our algorithms would lead to a compromisew.r.t. regret.low med high(a) γ0100020003000400050006000Social Welfare (ω)10 25 35(b) #Events02000400060008000100001 0.1 0.01 0.001(c) Graph density01000020000300004000050000DGPADGPCADGFigure 5.1: Effects of parameter choices on the performance of PADG andPCADG5.1 Experiments on synthetic datasetsFirst, to better understand the impact of various parameters on our proposed algo-rithms, we first perform rigorous evaluation on synthetically generated data. Wealso conduct scalability tests on large synthetic data to demonstrate that our algo-rithms are scalable and efficient.For all events a ∈ A, δa is sampled from a normal distribution with mean 20and variance 10, and given that, γa is sampled uniformly at random from the in-terval [1,δa]. The social network G = (U,E) is generated by a random power-lawgraph model with a power-law exponent of 1.5 [1]. The data generated has 500users and 50 events. A user is interested in an event with probability 0.05, and thusthe average number of events he is interested is 2.5. For each (u,v) ∈ E, the socialaffinity value is sampled from a normal distribution with mean 1.5 and variance 3,so are innate utilities σu,a for all (u,a) pairs in the user-event relation. All valuesless than 10−5 are set to be zero, and hence all affinity values are non-negative.This gives the default setting for the parameters used to generate the data, however,throughout this section, we vary these parameters to understand their effect on theperformance of our three dynamic greedy methods, DG, PADG and PCADG. Fig-ure 5.1 shows the social welfare achieved by these algorithms with three types of27comparisons: minimum cardinality constraints, total number of events, and densityof the social network graph.Effect of Minimum Cardinality. The first test is to alter minimum cardinalityconstraint (γ) and evaluate its effect on PADG and PCADG. We keep the maximumcardinality constraint δas unchanged from the basic setting for each event a ∈ A,and vary their γas. We generate three groups of data, by sampling the minimumcardinality constraint γa uniformly at random from [δa/2,δa] (low mean), [δa−δa/4,δa] (medium mean), and [δa−δa/8,δa] (high mean) respectively. As seen inFigure 5.1(a), there is a noticeable improvement in social welfare for PADG andPCADG over DG (which does not account for phantom events). As γ increases,more phantom events may be created, which increases the gain of PADG methodsover DG.Effect of the Number of Events. In the second test, we vary the number of eventsas 10, 25 and 35, for a 500 user dataset. Figure 5.1(b), shows the social welfareof the three dynamic greedy algorithms. As the number of events increases, eachevent needs to accommodate fewer users and thus the effect of social affinity de-creases. Clearly, with fewer events, PCADG is at an advantage over PADG andDG, as it is community aware and takes into account social affinity values by look-ing ahead.Effect of Graph Density. Next, we test various graph densities of the underly-ing social network graph by generating four different graphs using Erdo˝s-Re´nyimodel G(500, p) where the edge existence probability being p = 0.001, 0.01, 0.1,and 1 respectively. For denser graphs, more social affinity values are present andhence we observe that the margin between PCADG and the rest two is higher (Fig-ure 5.1(c)) in comparison with sparse graphs.0.5 1.0 1.5 2.0 2.5 3.0NYC10-1100101102103104105106#Edges0.8 1.6 2.4 3.2SFO10-11001011021031041051060.5 1.0 1.5 2.0 2.5CHI10-11001011021031041050.8 1.6 2.4 3.2SEA10-11001011021031041051.00 1.04 1.08 1.12 1.16SIG10-1100101102Figure 5.2: Distributions of social affinity values28Algorithm |U | Number of Events50 100 150 200 500PADG 1K 0.085 0.085 0.108 0.152 0.18710K 0.343 0.435 0.572 1.54 1.6100K 2.75 4.61 6.63 15.0 27.11K 0.315 0.759 1.46 3.17 9.05PCADG 10K 2.09 10.07 14.47 32.1 77.2100K 22.10 64.50 166 207 1085Table 5.1: Running time (in seconds) of PADG and PCADGRandom NRMP+ SG DG PADG PCADGTime (s) 0.98 0.14 12.7 0.31 0.43 10.1Table 5.2: Running time (in seconds) of all algorithms with 10K users and100 eventsRunning Time. Finally, we evaluate the scalability of the algorithms by varyingthe number of users (1K, 10K and 100K) and events (50, 100, 150, 200, and 500).We maintain the default settings for all other parameters. Table 5.1 shows the run-ning time of PADG and PCADG. Overall, both algorithms achieve good efficiency,finishing within seconds or minutes in all cases, and PADG always runs faster thanPCADG. As the trend is similar, we show the running time comparison with Ran-dom, NRMP+, SG, and DG for one case of 10K users and 100 events. Random,DG, and SG takes 0.98, 0.31, and 12.7 seconds to finish, while PADG takes 0.43and PCADG takes 10.07 seconds respectively (see Table 5.2). SG was consistentlythe slowest algorithm in all cases that we tested. For our largest simulation of 100Kusers and 500 events, PCADG takes 20 mins. This is a reasonable for large scaleevent organization, where real-time response is not critical.NRMP+ SG DG PADGPCADGNYC0481216ω(Malgo)/ω(MRandom)NRMP+ SG DG PADGPCADGSFONRMP+ SG DG PADGPCADGCHINRMP+ SG DG PADGPCADGSEANRMP+ SG DG PADGPCADGSIGFigure 5.3: Improvement of social welfare yielded by various algorithmsover Random290.0 0.2 0.4 0.6 0.8 1.0NYC0.00.20.40.60.81.0CDFPCADGDGRandomNRMP+SG0.0 0.2 0.4 0.6 0.8 1.0SFO0.00.20.40.60.81.00.0 0.2 0.4 0.6 0.8 1.0CHI0.00.20.40.60.81.00.0 0.2 0.4 0.6 0.8 1.0SEA0.00.20.40.60.81.00.2 0.4 0.6 0.8 1.0SIG0.00.20.40.60.81.0Figure 5.4: CDF showing regret ratio ρ for different algorithms.5.2 Experiments on real event datasetsData Description and PreprocessingWe evaluate our algorithms on the following three real datasets. Plancast andMeetup are local event organization websites that allow groups of users to interactand plan events. We make use of the datasets1 released by Liu et al. [19]. Since inPlancast and Meetup users and events are from all over the world, we select severalbig cities and project the data to these specific locations. Our third dataset is SIG-COMM2009 (referred to as SIG), collected by Pietilainen et al. [22] and containsthe bluetooth traces and social profiles (friends and interests) of 76 participants ofa mobile application during the SIGCOMM conference at 2009. The followingpre-processing was performed on the datasets to match our problem setting.Plancast. We extract two subsets from the Plancast dataset in [19] correspondingto users and events in the vicinity of Chicago (CHI) and Seattle (SEA). The twodatasets CHI and SEA have 2338 and 2327 users, and 339 and 360 events, respec-tively. For computing the innate affinity, we set σu,a to 1 for events located within0.01 units of Euclidian distance from the user’s geolocation. Plancast allows usersto subscribe to each other and receive updates on friends’ activities, which gives usa ground-truth social network. We compute the Katz distance [12] from each useron the subscription graph to learn social affinity w(u,v)’s. By definition of Katz,we havew(u,v) :=∞∑`=1α` · |P(`)u,v |,where P(`)u,v is the set of paths of length ` between u and v in the graph, and α is a1http://www.largenetwork.org/ebsn30damping factor so that the measure counts short path more heavily, which is set to0.01 in our case. Higher Katz scores intuitively implies that two nodes are moreconnected, and hence gives a higher social affinity value for our purpose.Meetup. Similarly, we project Meetup data from [19] on events and users locatedin San Francisco and New York City and refer to these datasets as SFO and NYC.SFO contains 6438 users and 59 events, while NYC contains 10328 users and 127events. Meetup allows users to create and participate in groups, which in turn or-ganize events. For both locations, we consider the labeled heterogeneous tripartitegraph between users, groups, and events, with edges labeled by the relation thatconnects the pairs of nodes: e.g., if user u is a member of group g that organizedevent a which the user attended, we draw edges (u,g) and (g,a). We then defineσu,a as the Katz distance between the user node u and event node a in the heteroge-neous graph. where higher Katz score indicating higher affinity. For social affinitybetween users, we utilize tags provided in the data. More specifically, users onMeetup can attach tags in their profiles to indicate preferences and interests. Intu-itively, users share common interests may enjoy being with each other in activitiesthey both like. Thus, for each (u,v) ∈ E, we compute w(u,v) as the Jaccard simi-larity coefficient of u’s tag sets and v’s tag sets:w(u,v) :=|Tu∩Tv||Tu∪Tv| ,where Tu and Tv is are sets of tags of u and v respectively. Note that users withoutany tags in their profile have been filtered out.SIGCOMM2009. This is a small dataset with 76 users, and 11 events, collected bya mobile application that records bluetooth device discovery information. Users’innate utility for events is 1 if a user attends an event as indicated by the data, and0 otherwise. The data includes ground-truth Facebook friendship information, andthus as in the case of Plancast, we take this underlying social network and computethe Katz scores for social affinities.Finally, for all five datasets described above, the user-event innate utility is setto 1 if the user attends the event indicated by the data, and to 0 otherwise. Alsodue to lack of ground-truth data, we generate the maximum and minimum cardi-31nality constraints on the events as in the basic synthetic case, i.e., let r be the ratiobetween the number of users and the number of events, for all a ∈ A, maximumcardinality constraint δa is sampled from a normal distribution with mean 2r andvariance r, while minimum cardinality γa is sampled uniformly at random from[1,δa]. Figure 5.2 shows the distributions of social affinity values for all datasets.Evaluations and AnalysisSocial Welfare. We evaluate the various algorithms on our objective, social wel-fare. Figure 5.3 shows the social welfare (Equation 3.2) obtained by the variousmethods considered relative to the welfare obtained using a Random assignment.Specifically, it shows the ratio between the social welfare yielded by assignmentsmade by NRMP+, SG, DG, PADG, PCADG and that by Random. PCADG consis-tently has the highest social welfare, followed by PCADG, DG, SG and NRMP+.The margin between PCADG and the rest of the algorithms is significant in allcases, indicting its overall effectiveness. The biggest lead of PCADG is observedin NYC, 17 times better than Random, while the smallest happens in SIG, in whichit is still 4 times better. On all datasets PADG and DG have similar welfare values,with PADG outperforming only slightly. This is because the generated minimumcardinality constraints for events are much smaller than maximum cardinality con-straints. Recall from Figure 5.1(a) that when γs are high, the gap between PADGand DG is also high.Regret Ratio. Figure 5.4 shows the cumulative distribution function (CDF) ofthe regret ratio ρ(u) (see Equation 5.1) achieved by the various methods (PADGskipped for clarity) on the five datasets. The general trend is similar to that of socialwelfare, where PCADG outperforms all baselines. For instance, in NYC, 20% ofthe users have a regret below 0.8 using PCADG, while only 8% have that regretwith NRMP+. This gap is even more pronounced in CHI and SEA, with the largestdifference in SIG. In particular, 70% of users have a regret ratio below 0.7 usingPCADG, while only 18% have that regret using NRMP+.In summary, through extensive experiments on both synthetic and real worlddata, we have demonstrated the effectiveness (in terms of social welfare and regret)and efficiency (in terms of running time) of our proposed solution.32Chapter 6Conclusions and future workWhile there has been considerable work on detecting emerging events from socialmedia, the related, equally important area of organizing events has received muchless research attention. This thesis provides a first systematic study towards thenovel research direction of Social Event Organization (SEO), motivated by popu-lar social event organization platforms like Meetup and Plancast and by applica-tions such as organizing events using these platforms over a wide local area, andorganizing events co-located with large conferences and conventions.In this thesis, we understand the organziation as the assignment problem, wherewe consider two critical factors: innate affinity, which captures a user’s intrinsicpreferences for or interests in the events being offered, and social affinity, whichcaptures the social connections among the users themselves. We formally definethe overall measure of social welfare in event organization and formalize the SEOproblem as an optimization problem for the social welfare with constraints on theparticipation cardinality of the events. We show that this problem is not only NP-hard, but also hard to approximate. We propose a set of heuristic solutions thatleverage the notion of phantom events and the technique of looking ahead the pote-nial gain that may accrue as a result of future assignments to the current event forwhich a user is being assigned. Using an extensive set of experiments over syn-thetic datasets and three real datasets including those from the platforms Meetupand Plancast, we demonstrate that our heuristic algorithms are scalable and fur-thermore outperform the baseline algorithms significantly in terms of achieving33superior social welfare.Furthermore, we would like to provide an landscape discussion on some inter-esting future directions to extend our problem formulation.To start with, we could incorporate interdependency between innate and socialaffinities. E.g., Jack and Jill may be close friends but may not like to play pokertogether since they know each other’s tells too well. Jill may like going to an icehockey game in which she normally has low innate affinity, but with Mike whois knowledgeable and keeps her engaged with interesting anecdotes. Handlingsuch interdependent affinities is important. Our framework could be extended bygeneralizing the innate affinity beyond what’s between one individual person andone event, to two or three more person. For the above example, we would havea high innate affinity value between the event of hockey and the pair of Jill andMike. Although strictly more difficult, our phantom community aware dynamicgreedy strategy would still apply in this case, where the community effect is nowconditioned on specific event.Another natural extention is to extend the weight to the negative case. In termsof innate affinity, this refers to the case that a person is ”forced” to go a a event thathe doesn’t want to attend. In terms of social affinity, this would mean the two per-son hate each other so much [7] that they don’t want to appear in the same events.Mathematically, our phantom community aware dynamic greedy strategy wouldstill work as usuall and moreover since these negative weights would seldomly popup in the priority queue, they would naturally be avoided. However, some betterheuristics can be designed towards the specific case. For example, we may needto pay special attention and keep track of these retricted assignments to preventit from happenning during post processing, or alternatively we could follow thescheme in the Gale-Shapley matching [10] for NRMP and redistribute the negativeassignment as an after step.More complex social interaction could be considered in terms of computingthe social affinity. E.g. the Ninja Turtles may want to fight the evil as a groupof Four, missing any of the four would undermine the integrety of the group anddecrease the general social welfare. To handle this, we would not only consider theaffinity based on pair, but also on triplet, quadraplet, etc. Then we would carry onour dynamic greedy strategy and each time, compute the community effect based34on different types of social affinity.On the event side, there are also many factors we can incorporate to empowerour model framework. Various dimensions of an event, e.g. where, when, whattype of event can also be formally studied. We could consider the scenario wherethe events spans across a wide area in a metropolitan region, each can only happenat specific time of day/week, and each person has a set home or office location andcertain busy schedule. Currently our framwork handles these preference in a ”onefits all” scheme and understand all such preference as a numeric value. However tomake the our solution better applies to these realistic situation, certain optimizationstrategy can be employed to accomodate it, e.g. we could preprocess the candidateassignment to filter out geoloigcally or temporally restricted assignments, or wecould employ the divide and conqueuer scheme and compute assignment in geo-logical parallelly.In terms of adding the time dimension to our problem, we could also model”multiple shot” event participation where each person is allowed to attend morethan one event. This is realistic when we consider performing event assignment ononline event organization platform such as Meetup, where the system could suggestyou an schedule of events over a whole month, or the entire year. A straighforwardsolution is to treat the unit assigned to an event as not a person, but a person atspecific time window, which would generates an assignment that will ”remove” theone shot assumption. Based upon this, we could adjust the length and starting pointof the time window to make personalized prediction to based on one’s frequencythe schedule preference.More complex interplay along the time dimension may also be considered,e.g. we could imagine the event assignment as a self adaptive dynamic processto model more general social or actitivity of human being. During the course ofparticipating events, people may learn to change their innate and social affinity, tocooperate and form a group or break up from a group, and act strategically. wemay eventually need to incorporate game theory to model the individual strategicbehavior. For example, we could view the event participation as a repeated game[20] with specific cost or gains for each individual, and we could study how tomake arrangements that is in accordance with nash equilibrium so that everyone issatiefied in both individual level while still taking into account the social welfare35from a global point of view. Although this would extend far beyond our currentmodel framework.36Bibliography[1] W. Aiello, F. Chung, and L. Lu. A random graph model for massive graphs.In Proceedings of the thirty-second annual ACM symposium on Theory ofcomputing, pages 171–180. Acm, 2000. → pages 27[2] S. Amer-Yahia, S. B. Roy, A. Chawla, G. Das, and C. Yu. Grouprecommendation: Semantics and efficiency. PVLDB, 2(1), 2009. → pages 8[3] A. Anagnostopoulos, L. Becchetti, C. Castillo, A. Gionis, and S. Leonardi.Online team formation in social networks. In WWW, 2012. → pages 8[4] N. Armenatzoglou, S. Papadopoulos, and D. Papadias. A general frameworkfor geo-social query processing. Proceedings of the VLDB Endowment, 6(10):913–924, 2013. → pages 9[5] N. Armenatzoglou, H. Pham, V. Ntranos, D. Papadias, and C. Shahabi.Real-time multi-criteria social graph partitioning: A game theoreticapproach. In Proceedings of the 2015 ACM SIGMOD InternationalConference on Management of Data, pages 1617–1628. ACM, 2015. →pages 9[6] P. Biro´, T. Fleiner, R. W. Irving, and D. Manlove. The college admissionsproblem with lower and common quotas. Theor. Comput. Sci, 411((34-36)):3136–3153, 2010. → pages 6, 7[7] M. J. Brzozowski, T. Hogg, and G. Szabo. Friends and foes: ideologicalsocial networking. In Proceedings of the SIGCHI conference on humanfactors in computing systems, pages 817–820. ACM, 2008. → pages 34[8] C. Chekuri and S. Khanna. A ptas for the multiple knapsack problem. InSODA, 2000. → pages 4, 6[9] L. Fleischer, M. X. Goemans, V. S. Mirrokni, and M. Sviridenko. Tightapproximation algorithms for maximum general assignment problems. InSODA, 2006. → pages 4, 637[10] D. Gale and L. S. Shapley. College admissions and the stability of marriage.Amer. Math. Monthly, 69, 1962. → pages 6, 18, 34[11] K. Hamada, K. Iwama, and S.Miyazaki. The hospitals/ residents problemwith quota lower bounds. In MATCH-UP: Matching Under PreferencesWorkshop at ICALP, 2008. → pages 6, 7[12] L. Katz. A new status index derived from sociometric analysis.Psychometrika, 18(1), 1953. ISSN 0033-3123. → pages 30[13] S. Khot. On the power of unique 2-prover 1-round games. STOC, 2002. →pages 15[14] J. Kleinberg and E. Tardos. Approximation algorithms for classificationproblems with pairwise relationships: Metric labeling and markov randomfields. Journal of the ACM (JACM), 49(5):616–639, 2002. → pages 9[15] S. O. Krumke and C. Thielen. The generalized assignment problem withminimum quantities. European Journal of Operational Research, 2013. →pages 4, 6, 13, 14[16] T. Lappas, K. Liu, and E. Terzi. Finding a team of experts in socialnetworks. In KDD, 2009. → pages 8[17] K. Li, W. Lu, S. Bhagat, L. V. Lakshmanan, and C. Yu. On social eventorganization. In Proceedings of the 20th ACM SIGKDD internationalconference on Knowledge discovery and data mining, pages 1206–1215.ACM, 2014. → pages iii[18] D. Liben-Nowell and J. Kleinberg. The link-prediction problem for socialnetworks. Journal of the American society for information science andtechnology, 58(7):1019–1031, 2007. → pages 11[19] X. Liu, Q. He, Y. Tian, W.-C. Lee, J. McPherson, and J. Han. Event-basedsocial networks: linking the online and offline social worlds. In KDD, 2012.→ pages 30, 31[20] J.-F. Mertens. Repeated games. Springer, 1989. → pages 35[21] E. Petrank. The hardness of approximations : Gap location. ComputationalComplexity, 4:133–157, 1994. → pages 14[22] A.-K. Pietilainen and C. Diot. CRAWDAD data set thlab/sigcomm2009 (v.2012-07-15). Downloaded fromhttp://crawdad.cs.dartmouth.edu/thlab/sigcomm2009, 2012. → pages 3038[23] P. Raghavendra and D. Steurer. Graph expansion and the unique gamesconjecture. In STOC, 2010. → pages 15[24] A. E. Roth. The evolution of the labor market for medical interns andresidents: a case study in game theory. Journal of Political Economy, 6(4):991–1016, 1984. → pages 4, 6[25] D. B. Shmoys and E´. Tardos. An approximation algorithm for thegeneralized assignment problem. Math. Program., 62:461–474, 1993. →pages 4, 6[26] M. Sozio and A. Gionis. The community-search problem and how to plan asuccessful cocktail party. In Proceedings of the 16th ACM SIGKDDinternational conference on Knowledge discovery and data mining, pages939–948. ACM, 2010. → pages 4, 939
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
On social event organization
Text