https://scholars.lib.ntu.edu.tw/handle/123456789/607255
標題: | Activity Organization for Friend-Making Optimization in Online Social Networks | 作者: | Shen C.-Y Yang D.-N Lee W.-C Chen M.-S. MING-SYAN CHEN |
關鍵字: | Algorithm design;Online social networks;Social activity organization;Approximation algorithms;Graph theory;Integer programming;Optimal systems;Polynomial approximation;Integer linear programming formulation;Optimal solutions;Optimisations;Performance;Social activities;Social presence;Social psychology;Threshold graphs;Social networking (online) | 公開日期: | 2022 | 卷: | 34 | 期: | 1 | 起(迄)頁: | 122-137 | 來源出版物: | IEEE Transactions on Knowledge and Data Engineering | 摘要: | The social presence theory in social psychology suggests that computer-mediated online interactions are inferior to face-to-face, in-person interactions. Thus, it's important to organize social activities for online social network users to meet in person. 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 prove that HMGF is NP-Hard, and there exists no approximation algorithm for it unless $P=NP$P=NP. We also provide an Integer Linear Programming (ILP) formulation for the HMGF problem. The ILP formulation, which can be solved efficiently by a commercial solver to obtain the optimal solution for small HMGF instances, acts as a baseline approach for comparison in the evaluation of the proposed algorithm. We further 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 also study HMGF on a class of special graphs, threshold graphs, which have properties very similar to many online social networks. We prove that MaxGF can obtain the optimal solution to HMGF on threshold graphs in polynomial time. 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. ? 1989-2012 IEEE. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85121722028&doi=10.1109%2fTKDE.2020.2980516&partnerID=40&md5=f418c004104b8536f8e752622c2bad93 https://scholars.lib.ntu.edu.tw/handle/123456789/607255 |
ISSN: | 10414347 | DOI: | 10.1109/TKDE.2020.2980516 |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。