Maximizing friend-making likelihood for social activity organization

Chih Ya Shen, De Nian Yang, Wang Chien Lee, Ming Syan Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations


The social presence theory in social psychology suggests that computer-mediated online interactions are inferior to face-to-face, inperson 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 perform extensive experiments on real datasets to demonstrate the efficiency and effectiveness of our proposed algorithm.

Original languageEnglish (US)
Title of host publicationAdvances in Knowledge Discovery and Data Mining - 19th Pacific-Asia Conference, PAKDD 2015, Proceedings
EditorsTu-Bao Ho, Hiroshi Motoda, Hiroshi Motoda, Ee-Peng Lim, Tru Cao, David Cheung, Zhi-Hua Zhou
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783319180373
StatePublished - 2015
Event19th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2015 - Ho Chi Minh City, Viet Nam
Duration: May 19 2015May 22 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other19th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2015
Country/TerritoryViet Nam
CityHo Chi Minh City

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Maximizing friend-making likelihood for social activity organization'. Together they form a unique fingerprint.

Cite this