A Novel Co-Sparse Nonnegative Matrix Factorization Algorithm (Co-SNMF) for Community Detection
An Approach Using Iterative Majorization
In this work, we proposed a novel Co-Sparse Nonnegative Matrix Factorization (CoSNMF) algorithm for the community detection task. It improves upon the previous baseline for NMF algorithms with a Co-(pseudo)norm sparsity constraint, which was set by Peharz and Pernkopf (2012). The novel algorithm is also capable of enforcing the Co-constraint for alternative NMF loss functions, which is not possible with the previous baseline. Iterative majorization was used to obtain a final updating expression. The updating rule decreases the loss function of NMF as much as possible with the best subset, whilst enforcing Co-sparsity. We have implemented the novel Co-SNMF algorithm on one synthetic and seven real-world network datasets, all widely used in academic research. Additionally, we tested its robustness through increasing contamination levels. The results demonstrate that the novel algorithm performs substantially better than the Co-sparse baseline when fixing the number of nonzero elements to one for sparse networks. It attains a higher Normalized Mutual Information under contamination and lower computation time with a slightly slower convergence. For the unconstrained Co-SNMF algorithm we conclude that performance is at least comparable to classic NMF in terms of NMI and robustness, whilst it has a lower computation time. We also observe that Co-constrained algorithms have in general a more stable performance than unconstrained ones for unknown number of communities and noise.
|Keywords||Nonnegative Matrix Factorization, NMF, Co-sparse, Iterative Majorization, Sparse NMF, Community Detection|
|Thesis Advisor||Groenen, P.J.F.|
Leeuw, D. de. (2020, March 17). A Novel Co-Sparse Nonnegative Matrix Factorization Algorithm (Co-SNMF) for Community Detection. Econometrie. Retrieved from http://hdl.handle.net/2105/51746