تشخیص اجتماع در شبکه های اجتماعی با رویکرد یادگیری عمیق

حسینی, منیره; گلوی, الناز

doi:10.22054/ims.2023.66048.2125

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

نویسندگان

¹ فناوری اطلاعات،دانشکده مهندسی صنایع، دانشگاه صنعتی خواجه نصیرالدین طوسی، تهران، ایران

² گروه مهندسی فناوری اطلاعات، دانشکده مهندسی صنایع، دانشگاه صنعتی خواجه نصیرالدین طوسی، تهران، ایران

https://doi.org/10.22054/ims.2023.66048.2125

چکیده

تشخیص اجتماع یک موضوع مهم در تحلیل شبکه‌های اجتماعی می‌باشد و برای درک ساختار شبکه‌های پیچیده ضروری است. در تشخیص اجتماع هدف، شناسایی گروه‌هایی است که گره‌های گروه به طور متراکم با هم در ارتباط هستند. در این تحقیق، ضمن ارائه معماری جامع و یکپارچه‌‌ای از روش‌های تشخیص اجتماع با یادگیری عمیق، از تکنیک‌های یادگیری عمیق برای کنترل داده‌های گراف با ابعاد بالا استفاده شده است. روش‌های کلاسیک تشخیص اجتماع برای شبکه‌های با ابعاد پایین مناسب هستند. از این رو، کاهش ابعاد شبکه‌های پیچیده موضوع مهمی در تشخیص اجتماع به شمار می‌آید. در این تحقیق، ابتدا ماتریس شباهت جدیدی از توپولوژی شبکه برای آشکار کردن اتصالات مستقیم و غیر مستقیم بین گره‌ها ایجاد می‌شود. سپس یک خودمرزگذار پشته براساس یادگیری بدون نظارت برای کاهش ابعاد طراحی شده‌است. پس ازآن الگوریتم‌های مختلف خوشه‌بندی تست و برای تشحیص اجتماعات به کار برده می‌شوند. ارزیابی مدل پیشنهادی تحقیق، با انجام آزمایش‌های متعدد بر روی معیار استاندارد و شش مجموعه داده‌ واقعی کاراته، دلفین‌ها، فوتبال، کتاب‌های سیاسی،کرا و شهروند مورد بررسی قرار می‌گیرد. نتایج ارزیابی روش پیشنهادی، در مجموعه داده فوتبال در مقایسه با دوازده الگوریتم مطرح به کار رفته در تحقیقات گذشته دقت بالاتری در شناسایی اجتماعات دارد و در سایر مجموعه داده‌ها در مقایسه با سیزده الگوریتم بهبود قابل توجهی را نشان می‌دهد.

کلیدواژه‌ها

موضوعات

علم داده، هوشمندی و تحلیل‌های آینده ‌نگر

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

Community Detection in Social Networks Using Deep Learning Approach

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

Monireh Hosseini ¹
Elnaz Galavi ²

¹ Information Technology Engineering Departement, Faculty of Industrial Engineering, K.N.Toosi University of Technology, Tehran, Iran.

² Information Technology Engineering Department, Faculty of Industrial Engineering, K.N.Toosi University of Technology, Tehran, Iran

چکیده [English]

Community detection is an important topic for social network analysis and is also essential to understanding complex networks structure. In community detection, the goal is to determine the groups in which the group nodes are densely connected to each other. In this research, deep learning techniques have been used to control graph data with high dimensions, while presenting a comprehensive and integrated architecture of community recognition methods with deep learning. Community detection classic approaches are suitable for networks with low dimensions. Therefore, the reduction of complex network dimensions is counted as a significant topic in community detection. In this paper, in order to reveal the direct and indirect connections among nodes, first a new similarity matrix of network topology is built. Then, a stacked auto-encoder is designed to decrease dimensions based on unsupervised learning. In order to detect communities, various clustering algorithms are then tested and utilized. Evaluation of the proposed research model is performed by surveying various experiments on standard criteria and six real data sets of Karate, Dolphins, Football, Polbooks, Cora and Citeseer. The proposed method evaluation outcomes show a higher accuracy in the identification of communities in the football data set compared to the twelve proposed algorithms used in past researches, and show a significant improvement in other data sets compared to the thirteen algorithms.

Introduction

Today, due to the increasing use of the Internet, social networks have found an important role in the real life of people. In social networks, some nodes are more connected than the entire network nodes, which are called communities(Sperli, 2019). Community Detection is an important topic for social network analysis and is also essential to understanding complex network structure In community detection, the goal is to determine the groups in which the group nodes are densely connected.
There are many methods for community detection, but deep learning has shown excellent performance in a wide range of research fields, such as social networks, graph embedding, etc.
In this research, deep learning techniques have been used to control graph data with high dimensions, while presenting a comprehensive and integrated architecture of community detection methods with deep learning.
Research Questions
Is it possible to create a new similarity matrix from the graph of complex networks that fully reveals the similarity relationships between network nodes?
What is the appropriate method of deep learning to represent the features of complex networks in low dimensions?
Is it possible to provide a suitable framework with model flexibility for networks of different sizes for community detection using the deep learning method?
Can more accurate clustering results be achieved for community detection?

Literature Review

2.1.Community detection classic approaches are suitable for networks with low dimensions. Therefore, the reduction of complex network dimensions is counted as a significant topic in community detection. The disadvantage of the high-dimensional network is the huge computational costs incurred by community detection methods. Therefore, a method is needed to transform high-dimensional graphs into a lower-dimensional space, where important information about network structure and node properties is still preserved. According to past research, autoencoders are the dominant method for mapping data points in lower-dimensional spaces (Souravlas et al, 2021).
2.2.To display the network, using the proximity matrix as the network similarity matrix can describe the similarity relationship between the nodes in the network. But the relationship between nodes in a social network is complex. On the other hand, in addition to the similarity between nodes that are directly connected, there are different degrees of similarity between nodes that are not directly connected (Su et al., 2020).
2.3. Wu et al. (2020) and Geng et al. (2020) reconstructed the adjacency matrix to represent the network. Dhilber and Bhavani (2020) used a cubic matrix for the input of the stack autoencoders, as did the work of Yang et al. (2016). Xie et al. (2018) first proposed a new representation of network similarity and then fed it with a sparse filtering model to extract meaningful features of network nodes. But in addition to the problem of lack of neighbor information in the proximity matrix based on Su et al.'s (2020) research, using only one function to check the similarity between nodes cannot fully reveal the topological information of the network. Therefore, a similarity matrix should be presented that can solve the proposed gaps.

Methodology

In this paper, to reveal the direct and indirect connections among nodes, first, a new similarity matrix of network topology is built. To construct the new similarity matrix, two matrices are used, i.e. proximity matrix and S∅rensen–Dice's (S∅) similarity matrix in Xie et al. (2018) 's research. In the next step to extract low-dimensional graph features, the new similarity matrix is given as input to the stack autoencoder networks, which have several hidden layers for unsupervised training. Then, using the newly learned features that are in the low-dimensional matrix with the help of K-means, DBSCAN, and SNNDPC clustering algorithms, communities are detected.

Conclusion

Evaluation of the proposed research model is performed by surveying various experiments on standard criteria and six real data sets of Karate, Dolphins, Football, Polbooks, Cora, and Citeseer. The proposed method evaluation outcomes show a higher accuracy in the detection of communities in the football data set compared to the twelve proposed algorithms used in past research and show a significant improvement in other data sets compared to the thirteen algorithms. In addition to these cases, the superiority of the similarity matrix used in this research was proved as a key prerequisite for community detection.

Keywords: Community Detection, Deep Learning, Autoencoder, Complex Networks.

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

Community detection
Deep learning
Autoencoder
Complex networks

مراجع

حسینیان، امیرحسین، تیمورپور، بابک و جمالی هندری، باقر. (1398). توسعه یک روش فرا ابتکاری ترکیبی برای شناسایی اجتماعات در شبکه‌های اجتماعی باهدف چگالی پودمانگی. مطالعات مدیریت کسب‌وکار هوشمند.8(29).61-86. doi: 10.22054/ims.2019.10376

روحانی، سعید، امیریان، سمانه و محمدیان، ایوب. (1396). شناسایی و اولویت‌بندی کاربردهای شبکه کاوی در تجارت الکترونیکی. مطالعات مدیریت کسب‌وکار هوشمند.6(21).1-32. doi: 10.22054/ims.2018.8510

روشنی، سعید، رضایی نیک، نفیسه و شجاعی، سید محمدحسین. (1392). مطالعه مقایسه‌ای قابلیت سازی و جامعه‌پذیری شبکه‌های اجتماعی عمومی و تخصصی. مطالعات مدیریت کسب‌وکار هوشمند.2(5).97-132.

شعار، مریم و سالارنژاد، علی‌اصغر. (1397). روشی جدید برای خوشه‌بندی اسناد HTML با استفاده از الگوریتم‌های تلفیقی. مطالعات مدیریت کسب‌وکار هوشمند.6 (24).37-62.doi: 10.22054/ims.2018.8891

کوثری لنگری، روح‌الله، سردار، سهیلا، امین موسوی، سید عبدالله و رادفر، رضا. (1398). مدلی برای انتشار داده‌های شبکه‌های اجتماعی برخط با حفظ حریم خصوصی. مطالعات مدیریت کسب‌وکار هوشمند.8(29).87-112. doi: 10.22054/ims.2019.10377

قاسم پور، محدثه، سیفی، عباس و علیزاده، حسین. (1392). تشخیص اجتماعات در شبکه‌های اجتماعی، دومین کنفرانس ملی مهندسی صنایع و سیستم‌ها، اصفهان،https://civilica. com/doc/251290

References

Al-Andoli, M., Cheah, W. P., & Tan, S. C. (2021). Deep learning-based community detection in complex networks with network partitioning and reduction of trainable parameters. Journal of Ambient Intelligence and Humanized Computing, 12 (2), 2527-2545. ‏

Al-Andoli, M. N., Tan, S. C., Cheah, W. P., & Tan, S. Y. (2021). A Review on Community Detection in Large Complex Networks from Conventional to Deep Learning Methods: A Call for the Use of Parallel Meta-Heuristic Algorithms. IEEE Access, 9, 96501-96527.‏

Bhatia, V., & Rani, R. (2019). A distributed overlapping community detection model for large graphs using autoencoder. Future Generation Computer Systems, 94, 16-26. ‏

Berahmand, K., Bouyer, A., & Vasighi, M. (2018). Community detection in complex networks by detecting and expanding core nodes through extended local similarity of nodes. IEEE Transactions on Computational Social Systems, 5(4), 1021-1033.‏

Blondel, V. D., Guillaume, J. L., Lambiotte, R., & Lefebvre, E. (2008). Fast unfolding of communities in large networks. Journal of statistical mechanics: theory and experiment, 2008 (10), P10008. ‏

Cai, B., Wang, Y., Zeng, L., Hu, Y., & Li, H. (2020). Edge classification based on convolutional neural networks for community detection in complex network. Physica A: Statistical Mechanics and its Applications, 556, 124826. ‏

Cao, J., Jin, D., & Dang, J. (2018, August). Autoencoder based community detection with adaptive integration of network topology and node contents. In International conference on knowledge science, engineering and management (pp. 184-196). Springer, Cham. ‏

Cao, J., Jin, D., Yang, L., & Dang, J. (2018). Incorporating network structure with node contents for community detection on large networks using deep learning. Neurocomputing, 297, 71-81. ‏

Chen, Z., Li, X., & Bruna, J. (2019). Supervised community detection with line graph neural networks. arXiv preprint arXiv:1705. 08415. ‏

Choong, J. J., Liu, X., & Murata, T. (2019, December). Optimizing variational graph autoencoder for community detection. In 2019 IEEE International Conference on Big Data (Big Data) (pp. 5353-5358). IEEE. ‏

Dhilber, M., & Bhavani, S. D. (2020, January). Community detection in social networks using deep learning. In International conference on distributed computing and internet technology (pp. 241-250). Springer, Cham. ‏

Duch, J., & Arenas, A. (2005). Community detection in complex networks using extremal optimization. Physical review E, 72(2), 027104.‏

Fei, R., Sha, J., Xu, Q., Hu, B., Wang, K., & Li, S. (2020). A new deep sparse autoencoder for community detection in complex networks. EURASIP Journal on Wireless Communications and Networking, 2020 (1), 1-25.

Geng, X., Lu, H., & Sun, J. (2020). Network structural transformation-based community detection with autoencoder. Symmetry, 12 (6), 944. ‏

Girvan, M., & Newman, M. E. (2002). Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12), 7821-7826.‏

Guo, K., Zhang, P., Guo, W., & Chen, Y. (2022). An attentional-walk-based autoencoder for community detection. Applied Intelligence, 1-19.‏

He, D., Feng, Z., Jin, D., Wang, X., & Zhang, W. (2017, February). Joint identification of network communities and semantics via integrative modeling of network topologies and node contents. In Thirty-First AAAI Conference on Artificial Intelligence. ‏

He, D., Song, Y., Jin, D., Feng, Z., Zhang, B., Yu, Z., & Zhang, W. (2021, January). Community-centric graph convolutional network for unsupervised community detection. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence (pp. 3515-3521). ‏

Ivannikova, E., Park, H., Hämäläinen, T., & Lee, K. (2018). Revealing community structures by ensemble clustering using group diffusion. Information Fusion, 42, 24-36.‏

Jia, Y., Zhang, Q., Zhang, W., & ang, X. (2019, May). Communitygan: Community detection with generative adversarial nets. In The World Wide Web Conference (pp. 784-794). ‏

Jin, D., Gabrys, B., & Dang, J. (2015). Combined node and link partitions method for finding overlapping communities in complex networks. Scientific reports, 5 (1), 1-8. ‏

Jin, D., Ge, M., Li, Z., Lu, W., He, D., & Fogelman-Soulie, F. (2017, November). Using deep learning for community discovery in social networks. In 2017 IEEE 29th International Conference on Tools with Artificial Intelligence (ICTAI) (pp. 160-167). IEEE. ‏

Jin, D., Liu, Z., Li, W., He, D., & Zhang, W. (2019, July). Graph convolutional networks meet markov random fields: Semi-supervised community detection in attribute networks. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 33, No. 01, pp. 152-159).

Kanawati, R. (2014, August). YASCA: an ensemble-based approach for community detection in complex networks. In International Computing and Combinatorics Conference (pp. 657-666). Springer, Cham. ‏

Li, Y., Han, Q., & Liu, J. (2019, November). Community Detection based on Autoencoder Reconstruction Similarity Matrix. In Journal of Physics: Conference Series (Vol. 1345, No. 3, p. 032055). IOP Publishing. ‏

Liu, C., Liu, J., & Jiang, Z. (2014). A multiobjective evolutionary algorithm based on similarity for community detection from signed social networks. IEEE transactions on cybernetics, 44 (12), 2274-2287. ‏

Liu, F., Xue, S., Wu, J., Zhou, C., Hu, W., Paris, C.,... & Yu, P. S. (2020). Deep learning for community detection: progress, challenges and opportunities. arXiv preprint arXiv:2005. 08225.

Liu, R., Wang, H., & Yu, X. (2018). Shared-nearest-neighbor-based clustering by fast search and find of density peaks. Information Sciences, 450, 200-226.‏

‏Liu, J. (2010, October). Comparative analysis for k-means algorithms in network community detection. In International Symposium on Intelligence Computation and Applications (pp. 158-169). Springer, Berlin, Heidelberg.‏

Lusseau, D., & Newman, M. E. (2004). Identifying the role that animals play in their social networks. Proceedings of the Royal Society of London. Series B: Biological Sciences, 271 (suppl_6), S477-S481. ‏

Mahmood, A., & Small, M. (2015). Subspace based network community detection using sparse linear coding. IEEE Transactions on Knowledge and Data Engineering, 28 (3), 801-812. ‏

Newman, M. E. (2004). Fast algorithm for detecting community structure in networks. Physical review E, 69 (6), 066133. ‏

Newman, M. E. (2006). Modularity and community structure in networks. Proceedings of the national academy of sciences, 103(23), 8577-8582.‏

Salehi, S. M., & Pouyan, A. A. (2020). Detecting overlapping communities in social networks using deep learning. International Journal of Engineering, 33 (3), 366-376. ‏

Shchur, O., & Günnemann, S. (2019). Overlapping community detection with graph neural networks. arXiv preprint arXiv:1909. 12201. ‏

Souravlas, S., Anastasiadou, S., & Katsavounis, S. (2021). A Survey on the Recent Advances of Deep Community Detection. Applied Sciences, 11 (16), 7179. ‏

Sperlí, G. (2019, April). A deep learning based community detection approach. In Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing (pp. 1107-1110). ‏

Su, X., Xue, S., Liu, F., Wu, J., Yang, J., Zhou, C.,... & Yu, P. S. (2021). A Comprehensive Survey on Community Detection with Deep Learning. arXiv preprint arXiv:2105. 12584. ‏

Tian, F., Gao, B., Cui, Q., Chen, E., & Liu, T. Y. (2014, June). Learning deep representations for graph clustering. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 28, No. 1). ‏

Wang, F., Zhang, B., Chai, S., & Xia, Y. (2018). Community detection in complex networks using deep auto-encoded extreme learning machine. Modern Physics Letters B, 32 (16), 1850180. ‏

Wang, C., Pan, S., Hu, R., Long, G., Jiang, J., & Zhang, C. (2019). Attributed graph clustering: A deep attentional embedding approach. arXiv preprint arXiv:1906. 06532. ‏

Wang, F., Zhang, B., & Chai, S. (2019). Deep auto-encoded clustering algorithm for community detection in complex networks. Chinese Journal of Electronics, 28 (3), 489-496. ‏

Wu, L., Zhang, Q., Chen, C. H., Guo, K., & Wang, D. (2020). Deep learning techniques for community detection in social networks. IEEE Access, 8, 96016-96026. ‏

Xie, Y., Gong, M., Wang, S., & Yu, B. (2018). Community discovery in networks with deep sparse filtering. Pattern Recognition, 81, 50-59. ‏

Xie, Y., Wang, X., Jiang, D., & Xu, R. (2019). High-performance community detection in social networks using a deep transitive autoencoder. Information Sciences, 493, 75-90. ‏

Xin, X., Wang, C., Ying, X., & Wang, B. (2017). Deep community detection in topologically incomplete networks. Physica A: Statistical Mechanics and its Applications, 469, 342-352. ‏

Xu, R., Che, Y., Wang, X., Hu, J., & Xie, Y. (2020). Stacked autoencoder-based community detection method via an ensemble clustering framework. Information sciences, 526, 151-165. ‏

Yang, J., McAuley, J., & Leskovec, J. (2013, December). Community detection in networks with node attributes. In 2013 IEEE 13th international conference on data mining (pp. 1151-1156). IEEE. ‏

Yang, L., Cao, X., He, D., Wang, C., Wang, X., & Zhang, W. (2016, July). Modularity Based Community Detection with Deep Learning. In IJCAI (Vol. 16, pp. 2252-2258). ‏

Yang, T., Jin, R., Chi, Y., & Zhu, S. (2009, June). Combining link and content for community detection: a discriminative approach. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 927-936).‏

Ye, F., Chen, C., & Zheng, Z. (2018, October). Deep autoencoder-like nonnegative matrix factorization for community detection. In Proceedings of the 27th ACM international conference on information and knowledge management (pp. 1393-1402). ‏

Zachary, W. W. (1977). An information flow model for conflict and fission in small groups. Journal of anthropological research, 33 (4), 452-473.

Zhang, Y., Xiong, Y., Ye, Y., Liu, T., Wang, W., Zhu, Y., & Yu, P. S. (2020, August). SEAL: Learning Heuristics for Community Detection with Generative Adversarial Networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (pp. 1103-1113). ‏

References [In Persian]

Ghasempoor, M., Seifi, A., & Alizadeh, H. (2019). Recognition of communities in social networks. The second national industrial and systems engineering conference, Isfahan, https://civilica. com/doc/251290

Hosseinian, A. H., Teimourpour, B., & Jamali Hondori, B. (2019). A Hybrid Algorithm for Detecting Communities of Social Networks based on the Modularity Density Criterion. Business Intelligence Management Studies, 8(29), 61-86. doi: 10.22054/ims.2019.10376

Kosari Langari, R., Sardar, S., Amin Mousavi, S. A., & Radfar, R. (2019). A Model to Publish Online Social Networks Data with Privacy Preserving. Business Intelligence Management Studies, 8(29), 87-112. doi: 10.22054/ims.2019.10377

Rohan, S., Amirian, S., & Mohammadian, A. (2017). Identification and Ranking of Social Mining Applications in E-Commerce. Business Intelligence Management Studies, 6(21), 1-32. doi: 10.22054/ims.2018.8510

Roshani, S., Rezaeenik, N., & Shojaei, S. M. H. (2013). A comparative study of Usability and Sociability Of public and specialized social networking websites. Business Intelligence Management Studies, 2(5), 97-132.

Shoar, M., & Salarnezhad, A. A. (2018). A New Method to Cluster HTML Documents Using Mixed Algorithms. Business Intelligence Management Studies, 6(24), 37-62. doi: 10.22054/ims.2018.8891

‌

‌ ‌استناد به این مقاله: حسینی، منیره.، گلوی، الناز. (1402). تشخیص اجتماع در شبکه‌های اجتماعی با رویکرد یادگیری عمیق، مطالعات مدیریت کسب وکار هوشمند، 11(44)، 83-112.

DOI: 10.22054/ims.2023.66048.2125

Journal of Business Intelligence Management Studies is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License..