NetLogo User Community Models

(back to the NetLogo User Community Models)

Download If clicking does not initiate a download, try right clicking or control clicking and choosing "Save" or "Download".(The run link is disabled for this model because it was made in a version prior to NetLogo 6.0, which NetLogo Web requires.)

## CHE COS'E'?

Questo modello simula l'esecuzione dell'algoritmo Fast MIS from 1986 per il calcolo del Maximal Independent Set su grafi. I grafi nel modello sono grafi generati in maniera casuale scegliendo il numero di nodi e archi oppure sono grafi generati scegliendo soltanto il numero dei nodi e calcolati applicando il modello probabilistico di Erdos-Renyi.
In particolare si vuole simulare il comportamento di tale algoritmo in un contesto distribuito.
La versione di riferimento e' quella presentata in [1], che garantisce un approccio probabilistico alla soluzione del problema.

L' algoritmo opera su round sincroni che vengono raggruppati in fasi.
Ogni fase è composta dai seguenti tre passi:

1) Ogni nodo v marca se stesso con probabilità pari a 1/(2d(v)) dove d(v) indica il grado attuale del nodo v.
2) Se nessun nodo vicino di v con più alto grado è marcato allora v fa join nel MIS. Altrimenti v "smarca" se stesso (fa unmark di se stesso). Se due nodi vicini hanno lo stesso grado allora si considera l'identificatore dei nodi.
3) Cancella tutti i nodi che hanno fatto join nel MIS e anche i loro vicini dato che non potranno più far parte del MIS.

L'algoritmo termina quando ogni nodo ha deciso se far parte o meno del Maximal Independent Set. Analizzando la correttezza dell'algoritmo abbiamo che grazie ai passi 1 e 2 siamo sicuri che se un nodo v entra a far parte del MIS allora i vicini di v non entreranno contemporaneamente a far parte anch'essi del MIS. Inoltre grazie al terzo passo siamo sicuri che se v entra a far parte del MIS, allora i suoi vicini non potranno mai più tentare di entrare nell'insieme. Dopo questa analisi, siamo certi quindi che l'algoritmo effettivamente è corretto.

## COME FUNZIONA

Sono presenti tre procedure. La procedura "fast_mis_1986" implementa effettivamente l'algoritmo. A ciascun agente sono assegnate quattro variabili locali:

- degree: variabile intera che indica il grado corrente del nodo.
- decided: variabile booleana che indica se il nodo ha deciso di entrare a far parte o meno del MIS.
- marked: variabile booleana che indica se il nodo è marcato o no nella fase corrente dell'algoritmo.
- steps: variabile intera che memorizza il numero di fasi che il nodo ha effettuato. Questa variabile non è vitale per l'esecuzione dell'algoritmo ma è stata inserita per una successiva analisi delle performance.

Per implementare il primo passo dell'algoritmo, abbiamo che la scelta probabilistica (basata sempre sul grado corrente del nodo) viene effettuata utilizzando la funzione random-float che estrae un numero casuale compreso tra 0 e 1. In questo modo il nodo marca se stesso solo se tale valore è minore di 1/(2d(v)).
Per il secondo passo invece ogni agente che non ha ancora deciso di entrare o meno a far parte del MIS ma che ha marcato se stesso, interroga concorrentemente i suoi vicini costruendo una lista in cui ogni elemento indica il grado di un vicino. Una volta compilata tale lista, l'agente la scorre controllando se esistono altri vicini con grado maggiore o uguale al suo. Se trova anche soltanto un nodo con grado maggiore e che è anch'esso marcato allora deve necessariamente "smarcarsi"; se invece trova un vicino con lo stesso grado e marcato allora chi dei due ha l'id più basso deve "smarcarsi". Gli agenti che dopo questo controllo restano ancora marcati entreranno a far parte del MIS e disattiveranno inoltre anche i loro vicini che rispettando l'algoritmo non possono entrare nel MIS. Viene così implementato anche il terzo passo dell'algoritmo.
Quando non ci sono più nodi il cui valore di decided è uguale a false l'algoritmo termina.

In "create-graph" sono presenti tutte le operazioni necessarie a creare la rete su cui verrà applicato l'algoritmo. Attraverso la variabile "graph-model" l'utente può scegliere la topologia del grafo che può essere: circle, random, oppure un grafo secondo il modello Erdos-Renyi. Il grafo quindi può essere creato in maniera random a partire dal numero di nodi e dal numero di archi specificati mediante le variabili globali "number-of-nodes" e "number-of-links", scelti dall'utente. Nel caso in cui il valore della variabile number-of-links sia maggiore del numero possibile massimo di archi presenti nel grafo, fissato il numero dei nodi, il numero di archi che vengono creati è pari al valore massimo consentito dalla topologia specificata. Oltre alla modalità random il grafo può essere creato secondo il modello Erdos-Renyi ed in questo caso verranno considerate le variabili globali "number-of-nodes" e "c-value" oppure "probability". Nel caso l'utente scelga di utilizzare la variabile "c-value" allora gli archi verrano generati con una probabilità pari a (c/n) log n. Altrimenti si può scegliere di utilizzare una probabilità indipendente dal numero di nodi ed in questo caso l'utente la può specificare grazie alla variabile "probability".

## COME USARLO

Per avviare l'algoritmo è necessario innanzitutto creare il grafo. Tale operazione viene effettuata specificando mediante gli appositi slider, il numero di nodi e di archi che si vuole creare nei layout "random" e "circle", oppure specificando il numero di nodi e la probabilità di generazione degli archi se si sceglie il modello "Erdos-Renyi". La fase di creazione del grafo termina cliccando sul bottone "Generate Graph" e viene visualizzato così il grafo scelto.
A questo punto si può eseguire l'algoritmo cliccando sul bottone Run.

## DA NOTARE

E' da notare che dopo aver eseguito l'algoritmo, si può nuovamente premere il pulsante Run ed eseguire da capo l'algoritmo sulla stessa topologia. Questo porterà al calcolo di un nuovo MIS che può in generale essere diverso da quello di partenza. Infatti su uno stesso grafo è possibile avere più MIS validi e diversi tra di loro. L'algoritmo termina in numero atteso di passi pari ad O (log n).

## RIFERIMENTI

[1] M. Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. In SIAM Journal on Computing, November 1986.
[2] http://dcg.ethz.ch/lectures/podc_allstars/index.html
[3] N. Alon, L. Babai, and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. Journal of Algorithms, 7(4):567-583, 1986.
[4] A. Israeli, A. Itai. A Fast and Simple Randomized Parallel Algorithm for Maximal Matching. In Information Processing Letters volume 22(2), pages 77-80, 1986.