Weighted Combinatorial Laplacian and its Application to Coverage Repair in Sensor Networks

Graphs have been used extensively to model networks of robot or sensor networks [10, 3]. One of the fundamental algebraic tools relevant to graphs is the graph Laplacian matrix, the spectrum of which encodes the connectivity of the graph [8]. In weighted graphs, one assigns non-negative, real-valued weights or importance to each edge of the graph, with a zero weight on an edge being equivalent to the edge being non-existent, thus allowing a continuum between different graph topologies. Furthermore, for robot or mobile sensor networks, the real-valued weights naturally correspond to the separation or distance between pairs of agents (with the weights being inversely related to the distances so that agents that are closer to each other are strongly connected, while agents that are farther from each other are weakly connected). A weighted graph Laplacian can be constructed accordingly, and real-valued optimization objectives can be formulated to control the connectivity of a network [13, 12].

On the other hand, simplicial complexes, which are a natural higher-dimensional extension of graphs, have also been used to model networks of robots and mobile sensors [4]. A simplicial complex is accompanied by a corresponding algebraic construction called combinatorial Laplacian matrix, the spectrum of which is related to the holes in the network. However, the definition of combinatorial Laplacian cannot naturally incorporate weights on the simplices and hence there does not exist any natural continuum between different simplicial complex topologies. While the eigenvectors of the combinatorial Laplacian have been used to identify holes in coverage of mobile sensor networks [4], the control of the mobile sensors for mending such holes involved finding the tightest cycle around the holes and then navigating the mobile sensors towards the holes.

The main technical contribution of this paper is a new theory of a weighted combinatorial Laplacian of a simplicial complex that can encode real-valued weights on the simplices, providing a continuum between different simplicial complex topologies. This allows us to design gradient descent algorithms for directly controlling the mobile sensors to optimize objective functions based on the spectrum of the weigted combinatorial Laplacian for mending holes in the complex.

Weighted Graph Laplacian: The important special case for the theory we provide in this paper, known as the weighted graph Laplacian operator, has been well-studied and has found wide range of applications in computational geometry and network theory [12]. The graph Laplacian operator can be constructed as a linear operator between the vector spaces over a field (typically $\mathbb{R}$ or $\mathbb{C}$) with basis the vertices of the graph. It was Fiedler [6] who first noticed that the smallest non-zero eigenvalue of the graph Laplacian has some implication about the connectivity of the graph. Figure 1 shows the coloring of the vertices of a graph based on the eigenvector corresponding to the smallest nonzero eigenvalue of the weighted graph Laplacian operator, often called the Fiedler vector. Edges of the graph are weighted, that is, each edge is assigned a real value, and in this particular example, weights are set to be the inverse of the length of the edge, giving the notion of “the shorter the edge, the stronger the connection.” Then it turns out that the resulting weighted Laplacian operator, and in particular the Fiedler vector, show how much the graph is “almost disconnected,” in the sense that the difference of colors between a pair of vertices measures the connection between the two vertices through the graph. Hence, by utilizing this “almost disconnectedness,” we can capture the clusters in the graph, the partition of vertices with similar colors.

Another advantage of our weighted Laplacian operators is the fact that the eigenvalues are the real-valued piece-wise smooth functions of weights, whose gradient computation is not too expensive even for a large simplicial complex, as we shall see. Hence, given that we have some control over the dynamics of the simplicial complex, say, positions of the vertices, our Laplacian operators will give us a good control over the holes of the simplicial complex. In this way, we will apply our weighted Laplacian operators to develop the efficient coverage repair algorithm for sensor networks.

The norm of a vector and a linear transformation (or a matrix) will be denoted by $\|\cdot\|$. Unless otherwise noted, the norm is the two norm. The inner product of the two vectors will be denoted by $\langle\cdot,\cdot\rangle$.

Given a linear operator, $\mathcal{O}:\mathscr{A}\rightarrow\mathscr{B}$, its adjoint with respect to an inner product is denoted by $\mathcal{O}^{\ast}$. For a given basis for the vector spaces, if $O$ represents the matrix representation of the linear operator, then with the standard Euclidean metric with respect to the basis, the matrix representation of the adjoint of the operator is the transpose, $O^{T}$.

In the literature of the graph Laplacian operators and the combinatorial Laplacian operators, it is more common to define them over cochain complexes than chain complexes. However, we will present our combinatorial Laplacian in terms of chain complexes with real coefficients, so that we explain the properties of Laplacian in terms of the holes of the simplicial complex. Note that, because we will keep our simplicial complex to be finite, homology with real coefficients and cohomology with real coefficients are essentially the same, as there will always be an isomorphism between the two when defined on the same simplicial complex.

More compactly, defining the weight operator, $\mathcal{W}:\mathrm{span}(E)\rightarrow\mathrm{span}(E)$, such that $\mathcal{W}(\{x,y\})=w(\{x,y\})\,\{x,y\}$, we have $\tilde{{\mathcal{B}}}={\mathcal{B}}\,\mathcal{W}$. If $W$ is the corresponding matrix representation of the weight operator (which is a diagonal matrix in the basis of the simplices), we have $\tilde{B}=BW$.

A natural extension of this definition to weighted graphs gives rise to the weighted graph Laplacian which is defined as $\tilde{\mathcal{L}}=\tilde{{\mathcal{B}}}\tilde{{\mathcal{B}}}^{\ast}$, with the corresponding matrix representation $\tilde{L}=\tilde{B}\tilde{B}^{T}=BW^{2}B^{T}$. Real-valued weights on edges enable a continuum between graphs in which an edge is existing (with positive weight) and a graph in which the same edge is removed (the edge with zero weight) – see Figure 4(a). This continuum allows construction of gradient-based algorithms based on the spectrum of the weighted graph Laplacian in order to control the connectivity of the graph. Weighted graph Laplacian has hence been extensively used to control the connectivity of sensor networks [13] and for transmission control in information networks [12].

A simplicial complex can be thought of as a higher-dimensional generalization of graphs, in which we not only can have the vertices (also called $0$-simplices) and edges (also called $1$-simplices, described by $2$-element subsets of $V$), but also $2$-simplices (can be thought of as “triangle elements”, described by $3$-element subsets of $V$) and higher-dimensional simplices. Algebraic constructions using a similicial complex involves higher-dimensional extensions of the boundary map and Laplacian matrix, and allows us to reason about “holes” in the complex, just as the graph Laplacian allowed reasoning about connected components of the graph.

The following technical discussions formalize the definition of simplicial complex, the boundary map, and introduces the concept of homology.

In the definition above, $V$ is the vertex set, $X_{0}$ contains all the singletons of $V$ (the $0$-simplices), $X_{1}$ contains $2$-element subsets of $V$ (the $1$-simplices or edges), $X_{2}$ contains $3$-element subsets of $V$ (the $2$-simplices), and so on. Given any $n$-simplex, $c\in X_{n}$, the condition of closure under inclusion implies that the faces of $c$ are also in the simplicial complex. An explicit example is given below.

Without loss of generality we will assume that the union of 0-simplices is equal to $V$, and thus we refer to call $V$ as a vertex set.

The key algebraic description of a simplicial complex is encapsulated in the definition of the higher-order (combinatorial) boundary maps. In this generalization of the boundary map, the vector space spanned by the $0$-simplices is denoted by $C_{0}$, vector space spanned by the $1$-simplices (edges) is denoted by $C_{1}$, vector space spanned by the $2$-simplices is denoted by $C_{2}$, and in general, vector space spanned by the $n$-simplices is denoted by $C_{n}$. Upon assigning an arbitrary orientation to each simplex, the boundary maps are denoted by ${\mathcal{B}}_{n}:C_{n}\rightarrow C_{n-1}$, whose matrix representations (in the basis of the simplices) are $B_{n}$ (see Figure 5 for an explicit example of $B_{1}$ and $B_{2}$). The technical discussions below gives the formal definitions and highlights the key property of the boundary maps, which paves the way to eason about holes in the simplicial complex.

We associate with a simplicial complex a natural algebraic structure that encodes the boundary information, called Chain Complex.

There is a natural way of assigning an algebraic structure of this kind to simplicial complexes, which is stated in the next proposition. We omit the proof, but interested readers can find the proof in a standard textbook of algebraic topology (See, for example, [9].)

Having defined the algebraic structure on the simplicial complex based on the boundary information, the holes can now be measured by how much the boundary information between adjacent dimensions fails to match up: Let $G$ be the graph defined on the vertex set $V=\{v_{0},\cdots,v_{3}\}$ as shown in the figure 6(a). Then we intuitively see that $G$ has three 1-dimensional holes, that is, the holes made up by 1-simplices. If we take the formal sum of edges creating a hole preserving the orientation, we can write down these three holes as 1-chains:

The important properties of these chains are that they will vanish when we take a boundary map; for example,

This property thus motivates us to define the set of 1-dimensional holes of $G$ to be the nullspace of ${\mathcal{B}}_{1}$, denoted $\text{Ker }{\mathcal{B}}$. This may seem sufficient for the definition of the holes on a graph, but it is in fact not sufficient for the higher dimensional simplicial complex. Let $H$ be the simplicial complex shown in the figure 6(b), which is just $G$ but with a 2-simplex attached on it. Now one of the three hole that were present in $G$, namely $c1$, is no longer a hole since it is now covered by a 2-simplex. To realize this we compute the image of the 2-simplex $f$ under ${\mathcal{B}}$

and notice that this equals to $c_{1}$. Hence, in order to take the higher dimensional simplices covering up the holes into account, we "forget" all of the images of ${\mathcal{B}}_{2}$ from $\text{Ker }{\mathcal{B}}_{1}$, and this is exactly the the definition of the first homology, and we can more generally define:

The intuition remains the same for the higher dimensional homology. The vectors in $\text{Ker }{\mathcal{B}}_{n}$ represent the holes made up by $n$-simplices, and the vectors in $\text{Im }{\mathcal{B}}_{n+1}$ are those holes that are filled up by the $(n+1)$-simplices, which we "forget" by taking quotient. The resulting vector space $H_{n}\,C$ thus contains the actual $n$-dimensional holes in $C$.

We now turn to an overview of what is called combinatorial Laplacian. Let ${\mathcal{B}}_{n}^{\ast}:C_{n-1}\to C_{n}$ be the adjoint of ${\mathcal{B}}$ with respect to an inner product $\langle\cdot,\cdot\rangle$ (i.e., a linear map that satisfies $\langle u,{\mathcal{B}}_{n}v\rangle=\langle{\mathcal{B}}^{\ast}_{n}u,v\rangle$ for each $u\in C_{n-1}$ and $v\in C_{n}$). Then the $n$-th combinatorial Laplacian $\mathcal{L}_{n}:C_{n}\to C_{n}$ is defined by

It is often convenient to define

Note that we have $\mathcal{L}_{n}=\mathcal{L}_{n}^{\textit{down}}+\mathcal{L}_{n}^{\textit{up}}$ by definition. The

Using the simplices as basis and the standard Euclidean norm on the vector spaces, the matrix representation of the combinatorial Laplacian is given by

The graph Laplacian matrix described earlier is then $L_{0}$ (assuming ${\mathcal{B}}_{0}=0$).

It is clear that $\mathcal{L}_{n}$ is positive semi-definite, and in particular all of their eigenvalues are real and non-negative. Moreover, the self-adjointness used in the construction, as well as the fact that ${\mathcal{B}}_{n}$ is a boundary map, carries out several important properties of the Combinatorial Laplacian.

The dimension of the kernel of the combinatorial Laplacian $\mathcal{L}_{n}$ thus counts the number of holes in the complex $C$.

Note that, when written out as a matrix, $\mathcal{W}_{n}$ is the diagonal matrix with the values of $w_{n}$ on its diagonal.

It is straightforward to verify that the maps $\tilde{\mathcal{B}}_{n}$ are in fact boundary maps. Hence we can systematically define the homology vector spaces for weighted chain complexes as well, which we will denote by $H_{n}\,\tilde{X}$. From the definition, it is clear that the diagram

commutes, that is, ${\mathcal{B}}_{n}\mathcal{W}_{n}=\mathcal{W}_{n-1}\tilde{\mathcal{B}}_{n}$ for each $n\geq 0$. Since $w_{n}$ is positive, each $\mathcal{W}_{n}$ is an isomorphism, thus we obtain

Furthermore, recall that the results in the previous section about the combinatorial Laplacian did not depend on anything beyond the self-adjointness and the fact that ${\mathcal{B}}_{n}$ is a boundary map. Hence, Theorem 2.3 applies to our weighted homology and weighted Laplacian as well, which in turn implies

where $\tilde{\mathcal{L}_{n}}$ is the weighted combinatorial Laplacian defined over $\tilde{X}=(X,w_{n})$ and $\mathcal{L}_{n}$ is the combinatorial Laplacian defined over $X$.

As with the case of combinatorial Laplacian, we can write our weighted combinatorial Laplacian explicitly; if $v=\alpha_{1}c_{1}+\cdots+\alpha_{|X_{n}|}c_{|X_{n}|}\in\tilde{C}_{n}\,X$, then

where $\sigma(c,f)$ is the sign function determined by the sign of $c$ in the sum ${\mathcal{B}}f$, that is,

We first consider the norm of our weighted Laplacian matrix. If we choose the weight function $\{w_{n}\}_{n\geq 0}$ completely independently, then $\|\tilde{\mathcal{L}}_{n}\|$ is unbounded; for example, let $X$ be a simple graph with one edge and, choose the constant weight functions $w_{0}=1$ and $w_{1}=m$ for some positive number $m$. Then one can compute that $\|\tilde{\mathcal{L}}_{0}\|=2m$, which clearly diverges as $m\to\infty$. Fortunately, there is a natural local condition on weights which gives us an upper bound of the 2-norm of the weighted Laplacian that is independent of the choice of weights:

The filtration condition is not only useful for bounding the norm from above, but it also allows us bound the small eigenvalues from above, as we shall see.

We now investigate the most important property of our weighted Laplacian; the behavior of the small eigenvalues and their implication. Our approach is to decompose a weighted simplicial complex into a union of multiple smaller complexes with larger weights and smaller weights, and observe that the small eigenvalues of the original weighted complex tends to emerge around the cells with smaller weights. The main results are stated in Theorem 3.4 and its direct generalization Proposition 3.5.

In the following discussion, by the intersection $\tilde{X}\cap\tilde{Y}$ (or the union $\tilde{X}\cup\tilde{Y}$, respectively) of weighted simplicial complex $\tilde{X}=(X,\;w_{X})$ and $\tilde{Y}=(Y,\;w_{Y})$, we mean the tuple $(X\cap Y,\;w_{X\cap Y})$ (or $(X\cup Y,\;w_{X\cup Y})$, respectively) where

Hence, for the union and the intersection of weighted simplicial complexes to be well-defined, whenever we write $\tilde{X}\cap\tilde{Y}$ or $\tilde{X}\cup\tilde{Y}$, it is understood that $X$ and $Y$ are defined on the same vertex set and their weight functions satisfy $w_{X}(c)=w_{Y}(c)$ for each $c\in X\cap Y$.

Let us consider the following motivating example. Let $\tilde{X}=(X,w_{X})$ be a weighted simplicial complex illustrated in Figure 7(a), and let us further assume that the weight function $w_{X}$ is constant, say $w_{X}=1$. Combinatorially, $X$ admits one 1-dimensional hole, and from the isomorphism (1), the weighted complex $\tilde{X}$ as well admits a 1-dimensional hole. We now introduce another weighted simplicial complex $\tilde{Y}=(Y,w_{Y})$, as shown in Figure 7(b), and suppose that each simplex of $\tilde{Y}-\tilde{X}$ has weight $\epsilon$, for some small $\epsilon>0$. By identifying certain boundaries, we can form a union $\tilde{X}\cup\tilde{Y}$, and fill the hole of $\tilde{X}$ with a sheet $\tilde{Y}$ with small weights. In fact, $\tilde{X}\cup\tilde{Y}$ has no combinatorially-defined 1-dimensional hole in it. However, because weights of $\tilde{Y}$ are so small, we would like to show that the smallest eigenvalue of $\tilde{X}\cup\tilde{Y}$ is also small so that it almost belongs to the kernel of $\tilde{\mathcal{L}}$, giving the notion of “almost 1-dimensional hole” mentioned in the introduction section. Furthermore, we would like to show the corresponding eigenvector also emerge around $\tilde{Y}$, the cells of small weights. This behavior of weighted complex is formally stated in Theorem 3.4, and our goal of this section is to prove it.

We start with a basic property of the weighted Laplacian with respect to union:

With a little extra effort it is possible to extend the Theorem 3.4 to a sequence of successive union operations thus extending the result to weighted complexes with multiple almost-holes:

Simplicial complexes are proved to be useful in studying coverage problems of the sensor network. Given $n$ sensors $\mathcal{S}=\{s_{1},\cdots,s_{n}\}$ in $\mathbb{R}^{2}$ and $\epsilon>0$, the simplicial complex $\mathcal{R}(\epsilon)$ defined by

is called a Vietoris-Rips complex. One of the initial results that successfully used simplicial complexes in the coverage problem of sensor networks was by Silva et al. [5], which showed that whether or not the a region $D\subseteq\mathbb{R}^{2}$ is covered by a sensor network is sufficient to perform a test on the algebraic image of its boundary $\partial D$ in the simplicial chain complex. Using the Čech complex, a subcomplex of Vietoris-Rips complex, Derenick et al. [4] gave a distributed motion-planning algorithm for mobile robot team that can collapse the homology. They used a combinatorial method to detect the precise location of the holes and used it to compute the motion plans.

In this section, we present a more continuous, parameter-free coverage repair algorithm using the weighted combinatorial Laplacian. Since the weighted Laplacian can measure the "almost holes", there does not have to be combinatorially well-defined holes in the simplicial complex. Hence we can take our simplicial complex to be just a contractible complex (a hole-free complex), and thus, as opposed to the case of using Vietoris-Rips complex (or Čech complex), the algorithm does not depend on the particular choice of $\epsilon$. Another advantage of using weighted Laplacian is the fact that the extremal eigenvalues are naturally piece-wise smooth functions of weights, and this gives an obvious candidate for an algorithm, that is, the gradient descent of the extremal eigenvalues with respect to the weights. If we define the weights to be again smooth functions of positions of the mobile robots in the plane, then we have a piece-wise smooth function that measures the significance of holes with respect to the positions of sensors.

Let us now be more specific. Given a set $S$ of points embedded in the Euclidean plane $\mathbb{R}^{2}$, we construct a 2-dimensional contractible complex $D$ by the Delaunay triangulation, that is, the triangulation on $S$ such that the open disk bounded by the circumcircle of any triangle of $D$ does not contain any point in $S$. In fact, the use of Delaunay triangulation (or its dual, the Voronoi partition) has been a natural choice for sensor coverage problems; for example, see [2], [11]. We let the weight of each edge be the inverse of the Euclidean length of it in $\mathbb{R}^{2}$ and then let the weight of a 2-simplex be the product of the weights of its boundary, that is,

for each 2-simplex $\{v_{0},v_{1},v_{2}\}\in D$. Under the assumption that the weight of the edge is always greater than 1 (which is possible by scaling the embedding as necessary), this choice of weight satisfy the filtration condition introduced in Section 3, and thus the resulting weighted simplicial complex $X$ has all the properties shown in the section. We then compute the first weighted Laplacian operator $\tilde{\mathcal{L}}_{1}(X)$, its eigenvector $v$ corresponding to the non-zero smallest eigenvalue $\lambda$, and the gradient $d\lambda/dS$ of $\lambda$ with respect to the embedding of $S$. Note that we need $v$ to compute the gradient because $d\lambda/d\tilde{\mathcal{L}}_{1}(X)=vv^{T}$. We can then update the embedding $S$ by the positive scalar multiple of $d\lambda/dS$, and therefore obtains the following algorithm:

Here, DelaunayTriangulation$(S)$ is the subroutine that computes the Delaunay triangulation based on the embedding $S$ of points in $\mathbb{R}^{2}$, and $\tilde{\mathcal{L}}_{1}(D,S)$ is the subroutine that computes the weighted Laplacian matrix. A computational result of the algorithm with 80 iterations is shown in Figure 9.

As an inverse approach to our method, we show that it is also possible to create holes in the sensor network. Let $k$ be the number of holes that we would like to create in the simplicial complex. Then it is possible to create $k$-holes in the complex by performing the gradient descent on the $k$th smallest non-zero eigenvalue. A result of this algorithm is shown in Figure 10.

It is often the case that the mobile robots need to explore a domain with obstacles. In this situation, however, the Algorithm 1 cannot be used because the Laplacian would not know whether the hole it sees is a hole in the coverage or an obstacle. To handle this issue, we let the Laplacian operator forget about the hole made by the obstacles so that it can make sure the hole it sees is the hole of the coverage. This leads us to the notion of a relative chain complex, and we further define the relative Laplacian operator.

Let $\{C_{n}\}$ be the chain complex, and let $\{C_{n}^{\prime}\}$ be a subcomplex of $\{C_{n}\}$, that is, each $C_{n}^{\prime}$ is a vector subspace of $C_{n}$, and $c\in C_{n}^{\prime}$ implies $\partial_{n}(c)\in C_{n-1}^{\prime}$. Then we define the relative chain complex $\{C_{n}/C_{n}^{\prime}\}$ to be the chain complex with the $n$-chains $C_{n}/C_{n}^{\prime}$ and the induced boundary maps $\partial_{n}:C_{n}/C_{n}^{\prime}\to C_{n-1}/C_{n-1}^{\prime}$. Because we have not assumed anything beyond $\{C_{n}\}$ being a chain complex, this construction of the relative complex works for the weighted chain complex we have defined in the previous section.

Having these notions in mind, we come back to the coverage repair algorithm with obstacles. Let $S=\{s_{1},\cdots,s_{k}\}\subseteq\mathbb{R}^{2}$ be the set of positions of the $k$ mobile robots distributed in the planar domain. Assume further that there are $m$ obstacles $P_{1},\cdots,P_{m}$ in the domain and that, for each $i=1,\cdots,m$, there is an obstacles $P_{i}$, represented as a disjoint embedding $\coprod_{i=1}^{m}D_{i}$ of discs $D_{i}$ into $\mathbb{R}^{2}$. Then we can choose a sufficiently fine discretization $\overline{P}_{i}$ of the boundary of $P_{i}$ as a 1-dimensional simplicial complex. Now let $X$ be the simplicial complex build by the Delaunay triangulation over the union of $S$ and the vertices of $\overline{P}_{i}$’s, and let $Y_{i}$ be the minimal subcomplex of $X$ containing all the 2-simplexes $X$ that intersects the interior of the obstacle $P_{i}$. If the $\overline{P}_{i}$ is a sufficiently fine discretization of the boundary of $P_{i}$, then we can guarantee that $P_{i}\subset Y_{i}$. We can now recursively compute the relative chain complex $C^{i}=\{C^{i-1}/C_{n}Y_{i}\}$, with the base case $C^{0}=C_{n}X$. Then the Laplacian $\tilde{\mathcal{L}_{1}}(C^{m})$ over the resulting chain complex $C^{m}$ is the weighted Laplacian operator that forgets about the holes created by obstacles. We know that $\text{Ker }\tilde{\mathcal{L}_{1}}(C^{m})=0$, because for each $i=1,\cdots,m$, the following part of the long exact sequence

yields that $\tilde{H}_{1}(C^{i})=0$. Thus the smallest eigenvalue of $\tilde{\mathcal{L}_{1}}(C^{m})$ is non-zero, and therefore we have obtained the following algorithm:

Here, VerticesOf($A$) is the function that takes in a simplicial complex $A$ and spits out the set of vertices of $A$, and $R(P_{i})$ is the repulsive gradient that tries to keep mobile robots away from the obstacles $P_{i}$ and is nonzero only near the boundary of $P_{i}$. Comparing this algorithm with the Algorithm 1, the repulsive gradient $R(P_{i})$ might seem a little unnatural. However, it is necessary; otherwise, some mobile robots will try to get inside the obstacles because the relative Laplacian operator forgets the concrete geometry of the obstacles. A numerical result from this algorithm is presented in Figure 11.