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

Ghadirian, M.; Bigdeli, N.

doi:10.22061/jecei.2023.9150.577

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

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

تعداد نشریات	13
تعداد شماره‌ها	200
تعداد مقالات	2,008
تعداد مشاهده مقاله	2,679,641
تعداد دریافت فایل اصل مقاله	1,936,956

	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.
آمار تعداد مشاهده مقاله: 174 تعداد دریافت فایل اصل مقاله: 150

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

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

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

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

آمار

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