Farsi, Behrad (2017) Social Event Organization. Masters thesis, Concordia University.
Preview |
Text (application/pdf)
719kBFarsi_MCompSc_F2017.pdf - Accepted Version Available under License Spectrum Terms of Access. |
Abstract
In recent years, services such as Meetup, Plancast, and Eventbrite have provided platforms for planning and organizing live events. Social event organization (SEO), the problem of finding an assignment of users to events by considering their interests and social connections, is a problem that has received growing attention after being introduced by [24]. Given a weighted bipartite graph specifying the interest of every user in every event, and a social network between the users, the main goal of the SEO problem is to assign users to events so as to maximize a social welfare function, while respecting the minimum and maximum cardinality bounds associated with events.
The problem is shown to be NP-complete, and in fact, hard to approximate [24]. First, we review the previous solutions proposed in [24] and discuss some problems in these algorithms. Then, we propose the Second-Chance Dynamic Greedy (SCDG) and Community-Aware Static Greedy (CASG) algorithms to enhance the quality of the results produced by the existing algorithms. Our experiments using both synthetic and datasets from Meetup and Plancast show that our algorithms obtain a social welfare up to 60% better than that obtained by Phantom-Aware Dynamic Greedy (PADG), the best algorithm in [24].
Second, we propose the personality-oriented objective function that takes into account a user’s willingness participate in large events, or events with unknown people. We adapt PADG, SCDG, and CASG so as to optimize this new objective function. Our experiments show that the personality-oriented version of SCDG improves the social welfare by up to 100% over the adaptation of PADG.
| Divisions: | Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering |
|---|---|
| Item Type: | Thesis (Masters) |
| Authors: | Farsi, Behrad |
| Institution: | Concordia University |
| Degree Name: | M. Comp. Sc. |
| Program: | Computer Science |
| Date: | 20 June 2017 |
| Thesis Supervisor(s): | Narayanan, Lata |
| ID Code: | 982637 |
| Deposited By: | BEHRAD FARSI |
| Deposited On: | 10 Nov 2017 21:40 |
| Last Modified: | 18 Jan 2018 17:55 |
References:
[1] Meetup, 2017. URL https://www.meetup.com/about/.[2] Networkit, 2017. URL https://networkit.iti.kit.edu/.
[3] William Aiello, Fan Chung, and Linyuan Lu. A random graph model for massive graphs. In Proceedings of the Annual ACM Symposium on Theory of Computing (STOC 2000), pages 171-180. ACM, 2000.
[4] Albert-L´aszl´o Barab´asi and R´eka Albert. Emergence of scaling in random networks. Science, 286(5439):509-512, 1999.
[5] Vladimir Batagelj and Ulrik Brandes. Efficient generation of large random networks. Physical Review E, 71(3):036113, 2005.
[6] Vincent Boyer, Didier El Baz, and Moussa Elkihel. Solution of multidimensional knapsack problems via cooperation of dynamic programming and branch and bound. European Journal of Industrial Engineering, 4(4):434-449, 2010.
[7] Rainer Burkard, Mauro Dell’Amico, and Silvano Martello. Assignment problems. SIAM Press, 2012.
[8] Chandra Chekuri and Sanjeev Khanna. A PTAS for the multiple knapsack problem. pages 213-222, 2000.
[9] Donald Cohen and James P. Schmidt. Ambiversion: characteristics of midrange responders on the introversion-extraversion continuum. Journal of Personality Assessment, 43(5):514-516, 1979.
[10] George B Dantzig. Discrete-variable extremum problems. Operations research, 5(2):266-288, 1957.
[11] P. Erd¨os and A. R´enyi. On random graphs I. Publicationes Mathematicae (Debrecen), 6:290-297, 1959.
[12] Lisa Fleischer, Michel X Goemans, Vahab S Mirrokni, and Maxim Sviridenko. Tight approximation algorithms for maximum general assignment problems. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm, pages 611-620, 2006.
[13] Santo Fortunato. Community detection in graphs. Physics reports, 486(3):75-174, 2010.[14] David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15, 1962.
[15] P. C. Gilmore and Ralph E. Gomory. The theory and computation of knapsack functions. Operations Research, 14(6):1045-1074, 1966.[16] S Louis Hakimi. On realizability of a set of integers as degrees of the vertices of a linear graph. Journal of the Society for Industrial and Applied Mathematics, 10(3):496-506, 1962.
[17] V´aclav Havel. A remark on the existence of finite graphs. Casopis Pest. Mat., 80:477-480, 1955.
[18] Petter Holme and Beom Jun Kim. Growing scale-free networks with tunable clustering. Physical Review E, 65(2):026107, 2002.
[19] Jianbin Huang, Yu Zhou, Xiaolin Jia, and Heli Sun. A novel social event organization approach for diverse user choices. The Computer Journal, 2016.
[20] Iaroslav Ispolatov, PL Krapivsky, and A Yuryev. Duplication-divergence model of protein interaction network. Physical Review E, 71(6):061911, 2005.
[21] Narendra Karmarkar and Richard M. Karp. An efficient approximation scheme for the one-dimensional bin-packing problem. In 23rd Annual Symposium on Foundations of Computer Science, 1982. SFCS’08. (FOCS 82), pages 312-320, 1982.
[22] Peter J Kolesar. A branch and bound algorithm for the knapsack problem. Management Science, 13(9):723-735, 1967.
[23] Sven O Krumke and Clemens Thielen. The generalized assignment problem with minimum quantities. European Journal of Operational Research, 228(1):46-55, 2013.
[24] Keqian Li, Wei Lu, Smriti Bhagat, Laks V. S. Lakshmanan, and Cong Yu. On social event organization. In The 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (KDD ’14), pages 1206-1215, 2014.
[25] Xingjie Liu, Qi He, Yuanyuan Tian, Wang-Chien Lee, John McPherson, and Jiawei Han. Event-based social networks: Linking the online and offline social worlds. In Proceedings of the 18th ACM SIGKDD conference on Knowledge Discovery and Data Mining, (KDD’12), 2012.
[26] Isabel Briggs Myers. The Myers-Briggs type indicator. Consulting Psychologists Press, 1962.
[27] Mark EJ Newman and Duncan J Watts. Renormalization group analysis of the small-world network model. Physics Letters A, 263(4):341-346, 1999.
[28] Jakob Puchinger, G¨unther R Raidl, and Ulrich Pferschy. The multidimensional knapsack problem: Structure and algorithms. INFORMS Journal on Computing, 22(2):250-265, 2010.
[29] Alvin E. Roth and Elliott Peranson. The redesign of the matching market for American physicians: Some engineering aspects of economic design. Technical report, 1999.
[30] Jieying She, Yongxin Tong, and Lei Chen. Utility-aware social event-participant planning. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, pages 1629-1643, 2015.
[31] Wei Shih. A branch and bound method for the multiconstraint zero-one knapsack problem. Journal of the Operational Research Society, pages 369-378, 1979.
[32] David B Shmoys and ´Eva Tardos. An approximation algorithm for the generalized assignment problem. Mathematical programming, 62(1-3):461-474, 1993.
[33] Ronald L. Rivest Thomas H. Cormen, Charles E. Leiserson and Clifford Stein. Introduction to Algorithms. MIT Press, 2009.
[34] Yongxin Tong, Jieying She, and Rui Meng. Bottleneck-aware arrangement over event-based social networks: the max-min approach. In Proceedings of the 2016 World Wide Web Conference, 19(6):1151-1177, 2016.
[35] Duncan J Watts and Steven H Strogatz. Collective dynamics of smallworldnetworks. Nature, 393(6684):440-442, 1998.
[36] H. Martin Weingartner and David N. Ness. Methods for the solution of the multidimensional 0/1 knapsack problem. Operations Research, 15(1):83-103, 1967.
Repository Staff Only: item control page
Download Statistics
Download Statistics