Hybrid adaptive modularized tri-factor non-negative matrix factorization for community detection in complex networks

Document Type : Article

Authors

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

Abstract

Community detection is a significant issue in extracting valuable information and ‎understanding complex network structures. Non-negative matrix factorization (NMF) methods ‎are the most remarkable topics in community detection. The modularized tri-factor NMF ‎‎(Mtrinmf) method was proposed as a new class of NMF methods that combines the modularized ‎information with tri-factor NMF. It has high computational complexity due to its dependence on ‎the choice of the initial value of the parameter and the number of communities (c). In other ‎words, the Mtrinmf method should search among different c candidates to find correct c. In this ‎paper, a novel hybrid adaptive Mtrinmf (Hamtrinmf) method is proposed to improve the ‎performance of Mtrinmf and reduce the computational complexity efficiently. In the proposed ‎method, computational complexity reduction is made by selecting the right c candidates and ‎tuning parameter. For this purpose, a hybrid algorithm including singular value decomposition ‎‎(SVD) and relative eigenvalue gap (REG) algorithms is suggested to estimate the set of c ‎candidates. Next, the Tpmtrinmf model is proposed to improve the performance of community ‎detection via employing a self-tuning β parameter. Moreover, experimental results confirm the ‎efficiency of the Hamtrinmf method with respect to other reference methods on artificial and ‎real-world networks.‎

Keywords

References

References:
1. Newman, M.E.J. "Networks", In Oxford university Press (2018).
2. Newman, M.E.J. and Girvan, M. "Finding and evaluating community structure in networks", Phys. Rev. E., 69, 026113 (2004).
3. Tang, W. and Daoutidis, P. "Network decomposition for distributed control through community detection in input-output bipartite graphs", J. Process Control., 64, pp. 7-14 (2018).
4. Campbell, W.M., Li, L., Dagli, C., et al. "Crossdomain entity resolution in social media", 4th Int. Workshop on Nat. Lang. Process. Social Media (2016).
5. Guerrero, M., Montoya, F.G., Banos, R., et al. "Adaptive community detection in complex networks using genetic algorithms", Neurocomputing, 266, pp. 101- 113 (2017).
6. Gong, M., MA, L., MA, Q., et al. "Community detection in networks by using multi-objective evolutionary algorithm with  decomposition", Phys. A: Stat. Mech. Appl., 391(15), pp. 4050-4060 (2012).
7. Sun, P.G. "Community detection by fuzzy clustering", Phys. A: Stat. Mech. Appl., 419, pp. 408-416 (2015).
8. Cordasco, G. and Gargano, L. "Community detection via semi-synchronous label propagation algorithms", Int. J. of Social Network Mining, 1(1), pp. 3-26 (2011).
9. Ding, J., He, X., Yuan, J., et al. "Community detection by propagating the label of center", Phys. A: Stat. Mech. Appl., 503, pp. 675-686 (2018).
10. Rosvall, M. and Bergstrom, C.T. "Maps of random walks on complex networks reveal community structure", Proc. Natl. Acad. Sci. U.S.A., 105(4), pp. 1118- 1123 (2008).
11. Essid, S. and Fevotte, C. "Smooth nonnegative matrix factorization for unsupervised audiovisual documen structuring", IEEE Trans. Multimedia, 15(2), pp. 415- 425 (2013).
12. Peng, S., Ser, W., Chen, B., et al. "Semi-supervised nonnegative matrix factorization for image clustering", Pattern Recognit, 111, 107683v (2021).
13. Huang, K., Fu, X., and Sidiropoulos, N.D. "Anchorfree correlated topic modeling: Identifiability and algorithm", Adv. Neural Inf. Process. Syst., pp. 1794- 1802 (2016).
14. He, C., Tang, Y., Liu, K., et al. "A robust multi-view clustering method for community detection combining link and content information", Phys. A: Stat. Mech. Appl., 514, pp. 396-411 (2018).
15. Wang, R.S., Zhang, S., Wang, Y., et al. "Clustering complex networks and biological networks by nonnegative matrix factorization with various similarity measures", Neurocomputing, 72(1-3), pp. 134-141 (2008).
16. Wu, W., Kwong, S., Zhou, Y., et al. "Nonnegative matrix factorization with mixed hypergraph regularization for community detection", Inf. Sci., 435, pp. 263-281 (2018).
17. Binesh, N. and Rezghi, M. "Fuzzy clustering in community detection based on nonnegative matrix factorization with two novel evaluation criteria", Appl. Soft Comput., 69, pp. 689-703 (2018).
18. Yang, L., Cao, X., Jin, D., et al. "A unified semisupervised community detection framework using latent space graph regularization", IEEE Trans. Cybern., 45(11), pp. 2585-2598 (2014).
19. Ma, X., Gao, L., Yong, X., et al. "Semi-supervised clustering algorithm for community structure detection in complex networks", Phys. A: Stat. Mech. Appl., 389(1), pp. 187-197 (2010).
20. He, C., Zhang, Q., Tang, Y., et al. "Community detection method based on robust semi-supervised nonnegative matrix factorization", Phys. A: Stat. Mech. Appl., 523, pp. 279-291 (2019).
21. Wang, F., Li, T., Wang, X., et al. "Community discovery using nonnegative matrix factorization", Data Min. Knowl. Discov., 22(3), pp. 493-521 (2011).
22. Zhang, Z.Y. "Nonnegative matrix factorization: Models, algorithms and applications", In Data Mining: Foundations and Intelligent Paradigms. Intelligent Systems Reference Library, Springer, Berlin, Heidelberg (2012).
23. Wang, Y.X. and Zhang, Y.J. "Nonnegative matrix factorization, A comprehensive review", IEEE Trans. Knowl. Data Eng., 25(6), pp. 1336-1353 (2013).
24. Liu, X., Wei, Y.M., Wang, J., et al. "Community detection enhancement using non-negative matrix factorization with graph regularization", Int. J. Mod. Phys. B., 30(20), 1650130 (2016).
25. Yan, C. and Chang, Z. "Modularized tri-factor nonnegative matrix factorization for community detection enhancement", Phys. A: Stat. Mech. Appl., 533, 122050 (2019).
26. Sarkar, S. and Dong, A. "Community detection in graphs using singular value decomposition", Phys. Rev. E., 83(4), 046114 (2011).
27. Lu, H., Sang, X., Zhoa, Q., et al. "Community detection algorithm based on nonnegative matrix factorization and pairwise constraints", Phys. A: Stat. Mech. Appl., 522, pp. 205-214 (2019).
28. Chen, K. and Lei, J. "Network cross-validation for determining the number of communities in network data", J. Am. Stat. Assoc., 113(521), pp. 241-251 (2018).
29. Wang, D. and Zhao, Y. "Network community from the perspective of time series", Phys. A: Stat. Mech. Appl., 522, pp. 205-214 (2019).
30. Fortunato, S. and Barth lemy, M. "Resolution limit in community detection", Proc. Natl. Acad. Sci., U.S.A, 104(1), pp. 36-41 (2007).
31. Huang, J., Zhang, T., Yu, W., et al. "Community detection based on modularized deep nonnegative matrix factorization", Intern. J. Pattern Recognit. Artif. Intell., 35(35), 2159006 (2021).
32. Wang, F., Li, T., Wang, X., et al. "Community discovery using nonnegative matrix factorization", Data Min. Knowl. Discov., 22(3), pp. 493-521 (2011).
33. Muff, S., Rao, F., and Caflisch, A. "Local modularity measure for network clusterizations", Phys. Rev. E., 72, 056107 (2005).
34. Li, Z., Zhang, S., Wang, R.S., et al. "Quantitative function for community detection", Phys. Rev. E., 77(3), 036109 (2008).
35. Zhang, M. and Zhou, Z. "Structural deep nonnegative matrix factorization for community detection", Appl. Soft Comput., 97, 106846 (2020).
36. Ye, F., Chen, C., Zheng, Z., et al. "Deep autoencoderlike nonnegative matrix factorization for community detection", 27th ACM Int. Conf. (2018).
37. Luo, X., Liu, Z., Jin, L., et al. "Symmetric nonnegative matrix factorization-based community detection models and their convergence analysis", IEEE Trans. Neural Netw. Learn. Syst., 99, pp. 1-13 (2021).
38. Tasgin, M., Herdagdelen, A., and Bingol, H. "Community detection in complex networks using genetic algorithms", arXiv, 0711.0491 (2007).
39. Zachary, W.W. "An information flow model for conflict and fission in small groups", J. Anthropol. Res., 33(4), pp. 452-473 (1977).
40. Gleiser, P.M. and Danon, L. "Community structure in jazz", Adv. Complex Syst., 6(4), pp. 565-573 (2003).
41. Kunegis, J. "KONECT: The koblenz network collection", Proc. 22nd Int. Conf. World Wide Web, pp. 1343-1350 (2013).
42. Lusseau, D., Schneider, K., Boisseau, O.J., et al. "The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations", Behav. Ecol. Sociobiol., 54(4), pp. 396-405 (2003).
43. Girvan, M. and Newman, M.E.J. "Community structure in social and biological networks", Proc. Natl. Acad. Sci. U.S.A., 99(12), pp. 7821-7826 (2002).
44. Lancichinetti, A., Fortunato, S., and Radicchi, F. "Benchmark graphs for testing community detection algorithms", Phys. Rev. E., 78(4) 046110 (2008).
45. Barber, M.J. and Clark, J.W. "Detecting network communities by propagating labels under constraints", Phys. Rev. E., 80, 026129 (2009).
46. Clauset, A., Newman, M.E.J., and Moore, C. "Finding community structure in very large networks", Phys. Rev. E., 2, 066111 (2004).
47. Blondel, V.D., Guillaume, J.L., Lambiotte, R., et al. "Fast unfolding of communities in large networks", J. Stat. Mech. Theory Exp., 10, pp. 1-12 (2008).
48. Ding, Z., Shang, Z., Sun, D., et al. "Low-rank subspace learning based network community detection", Knowl. Based Syst., 155, pp. 71-82 (2018).
49. Karimi-Majd, M., Fathian, A.M., and Amiri, B.A., "Hybrid artificial immune network for detecting communities in complex networks", Comput., 97(5), pp. 483-507 (2014).
Scientia Iranica
Volume 30, Issue 3
Transactions on Computer Science & Engineering and Electrical Engineering (D)
May and June 2023
Pages 1068-1084

Files

History

  • Receive Date: 16 April 2022
  • Revise Date: 07 October 2022
  • Accept Date: 14 November 2022

Share

How to cite

Statistics