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

Ghadirian, M.; Bigdeli, N.

doi:10.22061/jecei.2023.9150.577

Document Type : Original Research Paper

Authors

Department of Control Engineering, Faculty of Technical and Engineering, Imam-Khomeini International University, Qazvin, Iran.

https://doi.org/10.22061/jecei.2023.9150.577

Abstract

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.‎

Keywords

20.1001.1.23223952.2023.11.2.19.1

Main Subjects

Graph Clustering

Open Access

This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this license, visit: http://creativecommons.org/licenses/by/4.0/

Publisher’s Note

JECEI Publisher remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Publisher

Shahid Rajaee Teacher Training University

References

[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.

LETTERS TO EDITOR

Journal of Electrical and Computer Engineering Innovations (JECEI) welcomes letters to the editor for the post-publication discussions and corrections which allows debate post publication on its site, through the Letters to Editor. Letters pertaining to manuscript published in JECEI should be sent to the editorial office of JECEI within three months of either online publication or before printed publication, except for critiques of original research. Following points are to be considering before sending the letters (comments) to the editor.

[1] Letters that include statements of statistics, facts, research, or theories should include appropriate references, although more than three are discouraged.

[2] Letters that are personal attacks on an author rather than thoughtful criticism of the author’s ideas will not be considered for publication.

[3] Letters can be no more than 300 words in length.

[4] Letter writers should include a statement at the beginning of the letter stating that it is being submitted either for publication or not.

[5] Anonymous letters will not be considered.

[6] Letter writers must include their city and state of residence or work.

[7] Letters will be edited for clarity and length.

Name *

Email Address *

Affiliation *

Comments *

Security Code *

Journal of Electrical and Computer Engineering Innovations (JECEI)

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

References

References

Send comment about this article

Volume 11, Issue 2
July 2023
Pages 443-458

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

References

References

Send comment about this article

Volume 11, Issue 2July 2023Pages 443-458

Volume 11, Issue 2
July 2023
Pages 443-458