On social event organization

ABSTRACT

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 such platforms. In this paper, we study the key computational problem involved in organization of social events, to our best knowledge, for the first time.

We propose the Social Event Organization (SEO) problem as one of 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. As a first step toward Social Event Organization, we introduce a 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.

References

1. W. Aiello, F. R. K. Chung, and L. Lu. A random graph model for massive graphs. In STOC, pages 171--180, 2000.
2. S. Amer-Yahia, S. B. Roy, A. Chawla, G. Das, and C. Yu. Group recommendation: Semantics and efficiency. PVLDB, 2(1), 2009.
3. A. Anagnostopoulos et al. Online team formation in social networks. In WWW, 2012.
4. N. Armenatzoglou, S. Papadopoulos, and D. Papadias. A general framework for geo-social query processing. PVLDB, 6(10), 2013.
5. P. Biró et al. The college admissions problem with lower and common quotas. Theor. Comput. Sci, 411(34--36):3136--3153, 2010.
6. C. Chekuri and S. Khanna. A ptas for the multiple knapsack problem. In SODA, 2000.
7. L. Fleischer et al. Tight approximation algorithms for maximum general assignment problems. In SODA, 2006.
8. D. Gale and L. S. Shapley. College admissions and the stability of marriage. Amer. Math. Monthly, 69, 1962.
9. K. Hamada, K. Iwama, and S.Miyazaki. The hospitals/ residents problem with quota lower bounds. In MATCH-UP: Matching Under Preferences Workshop at ICALP, 2008.
10. L. Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1), 1953.
11. S. Khot. On the power of unique 2-prover 1-round games. STOC, 2002.
12. S. O. Krumke and C. Thielen. The generalized assignment problem with minimum quantities. European Journal of Operational Research, 2013.
13. T. Lappas, K. Liu, and E. Terzi. Finding a team of experts in social networks. In KDD, 2009.
14. D. Liben-Nowell and J. Kleinberg. The link-prediction problem for social networks. Journal of the American society for information science and technology, 58(7), 2007.
15. X. Liu et al. Event-based social networks: linking the online and offline social worlds. In KDD, 2012.
16. E. Petrank. The hardness of approximations: Gap location. Computational Complexity, 4:133--157, 1994.
17. A.-K. Pietilainen and C. Diot. CRAWDAD data set thlab/sigcomm2009 (v. 2012-07-15). Downloaded from http://crawdad.cs.dartmouth.edu/thlab/sigcomm2009, 2012.
18. P. Raghavendra and D. Steurer. Graph expansion and the unique games conjecture. In STOC, 2010.
19. A. E. Roth. The evolution of the labor market for medical interns and residents: a case study in game theory. Journal of Political Economy, 6(4):991--1016, 1984.
20. D. B. Shmoys et al. An approximation algorithm for the generalized assignment problem. Math. Program., 62:461--474, 1993.
21. M. Sozio and A. Gionis. The community-search problem and how to plan a successful cocktail party. In KDD, pages 939--948, 2010.

Index Terms

• Information systems

  • Information systems applications

    • Data mining