A Novel Co-Sparse Nonnegative Matrix Factorization Algorithm (Co-SNMF) for Community Detection

In this work, we proposed a novel Co-Sparse Nonnegative Matrix Factorization (Co­SNMF) 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 expres­sion. 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 contami­nation 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 con­tamination and lower computation time with a slightly slower convergence. For the unconstrained Co-SNMF algorithm we conclude that performance is at least compara­ble 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.