In particular, by propagating waves in a graph, one can compute partitions or clusters in a completely decentralized setting. The method is orders of magnitude faster than existing approaches [@Cit:kempe]. This is our first example of a dynamical systems theory based algorithm for a combinatorial optimization problem. We now discuss the details of the approach.

Let $\mathcal{G}=(V,E)$ be a graph with vertex set $V =
\{1,\dots,N\}$ and edge set $E\subseteq V\times V$, where a weight $\W_{ij} \geq 0$ is associated with each edge $(i,j)\in
E$, and $\W$ is the $N\times N$ weighted adjacency matrix of $\mathcal{G}$. We assume that $\W_{ij}=0$ if and only if $(i,j) \notin E$. The (normalized) graph Laplacian is defined as, $$\begin{aligned}
    \L_{ij} = \begin{cases}
                1 & \mbox{if}\: i = j\\
                -\W_{ij}/\sum_{\ell=1}^N \W_{i\ell} & \mbox{if}\: (i,j) \in E\\
                0   & \mbox{otherwise}\,,
             \end{cases}
             \label{eq:ldef}\end{aligned}$$ or equivalently, $\L = \I-\D^{-1}\W$ where $\D$ is the diagonal matrix with the row sums of $\W$.

Note that in [@Cit:cluster2], only undirected graphs were considered. The smallest eigenvalue of the Laplacian matrix is $\lambda_1 = 0$, with an associated eigenvector $\v^{(1)}=\1=\left[1,1,\dots,1\right]^T$. Eigenvalues of $\L$ can be ordered as, $ 0 = \lambda_1 \leq \lambda_2 \leq \lambda_3
\leq \cdots \leq \lambda_N$ with associated eigenvectors 