A Further Study on the Degree-Corrected Spectral Clustering under Spectral Graph Theory

Abstract

Spectral clustering algorithms are often used to find clusters in the community detection problem. Recently, a degree-corrected spectral clustering algorithm was proposed. However, it is only used for partitioning graphs which are generated from stochastic blockmodels. This paper studies the degree-corrected spectral clustering algorithm based on the spectral graph theory and shows that it gives a good approximation of the optimal clustering for a wide class of graphs. Moreover, we also give theoretical support for finding an appropriate degree-correction. Several numerical experiments for community detection are conducted in this paper to evaluate our method.

1. Introduction

Due to the growing availability of datasets of large-scale networks, community detection has attracted significant consideration. The community detection problem is to discover a community structure by dividing the network into multiple clusters according to the affinity between nodes. Because the spectral clustering method is easy to implement and can detect non-convex clusters, it is widely used for detecting clusters in networks. Compared to the traditional algorithms, spectral clustering performs well and has many fundamental advantages [1,2,3,4].

In the spectral clustering algorithm, the similarity between the data points is reflected by the weights on the edges in the graph. The data points are mapped to a lower-dimensional space through the Laplacian matrix of the graph, and finally, the non-convex datasets in the obtained low-dimensional space are clustered by traditional clustering algorithms.

Let $G=(V,E)$ be an undirected and unweighted simple graph with n nodes, where V and E are the set of nodes and edges, respectively. The adjacency matrix of graph G, denoted by $W=\left(w_{ij}\right)$, is a 0–1 symmetric matrix of order n, where the $(i,j)$-th and $(j,i)$-th element is 1 if there is an edge between two nodes i and j, and 0 otherwise. Let $d_i={\sum }_{j=1}^n{w}_{ij}$, which is defined as the degree of node i. Moreover, $d_{max}={max}_{i\in V}{d}_i$ and $d_{min}={min}_{i\in V}{d}_i$ are called the maximal degree and minimal degree of G, respectively. Denote $\overline{d}$ as the average degree of graph G, which equals $\frac{1}{n}{\sum }_{i=1}^n{d}_i$. The degree matrix is defined by $D=diag(d_1,\cdots ,d_n)$. The symmetric matrix $D-W$ is called an unnormalized Laplacian of G, each of whose row sum is zero. The normalized Laplacian $L=I-D^{-1/2}W{D}^{-1/2}$ has zero as the smallest eigenvalue and plays an very important role in the spectral clustering algorithm. It is well defined only in case $D^{-1}$ exists, i.e., there are no isolated nodes.

In 2002, Ng et al. [5] proposed a version of spectral clustering (NJW) under the normalized Laplacian matrix. Moreover, the authors in [5] analyzed their algorithm using matrix perturbation theory and gave the conditions for the algorithm performing well when nodes from different clusters are well-separated. However, when dealing with a sparse network with a strong degree of heterogeneity, i.e., the minimum degree of the graph is low, and NJW cannot concentrate well. To resolve this issue, Chaudhuri and Chung [6] introduced the notion of a degree-corrected random-walk Laplacian $I-{\left(D+\tau I\right)}^{-1}W$ and demonstrated that it outputs the correct partition under a wide-range graph generated from extended planted partition (EPP) model. Instead of doing the spectral decomposition on the entire matrix, Chaudhuri and Chung [6] divided the nodes into two random subsets and only used the induced subgraph on one of those random subsets to compute the spectral decomposition. Qin and Rohe [7] investigated the spectral clustering algorithm using the degree-corrected normalized Laplacian $L_{\tau }=I-{\left(D+\tau I\right)}^{-1/2}W{\left(D+\tau I\right)}^{-1/2}$ under the degree-corrected stochastic blockmodel, where $\tau =\overline{d}$. This method extended the previous statistical estimation results to the more canonical spectral clustering algorithm, which is called the regularized spectral clustering (RSC). Recently, Qing and Wang [8] proposed an improved spectral clustering under the degree-corrected stochastic blockmodel also, where $\tau =0.1\frac{d_{min}+d_{max}}{2}$, (ISC). Unlike NJW and RSC, which use the top k eigenvectors to construct the mapping matrix, ISC uses the top $k+1$ eigenvectors and the corresponding eigenvalues instead and outperforms especially in the weak signal networks, where k is the number of clusters.

Actually, previous works for spectral clustering with the degree-corrected Laplacian were mostly applied to graphs generated from stochastic blockmodels. Moreover, the optimal $\tau$ has a complex dependence on the degree of distribution of the graph and $\tau =\overline{d}$ provides good results [6,7]. In [7], the authors claimed that when $\tau =\overline{d}$, it could be adjusted by a multiplicative constant and the results are not sensitive to such adjustments. However, some numerical experiments show that an appropriate $\tau$ could be found for a better performance.

This paper investigates the spectral clustering algorithm using the degree-corrected Laplacian in view of spectral graph theory [9] and shows that it also works for a wide class of graphs. Moreover, we also provide theoretical guidance on the choice of the parameter $\tau$. Finally, six real-world datasets are used to test the performance of our method for an appropriate $\tau$. The results are roughly equivalent to that of RSC, or even better.

The rest of this paper is organized as follows. In Section 2, we list some relative definitions and useful lemmas in the analysis of our main results in Section 3. In Section 4, some numerical experiments are conducted for the real-world datasets. Moreover, some artificial networks are generated to analyze the effect of our method in terms of some related parameters. The conclusion and future work are provided in Section 5.

2. Preliminary

Let $G=(V,E)$ be a graph. The symmetric difference of two subsets S and T of V is defined as $S\Delta T=(S\backslash T)\cup (T\backslash S)$. For a subset S of V, $E(S,V\backslash S)=\left\{\right(u,v)\in E:u\in S,v\in V\backslash S\}$. The symbol $\mu \left(S\right)$ denotes the volume of S that is given by the sum of degree of all notes in S, i.e., $\mu \left(S\right)={\sum }_{v\in S}{d}_v$. If k disjoint subsets $S_1,\cdots ,S_k$ of V satisfy ${\cup }_{i=1}^k{S}_i=V$, we call $\{S_1,\cdots ,S_k\}$ a k-way partition of V. Kolev and Mehlhorn [10] introduced the minimal average conductance denoted by

$${\overline{\varphi }}_k\left(G\right)=\underset{\{S_1,\cdots ,S_k\}\in U}{min}\frac{1}{k}(\varphi \left(S_1\right)+\cdots +\varphi \left(S_k\right)),$$

where U is a set of containing every k way partition of the points set of G, and   $\varphi \left(S\right)=\frac{\left|E\right(S,V\backslash S\left)\right|}{\mu \left(S\right)}$. A partition $\{S_1,\cdots ,S_k\}$ is called optimal, if it satisfies that $\frac{1}{k}(\varphi \left(S_1\right)+\cdots +\varphi \left(S_k\right))={\overline{\varphi }}_k\left(G\right).$ In this paper, we denote $\left\{A_1,\dots ,A_k\right\}$ as the actual partition returned by the RSC algorithm, where k is the number of classes of the graph.

Let ${\parallel ·\parallel }_2$ denote the 2-norm for a vector and ${\parallel ·\parallel }_F$ denote the Frobenius norm for a matrix.

The k-means algorithm tends to find a set of k centers ${\mathit{c}}_1,\cdots ,{\mathit{c}}_k$ to minimize the sum of the squared-distance between the points and the center to which it is assigned.

Let F be a spectral embedding map from V to a vector space. Given any k-way partition of G and a set of vectors, say $\{S_1,\cdots ,S_k\}$ and ${\mathit{w}}_1,\cdots ,{\mathit{w}}_k$, respectively, the cost function of partition $\{S_1,\cdots ,S_k\}$ of V, mentioned in [11], is defined as

$$\begin{array}{c}\hfill g(S_1,\cdots ,S_k,{\mathit{w}}_1,\cdots ,{\mathit{w}}_k)=\sum _{i=1}^k\sum _{v\in S_i}{d}_v{\parallel F\left(v\right)-{\mathit{w}}_i\parallel }_2^2.\end{array}$$

(1)

The main idea of this function is to expand each element $F\left(v\right)$ of V by making $d_v$ copies of $F\left(v\right)$ and form a set with $2\left|E\right(G\left)\right|$ nodes. Then, it acquires a partition by using k-means algorithm. The “trick” is to copy every node u to $d_u$ identical nodes. This method can efficiently deal with the networks, which have the overlap between clusters. For convenience, it is necessary to assume that the k-means clustering algorithm outputs of the expansion of vertices V satisfying the following condition.

(A)

For every $v\in V$, all $d_v$ copies of $F\left(v\right)$ are contained in one part.

Suppose that $\{Y_1,\cdots ,Y_k\}$ is the partition of V with centers ${\mathit{z}}_1,\cdots ,{\mathit{z}}_k$, which is the output of the k-means clustering algorithm, the value of the clustering cost function is denoted by “COST”, i.e.,

$$COST=g(Y_1,\cdots ,Y_k,{\mathit{z}}_1,\cdots ,{\mathit{z}}_k).$$

Then, we will introduce the traditional NJW and RSC Algorithm 1.

Algorithm 1. The traditional NJW and RSC algorithm

Input:  $W,k,$ ( $\tau$ for RSC)   1:  Calculate the normalized Laplacian matrix $L=D^{-1/2}W{D}^{-1/2}$. ($L_{\tau }={(D+\tau I)}^{-1/2}W{(D+\tau I)}^{-1/2}$ for RSC).   2:  Find the eigenvectors $f_1,\cdots ,f_k$ corresponding to the k largest eigenvalues of L. Form $X=[f_1,\cdots ,f_k]$ by putting the eigenvectors into the columns.   3:  Normalize each row of X to get matrix Y, i.e., $Y_{ij}=X_{ij}/{\left({\sum }_{j=1}^k{X}_{ij}^2\right)}^{1/2},$ where $i=1,\cdots ,n$ and $j=1,\cdots ,k$.   4:  Apply k-means method to Y to get the label of each node. Output:  labels for all nodes

3. Analysis of RSC Algorithm

Our method for analyzing the RSC algorithm follows the strategy developed by Peng et al. [11], Kolve et al. [10], and Mizutani [12]. Let $\{S_1,\cdots ,S_k\}$ be a partition of the nodes set of V. Define ${\mathit{g}}_i\in {\mathbb{R}}^n$ is the normalized indicator of $S_i$. That means, if $v\in S_i$, the v-th element of ${\mathit{g}}_i$ is one, or else is zero. The normalized indicator ${\overline{\mathit{g}}}_i$ of $S_i$ is given as

$${\overline{\mathit{g}}}_i=\frac{D^{1/2}{\mathit{g}}_i}{\parallel D^{1/2}{\mathit{g}}_i{\parallel }_2}=\left\{\begin{array}{cc}\sqrt{\frac{d_v}{\mu \left(S_i\right)}}\hfill & v\in S_i\hfill \\ 0\hfill & v\notin S_i.\hfill \end{array}\right.$$

It is obvious that $\parallel {\overline{\mathit{g}}}_i{\parallel }_2=1$.

The following result is called the structure theoremwhich plays a very important role to examine the performance of the spectral clustering. It shows that there is a linear combination ${\widehat{\mathit{f}}}_i$ of ${\mathit{f}}_1,\cdots ,{\mathit{f}}_{k+1}$ such that ${\widehat{\mathit{f}}}_i$ and ${\mathit{g}}_i$ are close.

Theorem 1

(Structure Theorem). Let

$$\mathsf{\Psi }=\frac{1}{1-{\lambda }_{k+1}\left(\tau \right)}\left(1-\frac{d_{min}}{d_{max}+\tau }+{\overline{\varphi }}_k\left(G\right)\frac{d_{min}}{d_{max}+\tau }\right),$$

where ${\lambda }_{k+1}\left(\tau \right)$ (${\lambda }_{k+1}$ for short) is the $(k+1)$-th largest eigenvalue of $L_{\tau }$, and $\{S_1,\cdots ,S_k\}$ be the ${\overline{\varphi }}_k\left(G\right)$-optimal partition of G, $\overline{\mathit{G}}=[{\overline{\mathit{g}}}_1,\dots ,{\overline{\mathit{g}}}_k]\in {\mathbb{R}}^{n\times k}$, $\overline{\mathit{F}}=[{\mathit{f}}_1,\dots ,{\mathit{f}}_k]\in {\mathbb{R}}^{n\times k}.$ If $k\mathsf{\Psi }<1$, then there exists a $k\times k$ orthogonal matrix $\mathit{U}=[{\mathit{u}}_1,\dots ,{\mathit{u}}_k]$, such that

$$\parallel \overline{\mathit{F}}\mathit{U}-\overline{\mathit{G}}{\left|\right|}_F\le 2\sqrt{k\mathsf{\Psi }}.$$

Proof. 

Denote ${\overline{\mathit{g}}}_i^u$ as the element in ${\overline{\mathit{g}}}_i$ corresponding to the vertex u. Moreover, let

$${\overline{\mathit{g}}}_i=\sum _{j=1}^n{h}_{i,j}{\mathit{f}}_j,\widehat{{\mathit{f}}_i}=\sum _{j=1}^k{h}_{i,j}{\mathit{f}}_j.$$

First,

$$\begin{array}{cc}\hfill {\overline{\mathit{g}}}_i^T{L}_{\delta }\overline{{\mathit{g}}_i}& =\sum _{\{u,v\}\in E\left(G\right)}\left[{\left(\frac{1}{\sqrt{d_u}}{\overline{\mathit{g}}}_i^u\right)}^2-\frac{2}{\sqrt{d_u+\tau }\sqrt{d_v+\tau }}{\overline{\mathit{g}}}_i^u{\overline{\mathit{g}}}_i^v+{\left(\frac{1}{\sqrt{d_v}}{\overline{\mathit{g}}}_i^v\right)}^2\right]\hfill \\ \hfill & =\sum _{u\in S_i;v\in {\overline{S}}_i}\frac{1}{\mu \left(S_i\right)}+\sum _{u,v\in S_i}\frac{2}{\mu \left(S_i\right)}(1-\frac{\sqrt{d_u{d}_v}}{\sqrt{d_u+\tau }\sqrt{d_v+\tau }})\hfill \\ \hfill & \le \varphi \left(S_i\right)+\frac{2E\left(S_i\right)}{\mu \left(S_i\right)}(1-\frac{d_{min}}{d_{max}+\tau })\hfill \\ \hfill & =1-\frac{2E\left(S_i\right)}{\mu \left(S_i\right)}\frac{d_{min}}{d_{max}+\tau }\hfill \\ \hfill & =1-\frac{d_{min}}{d_{max}+\tau }+\varphi \left(S_i\right)\frac{d_{min}}{d_{max}+\tau }<1.\hfill \end{array}$$

(2)

On the other hand,

$$\begin{array}{cc}\hfill {\overline{\mathit{g}}}_i^T{L}_{\delta }\overline{{\mathit{g}}_i}& ={\left(\sum _{j=1}^n{h}_{i,j}{\mathit{f}}_j\right)}^T{L}_{\delta }\left(\sum _{j=1}^n{h}_{i,j}{\mathit{f}}_j\right)\hfill \\ \hfill & ={\left(\sum _{j=1}^n{h}_{i,j}{\mathit{f}}_j\right)}^T\left(\sum _{j=1}^n{h}_{i,j}(1-{\lambda }_j){\mathit{f}}_j\right)\hfill \\ \hfill & =\sum _{j=1}^n{h}_{i,j}^2(1-{\lambda }_j)\hfill \\ \hfill & \ge \sum _{j=k+1}^n{h}_{i,j}^2(1-{\lambda }_j)\hfill \\ \hfill & \ge (1-{\lambda }_{k+1})\sum _{j=k+1}^n{h}_{i,j}^2.\hfill \end{array}$$

Then,

$$\left|\right|\widehat{{\mathit{f}}_i}-\overline{{\mathit{g}}_i}{\left|\right|}_2^2=\sum _{j=k+1}^n{h}_{i,j}^2\le \frac{1}{1-{\lambda }_{k+1}}\left(1-\frac{d_{min}}{d_{max}+\tau }+\varphi \left(S_i\right)\frac{d_{min}}{d_{max}+\tau }\right),$$

and

$$\left|\right|\widehat{\mathit{F}}-\overline{\mathit{G}}{\left|\right|}_F^2=\sum _{i=1}^k\left|\right|\widehat{{\mathit{f}}_i}-\overline{{\mathit{g}}_i}{\left|\right|}_2^2\le \frac{1}{1-{\lambda }_{k+1}}\left(1-\frac{d_{min}}{d_{max}+\tau }+{\overline{\varphi }}_k\left(G\right)\frac{d_{min}}{d_{max}+\tau }\right).$$

Let ${\mathit{h}}_i={[h_{i,1},\dots ,h_{i,k}]}^T$, $i=1,\cdots ,k$, and $\mathit{H}=[{\mathit{h}}_1,\dots ,{\mathit{h}}_k]\in {\mathbb{R}}^{k\times k}$. Considering the singular value decomposition of $\mathit{H}$, given as $\mathit{H}=\mathit{A}\Sigma {\mathit{B}}^T$, where $\mathit{A}\in {\mathbb{R}}^{k\times k}$ and $\mathit{B}\in {\mathbb{R}}^{k\times k}$ are orthogonal matrices, and $\Sigma$ is a $k\times k$ diagonal matrix.

Let $\mathit{U}={\mathit{AB}}^T$ and $\mathit{R}=\mathit{U}-\mathit{H}\in {\mathbb{R}}^{k\times k}$. Then, $\mathit{U}$ is an orthogonal matrix. According to the proof of Theorem 4 in [12], it obtains

$$\begin{array}{c}\hfill {\parallel \mathit{R}\parallel }_F\le k\mathsf{\Psi }and{\parallel \overline{\mathit{F}}\mathit{U}-\overline{\mathit{G}}\parallel }_F\le k\mathsf{\Psi }+\sqrt{k\mathsf{\Psi }}.\end{array}$$

When $k\mathsf{\Psi }<1$, we have

$$\begin{array}{c}\hfill \parallel \overline{\mathit{F}}\mathit{U}-\overline{\mathit{G}}{\parallel }_F\le 2\sqrt{k\mathsf{\Psi }}.\end{array}$$

(3)

This completes the proof. □

Given k vectors, say ${\mathit{c}}_1,\dots ,{\mathit{c}}_k\in {\mathbb{R}}^k$, we suppose that $\left|\right|{\mathit{c}}_i-{\mathit{c}}_j{\left|\right|}_2^2$ is lower bounded by some real numbers ${\zeta }_{i,j}\ge 0$ and $g(S_i,\dots ,S_k,{\mathit{c}}_1,\dots ,{\mathit{c}}_k)$ is upper bound by a real number $\omega \ge 0$, i.e.,

$$\begin{array}{c}\hfill \left|\right|{\mathit{c}}_i-{\mathit{c}}_j{\left|\right|}_2^2\ge {\zeta }_{ij}(i\ne j)andg(S_i,\dots ,S_k,{\mathit{c}}_1,\dots ,{\mathit{c}}_k)\le \omega .\end{array}$$

(4)

We are now ready to derive the bounds of ${\zeta }_{ij}$ and $\omega$ shown in (4) for the RSC algorithm. Let $\overline{\mathit{F}}=[{\mathit{f}}_1,\cdots ,{\mathit{f}}_k]$ and ${\mathit{p}}_v$ be the v-th row of $\overline{\mathit{F}}$, corresponding to the node v. Since U is an orthogonal matrix, the inequality (3) can be rewritten as

$$\parallel \overline{\mathit{F}}U-\overline{\mathit{G}}{\parallel }_F=\parallel \overline{\mathit{F}}-\overline{\mathit{G}}{\mathit{U}}^T{\parallel }_F={\parallel {\overline{\mathit{F}}}^T-\mathit{U}{\overline{\mathit{G}}}^T\parallel }_F=\sum _{i=1}^k\sum _{v\in S_i}\parallel {\mathit{p}}_v-\sqrt{\frac{d_v}{\mu \left(S_i\right)}}{\mathit{u}}_i{\parallel }_2^2.$$

(5)

The spectral embedding map in the RSC algorithm, denoted by $F_{RSC}\left(v\right)$, is given as

$$F_{RSC}\left(v\right)=\frac{1}{\parallel {\mathit{p}}_v{\parallel }_2}{\mathit{p}}_v.$$

Hence, according to the discussion in [12], it is easy to obtain the upper bound of “COST”. The discussion needs the following inequality.

Lemma 1

([12]). The following inequality holds for a vector $\mathit{a}\in {\mathbb{R}}^k$ and a vector $\mathit{u}\in {\mathbb{R}}^k$ with ${\parallel \mathit{u}\parallel }_2=1$,

$$\parallel \frac{\mathit{a}}{{\parallel \mathit{a}\parallel }_2}-\mathit{u}{\parallel }_2\le 2{\parallel \mathit{a}-\mathit{u}\parallel }_2.$$

Theorem 2.

Let a partition $\{S_1,\cdots ,S_l\}$ of G be an optimal achieving ${\overline{\varphi }}_k\left(G\right)$ and $F_{RSC}$ be the spectral embedding map in RSC algorithm. Define the center of $S_i$, ${\mathit{c}}_i={\mathit{u}}_i$ for $i=1,\cdots ,k$, then

• $\parallel {\mathit{c}}_i-{\mathit{c}}_j{\parallel }_2^2=2$.
• $g(S_1,\dots ,S_k,{\mathit{c}}_1,\dots ,{\mathit{c}}_k)\le 16k{\mu }_{max}\mathsf{\Psi }$,

where ${\mu }_{max}=max\left\{\mu \left(S_i\right)\right|i=1,2,\cdots ,k\}$.

Proof. 

First, since ${\mathit{c}}_i={\mathit{u}}_{\mathit{i}}$, we have that

$$\parallel {\mathit{c}}_i-{\mathit{c}}_j{\parallel }_2^2={({\mathit{u}}_i-{\mathit{u}}_j)}^T({\mathit{u}}_i-{\mathit{u}}_j)=2.$$

On the other hand, let $F\left(v\right)=\sqrt{\frac{\mu \left(S_i\right)}{d_v}}{\mathit{p}}_v$. Then,

$$\begin{array}{cc}\hfill & g(S_1,\cdots ,S_k,{\mathit{c}}_1,\cdots ,{\mathit{c}}_k)\hfill \\ \hfill =& \sum _{i=1}^k\sum _{v\in S_i}{d}_v{\parallel F_{RSC}\left(v\right)-{\mathit{u}}_i\parallel }_2^2\hfill \\ \hfill =& \sum _{i=1}^k\sum _{v\in S_i}{d}_v\parallel \frac{\mathit{p}\left(v\right)}{\parallel \mathit{p}\left(v\right)\parallel }-{\mathit{u}}_i{\parallel }_2^2\hfill \\ \hfill =& \sum _{i=1}^k\sum _{v\in S_i}{d}_v\parallel \frac{F\left(v\right)}{\parallel F\left(v\right)\parallel }-{\mathit{u}}_i{\parallel }_2^2\hfill \\ \hfill \le & 4\sum _{i=1}^k\sum _{v\in S_i}{d}_v\parallel \sqrt{\frac{\mu \left(S_i\right)}{d_v}}{\mathit{p}}_v-{\mathit{u}}_i{\parallel }_2^2(\mathrm{by} \mathrm{Lemma} 1)\hfill \\ \hfill =& 4\sum _{i=1}^k\sum _{v\in S_i}\mu \left(S_i\right)\parallel {\mathit{p}}_v-\sqrt{\frac{d_v}{\mu \left(S_i\right)}}{\mathit{u}}_i{\parallel }_2^2(\mathrm{by} \mathrm{Equation} (5) \mathrm{and} \mathrm{Theorem} 1)\hfill \\ \hfill \le & 16k{\mu }_{max}\mathsf{\Psi }.\hfill \end{array}$$

The result holds. □

Assume that $\mathrm{OPT}$ stands for the optimal clustering cost of graph G, then it is obvious that $\mathrm{COST}\le \alpha ·\mathrm{OPT}$, where $\alpha$ is an approximation ratio. Moreover, $\mathrm{OPT}\le g(S_1,\cdots ,S_k,{\mathit{c}}_1,\cdots ,{\mathit{c}}_k)$. Therefore, we can obtain the upper bound of COST.

Theorem 3.

Let $\{S_1,\cdots ,S_k\}$ be a ${\overline{\varphi }}_k\left(G\right)$-optimal partition of G. Then

$$COST\le 16k\alpha {\mu }_{max}\mathsf{\Psi }.$$

Lemma 2

([12]). Assume that, for every permutation $\pi :\left\{1,\dots ,k\right\}\to \left\{1,\dots ,k\right\}$, there is an index l such that $\mu (A_l\Delta S_{\pi \left(l\right)})\ge 2ϵ\mu \left(S_{\pi \left(l\right)}\right)$ for a real number $0\le ϵ\le 1/2$. Then, the following inequality holds,

$$COST\ge \frac{1}{8}\sum _{i\in H}{\xi }_i{\zeta }_{i,p}min\left\{\mu \left(S_i\right),\mu \left(S_l\right)\right\}-\omega ,$$

where H is a subset of $\left\{1,\dots ,k\right\}$, p is an element of $\left\{1,\dots ,k\right\}$ and ${\xi }_i\ge 0$ is a non-negative real number satisfying ${\sum }_{i\in H}{\xi }_i\ge ϵ$, and ω is the upper bound of $g(S_1,\cdots ,S_k,{\mathit{c}}_1,\cdots ,{\mathit{c}}_k)$ in (4).

By setting ${\zeta }_{i,j}=2$ and $\omega =16k\alpha {\mu }_{max}\mathsf{\Psi }$, then we obtain the following result.

Theorem 4.

Suppose that the assumption of Lemma 2 holds. Then,

$$COST\ge \frac{1}{4}ϵ{\mu }_{min}-16k{\mu }_{max}\mathsf{\Psi }.$$

Theorem 5

(Main result). Given a graph G = (V,E) and a positive integer k, let a partition $\left\{S_1,\dots ,S_n\right\}$ of G be ${\overline{\varphi }}_k\left(G\right)-optimal$ and $A_1,\dots ,A_n$ be a partition of G returned by the RSC clustering algorithm. Assume that a k-means clustering algorithm has an approximation ratio of α and satisfies assumption (A). If $\mathsf{\Psi }\le \frac{{\mu }_{min}}{264\ast 2k\alpha {\mu }_{max}}$, then, after a suitable renumbering of $A_1,\dots ,A_k$, the following holds for $i=1,\dots ,k$,

$$\mu \left(A_i\Delta S_i\right)\le \left(\frac{264k\alpha {\mu }_{max}}{{\mu }_{min}}\mathsf{\Psi }\right)\mu \left(S_i\right).$$

Proof. 

Choose a real number

$$ϵ=\frac{132k\alpha {\mu }_{max}}{{\mu }_{min}}\mathsf{\Psi }<\frac{1}{4}.$$

Assume that, for every permutation $\pi :\left\{1,\dots ,k\right\}\to \left\{1,\dots ,k\right\}$, there is an index l such that $\mu (A_l\Delta S_{\pi \left(l\right)})\ge 2ϵ\mu \left(S_{\pi \left(l\right)}\right)$ for a real number $ϵ$. Hence, applying Theorems 3 and 4, we can obtain the following

$$\begin{array}{cc}\hfill COST& \ge \frac{1}{4}ϵ{\mu }_{min}-16k{\mu }_{max}\mathsf{\Psi }\hfill \\ \hfill & \ge 33k\alpha {\mu }_{max}\mathsf{\Psi }-16k\alpha {\mu }_{max}\mathsf{\Psi }\hfill \\ \hfill & =17k\alpha {\mu }_{max}\mathsf{\Psi }\hfill \\ \hfill & >16k\alpha {\mu }_{max}\mathsf{\Psi },\hfill \end{array}$$

which contradicts Theorem 3. That means, after a suitable renumbering of $A_1,\dots ,A_n$, we have

$$\mu \left(A_i\Delta S_i\right)\le 2ϵ\mu \left(S_i\right)=\left(\frac{264k\alpha {\mu }_{max}}{{\mu }_{min}}\mathsf{\Psi }\right)\mu \left(S_i\right),$$

for every $i=1,2,\cdots ,k$. □

4. Finding an Appropriate $\mathit{\tau }$ and Numerical Experiment

The main theorem gives an upper bound of $\mu (A_i\Delta S_i)$ in RSC algorithm. It tells us that the performance would vary while the term $\mathsf{\Psi }$ decreases with increasing $\tau$. In this section, we will try to find an appropriate $\tau$ for the good partitioning, according to this main theorem.

Before our analysis, we may make some reasonable assumptions as (B) to (D).

(B)

$2|E\left(S_i\right)|/\mu \left(S_i\right)>1/\overline{d}$

(C)

$\tau \le k\overline{d}$

(D)

${\mu }_{min}/{\mu }_{max}\le \frac{2\overline{d}}{n}.$

Firstly, $\frac{2\left|E\right(S_i\left)\right|}{\mu \left(S_i\right)}$ stands for the ratio of the edges in $S_i$ to the degree summation of all points in $S_i$. We may assume that $\frac{2\left|E\right(S_i\left)\right|}{\mu \left(S_i\right)}>1/\overline{d}$, since $S_i$ is one of clusters in the optimal partitioning. Second, as mentioned in [6,7], the choice of $\tau$ is very important. If $\tau$ is too small, there is insufficient regularization. If $\tau$ is too large, it washes out significant eigenvalues. Then, it is reasonable to assume that $\tau \le k\overline{d}$. Moreover, ${\mu }_{min}$ and ${\mu }_{max}$ stand for the edges in the responding cluster and the ratio of them stands for the relative density. Hence, we can assume that $\frac{{\mu }_{min}}{{\mu }_{max}}\le \frac{2\overline{d}}{n}.$

Then,

$$\mathsf{\Psi }\le \frac{1}{1-{\lambda }_{k+1}\left(\tau \right)}\left(1-\frac{d_{min}}{\overline{d}(d_{max}+\tau )}\right)\le \frac{\overline{d}(d_{max}+k\overline{d})-d_{min}}{(1-{\lambda }_{k+1}\left(\tau \right))\left(\overline{d}(d_{max}+\tau )\right)},$$

where ${\lambda }_{k+1}\left(\tau \right)$ is the $(k+1)$-th largest eigenvalue of $L_{\tau }$. Furthermore, the theoretical analysis in [7] shows that $\tau =\overline{d}$ provides good results and one could adjust this by a multiplicative constant. For these reasons, we set $\tau =\delta \overline{d}$ and attend to find an appropriate $\delta$ to refine the algorithm.

Six real datasets are used to test our method. These datasets can be downloaded directly from http://zke.fas.harvard.edu/software.html, accessed on 10 September 2022.

Table 1. The information of six real datasets.

DataSet	Source	n	k	${\mathit{d}}_{\mathit{min}}$	${\mathit{d}}_{\mathit{max}}$	$\overline{\mathit{d}}$
UKfaculty	Nepusz et al. (2008) [13]	79	3	2	39	13.97
caltech	Traud et al. (2011) [14]	590	8	1	179	43.46
dolphins	Lusseau (2003) [15]	62	2	1	12	5.12
karate	Zachary (1977) [16]	34	2	1	17	4.6
politicalblog	Adamic and Glance (2005) [1]	1222	2	1	351	27.35
simmons	Traud et al. (2011) [14]	1137	4	1	293	42.66

shows the detail information of six real datasets, including the source of the dataset, the number of data points (n), the number of communities included (k), the minimum degree of data points ($d_{min}$), and the maximum degree of data points ($d_{max}$).

4.1. Find an Appropriate $\delta$

Let

$$UB\left(\delta \right)=\frac{1}{(1-{\lambda }_{k+1}\left(\delta \overline{d}\right))(d_{max}+\delta \overline{d})}.$$

Figure 1 plots the variation of UB($\delta$) when $\delta$ varies between 0 and 1 in six real datasets. It is obvious that $UB\left(\delta \right)$ is decreasing with increasing $\delta$. The following theorem (often called the Geršgorin disc theorem) makes this observation true.

Theorem 6

(Geršgorin Disk Theorem). Let $A=\left(a_{ij}\right)\in {\mathbb{R}}^{n\times n}$ and

$$R_i\left(A\right)=\sum _{\genfrac{}{}{0pt}{}{j=1}{j\ne i}}^n\left|a_{ij}\right|,1\le i\le n$$

denote the deleted absolute row sums of A. Then, all the eigenvalues of A are located in the union of n discs

$$\bigcup _{i=1}^n\{z\in \mathbf{C}:|z-a_{ii}|\le R_i\left(A\right)\}\equiv G\left(A\right).$$

It tells us that, for all $i=1,2,\cdots ,n$, $R_i\left(L_{\delta \overline{d}}\right)$ decreases with increasing $\delta$. Then, ${\lambda }_{k+1}\left(\delta \overline{d}\right)$ and the term $UB\left(\delta \right)$ will decrease as well. It is easy to see that ${lim}_{\delta \to \infty }UB\left(\delta \right)=0$. Therefore, we would like to find an appropriate $\delta$, such that the upper bound $UB\left(\delta \right)$ will not vary too much, when $\delta$ varies small.

According to Theorem 5, we may assume that

$$\mathsf{\Psi }\le \frac{\overline{d}(d_{max}+k\overline{d})-d_{min}}{(1-{\lambda }_{k+1}\left(\tau \right))\left(\overline{d}(d_{max}+\tau )\right)}\le \frac{{\mu }_{min}}{264\ast 2k\alpha {\mu }_{max}}.$$

Then

$$\frac{1}{(1-{\lambda }_{k+1}\left(\tau \right))\left(\overline{d}(d_{max}+\tau )\right)}\le \frac{\overline{d}}{264k^{2}n},$$

follows from the assumption $\frac{{\mu }_{min}}{{\mu }_{max}}\le \frac{2\overline{d}}{n}$ and $\overline{d}(d_{max}+k\overline{d})-d_{min}\ge k$.

Define $UBD\left(\delta \right)$ as the absolute difference of $UB$ when $\delta$ increases 0.005, i.e., $UBD\left(\delta \right)=\left|UB\right(\delta +0.005)-UB(\delta \left)\right|$. We would like to find that ${\delta }_0$ satisfies the following conditions:

$$\begin{array}{c}\hfill \left\{\begin{array}{cc}\forall \delta \ge {\delta }_0,\hfill & UB{D}_{\delta }\le \frac{\overline{d}}{264k^{2}n}\hfill \\ \forall \delta <{\delta }_0,\hfill & UB{D}_{\delta }>\frac{\overline{d}}{264k^{2}n}.\hfill \end{array}\right.\end{array}$$

(6)

In the rest of this paper, three indices, namely RI, NMI, and error rate, are used to evaluate the effectiveness.

Evaluation Indices

Rand Index For a dataset with n data points, the total number of sample pairs is $\frac{n(n-1)}{2}$. If two sample points belong to the same class are classified into the same class, we denote the number of such sample pairs as a. If two sample points belong to different classes are divided into different classes, we denote the number of such sample pairs as b. The calculation formula of RI is as follows:

$$RI=\frac{a+b}{n(n-1)/2}.$$

The $RI$ value represents the proportion of correctly clustered sample pairs in all sample pairs and is often used to measure the similarity between two datasets. Obviously, $RI$ is between 0 and 1. If $RI=1$, the clustering is completely correct, and if $RI=0$, it is completely wrong.

Normalized Mutual Information We use U and V to denote the true label vector and predicted label vector, respectively. Let $U_i$ represent the elements belonging to class i in U and $V_j$ represent the elements belonging to class j in V. $H\left(U\right)$ represents the information entropy of U, that could be calculated by

$$H\left(U\right)=-\sum _{i=1}^n{p}_{i}log{p}_i,$$

where the base of the logarithmic function is usually 2 and $p_i$ represents the ratio of the number of nodes belonging to class i to the total amount of nodes, i.e., $p_i=\frac{|U_i|}{n}$. Now, we can obtain the formula for calculating mutual information (MI):

$$MI(U,V)=\sum _{i=1}^n\sum _{j=1}^n{p}_{ij}log\left(\frac{p_{ij}}{p_i\times p_j}\right),$$

where $p_{ij}=\frac{|U_i\cap V_j|}{n}$. Based on the information entropy and the mutual information, we can obtain the normalized mutual information as

$$NMI(U,V)=2\frac{MI(U,V)}{H\left(U\right)\times H\left(V\right)}.$$

Error Rate Error rate is defined by

$$mi{n}_{\left\{\pi :permutationover\left\{1,2,\cdots ,k\right\}\right\}}\frac{1}{n}\sum _{i=1}^{n}1\left\{\pi \left({\widehat{l}}_i\ne l_i\right)\right\},$$

where ${\widehat{l}}_i$ and $l_i$ are the true and predicted labels of node i, respectively.

4.2. Real Networks Experiments

After some pre-processing, these six real datasets are all networks containing k non-overlapping communities and are labeled. We will use RSC-$\delta$ to stand for the RSC algorithm when $\delta ={\delta }_0$ which satisfies the condition in (6). Actually, NJW, RSC, and RSC-$\delta$ are three different cases in RSC algorithm, when $\delta$ takes different values. When $\delta =0$, it is NJW algorithm. When $\delta =1$, it is the RSC algorithm. When $\delta ={\delta }_0$ in (6), it is RSC-$\delta$.

Table 2. Results on six real datasets.

DataSet		UKfaculty	Caltech	Dolphins	Karate	Politicalblog	Simmons
	NJW	0.9834	0.9091	1	0.9412	0.5003	0.8596
RI	RSC	0.9834	0.9091	1	0.9412	0.5003	0.8596
	RSC-$\delta$	1	0.8936	0.9677	1	0.9095	0.8550
	NJW	0.9502	0.6138	1	0.8365	0.0006	0.6796
NMI	RSC	1	0.5881	0.8904	1	0.7133	0.6143
	RSC-$\delta$	1	0.5867	0.8904	1	0.7317	0.6187
	NJW	1/79	149/590	0/62	1/34	586/1222	284/1137
Error rate	RSC	0/79	170/590	1/62	0/34	64/1222	244/1137
	RSC-$\delta$	0/79	174/590	1/62	0/34	58/1222	238/1137
${\delta }_0$		0.71	2.155	2.435	1.205	0.15	0.625

shows the experimental results of these three cases. Furthermore, the best performance in each dataset is indicated by the bold-type letter. The last row in Table 2 shows the corresponding ${\delta }_0$ in RSC-$\delta$.

As can be seen from the table, RSC-$\delta$ is fully clustered correctly on UKfaculty and karate dataset. Moreover, RSC-$\delta$ achieves the best clustering results on the politicalblog dataset, with only 58 clustering errors.

Table 3. The ${\overline{\varphi }}_k\left(G\right)\frac{k{\mu }_{max}}{{\mu }_{min}}$ of six real datasets.

DataSet	${\mathit{\mu }}_{\mathit{min}}$	${\mathit{\mu }}_{\mathit{max}}$	${\overline{\mathit{\varphi }}}_{\mathit{k}}\left(\mathit{G}\right)$	$\frac{{\mathit{\mu }}_{\mathit{max}}}{{\mathit{\mu }}_{\mathit{min}}}$	${\overline{\mathit{\varphi }}}_{\mathit{k}}\left(\mathit{G}\right)\frac{\mathit{k}{\mathit{\mu }}_{\mathit{max}}}{{\mathit{\mu }}_{\mathit{min}}}$
UKfaculty	189	519	0.1909	2.7460	1.5724
caltech	1443	4821	0.5062	3.3410	13.5302
dolphins	94	224	0.0453	2.3830	0.2159
karate	76	80	0.1283	1.0526	0.2701
politicalblog	16,175	17,253	0.0943	1.0666	0.2012
simmons	8796	15,592	0.2946	1.7726	2.0890

shows the items of the upper bound for $\mu (S_i\Delta A_i)$ proposed in Theorem 5. From the observation, the performance of the RSC-$\delta$ algorithm is effected by the two parameters of $\frac{{\mu }_{max}}{{\mu }_{min}}$ and ${\overline{\varphi }}_k\left(G\right)$. For example, the RSC-$\delta$ does not perform well in caltech and dolphins. All networks except caltech have the minimal average conductance smaller than 0.4 and that of caltech is larger than 0.5. Although dolphins has a small ${\overline{\varphi }}_k\left(G\right)$, $\frac{{\mu }_{max}}{{\mu }_{min}}$ is larger than 2.

4.3. Synthetic Data Experiments

In this section, we will use artificial networks to evaluate the performance of the RSC-$\delta$ algorithm in terms of the average degree, mixing parameter, and the number of nodes in the largest community. We generate artificial networks using the LFR benchmark, which is considered as a standard test network for community detection, characterized by a non-uniform distribution of node degrees and community sizes.

The test artificial networks are generated with the following parameters: the number of nodes (n), the average degree ($\overline{d}$), the maximum degree(maxd), the mixing parameter ($\mu$), the number of nodes in the smallest community (minc), and the number of nodes in the largest community (maxc). The value of the mixing parameter, denoted by $\mu$, is between 0.1 and 0.9. Low amounts of $\mu$ give a clear community structure where the intra-cluster link is much more than the inter-cluster link [17].

4.3.1. The Ratio of the Average Degree to the Maximum Degree

In this experiment, we generate nine artificial networks consisting of 500 nodes. To evaluate the performance of RSC-$\delta$ in terms of the average degree, we fix the parameter $\mu =0.5$, minc = 100, maxc = 300, maxd = 220, respectively, and the average degreevaries from 10 to 170, i.e., 10, 30, 50, 70, 90, 110, 130, 150, and 170, respectively. Then, the ratio of the average degree to the maximum degree varies from 0.0455 to 0.7727. The performance comparison is summarized in Figure 2.

From our observation, we can understand that the performance of RSC-$\delta$ is highly dependent on the average degree of the network. With the average degree increasing, RI and NMI increase, and the error rate decreases significantly. Actually, this phenomenon is verified by the inequality (2), since the equality holds when the graph is regular.

4.3.2. Mixing Parameter

In this experiment, we also generate nine artificial networks with 500 nodes and fix the parameter $\overline{d}=15$, minc = 100, maxc = 300, maxd = 220, respectively. In order to study the effect of the mixing parameter on RSC-$\delta$, $\mu$ varies from 0.1 to 0.9. The experimental results are shown in Figure 3.

From the observation, we understand that RSC-$\delta$ performs excellently when $\mu$ is between 0 and 0.3. However, it drops sharply when $\mu$ is varying from 0.3 to 0.5. This phenomenon coincides with the result for the real datasets, that RSC-$\delta$ does not perform well when ${\varphi }_k\left(G\right)$ is larger than 0.5. However, the performance of RSC-$\delta$ remains stable when $\mu \ge 0.5$. This shows that RSC-$\delta$ is less affected by $\mu \ge 0.5$.

4.3.3. The Number of Nodes in the Largest Community

In this experiment, we generate 13 artificial networks consisting of 1700 nodes. To evaluate the performance of RSC-$\delta$ in terms of the number of nodes in the largest community, we fix the parameter $\mu =0.5$, $\overline{d}$ = 30, minc = 300, maxd = 500, respectively, and the number of nodes in the largest community is varying from 300 to 900, step size is 50. The experimental results are shown in Figure 4.

Since both the degree and the community size distributions, in the graph generated by the LFR benchmark, are power laws, this experiment uses $\frac{minc}{maxc}$ to simulate $\frac{{\mu }_{max}}{{\mu }_{min}}$, and the experiment result shows that the RSC-$\delta$ algorithm performs well when the network is “balanced”, which also verifies the results in the real datasets.

5. Conclusions

Traditional spectral clustering algorithms such as NJW have poor performance in sparse networks with a strong degree of heterogeneity. The RSC algorithm improves the performance of spectral clustering in sparse networks through degree correction. Based on the spectral graph theory, this paper investigates the degree correction method of RSC, and shows that the RSC algorithm works for a wide class of networks. Moreover, we also provide a method to find an appropriate degree-correction $\tau$ to refine the RSC algorithm. Some numerical experiments are conducted to evaluate the performance of our method. By comparing the experimental results on the six real datasets, RSC-$\delta$ performs well on the datasets named karate, politicalblog, and simmons. Finally, the experimental results on the artificial networks show that RSC-$\delta$ performs well when the average degree is much smaller than the maximum degree. Furthermore, the performance of RSC-$\delta$ algorithm is less affected by the mixing parameter $\mu \ge 0.5$. At last, the numerical experiments also show that the algorithm is affected by two parameters of ${\overline{\varphi }}_k\left(G\right)$ and $\frac{{\mu }_{max}}{{\mu }_{min}}$.

6. Discussion

The RSC algorithm uses a constant $\tau$ for the degree-correction. Can we use different degree-corrections for different nodes? We try to use the information of the neighbor nodes of each node as follows.

Let $N\left(i\right)$ be the set of nodes adjacent to node i. Denote $d_{max}^i=max\{d_j:v_j\in N\left(i\right)\}$, $d_{min}^i=min\{d_j:v_j\in N\left(v_i\right)\}$, $d_{mid}^i=\frac{1}{2}(d_{max}^i+d_{min}^i)$ and $d_{mean}^i={\sum }_{j\in N\left(i\right)}{d}_j/d_i$.

Let $\Pi =diag({\pi }_1,\cdots ,{\pi }_n)$ be a diagonal matrix of order n. The modified normalized Laplacian matrix is

$$L_{\Pi }={(D+\Pi )}^{-1/2}W{(D+\Pi )}^{-1/2},$$

We used RSC-max, RSC-min, RSC-mean, and RSC-mid to denote the method when ${\pi }_i$ equals to $d_{max}^i$, $d_{min}^i$, $d_{mean}^i$, $d_{mid}^i$, and $i=1,2,\cdots ,n$, respectively.

Table 4. Different methods of degree correction.

DataSet		UKfaculty	Caltech	Dolphins	Karate	Politicalblog	Simmons
	RSC	1	0.8967	0.9677	1	0.9007	0.8521
	RSC-min	0.9646	0.9008	1	1	0.9065	0.8590
RI	RSC-max	0.9834	0.9018	1	1	0.5104	0.8525
	RSC-mean	0.9646	0.8976	1	1	0.5002	0.8504
	RSC-mid	0.9834	0.9005	1	1	0.5002	0.8539
	RSC	1	0.5881	0.8904	1	0.7133	0.6143
	RSC-min	0.8985	0.5953	1	1	0.7243	0.6228
NMI	RSC-max	0.9502	0.6016	1	1	0.0227	0.6172
	RSC-mean	0.8985	0.5933	1	1	0.0019	0.6073
	RSC-mid	0.9502	0.6006	1	1	0.0019	0.6189
	RSC	0/79	170/590	1/62	0/34	64/1222	244/1137
	RSC-min	2/79	162/590	0/62	0/34	60/1222	222/1137
Error rate	RSC-max	1/79	163/590	0/62	0/34	521/1222	242/1137
	RSC-mean	2/79	170/590	0/62	0/34	586/1222	240/1137
	RSC-mid	1/79	164/590	0/62	0/34	586/1222	237/1137

shows the experimental results of these methods. We can see that the RSC-min algorithm is a bit better than RSC. The RSC-min algorithm performs better than RSC in five datasets, and only misclassifies two nodes on UKfaculty. Therefore, using a different degree-correction for each node might improve the performance of the RSC algorithm. We will leave this to our future work.