Similarity Index based Link Prediction Algorithms in Social Networks: A Survey

• Autorzy: Srilatha P. , Manjula R.
• Języki publikacji: EN

Abstrakty

EN

Social networking sites have gained much popularity in the recent years. With millions of people connected virtually generate loads of data to be analyzed to infer meaningful associations among links. Link prediction algorithm is one such problem, wherein existing nodes, links and their attributes are analyzed to predict the possibility of potential links, which are likely to happen over a period of time. In this survey, the local structure based link prediction algorithms existing in literature with their features and also the possibility of future research directions is reported and discussed. This survey serves as a starting point for beginners interested in understanding link prediction or similarity index algorithms in general and local structure based link prediction algorithms in particular.

Słowa kluczowe

EN

link prediction; similarity based link prediction; similarity index; social network analysis

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2016
• Tom: nr 2
• Strony: 87--94
• Opis fizyczny: Bibliogr. 70 poz., rys., tab.

Twórcy

autor

Srilatha P.

• School of Computer Science & Engineering (SCOPE), VIT University, Vellore, Tamil Nadu, India

autor

Manjula R.

• School of Computer Science & Engineering (SCOPE), VIT University, Vellore, Tamil Nadu, India

Bibliografia

• [1] J. Scott, Social Network Analysis. Sage, 2012.
• [2] Z. Huang and D. K. Lin, “The time-series link prediction problem with applications in communication surveillance”, INFORMS J. Comput., vol. 21, no. 2, pp. 286–303, 2009.
• [3] K. Jahanbakhsh, V. King, and G. C. Shoja, “Predicting missing contacts in mobile social networks”, Pervas. & Mob. Comput., vol. 8, no. 5, pp. 698–716, 2012.
• [4] R. Guimerà and M. Sales-Pardo, “Missing and spurious interactions and the reconstruction of complex networks”, Proceedings of the National Academy of Sciences (PNAS), vol. 106, no. 52, pp. 22073–22078, 2009.
• [5] E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing, “Mixed membership stochastic block models for relational data with application to protein-protein interactions”, in Proc. Int. Biometrics Society Annual Meeting ENAR 2006, Tampa, FL, USA, 2006.
• [6] U. M. Singh-Blom, N. Natarajan, A. Tewari, J. O. Woods, I. S. Dhillon, and E. M. Marcotte, “Prediction and validation of gene-disease associations using methods inspired by social network analyses”, J. PLOS One, vol. 8, no. 9, 2013.
• [7] S. Milgram, “The small world problem”, Psychology Today, vol. 2, no. 1, pp. 60–67, 1967.
• [8] S. Goel, R. Muhamad, and D. Watts, “Social search in small-world experiments”, in Proc. 18th Int. Conf. World Wide Web WWW’09, Madrid, Spain, 2009, pp. 701–710.
• [9] Y. Sun, R. Barber, M. Gupta, C. C. Aggarwal, and J. Han, “Coauthor relationship prediction in heterogeneous bibliographic networks”, in Proc. Int. Conf. Adv. Social Netw. Anal. Mining ASONAM 2011, Kaohsiung, Taiwan, 2011, pp. 121–128.
• [10] M. E. Newman, “The structure and function of complex networks”, SIAM Rev., vol. 45, no. 2, pp. 167–256, 2003.
• [11] Z. Yin, M. Gupta, T. Weninger, and J. Han, “Linkrec: a unified framework for link recommendation with user attributes and graph structure”, in Proc. 19th Int. Conf. World Wide Web WWW’10, Raleigh, NC, USA, 2010, pp. 1211–1212.
• [12] U. Shardanand and P. Maes, “Social information filtering: algorithms for automating «Word of Mouth»”, in Proc. SIGCHI Conf. Human Fact Comput. Syst. CHI’95, Denver, CO, USA, 1995, pp. 210–217.
• [13] S. Hill, F. Provost, and C. Volinsky, “Network-based marketing: identifying likely adopters via consumer networks”, Statistical Sci., vol. 21, no. 2, pp. 256–276, 2006.
• [14] D. Liben-Nowell and J. Kleinberg, “The link-prediction problem for social networks”, J. American Soc. for Inform. Sci. & Technol., vol. 58, no. 7, pp. 1019–1031, 2007.
• [15] X. Li and H. Chen, “Recommendation as link prediction in bipartite graphs: a graph kernel-based machine learning approach”, Decision Support Syst., vol. 54, no. 2, pp. 880–890, 2013.
• [16] F. Ricci, L. Rokach, and B. Shapira, Introduction to Recommender Systems Handbook. Springer, 2011.
• [17] L. Lü, M. Medo, C. H. Yeung, Y.-C. Zhang, Z.-K. Zhang, and T. Zhou, “Recommender systems”, Phys. Reports, vol. 519, no. 1, pp. 1–49, 2012.
• [18] A. Zeng and G. Cimini, “Removing spurious interactions in complex networks”, Phys. Rev. E, vol. 85, no. 3, article ID 036101, 2012.
• [19] S. Garriss, M. Kaminsky, M. J. Freedman, B. Karp, D. Mazières, and H. Yu, “Re: Reliable email”, in Proc. 3rd Symp. Netw. Syst. Design & Implement. NSDI’06, San Jose, CA, USA, 2006, vol. 6, pp. 22–22.
• [20] H. Yu, M. Kaminsky, P. B. Gibbons, and A. Flaxman, “Sybilguard: defending against sybil attacks via social networks”, ACM SIGCOMM Comp. Commun. Rev., vol. 36, no. 4, pp. 267–278, 2006.
• [21] L. Lü and T. Zhou, “Link prediction in complex networks: A survey”, Physica A: Statist. Mechan. & its Appl., vol. 390, no. 6, pp. 1150–1170, 2011.
• [22] T. Zhou, L. Lü, and Y.-C. Zhang, “Predicting missing links via local information”, The Eur. Phys. J. B, vol. 71, no. 4, pp. 623–630, 2009.
• [23] M. Girvan and M. E. Newman, “Community structure in social and biological networks”, Proceedings of the National Academy of Sciences (PNAS), vol. 99, no. 12, pp. 7821–7826, 2002.
• [24] R. Guimera, M. Sales-Pardo, and L. A. Amaral, “Classes of complex networks defined by role-to-role connectivity profiles”, Nature Phys., vol. 3, no. 1, pp. 63–69, 2007.
• [25] L. Getoor, N. Friedman, D. Koller, and A. Pfeffer, “Learning probabilistic relational models”, in Relational Data Mining, S. Dˇzeroski and N. Lavraˇc, Eds. Springer, 2001, pp. 307–335.
• [26] R. R. Sarukkai, “Link prediction and path analysis using Markov chains”, Computer Networks, vol. 33, no. 1, pp. 377–386, 2000.
• [27] P. Sarkar and A. Moore, “A tractable approach to finding closest truncated-commute-time neighbors in large graphs”, in Proc. 23rd Conf. Uncertainty in Artif. Intellig. UAI 2007, Vancouver, BC, Canada, 2007 (arXiv preprint arXiv:1206.5259, 2012).
• [28] D. Heckerman, C. Meek, and D. Koller, “Probabilistic entityrelationship models, PRMs, and plate models”, in Introduction to Statistical Relational Learning, L. Getoor and B. Taskar, Eds. MIT Press, 2007, pp. 201–239.
• [29] H. Kashima and N. Abe, “A parameterized probabilistic model of network evolution for supervised link prediction”, in Proc. 6th Int. Conf. Data Mining ICDM 2006, Honk Kong, China, 2006, pp. 340–349.
• [30] C.Wang, V. Satuluri, and S. Parthasarathy, “Local probabilistic models for link prediction”, in Proc. 7th Int. Conf. Data Mining ICDM 2007, Omaha, NE, USA, 2007, pp. 322–331.
• [31] L. Lü and T. Zhou, “Link prediction in weighted networks: The role of weak ties”, Europhys. Lett. (EPL), vol. 89, no. 1, pp. 18001-p1– 18001-p6, 2010.
• [32] J. Zhao, L. Miao, J. Yang, H. Fang, Q.-M. Zhang, M. Nie, P. Holme, and T. Zhou, “Prediction of links and weights in networks by reliable routes”, Scientific Reports, vol. 5, article no. 12261, 2015.
• [33] N. Sett, S. R. Singh, and S. Nandi, “Influence of edge weight on node proximity based link prediction methods: An empirical analysis”, Neurocomputing, vol. 172, pp. 71–83, 2016.
• [34] F. Lorrain and H. C. White, “Structural equivalence of individuals in social networks”, The J. Mathem. Sociol., vol. 1, no. 1, pp. 49–80, 1971.
• [35] H. Liao, A. Zeng, and Y.-C. Zhang, “Predicting missing links via correlation between nodes”, Physica A: Statist. Mechan. & its Appl., vol. 436, pp. 216–223, 2015.
• [36] Z. Zhang, Y. Liu, W. Ding, W. W. Huang, Q. Su, and P. Chen, “Proposing a new friend recommendation method, frutai, to enhance social media providers’ performance”, Decision Support Syst., vol. 79, pp. 46–54, 2015.
• [37] M. E. Newman, “Clustering and preferential attachment in growing networks”, Phys. Rev. E, vol. 64, no. 2, article ID: 025102, 2001.
• [38] G. Kossinets, “Effects of missing data in social networks”, Social Networks, vol. 28, no. 3, pp. 247–268, 2006.
• [39] G. Salton and M. J. McGill, Introduction to Modern Information Retrieval. New York: McGraw-Hill, 1986.
• [40] A. Rodriguez, B. Kim, M. Turkoz, J.-M. Lee, B.-Y. Coh, and M. K. Jeong, “New multi-stage similarity measure for calculation of pairwise patent similarity in a patent citation network”, Sciento- metrics, vol. 103, no. 2, pp. 565–581, 2015.
• [41] P. Jaccard, “Etude comparative de la distribution florale dans une portion des Alpes et des Jura”, Bulletin del la Soci´et´e Vaudoise des Sciences Naturelles, vol. 37, pp. 547–579, 1901 (in French).
• [42] H. Liao and A. Zeng, “Reconstructing propagation networks with temporal similarity”, Scientific Reports, vol. 5, article no. 11404, 2015.
• [43] T. J. Sørensen, A Method of Establishing Groups of Equal Amplitude in Plant Sociology Based on Similarity of Species Content and its Application to Analyses of the Vegetation on Danish Commons. Biologiske skrifter, Kongelige Danske videnskabernes selskab. København: I kommission hos E. Munksgaard, 1948.
• [44] E. Ravasz, A. L. Somera, D. A. Mongru, Z. N. Oltvai, and A.-L. Barabási, “Hierarchical organization of modularity in metabolic networks”, Science, vol. 297, no. 5586, pp. 1551–1555, 2002.
• [45] Y.-L. He, J. N. Liu, Y.-X. Hu, and X.-Z. Wang, “OWA operator based link prediction ensemble for social network”, Expert Syst. with Appl., vol. 42, no. 1, pp. 21–50, 2015.
• [46] E. Leicht, P. Holme, and M. E. Newman, “Vertex similarity in networks”, Phys. Rev. E, vol. 73, no. 2, article ID: 026120, 2006.
• [47] Z. Huang, X. Li, and H. Chen, “Link prediction approach to collaborative filtering”, in Proc. 5th ACM/IEEE-CS Joint Conf. Digit. Librar., Denver, CO, USA, 2005, pp. 141–142.
• [48] A.-L. Barabási and R. Albert, “Emergence of scaling in random networks”, Science, vol. 286, no. 5439, pp. 509–512, 1999.
• [49] A.-L. Barabási, H. Jeong, Z. Néda, E. Ravasz, A. Schubert, and T. Vicsek, “Evolution of the social network of scientific collaborations”, Physica A: Statist. Mechan. & its Appl., vol. 311, no. 3, pp. 590–614, 2002.
• [50] L. A. Adamic and E. Adar, “Friends and neighbors on the Web”, Social Networks, vol. 25, no. 3, pp. 211–230, 2003.
• [51] L. Katz, “A new status index derived from sociometric analysis”, Psychometrika, vol. 18, no. 1, pp. 39–43, 1953.
• [52] A. Chartsias, “Link prediction in large scale social networks using hadoop”, PhD thesis, Technical University of Crete, Greece, 2010.
• [53] T. White, Hadoop: The Definitive Guide, 3rd ed. O’Reilly Media, 2012.
• [54] K.-H. Lee, Y.-J. Lee, H. Choi, Y. D. Chung, and B. Moon, “Parallel data processing with MapReduce: a survey”, ACM SIGMOD Record, vol. 40, no. 4, pp. 11–20, 2012.
• [55] J.-Y. Pan, H.-J. Yang, C. Faloutsos, and P. Duygulu, “Automatic multimedia cross-modal correlation discovery”, in Proc. 10th ACM SIGKDD Int. Conf. Knowl. Discov. & Data Mining KDD’04, Seattle, WA, USA, 2004, pp. 653–658.
• [56] G. Jeh and J. Widom, “Simrank: a measure of structural-context similarity”, in Proc. 8th ACM SIGKDD Int. Conf. Knowl. Discov. & Data Mining KDD’02, Edmonton, AB, Canada, 2002, pp. 538–543.
• [57] J. Sun, H. Qu, D. Chakrabarti, and C. Faloutsos, “Neighborhood formation and anomaly detection in bipartite graphs”, in Proc. 5th IEEE Int. Conf. Data Mining ICDM’05, Houston, TX, USA, 2005, pp. 418–425.
• [58] S. Brin and L. Page, “Reprint of: The anatomy of a large-scale hypertextual web search engine”, Computer Networks, vol. 56, no. 18, pp. 3825–3833, 2012.
• [59] W. Liu and L. Lü, “Link prediction based on local random walk”, Europhys. Lett. (EPL), vol. 89, no. 5, article ID: 58007, 2010.
• [60] W. Yu, X. Lin, W. Zhang, and J. McCann, “Fast all-pairs simrank assessment on large graphs and bipartite domains”, IEEE Trans. Knowl. & Data Engin., vol. 27, no. 7, pp. 1810–1823, 2015.
• [61] P. G. Doyle and J. L. Snell, Random Walks and Electric Networks, The Carus Mathematical Monographs no. 22. Mathema Association of America, 1984.
• [62] H. Tong, C. Faloutsos, and Y. Koren, “Fast direction-aware proximity for graph mining”, in Proc. 13th ACM SIGKDD Int. Conf. Knowl. Discov. & Data Mining KDD’07, San Jose, CA, USA, 2007, pp. 747–756.
• [63] H. H. Song, T. W. Cho, V. Dave, Y. Zhang, and L. Qiu, “Scalable proximity estimation and link prediction in online social networks”, in Proc. 9th ACM SIGCOMM Conf. Internet Measur. Conf. IMC 2009, Chicago, IL, USA, 2009, pp. 322–335.
• [64] L. Lü, C.-H. Jin, and T. Zhou, “Similarity index based on local paths for link prediction of complex networks”, Phys. Rev. E, vol. 80, no. 4, article ID: 046122, 2009.
• [65] X. Wang, X. Zhang, C. Zhao, Z. Xie, S. Zhang, and D. Yi, “Predicting link directions using local directed path”, Physica A: Statist. Mechan. & its Appl., vol. 419, pp. 260–267, 2015.
• [66] A. Papadimitriou, P. Symeonidis, and Y. Manolopoulos, “Fast and accurate link prediction in social networking systems”, J. Syst. & Softw., vol. 85, no. 9, pp. 2119–2132, 2012.
• [67] Y. Dong, C. Robinson, and J. Xu, “Hadoop based link prediction performance analysis”.
• [68] M. Fire, L. Tenenboim, O. Lesser, R. Puzis, L. Rokach, and Y. Elovici, “Link prediction in social networks using computationally efficient topological features”, in Proc. 3rd IEEE Int. Conf. on Priv., Secur., Risk and Trust and 3rd IEEE Int. Conf. on Social Comput. PASSAT/SocialCom 2011, Boston, MA, USA, 2011, pp. 73–80.
• [69] S. Soundarajan and J. Hopcroft, “Using community information to improve the precision of link prediction methods”, in Proc. 21st Int. Conf. Companion on World Wide Web WWW 2012, Lyon, France, 2012, pp. 607–608.
• [70] V. D. Blondel, J.-L. Guillaume, R. Lambiotte, and E. Lefebvre, “Fast unfolding of communities in large networks”, J. Statist. Mechanics: Theory and Experim., vol. 2008, no. 10, p. P10008, 2008.