روشی نوین برای خوشه‌بندی نیمه‌نظارتی شبکه‌های پیچیده‎ ‎مبتنی بر معیار پیمانگی

قدیریان, محمد; بیگدلی, نوشین

doi:10.22034/abmir.2023.19231.1018

	روشی نوین برای خوشه‌بندی نیمه‌نظارتی شبکه‌های پیچیده‎ ‎مبتنی بر معیار پیمانگی
پژوهش های نظری و کاربردی هوش ماشینی
مقاله 9، دوره 1، شماره 1، فروردین 1402، صفحه 88-101 اصل مقاله (617.99 K)
نوع مقاله: مقاله پژوهشی
شناسه دیجیتال (DOI): 10.22034/abmir.2023.19231.1018
نویسندگان
محمد قدیریان؛ نوشین بیگدلی^*
گروه مهندسی برق کنترل- دانشکده فنی و مهندسی- دانشگاه بین‌المللی امام خمینی (ره)- قزوین- ایران
چکیده
خوشه‌بندی، ابزاری پرکاربرد جهت تحلیل اطلاعات شبکه‌های پیچیده ‏است که برای مدل‌سازی سامانه‌های پیچیده بکار می‌رود. پیمانگی ، ‏معیاری پایه و فراگیر جهت ارزیابی و صحت‌سنجی خوشه‌بندی شبکه‌ها ‏است که دارای چالش‌هایی چون ان‌پی-سخت بودن مسئله و عدم‎ ‎امکان ‏استفاده از دانش اولیه در خوشه‌بندی می‌باشد. لذا، خوشه‌بندی‌ مبتنی بر ‏معیار پیمانگی، قابلیت تعمیم به خوشه‌بندی‌های نیمه‌نظارتی را ندارد. از ‏طرفی، یکی از روش‌های خوشه‌بندی نیمه‌نظارتی، روش خوشه‌بندی مبتنی ‏بر تجزیه نامنفی ماتریسی (‏NMF‏) می‌باشد. اما این روش، ویژگی‌های ‏خاص شبکه‌ها را در نظر نمی‌گیرد. در این مقاله، برای غلبه بر چالش‌های ‏نام‌برده‌ و با ارائه‌ی اثباتی جدید، برای خوشه‌بندی مبتنی بر معیار پیمانگی، ‏ساختاری مشابه با خوشه‌بندی مبتنی بر تجزیه نامنفی ماتریسی نامتقارن ‏ارائه می‌شود که در آن، امکان بهره‌گیری از دانش اولیه و حل به روش ‏تکراری میسر می‌گردد. سپس، روش خوشه‌بندی نیمه‌نظارتی نوینی به نام ‏تجزیه نیمه‌نظارتیِ نامنفی ماتریس‌های متقارن مبتنی بر معیار پیمانگی ‏‏(‏SSNMF-Q‏) با بهره‌گیری از مزیت دانش اولیه و روش حل تکراری، ‏به‌جای حل مسئله ان‌پی-سخت ارائه می‌گردد. برای ارزیابی روش ‏پیشنهادی، از پنج مجموعه داده واقعی استفاده‌شده که نتایج، بیانگر عملکرد ‏بهتر‎ SSNMF-Qدر مقایسه با سایر خوشه‌بندی‌های نیمه‌نظارتی مبتنی بر ‏NMF‏ می‌باشد.‏
کلیدواژه‌ها
تجزیه نامنفی ماتریسی؛ گروه‌بندی گراف؛ گروه‌بندی نیمه‌نظارتی؛ معیار پیمانگی
عنوان مقاله [English]
A novel semi-supervised clustering method for complex network based ‎on modularity
نویسندگان [English]
mohammad ghadirian؛ Nooshin Bigdeli
Control Engineering Department, Imam Khomeini International University, Qazvin, Iran
چکیده [English]
Clustering or community detection is a powerfrul tool for ‎analayzing complex networks which is widely used for ‎modeling complex systems. Modularity is a ‎comprehensive criterion for evaluating the quality of ‎clusters (or communities). However, it has some ‎limitations and challenges such as being a NP-hard ‎problem and not using prior information. So, Modularity-‎based community detection cannot be extended as a ‎semi-supervised community detection method. On the ‎other hand, one of the most common semi-supervised ‎methods which can use prior knowledge for clustering is ‎community detection based on non negative matrix ‎factorization (NMF). But, this method is not able to ‎consider the features of the networks. Therefore, in this ‎paper to overcome the mentioned limitations and ‎challenges and by presenting a new proof, a structure ‎similar to community detection based on NMF is ‎presented for modularity-based community detection ‎which can employ prior knowledge and iterative ‎solution. Therefore, a novel semi-supervised community ‎detection based on modularity (SSNMF-Q) criteria is ‎developed by utilizing prior information and iterative ‎solution instead of solving a NP-hard problem. To ‎evaluate SSNMF-Q, five real world networks are used ‎and it is shown that the SSNMF-Q had better ‎performance compared to other semi-supervised ‎community detection methods based on NMF.‎
کلیدواژه‌ها [English]
Non-negative matrix factorization, community detection, semi-supervised clustering, modularity criterion

مراجع
Kumar and R. Hanot, " Community Detection Algorithms in Complex Networks: A Survey", Advances in Signal Processing and Intelligent Recognition Systems, Vol. 1365, no. 202, 215, 2021. D. Asim, T. Yahui and G. R. Yulia, " Community detection in complex networks: From statistical foundations to data science applications ", WIREs Computational Statistics, Vol. 14, no. 2, 2021. E.J. Newman, "Networks", Oxford university press, 2018. E.J. Newman and M. Girvan, "Finding and evaluating community structure in networks", Physical Review E, Vol. 69, no. 2, Issue: 026113, 2004. Fariahhag, M. Mordi, Z. J. Wang, "Community structure detection from networks with weighted modularity", Pattern Recognition Letters, Vol. 122, pp. 14-22, 2019. Li, X. Wang, S.H. Zhu, S.H. Zhu and C. Ding, "Community discovery using nonnegative matrix factorization", Data Min. Knowl. Discovery, Vol. 22 no. 3, pp. 493–521, 2011. Li, H. Chen and T. Li, "A stable community detection approach for complex network based on density peak clustering and label propagation ", Applied Intelligence, Vol. 52pp. 1188-1208, 2022. Wang, S. Chen, X. Wang and J. Wang, "Label propagation algorithm based on node importance", Physica A: Statistical Mechanics and its Applications, Vol. 551, no. 124137, 2020. Rosvall and C.T. Bergstrom, "Maps of random walks on complex networks reveal community structure", Proceedings of the National Academy of Sciences, Vol. 105, no.4, pp. 1118–1123, 2008. Zhou, L. Li, A. Zeng, Y. Fan and Z. Di, "Random walk on signed networks", Physica A: Statistical Mechanics and its Applications, Vol. 508, pp. 558-556, 2018. Shang, K. Zhao, W. Zhang, J. Feng, Y. Li and L. Jiao, " Evolutionary multiobjective overlapping community detection based on similarity matrix and node correction, Applied Soft Computing, Vol. 127 no. 109397, 2022. Sanchez and A. Duarte, "Iterated Greedy algorithm for performing community detection in social networks", Future Generation Computer Systems, Vol. 88, pp. 785-791, 2018. Guerrero, F. G. Montoya, R. Baños, A. Alcayde and C. Gil, "Adaptive community detection in complex networks using genetic algorithms", Neurocomputing, Vol. 266, pp. 101-113, 2017. Fortunato and M. Barthłemy, "Resolution limit in community detection", Proceedings of the National Academy of Sciences, Vol. 104, no. 1, pp. 36–41, 2007. Ghadirian and N. Bigdeli, " Hybrid Adaptive Modularized Tri-Factor Non-Negative Matrix Factorization for ‌Community Detection in Complex Networks ", Scientia Iranica, Vol. 14, 2022. Liu, G. Yuan and X. Luo, "Symmetry and Nonnegativity-Constrained Matrix Factorization for Community Detection," IEEE/CAA Journal of Automatica Sinica, vol. 9, no. 9, pp. 1691-1693, 2022. He, Q. Zheng, Y. Tang, S. Liu, J. Zheng, "Community detection method based on robust semi-supervised nonnegative matrix factorization", Physica A: Statistical Mechanics and its Applications, Vol. 523, no. 1, pp. 279 – 291, 2019. He, Y. Tang, K. Liu, H. Li and S. Liu, "A robust multi-view clustering method for community detection combining link and content information", Physica A: Statistical Mechanics and its Applications Vol. 514, pp. 396-411, 2018. Yan and Z. Chang, "Modularized tri-factor nonnegative matrix factorization for community detection enhancement", Physica A: Statistical Mechanics and its Applications, Vol. 533, no. 122050, 2019. M. Zheng and Z. Zhou, "Structural Deep Nonnegative Matrix Factorization for community detection", Applied Soft Computing, Vol. 97, no: B, Issue: 106846, 2020. Handshutter, N. Gillis and X. Seibert, "A survey on deep matrix factorizations", Computer Science Review, Vol. 42, Issue: 100423, 2021. Huang, T. Zhang, W. Yu, J. Zhu and E. Cai, "Community Detection Based on Modularized Deep Nonnegative Matrix Factorization", International Journal of Pattern Recognition and Articial Intelligence, Vol. 35, no. 35, Issue: 2159006, 2021. jin and S. Li, "Graph regularized nonnegative matrix tri-factorization for overlapping community detection", Physica A: Statistical Mechanics and its Applications,. Vol. 515, pp. 376-387, 2019. Chen, W.Zho and B. Peng, "Differentiated graph regularized non-negative matrix factorization for semi-supervised community detection ", Physica A: Statistical Mechanics and its Applications,.Vol. 604, no. 127692, 2022. -Y. Zhang, "Community structure detection in complex networks with partial background information", Europhysics Letters, Vol. 101, no. 4, pp. 48005, 2013. Ma, L. Gao, X. Yong, and L. Fu, "Semi-supervised clustering algorithm for community structure detection in complex networks", Physica A: Statistical Mechanics and its Applications, Vol. 389, no. 1, pp. 187 – 197, 2010. Yang and B. Hu, "Pairwise constraints-guided non-negative matrix factorization for document clustering",in Web Intelligence, IEEE/WIC/ACM International Conference on. IEEE, pp. 250– 256, 2007. H. Shi, H.T. Lu, Y.C. He and S. He, "Community detection in social network with pairwisely constrained symmetric non-negative matrix factorization", Proceedings of the 7th IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pp. 541–546, 2015. Liu, W. Wang, D. He, P. Jiao, D. Jin and C. Vittorio, "Semi-supervised community detection based on non-negative matrix factorization with node popularity", Information Sciences, Vol. 381, no. 12, pp. 304–321, 2017. C. Févotte, E. Vincentand A. Ozerov. " Single-channel audio source separation with NMF: divergences, constraints and algorithms ", Audio Source Separation, Springer, hal-01631185f, pp. 1-24, 2018. A. Khan, J. Hu, T. li, B. Diallo and H. Wang,." Multi-view data clustering via non-negative matrix factorization with manifold regularization", International Journal of Machine Learning and Cybernetics, Vol. 13, pp. 677-689, 2022. Peng, W. Ser, B. Chen and Z. Lin, " Robust semi-supervised nonnegative matrix factorization for image clustering", Pattern Recognition, Vol. 111, no. 107683, 2021. Huang, X. Fu and N.D. Sidiropoulos, "Anchor-free correlated topic modeling: Identifiability and algorithm", Advances in Neural Information Processing Systems, pp. 1794-1802, 2016. Ma, D. Dong, Q. Wang, “Community detection in multi-layer networks using joint nonnegative matrix factorization”, IEEE Transaction on Knowledge and Data Engineering. 31 (2): 273-286, 2019. W. Zachary, "An information flow model for conflict and fission in small groups", Journal of anthropological research, Vol. 33, no. 4, pp. 452–473, 1977. Lancichinetti, S. Fortunato and F. Radicchi, "Benchmark graphs for testing community detection algorithms", Physical Review E, Vol. 78, no. 4, Isuue: 046110, 2008. Lusseau, K. Schneider, O.J. Boisseau, P. Haase, E. Slooten and S.M. Dawson, "The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations", Behavioral ecology and sociobiology, Vol. 54, no. 4, pp. 396–405, 2003. Kunegis. KONECT: "The Koblenz Network Collection", Proceedings of the 22nd international conference on World Wide Web companion, pp. 1343–1350, 2013. A. Adamic, N. Glance, "The political blogosphere and the 2004 US election: divided the blog", Proceedings of the 3rd workshop on Link discovery, ACM, pp. 36–43, 2005.
آمار تعداد مشاهده مقاله: 369 تعداد دریافت فایل اصل مقاله: 307

سامانه مدیریت نشریات علمی دانشگاه یزد

روشی نوین برای خوشه‌بندی نیمه‌نظارتی شبکه‌های پیچیده‎ ‎مبتنی بر معیار پیمانگی