PhD Degree

University of Chile

Faculty of Physical Sciences and Mathematics

Department of Mathematical Engineering

Doctoral Program in Engineering Sciences, Mention in Mathematical Modeling

LOCAL DYNAMICS FOR THE CALCULATION OF GLOBAL PROPERTIES IN GRAPHS

Laura Mayely Leal Chacón $^1$

lleal@dim.uchile.cl

April 2023

$^1$Laura was partly financed by ANID BECA DOCTORADO NACIONAL 2019-21191440.

Distributed system

Classic problems

The density classification problem

The computation of a Maximal Independent Set

To solve this problem we follow the idea proposed in [1], where the authors designed a cellular automaton inspired by two mechanisms: diffusion and amplification.

\begin{equation}\label{e_calor_biestable} \frac{\partial u}{\partial t} -\nu \Delta u = \gamma b_{\rho_c}(u), \end{equation}

(1.1)

$$b_{\rho_c}(u)=u(1-u)(u-\rho_c).$$

(1.2)

The resulting nonlinear heat-equation is called the bistable heat equation.

[1] Raimundo Briceño, Pablo Moisset de Espanés, Axel Osses, and Ivan Rapaport. Solving the density classification problem with a large diffusion and small amplification cellular automaton. Physica D: Nonlinear Phenomena, 261:70-80, 2013.

The idea proposed is:

\begin{equation*}\label{v_d_G} \frac{u_{i}^{k+1}-u_{i}^k}{\Delta t} + \frac{\nu}{h^2}\sum_{j \in N(i)} L_{ij}u_j^k = \gamma b_{\rho_c}(u^{k}_i), \end{equation*}

(1.3)

If we denote by $\sigma =\Delta t \gamma$, $\sigma'=\frac{\nu \Delta t}{h^2}$ and $b_{\rho_c}(u_i)=u_i(1-u_i)(u_i-\rho_c)$, we obtain the local rule:

$$u_{i}^{k+1} = u_{i}^k - \sigma' \sum_{j \in N(i)} L_{ij}u_j^k + \sigma b_{\rho_c}(u^{k}_i).$$

(1.4)

Finally we choose the parameter $\nu$ in order to fix $\sigma'=\frac{1}{(\Delta+1)}$, where $\Delta = \Delta(G)$ is the maximum degree of $G$.

Then, the large diffusion and small amplification dynamic over $G$ updating rule $\Phi_{\sigma}$:

\begin{align}\label{eq:dyn} v^{t} &= \left(I - \frac{L}{\Delta+1}\right) u^t \\ \\ u^{t+1}_i &= f_{\sigma}(v^t_i), \end{align}

(1.5)

(1.6)

where $f_\sigma(x) = x + \sigma b_{\rho_c}(x)$.

Algorithm:

$u_i(0) \leftarrow$ Randon $\{0, 1\}$
$t \leftarrow 1$
while stopping criteria do:
$u_{i}^{t+1} = u_{i}^t - \frac{1}{(\Delta+1)} \displaystyle\sum_{j \in N(i)} L_{ij}u_j^t + \sigma b_{\rho_c}(u^{t}_i)$
$t \leftarrow t+1$
end while

Stopping criteria with tol = $10^{-3}$
* if $\sigma=0$:
$max[u(t)-u(t-1)] < tol$
* if $\sigma > 0$:
$min\{max[u(t)-1], max[u(t)]\}< tol$

Convergence criterion
* if $max[u(t)-1] < max[u(t)]$
$u \rightarrow 1$
* else
$u \rightarrow 0$

Complete graph with 11 vertex and 55 edges.

\begin{bmatrix} 10 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \\ -1 & 10 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \\ -1 & -1 & 10 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \\ -1 & -1 & -1 & 10 & -1 & -1 & -1 & -1 & -1 & -1 & -1 \\ -1 & -1 & -1 & -1 & 10 & -1 & -1 & -1 & -1 & -1 & -1 \\ -1 & -1 & -1 & -1 & -1 & 10 & -1 & -1 & -1 & -1 & -1 \\ -1 & -1 & -1 & -1 & -1 & -1 & 10 & -1 & -1 & -1 & -1 \\ -1 & -1 & -1 & -1 & -1 & -1 & -1 & 10 & -1 & -1 & -1 \\ -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 10 & -1 & -1 \\ -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 10 & -1 \\ -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & -1 & 10 \\ \end{bmatrix}

Laplacian matrix of the complete graph with 11 vertex.

\begin{bmatrix} \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} \\ \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} \\ \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} \\ \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} \\ \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} \\ \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} \\ \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} \\ \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} \\ \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} & \frac{1}{11} \\ \end{bmatrix}

Diffusion coefficient for complete graph with 11 vertex
$ \omega = \left(I - \frac{L}{\Delta+1}\right) \rightarrow \frac{1}{11}*$ U

* Diffusion phenomenon

Simulation of the algorithm applied to
the complete graph of 11 vertex and $\sigma = 0$.

$u(0) = [0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1]$

$u(1) = \frac{1}{11}$ U $[0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1]^t$
$u(1) = \frac{8}{11} \overrightarrow{1}$

$u(2) = \frac{1}{11}$ U $\frac{8}{11} [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]^t$
$u(2) = \frac{8}{11} \overrightarrow{1}$

* Diffusion and amplification phenomenon

Simulation of the algorithm applied to
the complete graph of 11 vertex and $\sigma = 0.01$.

$u(0) = [0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1]$

$u(1) = \frac{8}{11} \overrightarrow{1} + \sigma \frac{8}{11} \overrightarrow{1} \frac{3}{11} \overrightarrow{1} \frac{5}{22} \overrightarrow{1}$
$u(1) = \frac{8}{11} \overrightarrow{1} + \frac{1}{100} \frac{60}{1331} \overrightarrow{1}$
$u(1) = \frac{8}{11} \overrightarrow{1} + \frac{3}{6655} \overrightarrow{1}$
$u(1) = 0.727272 \overrightarrow{1} + 0.00045078 \overrightarrow{1}$

Theoretical Result.

Theorem.

For every connected graph $G$ and for every $\varepsilon >0$ there exists a $\sigma>0$ such that the large diffusion and small amplification dynamic over $G$ solves the $\varepsilon$-approximation of the density classification problem.

Laura Leal, Pedro Montealegre, Axel Osses, and Iván Rapaport. A large diffusion and small amplification dynamics for density classification on graphs. International Journal of Modern Physics C, 34(05), 2023.

Experimental study.

Regular graphs, which are the $n$-node graphs where each node has the same degree $d$

Erdős-Rényi graphs, which is a model of random graphs, where each edge is independently included in the graph with probability $p$. For our experiments, for an $n$-node graph, we pick $p = \frac{2 \ln (n)}{n}$, which roughly corresponds to the minimum probability that ensures that the graph is connected with high probability.

Barabási-Albert graphs, which is another model of random graphs, generated sequentially according to a parameter $m$ as follows. The network starts with $m$ nodes connected randomly. Then, $n-m$ nodes are sequentially added to the graph. Each time that a new node is added it is connected to $m$ existing nodes with a probability that is proportional to the degree that existing nodes already have.

Barabási-Albert graphs with parameter m=2

Barabási-Albert graphs with parameter m=4

star graph

For our simulations:

Pick odd values of $n$, from $11$ to $251$ with a step of $30$.

For each $n$:

1) $d$-Regular graphs for $d \in \{4,6,8\}$ (50 samples for each $d$);

2) Erdős-Rényi graphs with parameter $p = \frac{(2 \ln (n))}{n}$;

3) Barabási-Albert graphs of parameter $m \in \{1,2,3,4\}$ (50 samples for each $m$).

For each graph, $10 \cdot n$ random initial configurations are picked uniformly at random.

Report the results of our computational simulations.

Experimental study when $\sigma = 0$.

Experimental study when $\sigma = 0.01$.

Mean convergence time vs amplification, in graphs of 11 vertex.

Mean porcentage of effectiveness vs amplification, in graphs of 11 vertex.

In a keynote talk of SIROCCO 2022 [1], George Giakkoupis presented two extremely simple randomized algorithms for MIS. His algorithms have two interesting properties: they are self-stabilizing and they require only two or three states.

[1] George Giakkoupis. Simple efficient distributed processes on graphs, 2022. Keynote talk of the 29th International Colloquium of Structural Information and Communication Complexity, SIROCCO 2022, Paderborn, Germany, June 28th, 2022.

2-MIS-Dynamics

(i) If $x_u=0$ and $\forall v \in N(u), x_v = 0$,
then $x_u = 1$.
(ii) If $x_u \neq 0$ and $\exists v \in N(u), x_v \neq 0$,
then $x_u \in_U \{0,1\}$.
(iii) $x'_u = x_u$ otherwise.

Example for $K_{10}$:

u(0) = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
u(1) = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
u(2) = [0, 0, 1, 1, 0, 0, 0, 0, 1, 0]
u(3) = [0, 0, 0, 0, 0, 0, 0, 0, 1, 0]

k-MIS-Dynamics with $k = {3}$

(i) If $x_u=0$ and $\forall v \in N(u), x_v = 0$,
then $x'_u \in_U [k-1]$.
(ii) If $x_u \neq 0$ and $\exists v\in N(u), x_u = x_v$
and $\forall v \in N(u), x_v \leq x_u$,
then $x'_u \in_U [k-1]$.
(iii) If $x_u \neq 0$ and $\exists v \in N(u), x_v > x_u$,
then $x'_u = 0$.
(iv) $x'_u = x_u$ otherwise.

Example for $K_{10}$:

u(0) = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
u(1) = [2, 2, 2, 1, 2, 1, 2, 1, 1, 2]
u(2) = [2, 1, 2, 0, 1, 0, 2, 0, 0, 2]
u(3) = [1, 0, 2, 0, 0, 0, 1, 0, 0, 1]
u(4) = [0, 0, 2, 0, 0, 0, 0, 0, 0, 0]

Experimental study.

For our simulations:

Pick values of $n$, from $10$ to $4.960$ with a step of $50$.
Pick values of $n$, from $10$ to $1.000$ with a step of $1$.

For each $n$:

1) $d$-Regular graphs for $d \in \{4,6,8\}$.

2) Erdős-Rényi graphs with parameter $p = \frac{(2 \ln (n))}{n}$.

3) Barabási-Albert graphs of parameter $m \in \{1,2,3,4\}$ (50 samples for each $m$).

For each graph, $1.000$ ó $5.000$ simulations.

Report the results of our computational simulations.

Simulation on the complete graph

Plots of the average convergence time for the 2-MIS-Dynamics and MIS-Dynamics for different graph classes. In the left column, we have the linear scale, while in the right column we give the $x$-axis in $\log_2$ scale.

Worst-case convergence

Theoretical Results.

A bound on the convergence time of the MIS-Dynamics on arbitrary graphs.

Theorem 1.

For every initial configuration, the MIS-Dynamics converges to a configuration representing a maximal independent set in $\mathcal{O}(\alpha\cdot\log n)$ time-steps with high probability.

$\alpha$ is the size on the maximun independent set.

The 2-MIS-Dynamics on arbitrary graphs.

Theorem 2.

For every initial configuration, the 2-MIS-Dynamics converges to a configuration representing a maximal independent set in $\mathcal{O}(\alpha\cdot\log^2 n)$ time-steps with high probability.

The 2-MIS-Dynamics on graphs of bounded degeneracy.

Theorem 3.

For every initial configuration over a $d$-degenerate graph, the 2-MIS-Dynamics converges to a configuration representing a maximal independent set in $\mathcal{O}(\log n)$ time-steps with high probability.

Eric Goles, Laura Leal, Pedro Montealegre, Iván Rapaport, and Martín Ríos-Wilson. Distributed maximal independent set computation driven by finite-state dynamics. International Journal of Parallel, Emergent and Distributed Systems, 38:85-97, 2023.

Local dynamics for the calculation of global properties in graphsMotivation.

The density classification problem.

The computation of a Maximal Independent Set.

Conclusions and Future Work.

University of Chile

Faculty of Physical Sciences and Mathematics

Department of Mathematical Engineering

Doctoral Program in Engineering Sciences, Mention in Mathematical Modeling

LOCAL DYNAMICS FOR THE CALCULATION OF GLOBAL PROPERTIES IN GRAPHS

Laura Mayely Leal Chacón $^1$

lleal@dim.uchile.cl

April 2023

$^1$Laura was partly financed by ANID BECA DOCTORADO NACIONAL 2019-21191440.

Distributed system

Classic problems

The density classification problem

The computation of a Maximal Independent Set

Algorithm:

* Diffusion phenomenon

* Diffusion and amplification phenomenon

Theoretical Result.

Theorem.

Experimental study.

For our simulations:

Report the results of our computational simulations.

Experimental study when $\sigma = 0$.

Experimental study when $\sigma = 0.01$.

Mean convergence time vs amplification, in graphs of 11 vertex.

Mean porcentage of effectiveness vs amplification, in graphs of 11 vertex.

2-MIS-Dynamics

Example for $K_{10}$:

k-MIS-Dynamics with $k = {3}$

Example for $K_{10}$:

Experimental study.

For our simulations:

Report the results of our computational simulations.

Simulation on the complete graph

Worst-case convergence

Theoretical Results.

A bound on the convergence time of the MIS-Dynamics on arbitrary graphs.

Theorem 1.

The 2-MIS-Dynamics on arbitrary graphs.

Theorem 2.

The 2-MIS-Dynamics on graphs of bounded degeneracy.

Theorem 3.

This research was partially supported by the supercomputing infrastructure of the NLHPC (ECM-02).

Local dynamics for the calculation of global properties in graphs
Motivation.