A Type-2 Fuzzy Model for Link Prediction in Social Network

Authors: Mansoureh Naderipour, Susan Bastani, Mohammad Fazel Zarandi

Abstract:

Predicting links that may occur in the future and missing links in social networks is an attractive problem in social network analysis. Granular computing can help us to model the relationships between human-based system and social sciences in this field. In this paper, we present a model based on granular computing approach and Type-2 fuzzy logic to predict links regarding nodes’ activity and the relationship between two nodes. Our model is tested on collaboration networks. It is found that the accuracy of prediction is significantly higher than the Type-1 fuzzy and crisp approach.

Keywords: Social Network, link prediction, granular computing, Type-2 fuzzy sets.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1126401

References:

[1] H.R. Sa and R.B.C. Prudencio, “Supervised learning for link prediction in weighted networks. In: 2011 Int Joint Conf on Neural Networks (IJCNN),” 2010.
[2] S. Wasserman and J. Galaskiewicz, “Advances in social network analysis: Research in the social and behavioral sciences,” Thousand Oaks, CA: Sage, 1994.
[3] S. Boccaletti, V. Latora, Y. Moreno, M. Chavez and D.U. Hwang, “Complex networks: Structure and dynamics,” Physical Review E, Vol. 424(4), 2006, pp. 175–308.
[4] S. Wasserman and K. Faust, “Social network analysis: Methods and applications. New York: Cambridge University Press,” 1994.
[5] M.E.J. Newman and J. Park, “Why social networks are different from other types of networks,” Physical Review E, Vol. 68, 2003, pp. 036122.
[6] J. Scott, “Social network analysis: A handbook,” Thousand Oaks, CA: Sage, 2000.
[7] L. Backstrom and J. Leskovec, “Supervised random walks: Predicting and recommending links in social networks,” New York ACM, 2011.
[8] L. Lu, T. Zhou, “Link prediction in complex networks: A survey,” Phys A, Vol. 390(6), 2011, pp. 1150–1170.
[9] S. Bastani, A. KhaliliJafarabad and M.H. Fazel Zarandi, “Fuzzy Models for Link Prediction in Social Networks,” International Journal of Intelligent Systems, Vol. 28, 2013, pp. 768–786.
[10] J. M. Mendel, R. I. B. John, “Type-2 Fuzzy Sets Made Simple,” IEEE Transactions on Fuzzy Systems, Vol. 10(2), April 2002
[11] L.A. Zadeh, “Fuzzy sets,” Inform Control, Vol. 8(3), 1965, pp. 338–353.
[12] J.M. Mendel, “Computing with words and its relationships with fuzzistics,” Information Sciences, Vol. 77(4), 2007, pp. 988–1006.
[13] L. A. Zadeh, “The concept of a linguistic variable and its application to approximate reasoning,” Information Sciences, Vol. 8, 1975, pp. 43–80.
[14] D. Hidalgo, P. Melin and O. Castillo, “An optimization method for designing type-2 fuzzy inference systems based on the footprint of uncertainty using genetic algorithms,” Expert Systems with Applications, Vol. 39, 2012, pp. 4590–4598.
[15] J.M. Mendel, “Uncertain rule-based fuzzy logic systems introduction and new directions,” Prentice Hall, 2001a.
[16] C. Bettstetter, “On the minimum node degree and connectivity of awireless multihop network,” In: MobiHoc ’02, Proc 3rd ACM IntSymp on Mobile Ad-Hoc Networking & Computing, 2002.
[17] L.A. Zadeh, “Toward a theory of fuzzy information granulation and its centrality in human reasoning and fuzzy logic,” Fuzzy Sets Syst, Vol. 90(2), 2013, pp. 111-127.
[18] A. Bargiela and W. Pedrycz, “Granular computing: an introduction”. Berlin: Springer; 2003.
[19] M. McPherson, L. Smith-Lovin and J.M Cook, “Birds of a feather: Homophily in social networks,” Annual Review of Sociology, Vol. 27, 2001, pp. 415-444.
[20] J. Saramaki, M. Kivela, J.P. Onnela, K. Kaski and J. Kertesz, “Generalizations of the clustering coefficient to weighted complex networks,” Physical Review E, Vol. 75(2), 2007, pp. 027105.
[21] D. LibenNowell and J. Kleinberg, “The link prediction problem for social networks,” American Society for Information Science and Technology, Vol. 58(7), 2007, pp. 1019-1031.
[22] A. Clauset, C. Moore and M.E. Newman, “Hierarchical structure and the prediction of missing links in networks,” Nature, Vol. 453(7191), 2008, pp. 98–101.
[23] A. Blum, T.H. Chan and M.R. Rwebangira, “A random-surfer web-graph model”, In: ANALCO ‘06, Proc Eigth Workshop on Algorithm Engineering and Experiments and the Third Workshop on Analytic Algorithmics and Combinatorics,2006, pp. 238–246.
[24] M. Mukherjee and L.B. Holder, “Graph-based data mining on social networks,” In: Workshop on Link Analysis and Group Detection (in conjunction with KDD), 2004.
[25] L. Lu and T. Zhou, “Link prediction in weighted networks: The role of weak ties,” Europhys Lett, Vol. 89(1), 2010, pp. 18001.
[26] A.M. Tang, C. Quek and G.S. Ng, “GA-TSK fnn: Parameters tuning of Fuzzy Neural Network using Genetic Algorithms,” Expert System with Applications, Vol. 29(4), 2005, pp. 769–781.
[27] L.A. Zadeh, “Fuzzy Logic=Computing with Words,” IEEE Transactions on Fuzzy Systems, Vol. 4(2), 2005, pp. 103.
[28] Z. Huang, X. Li and H. Chen, “Link prediction approach to collaborative filtering. In: Proc 5th ACM/IEEE-CS Joint Conf on Digital Libraries,” New York: ACM, 2005, pp. 141-142.
[29] G. Palla, I. Derenyi, s.I. Farka and T. Vicsek, “Uncovering the overlapping community structure of complex networks in nature and society,” Nature, Vol. 435(7043), 2005, pp. 814-818.
[30] S. Zhang, R.S. Wang andX.S. Zhang, “Identification of overlapping community structure in complex networks using fuzzy c-means clustering,” Physica A, Vol. 374(1), 2007, pp. 483–490.
[31] N. Mishra, R. Schreiber, I. Stanton and R.E. Tarjan, “Finding strongly knit clusters in social networks,” Internet Math, Vol. 5(1–2), 2008, pp. 155–174.
[32] M. Brunelli and M. Fedrizzi, “A fuzzy approach to social network analysis,” 2009.
[33] R.R. Yager, “Intelligent social network analysis using granular computing,” International Journal of Intelligent Systems, Vol. 23(11), 2008, pp. 1197-1219.
[34] D. Watts and S. Strogatz, “Collective dynamics of small-world networks,” Nature, Vol. 393(6684), 1998, pp. 440–442.
[35] S. Milgram, “The small world problem,” Psychol Today, Vol. 2(1), 1967, pp. 60-67.
[36] J.M. Mendel, “Advances in Type-2 fuzzy sets and systems,” Information Sciences, Vol. 177, 2007, pp. 84-110.
[37] M.E.J. Newman, “Finding community structure in networks using the Eigenvectors of matrices,” Physical Review E, Vol. 74(3), 2007, pp. 036104.