ارائه یک معیار مشابهت جهت پیش‌بینی پیوند در شبکههای اجتماعی
محورهای موضوعی : پردازش چند رسانه ای، سیستمهای ارتباطی، سیستمهای هوشمند
علی سرآبادانی
1
,
خیرالله رهسپارفرد
2
,
سید مرتضی پورنقی
3
1 - دانشجوی دکتری، مهندسی فناوری اطلاعات، دانشگاه قم، قم، ایران
2 - استادیار، گروه مهندسی کامپیوتر و فناوری اطلاعات، دانشکده فنی و مهندسی، دانشگاه قم، قم، ایران
3 - استادیار، گروه رایانش امن، دانشکده رایانه، شبکه و ارتباطات، دانشگاه جامع امام‌حسین (ع)، تهران، ایران
کلید واژه: تحلیل شبکه اجتماعی, پیش‌بینی پیوند, معیار مشابهت, شبکه هم نویسندگی,
چکیده مقاله :
یک شبکه اجتماعی، ساختاری متشکل از افراد یا سازمان‌ها است. تحلیل شبکههای اجتماعی، مبتنی بر رویکردی است که در آن شبکه را به صورت مجموعه‌ای از گره‌ها و روابط میان آن‌ها درنظر می‌گیرد. گره‌ها شامل اشخاص و موجودیت‌های درون شبکه هستند که با یکدیگر در تعامل ند و در واقع بازیگران درون شبکه محسوب می‌شوند که روابط میان آن‌ها به صورت اتصالاتی بین گره‌ها نمایش داده می‌شود. باتوجه به تعداد رو به رشد کاربران شبکههای اجتماعی، تحلیل روابط حاکم بر آن، پیش‌بینی پیوند‌ها و تعامل‌های ناشی از ارتباط میان گره‌ها (پیش‌بینی لینک یا پیوند، یعنی پیش‌بینی تعامل جدیدی که قرار است در آینده رخ دهد) از چالش‌های جدی در شبکههای اجتماعی می باشد. ما در این مقاله یک معیار شباهت جدید برای پیش‌بینی لینک در شبکههای اجتماعی را پیشنهاد می‌دهیم. این معیار را با چهار روش پیش‌بینی لینک Jaccard، Salton Index، Salton Cosine و Resource Allocation مقایسه می‌کنیم. ما شبیه‌سازی معیار پیشنهادی خود را بر روی پنج مجموعه داده در شبکههای اجتماعی، انجام می‌دهیم. نتایج شبیه‌سازی نشان می‌دهد که معیار پیشنهادی ما عملکرد بهتری نسبت به سایر روش‌های پیش‌بینی پیوند در شبکههای اجتماعی برروی همه دیتاست‌ها را دارد. تجزیه و تحلیل شبکه های اجتماعی به دلیل کاربرد گسترده آن در ثبت تعاملات اجتماعی اخیراً توجه بسیاری را در بین محققان به خود جلب کرده است. پیش‌بینی پیوند، مربوط به احتمال وجود پیوند بین دو گره شبکه که متصل نیستند، یک مشکل کلیدی در تحلیل شبکههای اجتماعی است. روش های زیادی برای حل مشکل پیشنهاد شده است. در میان این روش‌ها، روش‌های مبتنی بر شباهت با درنظرگرفتن ساختار شبکه و استفاده به عنوان معیاری اساسی از تعداد همسایه‌های مشترک بین دو گره برای ایجاد شباهت ساختاری، کارایی خوبی از خود نشان می‌دهند.
Introduction: A social network is a social structure made up of individuals or organizations. Social network analysis is an approach in which the network is considered as a set of nodes and relationships between them. Nodes are individuals and actually actors in the network and the relationships between them are displayed as connections between nodes.Method: Among many social network analysis issues, link prediction has attracted much attention due to the growing number of social network users. Link prediction means predicting which new interaction is going to happen in the future. Traditional link prediction methods considered pairs of nodes as a unit and made decisions based on commonalities between them. In addition, we proposed a new similarity measure for link prediction in social networks.Results: We compared this criterion with four prediction methods of Jaccard link, Salton Index, Salton Cosine, and resource allocation). Experimental runs in this article were carried out on five social network datasets. Our results showed that this criterion performed better than other link prediction techniques on all datasets.Discussion: Social network analysis has recently attracted lots of attention among researchers due to its wide applicability in capturing social interactions. Link prediction, related to the likelihood of having a link between two nodes of the network that are not connected, is a key problem in social network analysis. Many methods have been proposed to solve the problem. Among these methods, similarity-based methods exhibit good efficiency by considering the network structure and using as a fundamental criterion the number of common neighbors between two nodes to establish structural similarity.
[1] Mallek, S., Boukhris, I., Elouedi, Z., & Lefèvre, E. (2019). Evidential link prediction in social networks based on structural and social information. Journal of computational science, 30, 98-107.
[2] Pérez-Macías, N., Fernández-Fernández, J. L., & Rua Vieites, A. (2019). Entrepreneurial intentions: trust and network ties in online and face-toface students. Education+ Training, 61(4), 461-479. Authorized licensed use limited to: Auckland University of Technology. Downloaded on June 05,2020 at 21:29:50 UTC from IEEE Xplore. Restrictions apply.
[3] Ahuja, R., Singhal, V., & Banga, A. (2019). Using Hierarchies in Online Social Networks to Determine Link Prediction. In Soft Computing and Signal Processing (pp. 67-76). Springer, Singapore.
[4] Lai, Y. Y., Neville, J., & Goldwasser, D. (2019). TransConv: Relationship Embedding in Social Networks.
[5] Yuan, W., He, K., Guan, D., Zhou, L., & Li, C. (2019). Graph kernel based link prediction for signed social networks. Information Fusion, 46, 1-10.
[6] Alvi, Abdul & Islam, Arshad & Iqbal, Muhammad & Aleem, Muhammad. (2019). Centrality-Based Paper Citation Recommender System. EAI Endorsed Transactions on Industrial Networks and Intelligent Systems. 6. 159121. 10.4108/eai.13-6-2019.159121.
[7] Iraj Timuri; Mehdi Afzali "Increasing the accuracy of identifying overlapping communities using edge weighting". Intelligent multimedia processing and communication systems, 1, 1, 2019, 9-20.
[8] Ajami, Mojtaba, & Asgari, Nasser. (1400). A comparative analysis of graphical structural measures to detect anomalies in online social networks. Intelligent multimedia processing and communication systems, 2(1), 1-9.
[9] Nderlou, Lida, & Hagazi Sharbian, Mohammad. (1401). Presenting a method for dynamic multi-layered social networks to discover influential groups based on the combination of evolutionary frog jump algorithm and C-means clustering. Intelligent multimedia processing and communication systems, 3(3), 29-39.
[10] Z. Huang, X. Li, H. Chen, Link prediction approach to collaborative filtering, in: Proceedings of the 5th ACM/IEEE-CS joint conference on Digital libraries, JCDL’05, ACM, 2005, pp. 141–142.J. Clerk Maxwell, A Treatise on Electricity and Magnetism, 3rd ed., vol. 2. Oxford: Clarendon, 1892, pp.68-73.
[11] C. Lei, J. Ruan, A novel link prediction algorithm for reconstructing protein-protein interaction networks by topological similarity, Bioinformatics 29 (3) (2013) 355–364.K. Elissa, “Title of paper if known,” unpublished.
[12] Samad, Abdul. Evaluation of Textual and Topological Similarity Measures for Citation Recommendation. Diss. CAPITAL UNIVERSITY, 2019.
[13] W. Peng et al., “Link Prediction in Social Networks: the State-of-theArt,” Sci China Inf Sci, vol. 58, no. 58, pp. 11101–38, 2015.
[14] B. Cao, N. N. Liu, and Q. Yang, “Transfer Learning for Collective Link Prediction in Multiple Heterogenous Domains,” Int. Conf. Mach. Learn., pp. 180–186, 2010.
[15] G. Berlusconi, F. Calderoni, N. Parolini, M. Verani, and C. Piccardi, “Link prediction in criminal networks: A tool for criminal intelligence analysis,” PLoS One, vol. 11, no. 4, p. e0154244, 2016.
[16] Adar, E., Zhang, L., Adamic, L. A., & Lukose, R. M. (2004). Implicit+ Structure+ and+ the+ Dynamics+ of+ Blogspace.
[17] Samad, A., Qadir, M., Nawaz, I., Islam, M. A., & Aleem, M. (2020). A comprehensive survey of link prediction techniques for social network. EAI Endorsed Transactions on Industrial Networks and Intelligent Systems, 7(23),e3-e3.
[19] Tylenda, T., Angelova, R., & Bedathur, S. (2009, June). Towards timeaware link prediction in evolving social networks. In Proceedings of the 3rd workshop on social network mining and analysis (p. 9). ACM.
[18] Wang, C., Satuluri, V., & Parthasarathy, S. (2007, October). Local probabilistic models for link prediction. In Seventh IEEE international conference on data mining (ICDM 2007) (pp. 322-331). IEEE.
[20] Song, H. H., Cho, T. W., Dave, V., Zhang, Y., & Qiu, L. (2009, November). Scalable proximity estimation and link prediction in online social networks. In Proceedings of the 9th ACM SIGCOMM conference on Internet measurement (pp. 322-335). ACM.
[21] Munasinghe, L., & Ichise, R. (2011, August). Time aware index for link prediction in social networks. In International Conference on Data Warehousing and Knowledge Discovery (pp. 342-353). Springer, Berlin, Heidelberg.
[22] da Silva Soares, P. R., & Prudêncio, R. B. C. (2012, June). Time series based link prediction. In The 2012 international joint conference on neural networks (IJCNN) (pp. 1-7). IEEE.
[23] Zhang, J., & Philip, S. Y. (2014). Link prediction across heterogeneous social networks: A survey. Social networks.
[24] Ibrahim, N. M. A., & Chen, L. (2015). Link prediction in dynamic social networks by integrating different types of information. Applied Intelligence, 42(4), 738-750.
[25] Han, X., Wang, L., Farahbakhsh, R., Cuevas, Á., Cuevas, R., Crespi, N., & He, L. (2016). CSD: A multi-user similarity metric for community recommendation in online social networks. Expert Systems with Applications, 53, 14-26.
[26] Murata, T., & Moriyasu, S. (2007, November). Link prediction of social networks based on weighted proximity measures. In Proceedings of the IEEE/WIC/ACM international conference on web intelligence (pp. 85- 88). IEEE Computer Society.
[27] Newman, M. E. (2001). Clustering and preferential attachment in growing networks. Physical review E, 64(2), 025102.
[28] Adamic, L. A., & Adar, E. (2003). Friends and neighbors on the web. Social networks, 25(3), 211-230.
[29] Güneş, İ., Gündüz-Öğüdücü, Ş., & Çataltepe, Z. (2016). Link prediction using time series of neighborhood-based node similarity scores. Data Mining and Knowledge Discovery, 30(1), 147-180.
[30] Wang, D., Pedreschi, D., Song, C., Giannotti, F., & Barabasi, A. L. (2011, August). Human mobility, social ties, and link prediction. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 1100-1108). Acm.
[31] Samad, A., Islam, M. A., Iqbal, M. A., Aleem, M., & Arshed, J. U. (2017, December). Evaluation of features for social contact prediction. In 2017 13th International Conference on Emerging Technologies (ICET) (pp. 1-6). IEEE.
[32] Junuthula, R. R., Xu, K. S., & Devabhaktuni, V. K. (2018, June). Leveraging friendship networks for dynamic link prediction in social interaction networks. In Twelfth International AAAI Conference on Web and Social Media.
[33] Zhou, K., Michalak, T. P., Waniek, M., Rahwan, T., & Vorobeychik, Y. (2019, May). Attacking Similarity-Based Link Prediction in Social Networks. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (pp. 305-313). International Foundation for Autonomous Agents and Multiagent Systems.
[34] Lim, M., Abdullah, A., Jhanjhi, N. Z., & Supramaniam, M. (2019). Hidden Link Prediction in Criminal Networks Using the Deep Reinforcement Learning Technique. Computers, 8(1), 8.
[35] Lim, M., Abdullah, A., & Jhanjhi, N. Z. (2019). Performance optimization of criminal network hidden link prediction model with deep reinforcement learning. Jou
[36] Leskovec, J., Kleinberg, J., & Faloutsos, C. (2007). Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD), 1(1), 2.
[37] Srilatha, P., & Manjula, R. (2016). Similarity index based link prediction algorithms in social networks: A survey. Journal of Telecommunications and Information Technology.
[38] Wang, P., Xu, B., Wu, Y., & Zhou, X. (2015). Link prediction in social networks: the state-of-the-art. Science China Information Sciences, 58(1), 1-38.
[39] Sarna, G., & Bhatia, M. P. S. (2017). Content based approach to find the credibility of user in social networks: an application of cyberbullying. International Journal Of Machine Learning and Cybernetics, 8(2), 677- 689.
[40] Zhou, T., Lü, L., & Zhang, Y. C. (2009). Predicting missing links via local information. The European Physical Journal B, 71(4), 623-630.
_||_