,
نوع مقاله : مقاله پژوهشی
چکیده
خوشه‌بندی، ابزاری پرکاربرد جهت تحلیل اطلاعات شبکه‌های پیچیده است که برای مدل‌سازی سامانه‌های پیچیده بکار می‌رود. پیمانگی ، معیاری پایه و فراگیر جهت ارزیابی و صحت‌سنجی خوشه‌بندی شبکه‌ها است که دارای چالش‌هایی چون ان‌پی-سخت بودن مسئله و عدم امکان استفاده از دانش اولیه در خوشه‌بندی می‌باشد. لذا، خوشه‌بندی مبتنی بر معیار پیمانگی، قابلیت تعمیم به خوشه‌بندی‌های نیمه‌نظارتی را ندارد. از طرفی، یکی از روش‌های خوشه‌بندی نیمه‌نظارتی، روش خوشه‌بندی مبتنی بر تجزیه نامنفی ماتریسی (NMF) می‌باشد. اما این روش، ویژگی‌های خاص شبکه‌ها را در نظر نمی‌گیرد. در این مقاله، برای غلبه بر چالش‌های نام‌برده و با ارائه‌ی اثباتی جدید، برای خوشه‌بندی مبتنی بر معیار پیمانگی، ساختاری مشابه با خوشه‌بندی مبتنی بر تجزیه نامنفی ماتریسی نامتقارن ارائه می‌شود که در آن، امکان بهره‌گیری از دانش اولیه و حل به روش تکراری میسر می‌گردد. سپس، روش خوشه‌بندی نیمه‌نظارتی نوینی به نام تجزیه نیمه‌نظارتیِ نامنفی ماتریس‌های متقارن مبتنی بر معیار پیمانگی (SSNMF-Q) با بهره‌گیری از مزیت دانش اولیه و روش حل تکراری، به‌جای حل مسئله ان‌پی-سخت ارائه می‌گردد. برای ارزیابی روش پیشنهادی، از پنج مجموعه داده واقعی استفاده‌شده که نتایج، بیانگر عملکرد بهتر SSNMF-Qدر مقایسه با سایر خوشه‌بندی‌های نیمه‌نظارتی مبتنی بر NMF می‌باشد.
- 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.
)