2015/02/24 by Chih-Ya Shen, Shen, Chih-Ya, De-Nian Yang +6
Computer Science · Physics and Astronomy · #Complex Network Analysis Techniques #FOS: Computer and information sciences #Mobile Crowdsensing and Crowdsourcing #Opinion Dynamics and Social Influence #Social and Information Networks (cs.SI) #cs.SI
paper · pdf · doi:10.48550/arxiv.1502.06682
openalex publication_date 2015/02/24 · arxiv created 2015/02/26 · arxiv updated 2015/02/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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), by modeling both existing friendships and the likelihood of new friend making. To find a set of attendees for socialization activities, HMGF is unique and challenging due to the interplay of the group size, the constraint on existing friendships and the objective function on the likelihood of friend making. We prove that HMGF is NP-Hard, and no approximation algorithm exists unless P = NP. We then propose an error-bounded approximation algorithm to efficiently obtain the solutions very close to the optimal solutions. We conduct a user study to validate our problem formulation and per- form extensive experiments on real datasets to demonstrate the efficiency and effectiveness of our proposed algorithm.