Digraph Spectral Clustering with Applications in Distributed Sensor Validation

Abstract

In various sensor networks, the performances of sensors vary significantly over time, due to the changes of surrounding environment, device hardware, and so forth. Hence, monitoring the status is essential in sensor network maintenance. Spectral clustering has been employed as an enabling technique to solve this problem. However, the traditional spectral clustering is developed for undirected graph, and the naive generalization for directed graph by symmetrization of the adjacency matrix will lead to loss of network information, and thus cannot efficiently detect bad sensor nodes while applying it for sensor validation. In this paper, we develop a generalized digraph spectral clustering method. Instead of simply symmetrizing the adjacency matrix, our method takes into consideration the network circulation while clustering the sensors. The extensive simulation results demonstrate that our method outperforms the traditional spectral clustering method by increasing the bad detection ratio from 19% to 41%.

1. Introduction

Sensor networks as an enabling technique have been deployed in many scenarios that human beings find it hard to reach, for example, in the wild area, ocean, battle fields, and so forth. These sensor networks serve an important purpose to collect information to help people understand and monitor the unreachable regions. Due to various unpredictable reasons, for example, mechanical problems, malfunctioning, damage, turning to a function-reducing mode due to low battery power, and being compromised, the sensor performances may degrade over time. Thus a periodical validation of sensor status is needed. However, in many cases, it is not possible to reach the sensor network to find the problematic senor nodes. Hence, a self-validation method becomes more practical in reality, where sensor nodes validate their goodness by monitoring the signals received from their neighbors.

In the literature, the spectral clustering method is introduced as a key technique to identify those “bad sensor nodes” [1, 2]. However, because the traditional spectral clustering algorithm only works on symmetric matrices, [1] symmetrizes the asymmetric connectivity matrix among the sensor nodes, and applies the traditional spectral clustering algorithm, this symmetrization leads to a loss of significant information directed connections between sensor nodes, which makes the bad node detection highly inaccurate.

An n by n square adjacency matrix A represents a finite graph $G=(V,E,A)$ with $n=\left|V\right|$ vertices, where V is the vertex set and E denotes the collection of all directional edges. Each entry of adjacency matrix $a_{ij}$ represents the weight (or conductance) from vertex i to vertex j.

For undirected graph, associated with symmetric adjacency matrix A, the random walk theory has been extensively studied in the literature, such as the reversible Markov chain theory. Chung and Yau [3] define a normalized Laplacian matrix with the out-degree matrix of the undirected graph and provide several ways to derive the discrete Green's function. The effective resistance defined in [4–6] is exactly the commute time of random walk on directed graph and can be computed by the pseudoinverse of the graph Laplacian.

In contrast, for directed graph, where many key properties listed above cannot hold any more, due to the asymmetry of the adjacency matrix A in directed graphs, the in-degree and out-degree distribution are no longer equal to the stationary distribution.

In this paper, we focus on the strongly connected graph, which is corresponding to the irreducible Markov Chain, and develop a digraph spectral clustering algorithm to solve the sensor node validation problem. The main contributions of this paper are summarized below.

• (i)

To our knowledge, this is the first work to investigate the sensor node validation as digraph spectral clustering problem. We develop theoretical results that introduce a digraph spectral clustering algorithm without losing the information of directed links among sensors.

(ii)

By evaluating our algorithm and the traditional undirected graph based spectral clustering algorithm on randomly generated large-scale synthetic data, we show a significant promotion in terms of the sensor node detection accuracy.

This paper is organized as follows. Section 2 formally defines the sensor node validation problem. In Section 3, we introduce the generalized digraph spectral clustering algorithm. In Section 4, we provide extensive evaluation results that demonstrate the efficiency and effectiveness of our proposed digraph spectral clustering algorithm. We briefly introduce the related works below in Section 5. We conclude our paper and outline the future works in Section 6.

2. Problem Definition

Given a sensor network with n static sensor nodes, denoted as $V=\{s_{\mathrm{1}},\dots ,s_n\}$ , which is strongly connected, every sensor $s_i$ can reach $s_j$ in a number of hops. They periodically ping their one hop neighbors, where the received signal strength (RSS) values reported by a sensor to one of its neighbors correlate with the matching degree of their antenna polarizations. Thus, using the RSS as the goodness of a connection between two sensor nodes, denoted as $a_{ij}$ , the weighted adjacency matrix $A=[a_{ij}]$ captures the connectivity of sensor nodes in the sensor network. We denote $G=(V,E,A)$ as the directed graph established by the sensor network, with V as the set of all sensor nodes, E as the set of all directed edges between sensor nodes, and A as the weighted adjacency matrix.

Assume that properly working sensors of similar properties, such as radio and antenna characteristics, node environments, and power usage, will report similar measurements of RSS. Thus, those working sensors are called “good sensors” and other sensors that do not report proper measurements “bad sensors.” We illustrate these terminologies using a simple example, where sensors are indexed by their antenna orientations. In this case, nearby sensors are those which have similar antenna polarizations. Suppose that RSS values reported by a sensor to one of its neighbors correlate with the matching degree of their antenna polarizations. Then, nearby sensors, which are in good working condition, are expected to report similar RSS measurements on the same neighbor.

The sensor node validation problem in fact aims to find those “bad sensors” by detecting anomaly connection patterns received from “bad sensors.” To be precise, to identify bad sensors, we need to solve the problem of determining whether a sensor belongs to a cluster of nearby sensors. We assume that there are plentiful sensors so that clusters of nearby sensors will be large. A sensor is considered as a bad one if the sensor is in a small unique cluster or the sensor is in a small out-of-place component of a large cluster. As illustrated in [1], this can be achieved by applying spectral clustering algorithm. However, different from [1], in reality, the adjacency matrix A, in general, is asymmetric; namely, $a_{ij}$ is not necessarily equal to $a_{ji}$ . Thus the traditional spectral clustering algorithm developed for undirected graph cannot be directly applied to solve our sensor node validation problem. In this work, we provide theoretical results to generalize the spectral clustering algorithm to digraph case and apply our clustering algorithm to do sensor node validation. In the next section, we will introduce our digraph clustering algorithm.

3. Digraph Spectral Clustering Algorithm

In this section, we develop digraph spectral clustering algorithm for strongly connected digraphs by introducing the generalized objective function as $\tilde{\mathcal{L}}$ . We will first present the generalized objective function followed by the design of the digraph spectral clustering algorithm.

3.1. Generalized Objective Function

While using $\tilde{\mathcal{L}}$ as the objective function, we have

$$\begin{array}{cc}& f^T\tilde{\mathcal{L}}f={\displaystyle \sum }_{i,j=\mathrm{1}}^n‍F_{\Pi }\left(i,j\right)g\left(i\right)\left(g\left(i\right)-g\left(j\right)\right),\end{array}$$

(1)

where $g(i)=f(i){\pi }_i^{-\mathrm{1}/\mathrm{2}}$ and $F_{\Pi }(i,j)={\pi }_i{p}_{ij}$ is the circulation of edge $(i,j)\in E$ .

Detailed descriptions for the extension are presented in the following section.

3.2. Design of Digraph Spectral Clustering Algorithm

In this section, we will generalize the spectral clustering algorithm using the generalized random walk theory on digraphs.

Spectral clustering is one of the most popular modern clustering algorithms, with wide applications in distributed computing systems. For example, in [7, 8], spectral clustering is used to estimate the wireless transmission cost in wireless networks.

So far, most published spectral algorithms operate on symmetric matrices. However, there are important cases when data points have pairwise relationships that are not symmetric. The link delivery probabilities in wireless network, economic transactions, and internet communications are often asymmetric. The commonly used approach for spectral clustering link data is to obtain a symmetric matrix $\tilde{A}$ from the original adjacency A and then to apply spectral clustering techniques to $\tilde{A}$ . Typical transformations used in the literature include $\tilde{A}=A+A^T$ and $\tilde{A}=A^{T}A$ . Zhou et al. [9] design a symmetric combinational Laplacian matrix by symmetrizing the original unnormalized Laplacian of the digraph. There are two serious problems with these methods. First, in digraph, given a partition $V=\{S,\stackrel{-}{S}\}$ , the commonly used edge cuts, that is, $\text{cut}(\partial A)=\text{cut}(A,\stackrel{-}{A})={\sum }_{i\in A,j\in \stackrel{-}{A}}‍a_{ij}$ , are not symmetric; that is, $\text{cut}(\partial A)\ne \text{cut}(\partial \stackrel{-}{A})$ . These approaches cannot distinguish the directional variations in digraph cases. Secondly, they all apply the symmetrization to either adjacency matrix or Laplacian matrix in digraph, and thus the results obtained in fact represent the characteristics of the transferred undirected graphs instead of the original directed graphs.

Now, we are in the position to introduce how our generalized normalized Laplacian matrix can be used to address the above two problems in digraph based spectral clustering algorithms.

Given a strongly connected directed graph $G=(V,E,A)$ , $P=D^{-\mathrm{1}}A=[p_{ij}]$ is the transition probability matrix of the corresponding irreducible Markov Chain. The circulation F is defined as a function which maps each directed edge $(i,j)\in E$ to a nonnegative real value $F:E(G)\to {\mathbb{R}}^{+}\vee \{\mathrm{0}\}$ , and, for each vertex k,

$$\begin{array}{cc}& {\displaystyle \sum }_i‍F(i,k)={\displaystyle \sum }_j‍F(k,j).\end{array}$$

(2)

In [10], Chung proves that $F_{\Pi }(i,j)={\pi }_i{p}_{ij}$ is in fact the circulation function of the digraph G.

The circulation essentially interprets that, for each random walk state, the in-flow traffic is equal to the out-flow traffic, even though the digraph edge weights are not symmetric. Therefore, given a graph partition $V=\{S,\stackrel{-}{S}\}$ , one can easily check that the circulations between S and $\stackrel{-}{S}$ , defined as $F_{\Pi }(\partial S)={\sum }_{i\in S,j\in \stackrel{-}{S}}‍{\pi }_i{p}_{ij}$ , are symmetric; that is, $F_{\Pi }(\stackrel{-}{S})\ne F_{\Pi }(\partial \stackrel{-}{S})$ . This nice property of the circulation motivates us to redefine the graph cut for directed graph as below.

Definition 1 (CCut of digraph partition).

For a two-components digraph partition $V=\{S,\stackrel{-}{S}\}$ ,

$$\begin{array}{cc}& \text{CCut}(S,\stackrel{-}{S})=\frac{F_{\Pi }(\partial S)}{F_{\Pi }\left(S\right)},\end{array}$$

(3)

where $F_{\Pi }(\partial S)={\sum }_{i\in S,j\in \stackrel{-}{S}}‍{\pi }_i{p}_{ij}$ and $F_{\Pi }(S)={\sum }_{i,j\in S}‍{\pi }_i{p}_{ij}$ .

For a digraph partition with k disjoint components $V=\{S_{\mathrm{1}},\dots ,S_k\}$ ,

$$\begin{array}{cc}& \text{CCut}(S_{\mathrm{1}},\dots ,S_k)={\displaystyle \sum }_{m=\mathrm{1}}^k‍\text{CCut}(S_m,{\stackrel{-}{S}}_m).\end{array}$$

(4)

Note that one has the following.

The ${\min }_{S\subseteq V}\text{CCut}$ is in fact the Cheeger constant $h(G)$ [10] of digraph, when $k=\mathrm{2}$ .

In digraphs, the generalized normalized Laplacian matrix $\tilde{\mathcal{L}}={\Pi }^{\mathrm{1}/\mathrm{2}}(I-P){\Pi }^{-\mathrm{1}/\mathrm{2}}$ has close relationship with the circulation $F_{\Pi }$ as below.

Theorem 2.

For any column vector $f\in {\mathbb{R}}^n$ , we have

$$\begin{array}{cc}& f^T\tilde{\mathcal{L}}f={\displaystyle \sum }_{i,j=\mathrm{1}}^n‍F_{\Pi }\left(i,j\right)g\left(i\right)\left(g\left(i\right)-g\left(j\right)\right),\end{array}$$

(5)

where $g(i)=f(i){\pi }_i^{-\mathrm{1}/\mathrm{2}}$ and $F_{\Pi }(i,j)={\pi }_i{p}_{ij}$ is the circulation of edge $(i,j)\in E$ .

Proof.

Consider

$$\begin{array}{l}{f}^T\tilde{\mathcal{L}}f=f^T{\Pi }^{\mathrm{1}/\mathrm{2}}\left(I-P\right){\Pi }^{-\mathrm{1}/\mathrm{2}}f\\ \hspace{1em}\hspace{1em}\hspace{0.17em}={\displaystyle \sum }_{i=\mathrm{1}}^n‍f{\left(i\right)}^{\mathrm{2}}-{\displaystyle \sum }_{i,j=\mathrm{1}}^n‍f\left(i\right)f\left(j\right){\pi }_i^{\mathrm{1}/\mathrm{2}}{\pi }_j^{-\mathrm{1}/\mathrm{2}}{p}_{ij}\\ \hspace{1em}\hspace{1em}\hspace{0.17em}={\displaystyle \sum }_{i=\mathrm{1}}^n‍{\pi }_i{\left(\frac{f\left(i\right)}{\sqrt{{\pi }_i}}\right)}^{\mathrm{2}}-{\displaystyle \sum }_{i,j=\mathrm{1}}^n‍\frac{f\left(i\right)}{\sqrt{{\pi }_i}}\frac{f\left(j\right)}{\sqrt{{\pi }_j}}{\pi }_i{p}_{ij}\\ \hspace{1em}\hspace{1em}\hspace{0.17em}={\displaystyle \sum }_{i,j=\mathrm{1}}^n‍{\pi }_i{p}_{ij}\frac{f\left(i\right)}{\sqrt{{\pi }_i}}\left(\frac{f\left(i\right)}{\sqrt{{\pi }_i}}-\frac{f\left(j\right)}{\sqrt{{\pi }_j}}\right)\\ \hspace{1em}\hspace{1em}\hspace{0.17em}={\displaystyle \sum }_{i,j=\mathrm{1}}^n‍F_{\Pi }\left(i,j\right)g\left(i\right)\left(g\left(i\right)-g\left(j\right)\right).\end{array}$$

(6)

Given a partition of $V=\{S_{\mathrm{1}},\dots ,S_k\}$ , we can define k indicator vectors $r_i=(r_{\mathrm{1},i},\dots ,r_{n,i}{)}^T$ ( $\mathrm{1}\le i\le k$ ), by

$$\begin{array}{cc}& r_{i,j}=\{\begin{array}{cc}\sqrt{\frac{{\pi }_i}{F_{\Pi }\left(S_j\right)}}\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}i\in S_j\hfill \\ \mathrm{0}\hfill & \text{otherwise}.\hfill \end{array}\end{array}$$

(7)

Then, we set the matrix $R\in {\mathbb{R}}^{n\times k}$ as the matrix containing those k indicator vectors as columns. Then, the following equations hold:

$$\begin{array}{cc}& r_i^T\tilde{\mathcal{L}}{r}_i=\text{CCut}(S_i,{\stackrel{-}{S}}_i),\\ r_i^T\tilde{\mathcal{L}}{r}_i={\left(R^T\tilde{\mathcal{L}}R\right)}_{ii}.\end{array}$$

(8)

Hence, we have

$$\begin{array}{cc}& \text{CCut}\left(S_{\mathrm{1}},\dots ,S_k\right)={\displaystyle \sum }_{i=\mathrm{1}}^k‍r_i^T\tilde{\mathcal{L}}{r}_i=\mathrm{Tr}\left(R^T\tilde{\mathcal{L}}R\right).\end{array}$$

(9)

Using the similar optimization formulation as [11], we can write the problem of minimizing $\text{CCut}(S_{\mathrm{1}},\dots ,S_k)$ as

$$\begin{array}{cc}& \underset{S_{\mathrm{1}},\dots ,S_k}{\min }\mathrm{Tr}\left(R^T\tilde{\mathcal{L}}R\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\mathrm{\hspace{0.17em}\hspace{0.17em}}{\left(\Pi R\right)}^T\left(\Pi R\right)=I,R\hspace{1em}\text{as}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{in}\left(\mathrm{7}\right).\end{array}$$

(10)

We relax the problem by allowing the entries of matrix of matrix R to take arbitrary real values. Then, the relaxed problem becomes

$$\begin{array}{cc}& \underset{R\in {\mathbb{R}}^{n\times k}}{\min }\mathrm{Tr}\left(R^T\tilde{\mathcal{L}}R\right)\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{subject}\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{to}\mathrm{\hspace{0.17em}\hspace{0.17em}}{\left(\Pi R\right)}^T\left(\Pi R\right)=I.\end{array}$$

(11)

This is the standard form of a trace minimization problem, and Rayleigh-Ritz theorem [12] tells us that the solution is given by choosing R as the matrix which contains the first k eigenvectors corresponding to the k smallest eigenvalues of $\tilde{\mathcal{L}}$ as columns. Now, we need to reconvert the real valued solution matrix to a discrete partition. We use standard k-means algorithms [13] on the rows of R and get the clusters $S_{\mathrm{1}},\dots ,S_k$ .

Therefore, we obtain Algorithm 1.

Algorithm 1: Spectral clustering algorithm for digraphs.

(1) Construct the one hop probability matrix P for Graph G;

(2) Compute the generalized normalized laplacian $\tilde{\mathcal{L}}={\mathrm{\Pi }}^{\mathrm{1}/\mathrm{2}}(I-P){\mathrm{\Pi }}^{-\mathrm{1}/\mathrm{2}}$ ;

(3) Compute the first k eigenvectors $u_{\mathrm{1}},\dots ,u_k$ of $\tilde{\mathcal{L}}$ .

(4) Let indicator matrix R be the matrix containing the vectors $u_{\mathrm{1}},\dots ,u_k$ as columns.

(5) Use the k-means algorithm on the rows of the R, and cluster V into $S_{\mathrm{1}},\dots ,S_k$ .

How to choose k is a general problem for all clustering algorithms. The goal is to choose the number k, such that all eigenvalues of $\tilde{\mathcal{L}}$ , $\{{\lambda }_{\mathrm{1}},\dots ,{\lambda }_k\}$ are very small, but ${\lambda }_{k+\mathrm{1}}$ is relatively large. One heuristic proposed is using eigengap of $\tilde{\mathcal{L}}$ to compute the k. We will address this problem as part of our future work.

4. Evaluation

In this section, we conduct extensive evaluations on the performance of our proposed sensor validation algorithm.

4.1. Evaluation Settings

We consider a sensor network with $n=\mathrm{1000}$ sensor nodes and randomly generate the topologies among them, so the network is strongly connected. After getting a topology, we randomly generate RSS values among sensor pairs, such that nearby sensors maintain similar antenna polarizations. Then, we randomly choose a set of $b<\mathrm{1000}$ sensors to be the bad nodes and change their RSS values to their neighbors significantly. Then, by applying our digraph spectral clustering algorithm and the traditional undirected graph based spectral clustering algorithm on the symmetrized matrix $A^{T}A$ , we compare the detection accuracy between them. Given b as the number of “bad nodes,” we consider the number of detected correct “bad nodes” as $b^{\prime }$ and use $r=b^{\prime }/b$ to evaluate the detection accuracy.

In the evaluation we vary the size of bad node set b from $\mathrm{50}$ to $\mathrm{500}$ , and the degree of RSS changes from 10% to 50%, where the degree of RSS changes indicates the percentage of the change on the original RSS values. Note that, for each confuration setting, we run the simulation 100 times with randomly generated topologies and a set of randomly chosen bad nodes, to reduce the randomness introduced to the results. Below, we will present our evaluation results.

4.2. Evaluation Results

Figure 1 shows the results on how the number of bad nodes impacts the detection accuracy when using our digraph clustering algorithm and tradition spectral clustering algorithm. We observe that, as the number of “bad” nodes increases, the detection accuracy decreases almost linearly for both our digraph spectral clustering algorithm and the traditional spectral clustering algorithm. This happens because, as the more “bad nodes” exist, the harder it is for the clustering algorithms to detect them, where the malfunctioning nodes may coexist and dominate a neighborhood of sensor nodes and make the detection become harder. Overall, our method consistently outperforms the traditional method with 19% to 41% more detection accuracy.

Figure 1

The impact of number of “bad” nodes.

Figure 2 shows the results of how the change ratio on RSS affects the detection accuracy when using our digraph clustering algorithm and tradition spectral clustering algorithm. We observe that, as the change rate on RSS increases from 0.1 to 0.5, the detection accuracy of both our digraph spectral clustering method and the traditional spectral clustering method increases, which is because larger changes on RSS leads to higher dissimilarity between “bad nodes” and “good” nodes. Moreover, our method achieves 22% to 34% more detection accuracy over the traditional method.

Figure 2

The impact of change rate on RSS.

5. Related Work

In this paper, we develop generalized digraph spectral clustering algorithm for sensor status validation in distributed sensor networks. The related work for sensor node status validation has been discussed in the previous section, where in the section we primarily introduce the state-of-the-art spectral clustering methods. Spectral clustering is mainly employed in data mining and machining learning areas [14–19], where a few studies have attempted to extend the spectral clustering algorithms to digraph setting, for example, [7–9, 19–25]. However, while being applied to solve sensor status validation problem, these works have two fundamental drawbacks: (1) loss of information by symmetrizing the adjacency matrix or Laplacian matrix and (2) asymmetric cuts in digraphs.

The Loss of Information by Symmetrization of A or L. The algorithms proposed in [19, 20, 24] symmetrize the adjacency matrix or Laplacian matrix, so the traditional spectral clustering algorithm (for undirected graph) $[]$ can be used. However, by using the symmetrization to either adjacency matrix or Laplacian matrix in digraphs, they in fact apply existing undirected graph based spectral clustering algorithms in transferred undirected graphs, with $\tilde{A}=A^T+A$ , $\tilde{A}=A^{T}A$ , and so forth, instead of the original directed graphs. Therefore, the results will lose some information from the original digraph, and the clustering obtained will not be accurate. Many papers have explicitly addressed this problem, such as [23, 24].

In particular, in [9] by Zhou et al., they define the same cut function as $\text{CCut}(S,\stackrel{-}{S})={\sum }_{i\in S,j\in \stackrel{-}{S}}‍{\pi }_i{p}_{ij}$ and get good performances. However, the proposed algorithm still has problems. First, they use the symmetrized Laplacian as objective function, which will result in losing information from original digraph. Secondly, they proposed the symmetrized Laplacian and cut definition as heuristics and did not explicitly give the circulation interpretation of the algorithm.

Asymmetric Cuts in Digraphs. The directionality of directed links is crucial information, where [23–25] define the cluster cut in an asymmetric fashion. In digraph, given a partition $V=\{S,\stackrel{-}{S}\}$ , the edge cuts defined in many papers (for instance, $\text{cut}(\partial A)=\text{cut}(A,\stackrel{-}{A})={\sum }_{i\in A,j\in \stackrel{-}{A}}‍a_{ij}$ , etc.) are not symmetric; that is, $\text{cut}(\partial A)\ne \text{cut}(\partial \stackrel{-}{A})$ . These approaches cannot distinguish the directional difference in digraph cases.

6. Conclusion

In this paper we propose a generalized digraph spectral clustering algorithm for validating sensor status in distributed sensor networks. The proposed DSC algorithm considers the network flow circulation while performing the sensor node clustering; thus it preserves the directed link information, which is lost in the traditional spectral clustering method. In our extensive simulations, digraph spectral clustering algorithm demonstrates 19% to 41% mode detection accuracy over the traditional spectral clustering based method.

There exist several future directions. Firstly, we are planning to explore the applicability of digraph spectral clustering algorithm in other scenarios, for example, social network community detection, and so forth. Secondly, when the sensor network size scales up, a real-time statistical query for the number of “bad” nodes becomes time consuming. In this case, we consider applying sampling techniques [26–34] to perform fast and accurate estimation for it. Last but not least, we are interested in applying our digraph spectral graph method to detect node and link failures in large-scale cloud computing environments [35–38].