---
tags: Graph Theory Layout
title: README
---

## Graph Layout using Algebraic Connectivity

This program is trying to layout a graph in graph theorem, by adding some 'spring' as the edges in this graph, and the repulsive force computed from [algebraic connectivity](https://en.wikipedia.org/wiki/Algebraic_connectivity).

This program is avalible at [here](https://makoto-lee.github.io/p5/draw_graph_theory/). And github repository at [there](https://github.com/makoto-lee/graph-layout-using-algebraic-connectivity)

This HackMD [There](https://hackmd.io/@EWx9gzUbSg-mpTIcL2mJsg/BykIeuv1j).

---

### What is algebraic connectivity ?

The algebraic connectivity of a graph is the 2nd smallest eigenvalue of the [Laplacian matrix](https://en.wikipedia.org/wiki/Laplacian_matrix) of the graph. And the corresponding eigenvector is called Fiedler vector.

Fiedler vector can be a method to find out a 'center' of a graph, by indicating the nodes with numbers in the Fiedler vector.

For example:

with its Fiedler vector : $\vec{v_f} =\begin{pmatrix}
-0.3717\\
-0.6015\\
2.7637\times 10^{-15}\\
0.6015\\
0.3717\\
-2.6990\times 10^{-15}
\end{pmatrix}$

we denote node 0 ~ 5 with elements in $\vec{v_f}$ in its order then 1 of 2 cases below happens:

$A: \text{One node with denoted value = 0 }$
$B: \text{Two nodes with denoted value close to 0, and one of it is positive the another is negtive}$


The above example is case $B$.

In both case $A$ and $B$ the node(s) with value close (or equal) to 0 will approximately be a center of the graph.

By this we can layout a graph in some methods.

---

### How did this program use algebraic connectivity to layout ?

For each pair of nodes $a$ and $b$ we give a repulsive force between them, I design the power of the repulsive force by this following formula :
$$ \text{power} = \frac{| \text{sigmoid}(\vec{v_f}(a)) - \text{sigmoid}(\vec{v_f}(b)) | }{\text{distance between a and b}} \times k$$

Note that the $\vec{v_f}(a)$ is the denoted value of node $a$ in Fiedler vector $\vec{v_f}$, and $k$ is a const value used to adjust the power according to the size of canvas.

Also, to make sure all the value of $\vec{v_f}(i)$ were in a controllable range so I put them in a $sigmoid$ function. Next divid it with the distance between $a$ and $b$, so that the edges will not be stretch over when their distance is far enough, meanwhile nodes will have larger repulsive force when they are too close.

---

### Some examples

| Without algebraic connectivity support | With algebraic connectivity support |
| -------- | -------- |
| | 
|
||
|
||
|

---

### Future appliance

When doing the 2D softbody physics simulation:
1. We can use this method to prevent a softbody from self-collapse.
2. By using the Fiedler vector we know which nodes is closer, we can reduce the numbers we need to the iterate.

other project using this method:

LINK : https://github.com/makoto-lee/softbody-physics-simulation