A New Hybrid NMF-based Infrastructure for Community Detection in ‎Complex Networks

Ghadirian, M.; Bigdeli, N.

doi:10.22061/jecei.2023.9150.577

فهرست نشریات

دانشگاه تربیت دبیر شهید رجائی

انتشارات دانشگاه تربیت دبیر شهید رجائی

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

نشریه معماری وشهرسازی پایدار موفق به اخذ رتبه علمی-پژوهشی شد

تعداد نشریات	11
تعداد شماره‌ها	210
تعداد مقالات	2,098
تعداد مشاهده مقاله	2,877,971
تعداد دریافت فایل اصل مقاله	2,085,872

	A New Hybrid NMF-based Infrastructure for Community Detection in ‎Complex Networks
Journal of Electrical and Computer Engineering Innovations (JECEI)
دوره 11، شماره 2، مهر 2023، صفحه 443-458 اصل مقاله (1002.67 K)
نوع مقاله: Original Research Paper
شناسه دیجیتال (DOI): 10.22061/jecei.2023.9150.577
نویسندگان
M. Ghadirian؛ N. Bigdeli^*
Department of Control Engineering, Faculty of Technical and Engineering, Imam-Khomeini International University, Qazvin, Iran.
تاریخ دریافت: 19 دی 1401، تاریخ بازنگری: 01 اردیبهشت 1402، تاریخ پذیرش: 17 اردیبهشت 1402
چکیده
Background and Objectives: Community detection is a critical problem in ‎investigating complex networks. Community detection based on ‎modularity/general modularity density are the popular methods with the ‎advantage of using complex network features and the disadvantage of ‎being NP-hard problem for clustering. Moreover, Non-negative matrix ‎factorization (NMF)-based community detection methods are a family of ‎community detection tools that utilize network topology; but most of ‎them cannot thoroughly exploit network features. In this paper, a hybrid ‎NMF-based community detection infrastructure is developed, including ‎modularity/ general modularity density as more comprehensive indices of ‎networks. The proposed infrastructure enables to solve the challenges of ‎combining the NMF method with modularity/general modularity density ‎criteria and improves the community detection methods for complex ‎networks.‎ Methods: First, new representations, similar to the model of symmetric ‎NMF, are derived for the model of community detection based on ‎modularity/general modularity density. Next, these indices are ‎innovatively augmented to the proposed hybrid NMF-based model as two ‎novel models called ‘general modularity density NMF (GMDNMF) and ‎mixed modularity NMF (MMNMF)’. In order to solve these two NP-hard ‎problems, two iterative optimization algorithms are developed.‎ Results: it is proved that the modularity/general modularity density-‎based community detection can be consistently represented in the form ‎of SNMF-based community detection. The performances of the proposed ‎models are verified on various artificial and real-world networks of ‎different sizes. It is shown that MMNMF and GMDNMF models ‎outperform other community detection methods. Moreover, the ‎GMDNMF model has better performance with higher computational ‎complexity compared to the MMNMF model.‎ Conclusion: The results show that the proposed MMNMF model improves ‎the performance of community detection based on NMF by employing ‎the modularity index as a network feature for the NMF model, and the ‎proposed GMDNMF model enhances NMF-based community detection by ‎using the general modularity density index.‎
کلیدواژه‌ها
Complex Networks؛ ‎Nonnegative Matrix ‎Factorization؛ Modularity؛ ‎General Modularity Density؛ ‎Graph Clustering

مراجع
[1] M. E. J. Newman, “Networks,” OUP, 2018. [2] P. Bedi, C. Sharma, “Community detection in social networks,” Wiley Interdiscip. Rev.: Data Min. Knowl. Discovery, 6 (3): 115-135, 2016. [3] Z. Li, S. Zhang, R. S. Wang, X. S. Zhang, L. Chen, “Quantitative function for community detection,” Phys. Rev. E, 77 (3): 036109, 2008. [4] L. H. N. Lorena, M. G. Quiles, L. A. N. Lorena, “Improving the performance of an integer linear programming community detection algorithm through clique filtering,” in Proc. International Conference on Computational Science and Its Applications (ICCSA): 757–769, 2019. [5] M. Sathyakala, M. A. Sangeetha, “Weak clique based multi objective genetic algorithm for overlapping community detection in complex networks,” J. Ambient Intell. Humaniz. Comput. 12: 6761–6771, 2021. [6] M. Mohammadi, M. Fazeli, M. Hosseinzadeh, "Parallel louvain community detection algorithm based on dynamic thread assignment on graphic processing unit", J. Electr. Comput. Eng. Innovations (JECEI), 10(1): 75-88, 2022. [7] C. K. Tsung, S. L. Lee, H. J. Ho, S. Chou, “A modularity-maximization-based approach for detecting multi-communities in social networks,” Ann. Oper. Res., 303: 381–411, 2021. [8] S. Muff, F. Rao, A. Caflisch, “Local modularity measure for network clusterizations”, Phys. Rev. E, 72: 056107, 2005. [9] K. Sato, Y. Izunaga, “An enhanced MILP-based branch-and-price approach to modularity density maximization on graphs,” Comput. Oper. Res., 106: 236–245, 2019. [10] J. Liu, J. Zeng, “Community detection based on modularity density and genetic algorithm,” in Proc. 2010 International Conference on Computational Aspects of Social Networks: 29-32, 2010. [11] M. Li, J. Liu, “A link clustering based memetic algorithm for overlapping community detection,” Phys. A: Stat. Mech. Appl., 503: 410–423, 2018. [12] A. Costa, “MILP formulations for the modularity density maximization problem,” Eur. J. Oper. Res., 245(1): 14–21, 2015. [13] M. J. Barber, J. W. Clark, “Detecting network communities by propagating labels under constraints,” Phys. Rev. E, 80: 026129, 2009. [14] Q. Wu, R. Chen, L. Wang, K. Guo, “A label propagation algorithm for community detection on high-mixed networks,” Concurr. Comput. Pract. Exp., 33 (9): e6141, 2020. [15] M. Rosvall, C. T. Bergstrom, “Maps of random walks on complex networks reveal community structure,” Proc. Natl. Acad. Sci. U.S.A., 105 (4): 1118–1123, 2008. [16] J. Zhou, L. Li, A. Zeng, Y. Fan, Z. Di, “Random walk on signed networks,” Phys. A: Stat. Mech. Appl., 508: 558-556, 2018. [17] C. Liu, F. Huang, R. Li, Q. Yang, Y. Li, S. Yu, “Community detection using multitopology and attributes in social networks,” Concurr. Comput. Pract. Exp., 34 (12): e6028, 2020. [18] R. S. Wang, S. Zhang, Y. Wang, X. Zhang, L. Chen, “Clustering complex networks and biological networks by nonnegative matrix factorization with various similarity measures,” Neurocomputing 72 (1-3): 134-141, 2008. [19] L. Xu, T. Ming, W. Xiaofei, W. Chao, F. Qiang, Y. Yonghong, “Single-channel speech separation based on non-negative matrix factorization and factorial conditional random field,” Chin. J. Electron., 27 (5): 1063-1070, 2018. [20] S. Peng, W. Ser, B. Chen, Z. Lin, “Robust semi-supervised nonnegative matrix factorization for image clustering,” Pattern Recognit., 111: 107683, 2021. [21] S. Zhang, G. Zhang, F. Li, C. Deng, S. Wang, A. Plaza, J. Li, “Spectral-spatial hyperspectral unmixing using nonnegative matrix factorization,” IEEE Geosci. Remote. Sens., 60: 5505713, 2021. [22] E. L. Lydia, P. K. Kumar, K. Kumar, S. K. Lakshmanaprabu, R. M. Vidhyavathi, “Charismatic Document clustering through novel K-Means Non-negative Matrix Factorization (KNMF) Algorithm using key phrase extraction,” Int. J. Parallel Program., 48: 496–514, 2020. [23] C. He, Y. Tang, K. Liu, H. Li, S. Liu, “A robust multi-view clustering method for community detection combining link and content information,” Phys. A: Stat. Mech. Appl., 514: 396-411, 2018. [24] K. Shu, S. Wang, H. Liu, “Beyond news contents: the role of social context for Fake news detection,” in Proc. Twelfth ACM International Conference on Web Search and Data Mining: 312-320, 2019. [25] C. He, Q. Z, Y. Tang, S. Liu, J. Zheng, “Community detection method based on robust semi-supervised nonnegative matrix factorization,” Phys. A: Stat. Mech. Appl., 523: 279-291, 2019. [26] H. Lu, X. Sang, Q. Zhoa, J. Lu, “Community detection algorithm based on nonnegative matrix factorization and pairwise constraints,” Phys. A: Stat. Mech. Appl., 522: 205-214, 2019. [27] W. Wu, S. Kwong, Y. Zhou, Y. Jia, W. Gao, “Nonnegative matrix factorization with mixed hypergraph regularization for community detection,” Inf. Sci., 435: 263-281, 2018. [28] M. Zhang, Z. Zhou, “Structural deep nonnegative matrix factorization for community detection,” Appl. Soft Comput., 97: 106846, 2020. [29] J. Huang, T. Zhang, W. Yu, J. Zhu, E. Cai, “Community detection based on modularized deep nonnegative matrix factorization,” Int. J. Pattern Recognit. Artif. Intell., 2 (35): 2159006, 2021. [30] C. Yan, Z. Chang, “Modularized tri-factor nonnegative matrix factorization for community detection enhancement,” Phys. A: Stat. Mech. Appl., 533: 122050, 2019. [31] X. Ma, L. Gao, L. Fu, X. Yong, “Semi-supervised clustering algorithm for community structure detection in complex networks,” Phys. A: Stat. Mech. Appl., 389(1): 187–197, 2010. [32] X. Wang, P. Cui, J. Wang, J. pei, W. Zhu, S. Yang, “Community preserving network embedding,” in Proc. Thirty-First AAAI Conference on Artificial Intelligence: 203-209, 2017. [33] X. Ma, D. Dong, Q. Wang, “Community detection in multi-layer networks using joint nonnegative matrix factorization,” IEEE Trans. Knowl. Data. Eng., 31 (2): 273-286, 2019. [34] L. Zong, Z. Zhang, L. Zhao, H. Yu, Q. Zhao, “Multi-view clustering via multi-manifold regularized non-negative matrix factorization,” Neural Netw., 88: 74-89, 2017. [35] S. Peng, W. Ser, B. Chen, Z. Lin, “Robust orthogonal nonnegative matrix tri-factorization for data representation,” Knowl-Based Syst., 201-202: 106054, 2020. [36] J. Liu, C. Wang, J. Gao, J. Han, “Multi-view clustering via Joint nonnegative matrix factorization,” in Proc. the 2013 SIAM International Conference on Data Mining: 252-260, 2013. [37] A. Clauset, M. E. J. Newman, C. Moore, “Finding community structure in very large networks,” Phys. Rev. E, 70(6): 066111, 2004. [38] Z. Ding, Z. Shang, D. Sun, B. Luo, “Low-rank subspace learning based network community detection,” Knowl-Based Syst., 155: 71-82, 2018. [39] W. W. Zachary, “An information flow model for conflict and fission in small groups,” J. Anthropol. Res., 33 (4): 452–473, 1977. [40] P. M. Gleiser, L. Danon, “Community structure in jazz,” Adv. Compl. Syst., 6 (4): 565–573, 2003 [41] J. Kunegis, “KONECT: The koblenz network collection,”in Proc. 22nd International Conference on World Wide Web: 1343–1350, 2013. [42] D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, S. M. Dawson, “The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations,” Behav. Ecol. Sociobiol., 54 (4): 396–405, 2003. [43] A. Lancichinetti, S. Fortunato, F. Radicchi, “Benchmark graphs for testing community detection algorithms”, Phys. Rev. E, 78 (4): 046110, 2008. [44] L. Yang, X. Cao, D. Jin, X. Wang, D. Meng, “A unified semi-supervised community detection framework using latent space graph regularization,” IEEE Trans. Cyber., 45(11): 2585–2598, 2015. [45] L. A. Adamic, N. Glance, “The political blogosphere and the 2004 us election: divided they blog,”in Proc. 3 the 3rd international workshop on Link discovery: 36–43, 2005. [46] D. He, Z. Feng, D. Jin, X. Wang, W. Zhang, “Joint identification of network communities and semantics via integrative modeling of network topologies and node contents,” in Proc. the Thirty-First AAAI Conference on Artificial Intelligence: 116–124, 2017. [47] G. Namata, B. London, L. Getoor, B. Huang, U. EDU, “Query-driven active surveying for collective classification,” in Proc. 10th Workshop on Mining and Learning with Graphs, 8 ,2012.
آمار تعداد مشاهده مقاله: 255 تعداد دریافت فایل اصل مقاله: 197

سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب

پیوندهای مفید

پیوندهای مفید

اخبار و اعلانات

آمار

A New Hybrid NMF-based Infrastructure for Community Detection in ‎Complex Networks