## 4 The Proposed Community Detection Method
### Sparse Representation Theory  
SSC is based on the assumption that the data in high-dimensional space belong to some low-dimensional subspace essentially. Using the self-expression property of the data set, each data point can be sparsely represented as a linear combination by other data in the same subspace. The similarity matrix is then constructed by the sparse representation coefficient matrix [21]. Let \(\text{Y}\in\text{R}^{\text{D}\times\text{N}}\) of D-dimensional data \(\{y_{i}\}_{i=1}^{N}\) be located in the linear subspaces \(\{S_{l}\}_{l=1}^{n}\) of \(\text{R}^{\text{D}}\) space, then the dimensions of corresponding subspaces are \(\{d_{i}\}_{i=1}^{n}\). The data set Y is self-represented in matrix form as  
\[\text{Y}=[y_{1},\ldots,y_{N}]=[Y_{1},\ldots,Y_{n}]\Gamma. \tag{7}\]  
In Equation (7), \(Y_{l}\in R^{D\times N_{1}}\) is a matrix composed of \(\text{N}_{l}\) data in the \(l\)th subspace \(\text{S}_{l}\), whose rank is the dimension \(\text{d}_{l}\) of the subspace \(\text{S}_{l}\). \(\Gamma\in R^{N\times N}\) is the coefficient matrix to be solved. For each data point \(y_{i}\), it can be represented by other data points besides itself, that is, \(y_{i}=Yc_{i}\). The vector \(c_{i}=[c_{i1}\ c_{i2}\ \ldots c_{iN}]^{T}\) satisfies \(c_{ii}=0\). And when the data points \(y_{i}\) and \(y_{j}\) are not in the same subspace, \(c_{ij}=0\). The number of nonzero elements in vectors is usually represented by \(\ell_{0}\)-norm, but \(\ell_{0}\)-norm optimization is an NP-hard(Non-deterministic Polynomial) problem [32; 33]. Compressed sensingtheory shows that minimization of \(\ell_{1}\)-norm of the absolute values of vector element is the optimal convex approximation of minimization of the \(\ell_{0}\)-norm. The \(\ell_{1}\)-norm sparse optimization model is:  
\[\min\lVert C\rVert_{1} \tag{8}\]  
\[s.t.\ Y=YC,\ diag(C)=0.\]  
In Equation (8), matrix \(C\) is \([c_{1}\ c_{2}\ \ldots c_{N}]\in R^{N\times N}\), column vector \(c_{i}=[c_{i1}\ c_{i2}\ \ldots c_{N}]^{T}\) corresponds to a sparse representation of data point \(y_{i}\), and \(\mathrm{diag}(C)\in R^{N}\) is a vector composed of diagonal elements \(c_{ii}\) of matrix \(C\). There may be noises and errors in the data set of practical problems. The SSC problem after adding the error term \(E\) can be described as:  
\[\min_{C,E}\frac{\lambda_{z}}{2}\lVert Y-YC-E\rVert_{F}^{2}+\lVert C\rVert_{1} +\lambda_{e}\lVert E\rVert_{1} \tag{9}\]  
\[s.t.diag(C)=0.\]  
In Equation (8), \(\lambda_{z}\)_and_\(\lambda_{e}\) are positive penalty parameters that balance the reconstruction error \(Y-YC\) and noise term \(E\). To solve the coefficient matrix \(C\), two auxiliary variables \(U\) and \(Z\) are introduced as:  
\[\min_{C,E,U,Z}\frac{\lambda_{z}}{2}\lVert Y-YC-E\rVert_{F}^{2}+\lVert Z\rVert _{1}+\lambda_{e}\lVert U\rVert_{1} \tag{10}\]  
\[s.t.C=Z,\ E=U,\ diag(C)=0.\]  
The corresponding augmented Lagrangian objective function is shown as:  
\[ \begin{array}{l}\min_{C,E,U,Z}\frac{\lambda_{Z}}{2}\lVert Y-YC-E\rVert_{F}^ {2}+\lVert Z\rVert_{1}+\lambda_{e}\lVert U\rVert_{1}+\langle A_{C},C-(Z-diag (Z))\rangle+\\ \frac{\alpha_{C}}{2}\lVert C-(Z-diag(Z))\rVert_{F}^{2}+\langle A_{E},E-U \rangle+\frac{\alpha_{E}}{2}\lVert E-U\rVert_{F}^{2}.\end{array}  \tag{11}\]  
In Equation (11), \(\lambda_{z}\,\ \lambda_{e}\ Z,\ E\) and \(U\) are the same as in Equation (9). \(\alpha_{C}\) and \(\alpha_{E}\) are positive penalty parameters, \(A_{C}\) and \(A_{E}\) are the multiplier matrixes, constant. The alternating directions iterations of multipliers are described as the following updating steps to solve the SSC model Equation (11):  
Step 1: Update \(C\). When other parameters are given in the \(k\)th iteration, the objective function is minimized with respect to \(C\). The linear equation of the \(\mathrm{C_{k+1}}\) can be solved as:  
\[\Big{(}\lambda_{n}\mathrm{Y^{T}Y+a_{c}I}\Big{)}\mathrm{C_{k+1}}=\lambda_{n} \mathrm{Y^{T}(Y-E)+a_{c}(Z_{k}+diag(Z_{k}))-A_{c,k}}. \tag{12}\]  
Step 2: Update \(E\).