An augmented Lagrangian alternating direction method for overlapping community detection based on symmetric nonnegative
- PDF / 3,228,699 Bytes
- 13 Pages / 595.276 x 790.866 pts Page_size
- 55 Downloads / 242 Views
ORIGINAL ARTICLE
An augmented Lagrangian alternating direction method for overlapping community detection based on symmetric nonnegative matrix factorization Liying Hu1 · Gongde Guo1 Received: 10 April 2018 / Accepted: 10 July 2019 © Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract In this paper, we present an augmented Lagrangian alternating direction algorithm for symmetric nonnegative matrix factorization. The convergence of the algorithm is also proved in detail and strictly. Then we present a modified overlapping community detection method which is based on the presented symmetric nonnegative matrix factorization algorithm. We apply the modified community detection method to several real world networks. The obtained results show the capability of our method in detecting overlapping communities, hubs and outliers. We find that our experimental results have better quality than several competing methods for identifying communities. Keywords Augmented Lagrangian function · Alternating direction method · Symmetric nonnegative matrix factorization · Overlapping community detection
1 Introduction Nonnegative matrix factorization (NMF) is a matrix decomposition method proposed by Lee and Seung in 1999 in Nature [1]. NMF decomposes the nonnegative data matrix A ∈ Rm×n as a product of two nonnegative matrices U ∈ Rr×m and V ∈ Rr×n such that the objective function
f (U, V) ∶=
1 ‖A − U T V‖2F . 2
(1)
is minimized, where 0 < r ≪ min{m, n} is a given positive integer and ‖ ⋅ ‖F represents the Frobenius norm of the corresponding matrix. NMF plays an important role in many real applications, such as extraction and identification applicable to image processing [1–4], text mining [5–8], spectral data analysis [9], speech processing [10], air quality analysis , and so on. Moreover, NMF is a feature extraction and dimensionality reduction technique in machine learning, which has been * Gongde Guo [email protected] 1
School of Mathematics and Information and Digital Fujian Internet‑of‑things Laboratory of Environmental Monitoring, Fujian Normal University, Fuzhou, China
adapted to community detection recently. For example, Zarei et al. [11] introduced a vertex−vertex correlation matrix and proposed a NMF-based algorithm for identifying the structure of overlapping communities in complex networks. Psorakis et al. [12] proposed a probabilistic approach which utilized a Bayesian nonnegative matrix factorization model to extract overlapping modules from a network. Wang et al. [13] developed three different techniques, Symmetric nonnegative matrix factorization (SNMF), Asymmetric NMF (ANMF) and Joint NMF (JNMF) to identify the hidden communities on different networks. Cao et al. [14] utilized symmetric NMF to identifying overlapping communities as well as hubs and outliers. They not only focused on the detection of communities, but also took into account the identification of vertex roles. Cao et al. [14] adopted a multiplicative updating rule to decompose the symmetric nonnegative data matrix. However, t
Data Loading...
