Abstract
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 include “People You May Know” on LinkedIn and “You May Know” on Google+. In academia, link recommendation has been and remains a highly active research area. This article surveys state-of-the-art link recommendation methods, which can be broadly categorized into learning-based methods and proximity-based methods. We further identify social and economic theories, such as social interaction theory, that underlie these methods and explain from a theoretical perspective why a link recommendation method works. Finally, we propose to extend link recommendation research in several directions that include utility-based link recommendation, diversity of link recommendation, link recommendation from incomplete data, and experimental study of link recommendation.
- E. Acar, D. M. Dunlavy, and T. G. Kolda. 2009. Link prediction on evolving data using matrix and tensor factorizations. In Proceedings of IEEE International Conference on Data Mining Workshops. 262--269. Google ScholarDigital Library
- S. Adali, F. Sisenda, and M. Magdon-Ismail. 2012. Actions speak as loud as words: Predicting relationships from social behavior data. In Proceedings of the 21st International Conference on World Wide Web (WWW’12) 689--698. Google ScholarDigital Library
- L. A. Adamic and E. Adar. 2003. Friends and neighbors on the web. Soc. Netw. 25, 3 (2003), 211--230.Google ScholarCross Ref
- C. Aggarwal. 2007. Data Streams: Models and Algorithms. Springer, New York, NY. Google ScholarDigital Library
- G. A. Akerlof. 1997. Social distance and social decisions. Econometrica 65, 5 (1997), 1005--1027.Google ScholarCross Ref
- R. Albert, H. Jeong, and A. L. Barabasi. 2000. Error and attack tolerance of complex networks. Nature 406, 6794 (2000), 378--382.Google Scholar
- S. Aral, L. Muchnik, and A. Sundararajan. 2009. Distinguishing influence-based contagion from homophily-driven diffusion in dynamic networks. Proc. Natl. Acad. Sci. U.S.A. 106, 51 (2009), 21544--21549.Google ScholarCross Ref
- S. Aral and D. Walker. 2012. Identifying influential and susceptible members of social networks. Science 337, 6092 (2012), 337--341.Google ScholarCross Ref
- J. Akehurst, I. Koprinska, K. Yacef, L. Pizzato, J. Kay, and T. Rej. 2011. A hybrid content-collaborative reciprocal recommender for online dating. In Proceedings of International Joint Conference on Artificial Intelligence. Google ScholarDigital Library
- S. B. Bacharach. 1989. Organizational theories: Some criteria for evaluation. Acad. Manage. Rev. 14, 4 (1989), 496--515.Google ScholarCross Ref
- L. Backstrom and J. Leskovec. 2011. Supervised random walks: Predicting and recommending links in social networks. In Proceedings of the 4th ACM International Conference on Web Search and Data Mining (WSDM’11). 635--644. Google ScholarDigital Library
- A. Barabási and R. Albert. 1999. Emergence of scaling in random networks. Science 286, 5439 (1999), 509--512.Google Scholar
- A. Barabási, H. Jeong, Z. Néda, E. Ravasz, A. Schubert, and T. Vicsek. 2002. Evolution of the social network of scientific collaborations. Physica A 311, 3 (2002), 590--614.Google ScholarCross Ref
- N. Barbieri, F. Bonchi, and G. Manco. 2014. Who to follow and why: Link prediction with explanations. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’14). 1266--1275. Google ScholarDigital Library
- G. Becker. 1974. A Theory of social interactions. J. Polit. Econ. 82 (1974), 1063--1093.Google ScholarCross Ref
- N. Benchettara, R. Kanawati, and C. Rouveirol. 2010. A supervised machine learning link prediction approach for academic collaboration recommendation. In Proceedings of the 4th ACM Conference on Recommender Systems. 253--256. Google ScholarDigital Library
- C. R. Berger and R. J. Calabrese. 1975. Some explorations in initial interaction and beyond: Toward a developmental theory of interpersonal communication. Hum. Commun. Res. 1, 2 (1975), 99--112.Google ScholarCross Ref
- C. A. Bliss, M. R. Frank, C. M. Danforth, and P. S. Dodds. 2014. An evolutionary algorithm approach to link prediction in dynamic social networks. J. Comput. Sci. 5, 5 (2014), 750--764.Google ScholarCross Ref
- M. Bilgic, G. M. Namata, and L. Getoor. 2007. Combining collective classification and link prediction. In Proceedings of 7th IEEE International Conference on Data. 381--386. Google ScholarDigital Library
- M. A. Brandão, M. M. Moro, G. R. Lopes, and J. P. M. Oliveira. 2013. Using link semantics to recommend collaborations in academic social networks. In Proceedings of the 22nd International Conference on World Wide Web Companion (WWW’13). 833--840. Google ScholarDigital Library
- S. Brin and L. Page. 1998. The anatomy of a large-scale hypertextual web search engine. Comput. Netw. 30 (1998), 107--117. Google ScholarDigital Library
- R. Burt. 1992. Structural Holes: The Social Structure of Competition. Harvard University Press, Cambridge, MA.Google ScholarCross Ref
- X. Cai, M. Bain, A. Krzywicki, W. Wobcke, Y. Kim, P. Compton, and A. Mahidadia. 2012. Reciprocal and heterogeneous link prediction in social networks. Adv. Knowl. Discov. Data Min. (2012) 193--204. Google ScholarDigital Library
- J. Chen, W. Geyer, C. Dugan, M. Muller, and I. Guy. 2009. Make new friends, but keep the old: Recommending people on social networking sites. In Proceedings of the 27th International Conference on Human Factors in Computing Systems. 201--210. Google ScholarDigital Library
- J. Cheng, D. M. Romero, B. Meeder, and J. Kleinberg. 2011. Predicting reciprocity in social networks. In Proceedings of the IEEE 3rd International Conference on Privacy, Security, Risk and Trust and the IEEE 3rd International Conference on Social Computing. 49--56.Google Scholar
- A. Clauset, C. Moore, and M. E. Newman. 2008. Hierarchical structure and the prediction of missing links in networks. Nature 453, 7191 (2008), 98--101.Google Scholar
- D. J. Crandall, L. Backstrom, D. Cosley, S. Suri, D. Huttenlocher, and J. Kleinberg. 2010. Inferring social ties from geographic coincidences. Proc. Natl. Acad. Sci. U.S.A. 107, 52 (2010), 22436--22441.Google ScholarCross Ref
- T. Davenport and D. J. Patil. 2012. Data scientist: the sexist job of the 21st century. Harv. Bus. Rev. 90, 10 (2012), 70--76.Google Scholar
- J. A. Davis and S. Leinhardt. 1971. The structure of positive interpersonal relations in small groups. In Sociological Theories in Progress (2nd ed.). Houghton-Mifflin, Boston.Google Scholar
- S. Deerwester, S. T. Dumais, G. W. Furnas, and T. K. Landauer. 1990. Indexing by latent semantic analysis. J. Am. Soc. Inf. Sci. 41, 6 (1990), 391--407.Google ScholarCross Ref
- A. P. Dempster, N. M. Laird, and D. B. Rubin. 1977. Maximum likelihood from incomplete data via the em algorithm. J. Roy. Stat. Soc. Ser. B 39, 1, 1--38.Google ScholarCross Ref
- J. R. Doppa, J. Yu, P. Tadepalli, and L. Getoor. 2010. Learning algorithms for link prediction based on chance constraints. Machine Learning and Knowledge Discovery in Databases. Springer, Berlin, 344--360. Google ScholarDigital Library
- Y. Dong, J. Tang, S. Wu, J. Tian, N. V. Chawla, J. Rao, and H. Cao. 2012. Link prediction and recommendation across heterogeneous social networks. In Proceedings of the 12th International Conference on Data Mining. 181--190. Google ScholarDigital Library
- Y. Dong, J. Zhang, J. Tang, N. V. Chawla, and B. Wang. 2015. CoupledLP: Link prediction in coupled networks. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’15). 199--208. Google ScholarDigital Library
- D. M. Dunlavy, T. G. Kolda, and E. Acar. 2011. Temporal link prediction using matrix and tensor factorizations. ACM Trans. Knowl. Discov. Data 5, 2 (2011), 1--27. Google ScholarDigital Library
- N. Eagle, M. Macy, and R. Claxton. 2010. Network diversity and economic development. Science 328, 5981 (2010), 1029--1031.Google Scholar
- Facebook 10-K2013. Form 10-K of Facebook Inc. for the Fiscal Year Ended December 31, 2013. Securities and Exchange Commission's Edgar Website. Retrieved on January 7, 2016 from https://www.sec.gov/edgar.shtml.Google Scholar
- X. Fang, P. Hu, Z. Li, and W. Tsai. 2013a. Predicting adoption probabilities in social networks. Inf. Syst. Res. 24, 1 (2013), 128--145.Google ScholarCross Ref
- X. Fang, O. R. Liu Sheng, and P. Goes. 2013b. When is the right time to refresh knowledge discovered from data? Operat. Res. 61, 1 (2013), 32--44. Google ScholarDigital Library
- X. Fang. 2013. Inference-based naïve bayes: Turning naïve bayes cost-sensitive. IEEE Trans. Knowl. Data Eng. 25, 10 (2013), 2302--2313. Google ScholarDigital Library
- Scott L. Feld. 1981. The focused organization of social ties. Am. J. Sociol. 86, 5 (1981), 1015--1035.Google ScholarCross Ref
- M. Fire, L. Tenenboim, O. Lesser, R. Puzis, L. Rokach, and Y. Elovici. 2011. Link prediction in social networks using computationally efficient topological features. In Proceedings of Privacy, Security, Risk and Trust and IEEE 3rd International Conference on Social Computing. 73--80.Google Scholar
- F. Fouss, A. Pirotte, J. M. Renders, and M. Saerens. 2007. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Trans. Knowl. Data Eng. 19, 3 (2007), 355--369. Google ScholarDigital Library
- N. Friedman, L. Getoor, D. Koller, and A. Pfeffer. 1999. Learning probabilistic relational models. In Proceedings of International Joint Conferences on Artificial Intelligence 1300--1309. Google ScholarDigital Library
- L. Getoor, N. Friedman, D. Koller, and B. Taskar. 2001. Learning probabilistic models of relational structure. In Proceedings of International Conference on Machine Learning (ICML’01). 170--177. Google ScholarDigital Library
- L. Getoor, N. Friedman, D. Koller, and B. Taskar. 2003. Learning probabilistic models of link structure. J. Mach. Learn. Res. 3 (2003), 679--707. Google ScholarDigital Library
- L. Getoor and B. Taskar. 2007. Introduction to Statistical Relational Learning. MIT Press, Cambridge, MA. Google ScholarDigital Library
- N. Z. Gong, A. Talwalkar, L. Mackey, L. Huang, E. C. R. Shin, E. Stefanov, E. R. Shhi, and D. Song. 2014. Jointly predicting links and inferring attributes using a social-attribute network. ACM Trans. Intell. Syst. Technol. 5, 2 (2014), 1--20. Google ScholarDigital Library
- R. Guimerà and S. Marta. 2009. Missing and spurious interactions and the reconstruction of complex networks. Proc. Natl. Acad. Sci U.S.A. 106, 52 (2009), 22073--22078.Google ScholarCross Ref
- R. Guha, R. Kumar, P. Raghavan, and A. Tomkins. 2004. Propagation of trust and distrust. In Proceedings of the 23rd International Conference on World Wide Web. 403--412. Google ScholarDigital Library
- M. Hasan, V. Chaoji, S. Salem, and M. Zaki. 2006. Link prediction using supervised learning. In SIAM International Conference on Data Mining Workshop on Link Analysis, Counter-terrorism and Security.Google Scholar
- M. Hasan and M. Zaki. 2009. A survey of link prediction in social networks. In Social Network Data Analytics. Springer, New York, NY.Google Scholar
- T. H. Haveliwala. 2002. Topic-sensitive Pagerank. In Proceedings of the 11th International Conference on World Wide Web (WWW’02). 517--526. Google ScholarDigital Library
- D. Heckerman, D. M. Chickering, C. Meek, R. Rounthwaite, and C. Kadie. 2001. Dependency networks for inference, collaborative filtering, and data visualization. J. Mach. Learn. Res. 1 (2001), 49--75. Google ScholarDigital Library
- D. Heckerman, C. Meek, and D. Koller. 2004. Probabilistic models for relational data. Technical Report MSR-TR-2004-30. Microsoft Research.Google Scholar
- F. Heider. 1958. The Psychology of Interpersonal Relations. Wiley, New York, NY.Google Scholar
- T. Hofmann. 2004. Latent semantic models for collaborative filtering. ACM Trans. Inf. Syst. 22, 1 (2004), 89--115. Google ScholarDigital Library
- G. C. Homans. 1950. The Human Group. Harcourt, Brace, and World, New York, NY.Google Scholar
- J. Hopcroft, T. Lou, and J. Tang. 2011. Who will follow you back?: Reciprocal relationship prediction. In Proceedings of the 20th ACM International Conference on Information and Knowledge Management. 1137--1146. Google ScholarDigital Library
- Z. Huang. 2010. Link prediction based on graph topology: The predictive value of generalized clustering coefficient. Retrieved fromGoogle Scholar
- Z. Huang and D. K. J. Lin. 2009. The time-series link prediction problem with applications in communication surveillance. INFORMS J. Comput. 21, 2 (2009), 286--303. Google ScholarDigital Library
- G. Jeh and J. Widom. 2002. SimRank: A measure of structural-context similarity. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’02). 538--543. Google ScholarDigital Library
- G. Jeh and J. Widom. 2003. Scaling personalized web search. In Proceedings of the 12th International Conference on World Wide Web (WWW’03). 271--279. Google ScholarDigital Library
- B. Jiang, Z. Zhang, and D. Towsley. 2015. Reciprocity in social networks with capacity constraints. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’15). 457--466. Google ScholarDigital Library
- I. Kahanda and J. Neville. 2009. Using transactional information to predict link strength in online social networks. In Proceedings of the 3rd International Conference on Web and Social Media (ICWSM’09). 74--81.Google Scholar
- H. Kashima and N. Abe. 2006. A parameterized probabilistic model of network evolution for supervised link prediction. In Proceedings of the 6th International Conference on Data Mining (ICDM’06). 340--349. Google ScholarDigital Library
- L. Katz. 1953. A new status index derived from sociometric analysis. Psychometrika 18, 1 (1953), 39--43.Google ScholarCross Ref
- H. H. Kelley. 1971. Attribution in social interaction. General Learning Press, New York, NY.Google Scholar
- J. G. Kemeny and J. L. Snell. 1976. Finite Markov Chains 210. Springer-Verlag, New York, NY.Google Scholar
- M. Kim and J. Leskovec. 2011. The network completion problem: inferring missing nodes and edges in networks. In Proceedings of SIAM International Conference on Data Mining. 47--58.Google Scholar
- J. M. Kleinberg. 2000. Navigation in a small world. Nature 406, 6798 (2000), 845--845.Google Scholar
- Y. Koren, R. Bell, and C. Volinsky. 2009. Matrix factorization techniques for recommender systems. Computer 42, 8 (2009), 30--37. Google ScholarDigital Library
- J. Kunegis and A. Lommatzsch. 2009. Learning spectral graph transformations for link prediction. In Proceedings of the 29th International Conference on Machine Learning (ICML’09). 561--568. Google ScholarDigital Library
- J. Kunegis, A. Lommatzsch, and C. Bauckhage. 2009. The slashdot zoo: Mining a social network with negative edges. In Proceedings of the 18th International Conference on World Wide Web. 741--750. Google ScholarDigital Library
- T. T. Kuo, R. Yan, Y. Y. Huang, P. H. Kung, and S. D. Lin. 2013. Unsupervised link prediction using aggregative statistics on heterogeneous social networks. In Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’13). 775--783. Google ScholarDigital Library
- E. A. Leicht, P. Holme, and M. E. J. Newman. 2006. Vertex similarity in networks. Phys. Rev. E 73, 2 (2006), 026120.Google ScholarCross Ref
- V. Leroy, B. B. Cambazoglu, and F. Bonchi. 2010. Cold start link prediction. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 393--402. Google ScholarDigital Library
- J. Leskovec, D. Huttenlocher, and J. Kleinberg. 2010a. Signed networks in social media. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. 1361--1370. Google ScholarDigital Library
- J. Leskovec, D. Huttenlocher, and J. Kleinberg. 2010b. Predicting positive and negative links in online social networks. In Proceedings of the 19th International Conference on World Wide Web. 641--650. Google ScholarDigital Library
- Z. Li, X. Fang, X. Bai, and O. R. Liu Sheng. 2017. Utility-based link recommendation for online social networks. Manage. Sci. 63, 6 (2017), 1938--1952.Google ScholarDigital Library
- D. Liben-Nowell and J. Kleinberg. 2007. The link prediction problem for social networks. J. Am. Soc. Inf. Sci. Technol. 58, 7 (2007), 1019--1031. Google ScholarDigital Library
- R. N. Lichtenwalter, J. T. Lussier, and N. V. Chawla. 2010. New perspectives and methods in link prediction. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’10). 243--252. Google ScholarDigital Library
- W. Liu and L. Lü. 2010. Link prediction based on local random walk. Europhys. Lett. 89, 5 (2010), 58007.Google ScholarCross Ref
- T. Lou, J. Tang, J. Hopcroft, Z. Fang, and X. Ding. 2013. Learning to predict reciprocity and triadic closure in social networks. ACM Trans. Knowl. Discov. Data, 7, 2 (2013), 5. Google ScholarDigital Library
- Z. Lu, B. Savas, W. Tang, and I. S. Dhillon. 2010. Supervised link prediction using multiple sources. In Proceedings of 10th International Conference on Data Mining (ICDM’10). 923--928. Google ScholarDigital Library
- L. Lü, C.-H. Jin, and T. Zhou. 2009. Similarity index based on local paths for link prediction of complex networks. Phys. Rev. E 80, 4, 046122.Google ScholarCross Ref
- L. Lü and T. Zhou. 2011. Link prediction in complex networks: A survey. Physica A 390, 6 (2011), 1150--1170.Google ScholarCross Ref
- F. Maccheroni, M. Marinacci, and A. Rustichini. 2012. Social decision theory: Choosing within and between groups. Rev. Econ. Stud. 79, 4 (2012), 1591--1636.Google ScholarCross Ref
- M. Makrehchi. 2011. Social link recommendation by learning hidden topics. In Proceedings of the 5th ACM Conference on Recommender Systems. 189--196. Google ScholarDigital Library
- J. M. McPherson. 1983. Ecology of affiliation. Am. Sociol. Rev. 48 (1983), 519--532.Google ScholarCross Ref
- J. M. McPherson and J. R. Ranger-Moore. 1991. Evolution on a dancing landscape: Organizations and networks in dynamic blau space. Soc. Forces 70 (1991), 19--42.Google ScholarCross Ref
- M. McPherson, L. Smith-Lovin, and J. M. Cook. 2001. Birds of a feather: Homophily in social networks. Ann. Rev. Sociol. 27 (2001), 415--444.Google ScholarCross Ref
- A. K. Menon and C. Elkan. 2011. Link prediction via matrix factorization. In Proceedings of the 2011 European Conference on Machine Learning and Knowledge Discovery in Databases. 437--452. Google ScholarDigital Library
- N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, E. Teller. 1953. Equation of state calculations by fast computing machines. J. Chem. Phys. 21 (1953), 1087.Google ScholarCross Ref
- L. Mihalkova, W. Moustafa, and L. Getoor. 2011. Learning to predict web collaborations. In Workshop on User Modeling for Web Applications.Google Scholar
- M. E. Newman. 2001. Clustering and preferential attachment in growing networks. Phys. Rev. E 64, 2 (2001), 025102.Google ScholarCross Ref
- M. E. Newman, S. H. Strogatz, and D. J. Watts. 2001. Random graphs with arbitrary degree distributions and their applications. Phys. Rev. E 64, 2 (2001), 026118.Google ScholarCross Ref
- M. E. Newman and J. Park. 2003. Why social networks are different from other types of networks. Phys. Rev. E 68, 3 (2003), 036122.Google ScholarCross Ref
- M. Nowak and K. Sigmund. 2005. Evolution of indirect reciprocity. Nature 437 (2005), 1291--1298.Google ScholarCross Ref
- J. O'Madadhain, J. Hutchins, and P. Smyth. 2005. Prediction and ranking algorithms for event-based network data. ACM SIGKDD Explor Newslett. 7, 2 (2005), 23--30. Google ScholarDigital Library
- J. Pan and Q. Yang. 2010. A survey on transfer learning. IEEE Trans. Knowl. Data Eng. 22, 10 (2010), 1345--1359. Google ScholarDigital Library
- A. Papadimitriou, P. Symeonidis, and Y. Manolopoulos. 2012. Fast and accurate link prediction in social networking systems. J. Syst. Softw. 85, 9 (2012), 2119--2132. Google ScholarDigital Library
- T. Parsons. 1938. The role of theory in social research. Am. Sociol. Rev. 3, 1 (1938), 13--20.Google ScholarCross Ref
- J. Pfeffer, G. R. Salancik, and H. Leblebici. 1976. The effect of uncertainty on the use of social influence in organizational decision making. Admin. Sci. Quart. 21, 2 (1976), 227--245.Google ScholarCross Ref
- A. Popescul and L. Ungar. 2003. Statistical relational learning for link prediction. In Proceedings of International Joint Conferences on Artificial Intelligence Workshop on Learning Statistical Models from Relational Data. 81--90.Google Scholar
- D. Quercia and L. Capra. 2009. Friendsensing: Recommending friends using mobile phones. In Proceedings of the 3rd ACM conference on Recommender Systems. 273--276. Google ScholarDigital Library
- M. J. Rattigan and D. Jensen. 2005. The case for anomalous link discovery. SIGKDD Explor. Newslett. 7, 2 (2005), 41--47. Google ScholarDigital Library
- E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai, and A. Barabási. 2002. Hierarchical organization of modularity in metabolic networks. Science 297, 5586 (2002), 1551--1555.Google Scholar
- J. Rennie and N. Srebro. 2005. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the 22nd International Conference on Machine Learning. 713--719. Google ScholarDigital Library
- G. R. Salancik and J. Pfeffer. 1978. A social information processing approach to job attitudes and task design. Admin. Sci. Quart. 224--253.Google Scholar
- G. Salton and M. J. McGill. 1986. Introduction to Modern Information Retrieval. McGraw-Hill, New York, NY. Google ScholarDigital Library
- G. Salton. 1989. Automatic Text Processing: the Transformation Analysis, and Retrieval of Information by Computer. Addison-Wesley Longman Publishing Co., Inc., Boston, MA. Google ScholarDigital Library
- S. Scellato, A. Noulas, and C. Mascolo. 2011. Exploiting place features in link prediction on location-based social networks. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’11). 1046--1054. Google ScholarDigital Library
- R. Schifanella, A. Barrat, C. Cattuto, B. Markines, and F. Menczer. 2010. Folks in folksonomies: Social link prediction from shared metadata. In Proceedings of the 3rd ACM International Conference on Web Search and Data Mining (WSDM’10). 271--280. Google ScholarDigital Library
- D. Shen, J. Sun, Q. Yang, and Z. Chen. 2006. Latent friend mining from blog data. In Proceedings of IEEE 6th International Conference on Data Mining (ICDM’06). 552--561. Google ScholarDigital Library
- D. Shin, S. Si, and I. S. Dhillon. 2012. Multi-scale link prediction. In Proceedings of the 21st ACM International Conference on Information and Knowledge Management. 215--224. Google ScholarDigital Library
- A. Singhal, K. Subbian, J. Srivastava, T. Kolda, and A. Pinar. 2013. Dynamics of trust reciprocation in multi-relational networks. In Proceedings of the IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM’13). 661--665. Google ScholarDigital Library
- D. Song, A. Meyer, and D. Tao. 2015. Efficient latent link recommendation in signed networks. In Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’15). 1105--1114. Google ScholarDigital Library
- H. H. Song, T. W. Cho, V. Dave, Y. Zhang, and L. Qiu. 2009. Scalable proximity estimation and link prediction in online social networks. In Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement Conference. 322--335. Google ScholarDigital Library
- D. Song, D. A. Meyer, and D. Tao. 2015. Efficient latent link recommendation in signed networks. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’15). 1105--1114. Google ScholarDigital Library
- T. Sørensen. 1948. A method of establishing groups of equal amplitude in plant sociology based on similarity of species and its application to analyses of the vegetation on danish commons. Biol. Skr. 5 (1948), 1--34.Google Scholar
- P. Symeonidis, E. Tiakas, and Y. Manolopoulos. 2010. Transitive node similarity for link prediction in social networks with positive and negative links. In Proceedings of the 4th ACM Conference on Recommender Systems 183--190. Google ScholarDigital Library
- J. Tang, S. Chang, C. Aggarwal, and H. Liu. 2015. Negative link prediction in social media. In Proceedings of the Eighth ACM International Conference on Web Search and Data Mining (WSDM’15). 87--96. Google ScholarDigital Library
- J. Tang, T. Lou, J. Kleinberg, and S. Wu. 2015a. Transfer learning to infer social ties across heterogeneous networks. ACM Trans. Inf. Syst. 34, 3, Article 1 (December 2015). Google ScholarDigital Library
- T. Tanizawa, G. Paul, R. Cohen, S. Havlin, and H. E. Stanley. 2005. Optimization of network robustness to waves of targeted and random attacks. Phys. Rev. E 71, 4 (2005), 047101.Google ScholarCross Ref
- T. Taskar, M. F. Wong, P. Abbeel, and D. Koller. 2003. Link prediction in relational data. In Proceedings of Advances in Neural Information Processing Systems. 659--666. Google ScholarDigital Library
- H. Tong, C. Faloutsos, and J. Y. Pan. 2006. Fast random walk with restart and its applications. In Proceedings of the 6th IEEE International Conference on Data Mining (ICDM’06). 613--622. Google ScholarDigital Library
- J. Ugander, L. Backstrom, C. Marlow, and J. Kleinberg. 2012. Structural diversity in social contagion. Proc. Natl. Acad. Sci. U.S.A. 109, 16 (2012), 5962--5966.Google ScholarCross Ref
- S. Vargas and P. Castells. 2011. Rank and relevance in novelty and diversity metrics for recommender systems. In Proceedings of the 5th ACM Conference on Recommender Systems. 109--116. Google ScholarDigital Library
- D. J. Watts and S. H. Strogatz. 1998. Collective dynamics of ‘small world’ networks. Nature 393, 6684 (1998), 440--442.Google Scholar
- S. Wasserman and K. Faust. 1994. Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, UK.Google Scholar
- C. Wang, V. Satuluri, and S. Parthasarathy. 2007. Local probabilistic models for link prediction. In Proceedings of 7th IEEE International Conference on Data Mining (ICDM’07). 322--331. Google ScholarDigital Library
- D. Wang, D. Pedreschi, C. Song, F. Giannotti, and A. L. Barabasi. 2011. Human mobility, social ties, and link prediction. In Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’11). 1100--1108. Google ScholarDigital Library
- R. Xiang, J. Neville, and M. Rogati. 2010. Modeling relationship strength in online social networks. In Proceedings of the 19th International Conference on World Wide Web (WWW’10). 981--990. Google ScholarDigital Library
- Y. Xu and D. Rockmore. 2012. Feature selection for link prediction. In Proceedings of the 5th Ph.D. ACM Workshop on Information and Knowledge. 25--32. Google ScholarDigital Library
- Y. Xu, N. Chen, A. Fernandez, O. Sinno, and A. Bhasin. 2015. From infrastructure to culture: A/B testing challenges in large scale social networks. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2227--2236. Google ScholarDigital Library
- S. H. Yang, B. Long, A. Smola, N. Sadagopan, Z. Zheng, and H. Zha. 2011. Like like alike: Joint friendship and interest propagation in social networks. In Proceedings of the 20th International Conference on World Wide Web (WWW’11). 537--546. Google ScholarDigital Library
- S. Yang, A. Smola, B. Long, H. Zha, and Y. Chang. 2012. Friend or frenemy? predicting signed ties in social networks. In Proceedings of the 35th ACM SIGIR Conference on Research and Development in Information Retrieval. 555--564. Google ScholarDigital Library
- J. Ye, H. Cheng, Z. Zhu, and M. Chen. 2013. Predicting positive and negative links in signed social networks by transfer learning. In Proceedings of the 22nd International Conference on World Wide Web. 1477--1488. Google ScholarDigital Library
- Z. Yin, M. Gupta, T. Weninger, and J. Han. 2010. A unified framework for link recommendation using random walks. In Proceedings of the 2010 International Conference on Advances in Social Networks Analysis and Mining. 152--159. Google ScholarDigital Library
- K. Yu, W. Chu, S. Yu, T. Volker, and Z. Xu. 2006. Stochastic relational models for discriminative link prediction. Adv. Neur. Inf. Process. Syst. P. B. Schölkopf, J. C. Platt, and T. Hoffman (Eds.). MIT Press. 333--340. Google ScholarDigital Library
- G. Yuan, P. K. Murukannaiah, Z. Zhang, and M. P. Singh. 2014. Exploiting sentiment homophily for link prediction. In Proceedings of the 8th ACM Conference on Recommender Systems. 17--24. Google ScholarDigital Library
- M. Zhang and N. Hurley. 2008. Avoiding monotony: Improving the diversity of recommendation lists. In Proceedings of ACM Conference on Recommender Systems. 123--130. Google ScholarDigital Library
- J. Zhang, P. S. Yu, and Z. H. Zhou. 2014. Meta-path based multi-network collective link prediction. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD’14). 1286--1295. Google ScholarDigital Library
- K. Zhao, X. Wang, M. Yu, and B. Gao. 2014. User recommendations in reciprocal and bipartite social networks: An online dating case study. IEEE Intell. Syst. 29, 2 (2014), 27--35.Google ScholarCross Ref
- E. Zheleva, L. Getoor, J. Golbeck, and U. Kuter. 2008. Using friendship ties and family circles for link prediction. In Proceedings of the 2nd International Conference on Advances in Social Network Mining and Analysis. Springer-Verlag, Berlin, 97--113. Google ScholarDigital Library
- T. Zhou, L. Lü, and Y. Zhang. 2009. Predicting missing links via local information. Eur. Phys. J B 71, 4 (2009), 623--630.Google ScholarCross Ref
Index Terms
- A Survey of Link Recommendation for Social Networks: Methods, Theoretical Foundations, and Future Research Directions
Recommendations
Link Recommendation for Social Influence Maximization
Social link recommendation systems, like “People-you-may-know” on Facebook, “Who-to-follow” on Twitter, and “Suggested-Accounts” on Instagram assist the users of a social network in establishing new connections with other users. While these systems are ...
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 ...
Utility-Based Link Recommendation for Online Social Networks
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 ...
Comments