Node Classification in Social Network by Distributed Learning Automata
Subject Areas : Data MiningAhmad Rahnama Zadeh 1 , meybodi meybodi 2 * , Masoud Taheri Kadkhoda 3
1 - Qazvin Branch, Islamic Azad University, Qazvin, Iran
2 -
3 - Qazvin Branch, Islamic Azad University, Qazvin, Iran
Keywords: Social Network, , Classification, , Distributed Learning Automata, , Node Labeling.,
Abstract :
The aim of this article is improving the accuracy of node classification in social network using Distributed Learning Automata (DLA). In the proposed algorithm using a local similarity measure, new relations between nodes are created, then the supposed graph is partitioned according to the labeled nodes and a network of Distributed Learning Automata is corresponded on each partition. In each partition the maximal spanning tree is determined using DLA. Finally nodes are labeled according to the rewards of DLA. We have tested this algorithm on three real social network datasets, and results show that the expected accuracy of presented algorithm is achieved.
[1] J. Neville and D. Jensen, "Iterative classification in relational data," in Proc. AAAI-2000 Workshop on Learning Statistical Models from Relational Data, 2000, pp. 13-20.
[2] S. A. Macskassy and F. Provost, "A simple relational classifier," DTIC Document2003.
[3] S. Bhagat, I. Rozenbaum, and G. Cormode, "Applying link-based classification to label blogs," in Proceedings of the 9th WebKDD and 1st SNA-KDD 2007 workshop on Web mining and social network analysis, 2007, pp. 92-101.
[4] S. Chakrabarti, B. E. Dom, and P. Indyk, "Enhanced hypertext categorization using hyperlinks," ed: Google Patents, 2002.
[5] X. Zhu, Z. Ghahramani, and J. Lafferty, "Semi-supervised learning using gaussian fields and harmonic functions," in ICML, 2003, pp. 912-919.
[6] M. S. T. Jaakkola and M. Szummer, "Partially labeled classification with Markov random walks," Advances in neural information processing systems (NIPS), vol. 14, pp. 945-952, 2002.
[7] Y. Zhou, H. Cheng, and J. X. Yu, "Graph clustering based on structural/attribute similarities," Proceedings of the VLDB Endowment, vol. 2, pp. 718-729, 2009.
[8] J. Kleinberg and E. Tardos, "Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields," Journal of theACM (JACM), vol. 49, pp. 616-639, 2002.
[9] F. McSherry, "Spectral partitioning of random graphs," in Foundations of Computer Science, 2001. Proceedings. 42nd IEEE Symposium on, 2001, pp. 529-537.
[10] A.B.Goldberg, X. Zhu, and S. J. Wright, "Dissimilarity in graph-based semi-supervised classification," in International Conference on Artificial Intelligence and Statistics, 2007, pp. 155-162.
[11] J. Leskovec, D. Huttenlocher, and J. Kleinberg, "Predicting positive and negative links in online social networks," in Proceedings of the 19th international conference on World wide web, 2010, pp. 641-650.
[12] A. Goyal, F. Bonchi, and L. V. Lakshmanan, "Learning influence probabilities in social networks," in Proceedings of the third ACM international conference on Web search and data mining, 2010, pp. 241-250.
[13] X. Xu, L. Lu, P. He, Y. Ma, Q. Chen, and L. Chen, "Semi-supervised classification with multiple ants maximal spanning tree," in Web Intelligence (WI) and Intelligent Agent Technologies (IAT), 2013 IEEE/WIC/ACM International Joint Conferences on, 2013, pp. 315-320.
[14] H. Xu, Y. Yang, L. Wang, and W. Liu, "Node classification in social network via a factor graph model," in Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2013, pp. 213-224.
[15] H. Beigy and M. R. Meybodi, "Utilizing distributed learning automata to solve stochastic shortest path problems," International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, vol. 14, pp. 591-615, 2006.
[16] M. Al Hasan and M. J. Zaki, "A survey of link prediction in social networks," in Social network data analytics, ed: Springer, 2011, pp. 243-275.
[17] C. A. Bliss, M. R. Frank, C. M. Danforth, and P. S. Dodds, "An evolutionary algorithm approach to link prediction in dynamic social networks," Journal of Computational Science, vol. 5, pp. 750-764, 2014.
[18] L. Adamic and E. Adar, "How to search a social network," Social networks, vol. 27, pp. 187-203, 2005.
[19] Y.-X. Zhu, L. Lü, Q.-M. Zhang, and T. Zhou, "Uncovering missing links with cold ends," Physica A: Statistical Mechanics and its Applications, vol. 391, pp. 5769-5778, 2012.
[20] W. Cukierski, B. Hamner, and B. Yang, "Graph-based features for supervised link prediction," in Neural Networks (IJCNN), The 2011 International Joint Conference on, 2011, pp. 1237-1244.
[21] E. Zheleva and L. Getoor, "To join or not to join: the illusion of privacy in social networks with mixed public and private user profiles," in Proceedings of the 18th international conference on World wide web, 2009, pp. 531-540.