More Web Proxy on the site http://driver.im/

article

Utility-Based Link Recommendation for Online Social Networks

Authors:

Olivia R. Liu ShengAuthors Info & Claims

Management Science, Volume 63, Issue 6

Pages 1938 - 1952

https://doi.org/10.1287/mnsc.2016.2446

Published: 01 June 2017 Publication History

Abstract

Link recommendation, which suggests links to connect currently unlinked users, is a key functionality offered by major online social networks. Salient examples of link recommendation include "People You May Know" on Facebook and LinkedIn as well as "You May Know" on Google+. The main stakeholders of an online social network include users e.g., Facebook users who use the network to socialize with other users and an operator e.g., Facebook Inc. that establishes and operates the network for its own benefit e.g., revenue. Existing link recommendation methods recommend links that are likely to be established by users but overlook the benefit a recommended link could bring to an operator. To address this gap, we define the utility of recommending a link and formulate a new research problem-the utility-based link recommendation problem. We then propose a novel utility-based link recommendation method that recommends links based on the value, cost, and linkage likelihood of a link, in contrast to existing link recommendation methods that focus solely on linkage likelihood. Specifically, our method models the dependency relationship between the value, cost, linkage likelihood, and utility-based link recommendation decision using a Bayesian network; predicts the probability of recommending a link with the Bayesian network; and recommends links with the highest probabilities. Using data obtained from a major U.S. online social network, we demonstrate significant performance improvement achieved by our method compared with prevalent link recommendation methods from representative prior research.

This paper was accepted by Anandhi Bharadwaj, information systems.

References

[1]

Adali S, Sisenda F, Magdon-Ismail M (2012) Actions speak as loud as words: Predicting relationships from social behavior data. Proc. 21st Internat. Conf. World Wide Web (ACM, New York), 689-698.

[2]

Adamic LA, Adar E (2003) Friends and neighbors on the web. Soc. Networks 25(3):211-230.

[3]

Al Hasan M, Chaoji V, Salem S, Zaki M (2006) Link prediction using supervised learning. Proc. SIAM Workshop on Link Anal., Counterterrorism Security, Society for Industrial and Applied Mathematics, Philadelphia.

[4]

Backstrom L, Leskovec J (2011) Supervised random walks: Predicting and recommending links in social networks. Proc. 4th ACM Internat. Conf. Web Search Data Mining (ACM, New York), 635-644.

[5]

Ballester C, Calvó-Armengol A, Zenou Y (2006) Who's who in networks. Wanted: The key player. Econometrica 74(5):1403-1417.

[6]

Barabási A, Albert R (1999) Emergence of scaling in random networks. Science 286(5439):509-512.

[7]

Barabási A, Jeong H, Néda Z, Ravasz E, Schubert A, Vicsek T (2002) Evolution of the social network of scientific collaborations. Physica A: Statist. Mechanics Appl. 311(3):590-614.

[8]

Benchettara N, Kanawati R, Rouveirol C (2010) Supervised machine learning applied to link prediction in bipartite social networks. Memon N, Alhajj R, eds. Proc. 2nd Internat. Conf. Adv. Soc. Network Anal. Mining (IEEE Computer Society, Washington, DC), 326-330.

[9]

Bensoussan AR, Mookerjee V, Mookerjee W, Yue T (2009) Maintaining diagnostic knowledge-based systems: A control theoretic approach. Management Sci. 55(2):294-310.

Digital Library

[10]

Bishop CM, Nasrabadi NM (2006) Pattern Recognition and Machine Learning (Springer, New York).

[11]

Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. Comput. Networks 30(1-7):107-117.

Digital Library

[12]

Chen J, GeyerW, Dugan C, Muller M, Guy I (2009) Make newfriends, but keep the old: Recommending people on social networking sites. Greenberg S, Hudson SE, Hinckley K, Morris MR, Olsen DR Jr, eds. Proc. 27th Internat. Conf. Human Factors Comput. Systems (ACM, New York), 201-210.

[13]

Crandall DJ, Backstrom L, Cosley D, Suri S, Huttenlocher D, Kleinberg J (2010) Inferring social ties from geographic coincidences. Proc. Natl. Acad. Sci. USA 107(52):22436-22441.

[14]

Davenport T, Patil DJ (2012) Data scientist: The sexist job of the 21st century. Harvard Bus. Rev. 90(10):70-76.

[15]

Dempster AP, Laird NM, Rubin DB (1977) Maximum likelihood from incomplete data via the EM algorithm. J. Roy. Statist. Soc. Ser. B 39(1):1-38.

[16]

Domingos P, Richardson M (2001) Mining the network value of customers. Proc. 7th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 57-66.

[17]

Dong Y, Tang J, Wu S, Tian J, Chawla NV, Rao J, Cao H (2012) Link prediction and recommendation across heterogeneous social networks. Zaki MJ, Siebes A, Yu JX, Goethals B, Webb G, Wu X, eds. Proc. 12th Internat. Conf. Data Mining (IEEE Computer Society, Washington, DC), 181-190.

[18]

Doreian P (1989) Two regimes of network autocorrelation. Kochen M, ed. The Small World (Ablex, Norwood, NJ), 280-295.

[19]

Duda RO, Hart PE (1973) Pattern Classification and Scene Analysis (John Wiley & Sons, New York).

[20]

Ellison NB, Steinfield C, Lampe C (2007) The benefits of Facebook "friends": Social capital and college students' use of online social network sites. J. Comput.-Mediated Comm. 12(4):1143-1168.

[21]

eMarketer (2012) Total worldwide social network ad revenues continue strong growth. (February 24), http://www.emarketer.com/Article/Total-Worldwide-Social-Network-Ad-Revenues-Continue-Strong-Growth/1008862.

[22]

Facebook Inc. (2013) Form 10-K for the fiscal year ended December 31, 2013. Accessed February 1, 2015, https://www.sec.gov/Archives/edgar/data/1326801/000132680114000007/fb-12312013x10k.htm.

[23]

Fang X, Sheng ORL, Goes P (2013a) When is the right time to refresh knowledge discovered from data? Oper. Res. 61(1):32-44.

Digital Library

[24]

Fang X, Hu P, Li Z, Tsai W (2013b) Predicting adoption probabilities in social networks. Inform. Systems Res. 24(1):128-145.

[25]

Fouss F, Pirotte A, Renders JM, Saerens M (2007) Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Trans. Knowledge Data Engrg. 19(3):355-369.

Digital Library

[26]

Freund JE (1961) A bivariate extension of the exponential distribution. J. Amer. Statist. Assoc. 56(296):971-977.

[27]

Friedman N (1998) The Bayesian structural EM algorithm. Cooper G, Moral S, eds. Proc. 14th Conf. Uncertainty Artificial Intelligence (Morgan Kaufmann, San Francisco), 129-138.

[28]

Gong NZ, Talwalkar A, Mackey L, Huang L, Shin ECR, Stefanov E, Shi ER, Song D (2014) Joint link prediction and attribute inference using a social-attribute network. ACM Trans. Intelligent Systems Technol. (TIST) 5(2):27.

[29]

Granovetter MS (1973) The strength of weak ties. Amer. J. Sociol. 78(6):1360-1380.

[30]

Granovetter M (2005) The impact of social structure on economic outcomes. J. Econom. Perspect. 19(1):33-50.

[31]

Heckerman D (2008) A tutorial on learning with Bayesian networks. Holmes D, Jain L, eds. Innovations in Bayesian Networks (Springer-Verlag, Berlin), 33-82.

[32]

Heider F (1958) The Psychology of Interpersonal Relations (John Wiley & Sons, New York).

[33]

Hopcroft J, Lou T, Tang J (2011) Who will follow you back? Reciprocal relationship prediction. Berendt B, de Vries A, Fan W, MacDonald G, Ounis I, Ruthven I, eds. Proc. 20th ACM Internat. Conf. Inform. Knowledge Management (ACM, New York), 1137-1146.

[34]

Huberman BA, Romero DM, Wu F (2009) Social networks that matter: Twitter under the microscope. First Monday 14(1). http://firstmonday.org/ojs/index.php/fm/article/view/2317/2063.

[35]

Jackson MO (2008) Social and Economic Networks (Princeton University Press, Princeton, NJ).

[36]

Jackson MO, Rogers BW (2005) The economics of smallworlds. J. Eur. Econom. Assoc. 3(2-3):617-627.

[37]

Jackson MO, Wolinsky A (1996) A strategic model of social and economic networks. J. Econom. Theory 71(1):44-74.

[38]

Jeh G, Widom J (2002) SimRank: A measure of structural-context similarity. Proc. 8th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 538-543.

[39]

Kaplan AM, Haenlein M (2010) Users of the world, unite! The challenges and opportunities of social media. Bus. Horizons 53(1): 59-68.

[40]

Katz L (1953) A new status index derived from sociometric analysis. Psychometrika 18(1):39-43.

[41]

Kunegis J, De Luca EW, Albayrak S (2010) The link prediction problem in bipartite networks. Hüllermeier E, Kruse R, Hoffmann F, eds. Computational Intelligence for Knowledge-Based Systems Design, Lecture Notes in Artificial Intelligence, Vol. 6178 (Springer-Verlag, Berlin), 380-389.

[42]

Kuo TT, Rui Y, Huang YY, Kung PH, Lin SD (2013) Unsupervised link prediction using aggregative statistics on heterogeneous social networks. Dhillon IS, Koren Y, Ghani R, Senator TE, Bradley P, Parekh R, He J, Grossman RL, Uthurusamy R, eds. Proc. 19th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 775-783.

[43]

Liben-Nowell D, Kleinberg J (2007) The link prediction problem for social networks. J. Amer. Soc. Inform. Sci. Tech. 58(7): 1019-1031.

Digital Library

[44]

Lichtenwalter RN, Lussier JT, Chawla NV (2010) New perspectives and methods in link prediction. Proc. 16th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 243-252.

[45]

LinkedIn Corporation (2014) Form 10-K for the fiscal year ended December 31, 2013. Accessed February 1, 2015, https://www.sec.gov/Archives/edgar/data/1271024/000144530514000439/a20131231-10xkdocument.htm.

[46]

McLachlan G, Krishnan T (2007) The EM Algorithm and Extensions (John Wiley & Sons, Hoboken, NJ).

[47]

McPherson JM, Smith-Lovin L, Cook JM (2001) Birds of a feather: Homophily in social networks. Annual Rev. Sociol. 27: 415-444.

[48]

Mitchell TM (1997) Machine Learning (McGraw-Hill, New York).

[49]

Newman MEJ (2001) The structure of scientific collaboration networks. Proc. Natl. Acad. Sci. USA 98(2):404-409.

[50]

Newman MEJ, Watts DJ, Strogatz SH (2002) Random graph models of social networks. Proc. Natl. Acad. Sci. USA 99(1):2566-2572.

[51]

O'Madadhain J, Hutchins J, Smyth P (2005) Prediction and ranking algorithms for event-based network data. SIGKDD Explorations 7(2):23-30.

Digital Library

[52]

Popescul A, Ungar L (2003) Statistical relational learning for link prediction. Gottlob G, Walsh T, eds. Workshop Learn. Statist. Models Relational Data Internat. Joint Conf. Artificial Intelligence (Morgan Kaufmann, San Francisco), 81-90.

[53]

Quercia D, Capra L (2009) FriendSensing: Recommending friends using mobile phones. Proc. 3rd ACM Conf. Recommender Systems (ACM, New York), 273-276.

[54]

Saar-Tsechansky M, Melville P, Provost F (2009) Active feature-value acquisition. Management Sci. 55(4):664-684.

Digital Library

[55]

Salton G, McGill MJ (1983) Introduction to Modern Information Retrieval (McGraw-Hill, New York).

[56]

Scellato S, Noulas A, Mascolo C (2011) Exploiting place features in link prediction on location-based social networks. Proc. 17th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 1046-1054.

[57]

Schifanella R, Barrat A, Cattuto C, Markines B, Menczer F (2010) Folks in folksonomies: Social link prediction from shared metadata. Proc. 3rd ACM Internat. Conf. Web Search Data Mining (ACM, New York), 271-280.

[58]

Shen D, Sun JT, Yang Q, Chen Z (2006) Latent friend mining from blog data. Clifton CW, Zhong N, Liu J, Wah BW, Wu X, eds. Proc. 6th IEEE Internat. Conf. Data Mining (IEEE Computer Society, Washington, DC), 552-561.

[59]

Tan P-N, Steinbach M, Kumar V (2005) Introduction to Data Mining (Addison-Wesley, Boston).

[60]

Tong H, Faloutsos CC, Pan JY (2006) Fast random walk with restart and its applications. Clifton CW, Zhong N, Liu J, Wah BW, Wu X, eds. Proc. 6th IEEE Internat. Conf. Data Mining (IEEE Computer Society, Washington, DC), 613-622.

[61]

Wang C, Satuluri V, Parthasarathy S (2007) Local probabilistic models for link prediction. Ramakrishnan N, Zaïane OR, Shi Y, Clifton CW, Wu X, eds. Proc. 7th IEEE Internat. Conf. Data Mining (IEEE Computer Society, Washington, DC), 322-331.

[62]

Wang D, Pedreschi D, Song C, Giannotti F, Barabasi AL (2011) Human mobility, social ties, and link prediction. Proc. 17th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 1100-1108.

[63]

Watts A (2001) A dynamic model of network formation. Games Econom. Behav. 34(2):331-341.

[64]

Weiss G, Zadrozny B, Saar-Tsechansky M (2008) Special issue on utility-based data mining. Data Mining Knowledge Discovery 17(2): 129-135.

Digital Library

[65]

Yang S-H, Long B, Smola A, Sadagopan N, Zheng Z, Zha H (2011) Like like alike: Joint friendship and interest propagation in social networks. Proc. 20th ACM Internat. Conf. World Wide Web (ACM, New York), 537-546.

[66]

Zhang B, Thomas A, Doreian P, Krackhardt D, Krishnan R (2013) Contrasting multiple social network autocorrelations for binary outcomes, with applications to technology adoption. ACM Trans. Management Inform. Systems 3(4): Article 18.

[67]

Zhao K, Yen J, Ngamassi L, Maitland C, Tapia A (2012) Simulating inter-organizational collaboration networks: A multirelational and event-based approach. Simulation 88(5):617-633.

Digital Library

[68]

Zheleva E, Getoor L, Golbeck J, Kuter U (2010) Using friendship ties and family circles for link prediction. Giles L, Smith M, Yen J, Zhang H, eds. Advances in Social Network Mining and Analysis, Lecture Notes in Computer Science, Vol. 5498 (Springer-Verlag, Berlin), 97-113.

[69]

Zheng Z, Pavlou P (2010) Toward a causal interpretation from observational data: A new Bayesian networks method for structural models with latent variables. Inform. System Res. 21(2): 365-391.

Digital Library

Cited By

Liu XLi X(2024)Cost-Effective Acquisition of First-Party Data for Business AnalyticsINFORMS Journal on Computing10.1287/ijoc.2022.003736:5(1242-1260)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1287/ijoc.2022.0037
De Biasio AJannach DNavarin N(2024)Model-based approaches to profit-aware recommendationExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.123642249:PBOnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.eswa.2024.123642
Ding YZhang LHuang CGe R(2024)Two-stage travel itinerary recommendation optimization model considering stochastic traffic timeExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.121536237:PBOnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.eswa.2023.121536
Show More Cited By

Recommendations

Bayesian-Inference-Based Recommendation in Online Social Networks

In this paper, we propose a Bayesian-inference-based recommendation system for online social networks. In our system, users share their content ratings with friends. The rating similarity between a pair of friends is measured by a set of conditional ...
Diversity Preference-Aware Link Recommendation for Online Social Networks
Link recommendation, such as “People You May Know” on LinkedIn, recommends links to connect unlinked online social network users. Existing link recommendation methods tend to recommend similar friends to a user but overlook the fact that different users ...
Link recommendation, which recommends links to connect unlinked online social network users, is a fundamental social network analytics problem with ample business implications. Existing link recommendation methods tend to recommend similar friends to a ...
A Survey of Link Recommendation for Social Networks: Methods, Theoretical Foundations, and Future Research Directions

Link recommendation has attracted significant attention from both industry practitioners and academic researchers. In industry, link recommendation has become a standard and most important feature in online social networks, prominent examples of which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Management Science

Management Science Volume 63, Issue 6

June 2017

392 pages

ISSN:0025-1909

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 June 2017

Accepted: 17 December 2015

Received: 15 February 2015

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Liu XLi X(2024)Cost-Effective Acquisition of First-Party Data for Business AnalyticsINFORMS Journal on Computing10.1287/ijoc.2022.003736:5(1242-1260)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1287/ijoc.2022.0037
De Biasio AJannach DNavarin N(2024)Model-based approaches to profit-aware recommendationExpert Systems with Applications: An International Journal10.1016/j.eswa.2024.123642249:PBOnline publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.eswa.2024.123642
Ding YZhang LHuang CGe R(2024)Two-stage travel itinerary recommendation optimization model considering stochastic traffic timeExpert Systems with Applications: An International Journal10.1016/j.eswa.2023.121536237:PBOnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.eswa.2023.121536
Yang GWang XLiu YLin SXu J(2024)A study on exit and entry mechanism and evolution of relationships between decision makers for multistage large-scale group decision-making problems▪Expert Systems with Applications: An International Journal10.1016/j.eswa.2023.121343237:PAOnline publication date: 27-Feb-2024
https://dl.acm.org/doi/10.1016/j.eswa.2023.121343
Yin KFang XChen BSheng O(2023)Diversity Preference-Aware Link Recommendation for Online Social NetworksInformation Systems Research10.1287/isre.2022.117434:4(1398-1414)Online publication date: 1-Dec-2023
https://dl.acm.org/doi/10.1287/isre.2022.1174
Han XWang LFan W(2023)Cost-Effective Social Media Influencer MarketingINFORMS Journal on Computing10.1287/ijoc.2022.124635:1(138-157)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1287/ijoc.2022.1246
Dutta H(2022)A Consensus Algorithm for Linear Support Vector MachinesManagement Science10.1287/mnsc.2021.404268:5(3703-3725)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1287/mnsc.2021.4042
Wang YTao LZhang X(2022)Recommending for a multi-sided marketplace with heterogeneous contentsProceedings of the 16th ACM Conference on Recommender Systems10.1145/3523227.3547379(456-459)Online publication date: 12-Sep-2022
https://dl.acm.org/doi/10.1145/3523227.3547379
Xiong TZhou LZhao YZhang X(2022)Mining semantic information of co-word network to improve link prediction performanceScientometrics10.1007/s11192-021-04247-9127:6(2981-3004)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s11192-021-04247-9
Zhou FZhang KWu BYang YWang H(2021)Unifying Online and Offline Preference for Social Link PredictionINFORMS Journal on Computing10.1287/ijoc.2020.098933:4(1400-1418)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1287/ijoc.2020.0989
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents