1
$\begingroup$

On a graph $G(V,E)$, knowing that each entry of the incidence matrix $\nabla$ is defined as: \begin{equation} \nabla_{ev} = \begin{cases} -1 & \text{if $v\in V$ is the initial vertex fo the edge $e \in E$}\\ +1 & \text{if $v\in V$ is the final vertex of the edge $e \in E$}\\ 0 & \text{otherwise} \end{cases} \end{equation}

if we have a function $h:E \to \mathbb{R}$ and the incidence matrix $\nabla$, the $i$-th component of the product between its transposed version and $h$ results to be $(\nabla^T h^T) _i=\sum\limits_{\text{$e\in E$ exits from $i\in V$}}h_e - \sum\limits_{\text{$e\in E$ enters in $i\in V$}}h_e$.

This operator $\nabla^T$ is also called, in graph theory, divergence operator. One application of this operator is the construction of the graph Laplacian Matrix $\nabla^2$ defined as $\nabla^2=\nabla^T \nabla$, that conceptually should be ''the divergence of gradient'', as for the classic Laplacian operator. While it seems clear to me the approximation of $\nabla$ to the derivative operator ( if we have $f:V \to \mathbb{R}$, the $e$-th component $(\nabla f)_e$ results to be the difference $f(j)-f(i)$ if $e \in E$ connect $i\in V$ to $j\in V$), $\nabla^T$ on graphs seems to me very different from the classical divergence operator used in maths, which is defined as $\nabla\cdot\mathbf{F} = \left( \frac{\partial}{\partial x}, \frac{\partial}{\partial y}, \frac{\partial}{\partial z} \right) \cdot (F_x,F_y,F_z) = \frac{\partial F_x}{\partial x}+\frac{\partial F_y}{\partial y}+\frac{\partial F_z}{\partial z}$ where $\mathbf{F}$ is a vector field.

For example, in the classical divergence definition we have a sum of derivatives (derivatives which could be viewed as ''differences'' in the discrete case), instead in the the graph case we have a difference of sums. So, why we refer to it as ''divergence'' if $\nabla^T$ seems to be a different object? How is it possible that $\nabla^T \nabla$ turns out to be the equivalent of the classic Laplacian despite the differences between $\nabla^T$ on graphs and the classic divergence operator?

$\endgroup$

1 Answer 1

1
$\begingroup$

You can see your difference of sums as $\underset{e\in E \text{ enters or exits } i\in V}{\sum} h_e \varepsilon_{i,e}$ where $\varepsilon_{i,e}$ is $\pm1$ depending on the wether $e$ enters or exits $i$, and then indicates the "variation" of $h$ when you follow the edge $e$ (as in the real case, if you reverse the time your sign of the derivative changes). Then your divergence in the graph is the sum over all possible directions (the edges) of the variations of $h$ (signed by the way the edge is directed).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .