1. Activity Organization for Friend-Making Optimization in Online Social Networks
- Author
-
Wang-Chien Lee, Ming-Syan Chen, De-Nian Yang, and Chih-Ya Shen
- Subjects
Social psychology (sociology) ,business.industry ,Computer science ,Approximation algorithm ,Machine learning ,computer.software_genre ,Computer Science Applications ,Social presence theory ,Constraint (information theory) ,Core (game theory) ,Computational Theory and Mathematics ,Graph (abstract data type) ,Artificial intelligence ,Pruning (decision trees) ,business ,Set (psychology) ,computer ,Information Systems - Abstract
The social presence theory in social psychology suggests that computer-mediated online interactions are inferior to face-to-face, in-person interactions. In this paper, we consider the scenarios of organizing in person friend-making social activities via online social networks (OSNs) and formulate a new research problem, namely, Hop-bounded Maximum Group Friending (HMGF), that takes into consideration both existing friendships and the likelihood of new friend making in organization of the targeted in person friend-making social activities. To find a set of attendees for such social activities, HMGF is unique and challenging due to the interplay of the group size, the constraint on existing friendships, and the objective of maximizing the likelihood of friend making. We propose an error-bounded approximation algorithm, MaxGF, to efficiently obtain the solutions very close to the optimal solutions. To boost the performance, we devise two graph-theoretical pruning strategies, namely Neighbor Pruning and Core Pruning, which can effectively avoid redundant graph explorations to improve the performance of HMGF. We conduct a user study to validate our problem formulation and perform extensive experiments on real datasets to demonstrate the efficiency and effectiveness of our proposed algorithm. The experimental results manifest that our proposed algorithms outperform the baselines, including the ILP formulation.
- Published
- 2022