Maximizing friend-making likelihood for social activity organization

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

doi:10.1007/978-3-319-18038-0_1

Maximizing friend-making likelihood for social activity organization

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

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

5 Scopus citations

Abstract

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 language	English (US)
Title of host publication	Advances in Knowledge Discovery and Data Mining - 19th Pacific-Asia Conference, PAKDD 2015, Proceedings
Editors	Tu-Bao Ho, Hiroshi Motoda, Hiroshi Motoda, Ee-Peng Lim, Tru Cao, David Cheung, Zhi-Hua Zhou
Publisher	Springer Verlag
Pages	3-15
Number of pages	13
ISBN (Print)	9783319180373
DOIs	https://doi.org/10.1007/978-3-319-18038-0_1
State	Published - 2015
Event	19th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2015 - Ho Chi Minh City, Viet Nam Duration: May 19 2015 → May 22 2015

Publication series

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

Other

Other	19th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2015
Country/Territory	Viet Nam
City	Ho Chi Minh City
Period	5/19/15 → 5/22/15

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-18038-0_1

Cite this

Shen, C. Y., Yang, D. N., Lee, W. C., & Chen, M. S. (2015). Maximizing friend-making likelihood for social activity organization. In T.-B. Ho, H. Motoda, H. Motoda, E.-P. Lim, T. Cao, D. Cheung, & Z.-H. Zhou (Eds.), Advances in Knowledge Discovery and Data Mining - 19th Pacific-Asia Conference, PAKDD 2015, Proceedings (pp. 3-15). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9077). Springer Verlag. https://doi.org/10.1007/978-3-319-18038-0_1

Shen, Chih Ya ; Yang, De Nian ; Lee, Wang Chien et al. / Maximizing friend-making likelihood for social activity organization. Advances in Knowledge Discovery and Data Mining - 19th Pacific-Asia Conference, PAKDD 2015, Proceedings. editor / Tu-Bao Ho ; Hiroshi Motoda ; Hiroshi Motoda ; Ee-Peng Lim ; Tru Cao ; David Cheung ; Zhi-Hua Zhou. Springer Verlag, 2015. pp. 3-15 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{0d3f9c7bd9aa4aaba38cb34af9663a9d,

title = "Maximizing friend-making likelihood for social activity organization",

abstract = "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.",

author = "Shen, {Chih Ya} and Yang, {De Nian} and Lee, {Wang Chien} and Chen, {Ming Syan}",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 19th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2015 ; Conference date: 19-05-2015 Through 22-05-2015",

year = "2015",

doi = "10.1007/978-3-319-18038-0_1",

language = "English (US)",

isbn = "9783319180373",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "3--15",

editor = "Tu-Bao Ho and Hiroshi Motoda and Hiroshi Motoda and Ee-Peng Lim and Tru Cao and David Cheung and Zhi-Hua Zhou",

booktitle = "Advances in Knowledge Discovery and Data Mining - 19th Pacific-Asia Conference, PAKDD 2015, Proceedings",

address = "Germany",

}

Shen, CY, Yang, DN, Lee, WC & Chen, MS 2015, Maximizing friend-making likelihood for social activity organization. in T-B Ho, H Motoda, H Motoda, E-P Lim, T Cao, D Cheung & Z-H Zhou (eds), Advances in Knowledge Discovery and Data Mining - 19th Pacific-Asia Conference, PAKDD 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9077, Springer Verlag, pp. 3-15, 19th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2015, Ho Chi Minh City, Viet Nam, 5/19/15. https://doi.org/10.1007/978-3-319-18038-0_1

Maximizing friend-making likelihood for social activity organization. / Shen, Chih Ya; Yang, De Nian; Lee, Wang Chien et al.
Advances in Knowledge Discovery and Data Mining - 19th Pacific-Asia Conference, PAKDD 2015, Proceedings. ed. / Tu-Bao Ho; Hiroshi Motoda; Hiroshi Motoda; Ee-Peng Lim; Tru Cao; David Cheung; Zhi-Hua Zhou. Springer Verlag, 2015. p. 3-15 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9077).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Maximizing friend-making likelihood for social activity organization

AU - Shen, Chih Ya

AU - Yang, De Nian

AU - Lee, Wang Chien

AU - Chen, Ming Syan

N1 - Publisher Copyright: © Springer International Publishing Switzerland 2015.

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84945892468&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84945892468&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-18038-0_1

DO - 10.1007/978-3-319-18038-0_1

M3 - Conference contribution

AN - SCOPUS:84945892468

SN - 9783319180373

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 3

EP - 15

BT - Advances in Knowledge Discovery and Data Mining - 19th Pacific-Asia Conference, PAKDD 2015, Proceedings

A2 - Ho, Tu-Bao

A2 - Motoda, Hiroshi

A2 - Lim, Ee-Peng

A2 - Cao, Tru

A2 - Cheung, David

A2 - Zhou, Zhi-Hua

PB - Springer Verlag

T2 - 19th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2015

Y2 - 19 May 2015 through 22 May 2015

ER -

Shen CY, Yang DN, Lee WC, Chen MS. Maximizing friend-making likelihood for social activity organization. In Ho TB, Motoda H, Motoda H, Lim EP, Cao T, Cheung D, Zhou ZH, editors, Advances in Knowledge Discovery and Data Mining - 19th Pacific-Asia Conference, PAKDD 2015, Proceedings. Springer Verlag. 2015. p. 3-15. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-18038-0_1

Maximizing friend-making likelihood for social activity organization

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this