ارائه روشی بهبودیافته در شبکه های اجتماعی جهت پیش بینی پیوند در شبکه های چندلایه

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشگاه باراجین قزوین

2 دانشگاه قزوین

چکیده

تجزیه و تحلیل شبکه­های مقیاس بزرگ پویا، اطلاعات مفیدی دراختیارمدیر شبکه قرارمی­دهد. پیش­بینی ارتباطات مفقود شده یا پیوندهای احتمالی که در آینده ممکن است وجود داشته باشند یک مساله مهم و جالب در شبکه­های اجتماعی می­باشد. در بسیاری از شبکه­های اجتماعی واقعی، ارتباطات را در چند لایه می­توان مدل‌سازی کرد. دراین مقاله، مسئله پیش­بینی پیوند در شبکه­های چندلایه مورد بررسی قرار گرفته است. در این مقاله، روش جدید پیش‌بینی پیوند در شبکه­های مالتی‌پلکس مبتنی بر الگوریتم­های مبتنی بر ساختار گراف و بدون ناظر مبتنی بر الگوریتم جستجوی گرانشی ارائه گردیده و از لایه­های مختلف در شبکه مالتی پلکس، جهت افزایش دقت، صحت و عملکرد الگوریتم پیش­بینی استفاده شده است. با انتخاب موثر معیارهای درون لایه­ای و بین لایه­ای مثل امتیاز انجمن­ها و انتساب عامل­ها به آن­ها از محورهای معماری پیشنهادی روشی ارائه‌شده، که بر کار­آیی و سرعت پاسخ موردنیاز اثر دارد. برای مقایسه کار پیشنهادی از معیار AUC استفاده گردیده. واز مجموعه دادهtravian  به‌عنوان مجموعه محک استفاده شده است. AUC محاسبه شده پیشنهادی 72/0 است. نتایج نشان می­دهد که استفاده از اطلاعات انجمنی با استفاده از الگوریتم گرانشی در شبکه­های چندلایه به بهبود فرآیند پیش­بینی پیوند کمک می­کند.

کلیدواژه‌ها


عنوان مقاله [English]

An Improved New Link Prediction Method in Social Multilplex Networks Based on the Gravitational Search Algorithm

نویسندگان [English]

  • F. Golshahi 1
  • A. Toroghi Haghighat 2
1 Univercity Azad barajin Ghazvin
2 Professor Univercity Ghazvin
چکیده [English]

The analysis of large scale dynamic networks provides useful information for the network administrator. This plays an important role in modern societies. The prediction of missing links or possible links in the future is an important and interesting issue on social networks that can support important applications with features such as new recommendations for users, friendship suggestions, and discovery of forged connections. Many real-world social networks display communications in multi-layers (for example, several social networking platforms). In this research, the problem of link prediction in multiple networks has been     studied and a new link prediction method in multiplex networks, based on unsupervized graph structure and the gravitational search algorithms is presented. Different layers of the multiplex network have been used to increase the accuracy of the proposed method and we have presented a methodology that uses information from other layers and community information where people are associated. We have provided this          information in the form of a rating. These privileges, in a way, determine the prediction of the edges       between individuals in these types of networks. One of the criteria for comparing predictive algorithms is to calculate the AUC for these algorithms and using this criterion for comparison accompanied by a travian data set used as a benchmark, it is seen that the AUC of our method has improved 7% compared to Adamic which is a similar method. The results demonstrate that using community information and the gravitational algorithm in layered networks improves link prediction.
 

کلیدواژه‌ها [English]

  • Link Prediction
  • Multiplex Networks
  • Social Network Analysis
  • Static Analysis
[1]   Kong, Xiangnan, Jiawei Zhang, and Philip S. Yu, “Inferring anchor links across multiple heterogeneous social networks,” Proceedings of the 22nd ACM international conference on Information & Knowledge Management, ACM, 2013.##
 [2]  Wang, Dashun, et al., “Human mobility, social ties, and link prediction,” Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, Acm, 2011.##
 [3]  Bastami, Esmaeil, Aminollah Mahabadi, and Elias Taghizadeh, “A gravitation-based link prediction approach in social networks,” Swarm and evolutionary computation, vol. 44 pp. 176-186. 2019.##
 [4]  Wang, Huan, et al., “Nodes' evolution diversity and link prediction in social networks,” IEEE Transactions on Knowledge and Data Engineering 3.10, pp.     2263-2274, 2017.##
 [5    Konstas, Ioannis, Vassilios Stathopoulos, and Joemon M. Jose, “On social networks and collaborative recommendation,” Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval. ACM, 2009.##
 [6]  Tong, Hanghang, Christos Faloutsos, and Jia-Yu Pan, “Fast random walk with restart and its applications,” Sixth International Conference on Data Mining (ICDM'06), IEEE, 2006.##
 [7]  Menon, Aditya Krishna, and Charles Elkan, “Link prediction via matrix factorization,” Joint european conference on machine learning and knowledge discovery in databases, Springer, Berlin, Heidelberg, 2011.##
 [8]  Tang, Jiliang, et al., “Exploiting homophily effect for trust prediction,” Proceedings of the sixth ACM international conference on Web search and data mining, ACM, 2013.##
 [9]  Dunlavy, Daniel M., Tamara G. Kolda, and Evrim Acar, “Temporal link prediction using matrix and tensor factorizations,” ACM Transactions on Knowledge Discovery from Data (TKDD) 5.2, vol. 10, 2011.##
 [10] Sun, Yizhou, et al., “When will it happen?: relationship prediction in heterogeneous information networks,” Proceedings of the fifth ACM international conference on Web search and data mining, ACM, 2012.##
 [11] Yu, Xiao, et al., “Citation prediction in heterogeneous bibliographic networks,” Proceedings of the 2012 SIAM International Conference on Data Mining, Society for Industrial and Applied Mathematics, 2012.##
 [12] Domingos, Pedro, and Matthew Richardson, “1 markov logic: A unifying framework for statistical relational learning,” Statistical Relational Learning, vol. 339, 2007.##
 [13] Newman, Mark E. J., “Clustering and preferential attachment in growing networks,” Physical review E 64.2, 025102, 2001.##
[14] Lü, Linyuan, and Tao Zhou, “Link prediction in complex networks: A survey,” Physica A: statistical mechanics and its applications 390.6,  pp. 1150-1170, 2011.##
 [15] Zhou, Tao, Linyuan Lü, and Yi-Cheng Zhang, “Predicting missing links via local information,” The European Physical Journal B71.4, pp. 623-630. 2009.##
 [16] Bliss, Catherine A., et al., “An evolutionary algorithm approach to link prediction in dynamic social networks,” Journal of Computational Science 5.5, pp. 750-764. 2014.##
 [17]Zhang, Jiawei, Xiangnan Kong, and S. Yu Philip,” Predicting social links for new users across aligned heterogeneous social networks,” 2013 IEEE 13th International Conference on Data Mining, IEEE, 2013.‏##
[18]Leskovec, Jure, Daniel Huttenlocher, and Jon Kleinberg, “Predicting positive and negative links in online social networks,” Proceedings of the 19th international conference on World wide web, ACM, 2010.##
 [19]Lü, Linyuan and Tao Zhou, “Link prediction in complex networks: A survey,” Physica A: statistical mechanics and its applications 390.6, pp. 1150-1170, 2011.##
 [20]Zhang, Jiawei, Xiangnan Kong, and Philip S. Yu, “Transferring heterogeneous links across location-based social networks,” Proceedings of the 7th ACM international conference on Web search and data mining, ACM, 2014.##
 [21]Backstrom, Lars, Cynthia Dwork, and Jon Kleinberg, “Wherefore art thou r3579x?: anonymized social networks, hidden patterns, and structural steganography,” Proceedings of the 16th international conference on World Wide Web. ACM, 2007.##
[22]Wang, Dashun, et al., “Human mobility, social ties, and link prediction,” Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining, Acm, 2011.##
 [23]Clauset, Aaron, Cristopher Moore, and Mark E. J. Newman, “Hierarchical structure and the prediction of missing links in networks,” Nature 453.7191, vol. 98, 2008.##
 [24]Liben‐Nowell, David, and Jon Kleinberg, “The link‐prediction problem for social networks,” Journal of the American society for information science and technology 58.7, pp.    1019-1031, 2007.##
 [25]Wang, Huan, et al., “Nodes' evolution diversity and link prediction in social networks,” IEEE Transactions on Knowledge and Data Engineering 29.10, pp.   2263-2274, 2017.##
 [26] Pirotte, Alain, Jean-Michel Renders, and Marco Saerens, “Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation,” IEEE Transactions on Knowledge & Data Engineering 3 pp. 355-369, 2007.##
 [27]Konstas, Ioannis, Vassilios Stathopoulos, and Joemon M. Jose, “On social networks and collaborative recommendation,” Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval. ACM, 2009.##
 [28] Tong, Hanghang, Christos Faloutsos, and Jia-Yu Pan, “Fast random walk with restart and its applications,” Sixth International Conference on Data Mining (ICDM'06), IEEE, 2006.##
[29] Menon, Aditya Krishna, and Charles Elkan, “Link prediction via matrix factorization,” Joint european conference on machine learning and knowledge discovery in databases, Springer, Berlin, Heidelberg, 2011.##