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

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

نویسندگان

گروه مهندسی برق کنترل- دانشکده فنی و مهندسی- دانشگاه بین‌المللی امام خمینی (ره)- قزوین- ایران

چکیده

خوشه‌بندی، ابزاری پرکاربرد جهت تحلیل اطلاعات شبکه‌های پیچیده ‏است که برای مدل‌سازی سامانه‌های پیچیده بکار می‌رود. پیمانگی ، ‏معیاری پایه و فراگیر جهت ارزیابی و صحت‌سنجی خوشه‌بندی شبکه‌ها ‏است که دارای چالش‌هایی چون ان‌پی-سخت بودن مسئله و عدم‎ ‎امکان ‏استفاده از دانش اولیه در خوشه‌بندی می‌باشد. لذا، خوشه‌بندی‌ مبتنی بر ‏معیار پیمانگی، قابلیت تعمیم به خوشه‌بندی‌های نیمه‌نظارتی را ندارد. از ‏طرفی، یکی از روش‌های خوشه‌بندی نیمه‌نظارتی، روش خوشه‌بندی مبتنی ‏بر تجزیه نامنفی ماتریسی (‏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.

 

پژوهش های نظری و کاربردی هوش ماشینی
دوره 1، شماره 1
فروردین 1402
صفحه 88-101

فایل ها

هم رسانی

ارجاع به این مقاله

آمار