IoT City: pettegolezzi e diffusione delle informazioni

“Se ognuno si facesse i cavoli suoi, il mondo girerebbe un bel po’ più svelto.” — Lewis Carroll

E’ mattina come tante ad IoT City. I cittadini vivono le loro vite tranquille, ignari di tutto. Finché un cittadino che vive nella zona nord della città non riceve una notizia sorprendente: qualcuno in città ha vinto una fortuna alla lotteria. Come si diffonderà la voce? Ne parleranno tutti?

In questo episodio affronteremo questo tema: come è possibile diffondere un’informazione fra un insieme di nodi senza un canale centrale? Come si diffonde questa vera e propria “epidemia” di informazione? In effetti poche e semplici interazioni causali fra i passanti possono portare l’intera città a parlare della ricca vincita. Nello specifico affronteremo una famiglia di protocolli decentralizzati per lo scambio di informazioni fra i nodi di una rete: gli algoritmi di gossip basati su “rumor mongering”. Si tratta di una famiglia di algoritmi introdotti nel 1987 da Alan Demers et al. nel loro paper *“Epidemic algorithms for replicated database maintenance”*. Nell’articolo gli autori cercano di affrontare il problema della propagazione delle modifiche nell’ambito di un database distribuito; approcci semplici derivanti dal mondo della epidemiologia sono stati analizzati al fine di garantire la propagazione in tempi ridotti e senza particolari requisiti infrastrutturali delle modifiche a tutte le repliche. In altri termini, riassumendo i concetti che abbiamo già visto negli episodi precedenti, tali algoritmi sono stati considerati per il conseguimento della consistenza eventuale. Il protocollo di gossip rumor mongering si basa su nodi interconnessi (analizzeremo in seguito come la topologia della rete influisca sull’esecuzione dell’algoritmo) che possono ricoprire 3 specifici ruoli:

• Nodo IGNORANTE (ignorant): è all’oscuro del pettegolezzo e pronto ad ascoltarlo. All’arrivo di un pettegolezzo passa in stato DIFFUSORE;
• Nodo DIFFUSORE (spreader o hot rumor nell’articolo originale): ad intervalli regolari seleziona un nodo a caso fra quelli presenti nella rete e condivide il pettegolezzo. Ogni volta che incontra un nodo già a conoscenza del pettegolezzo, il nodo diffusore “perde” un po’ di interesse nella diffusione dell’informazione. L’informazione diviene, in altri termini, meno calda;
• Nodo SOFFOCANTE (stifler): è un nodo DIFFUSORE che ha perso tutto l’interesse per l’informazione. Non diffonde ulteriormente l’informazione e risponde agli eventuali nodi diffusori “soffocando” il loro entusiasmo.

Quale variante al protocollo è possibile prevedere che dallo stato SOFFOCANTE sia possibile, se esposto nuovamente al pettegolezzo, tornare allo stato DIFFUSORE. Rappresenta uno scenario analogo alla persona che, guarita da una epidemia, può tornare, dopo un po’ di tempo, ad infettarsi. Il processo di diffusione dell’informazione termina quando non vi sono più nodi DIFFUSORE attivi; il sistema, in questo caso, raggiunge un equilibrio (anche se potrebbe non essere garantita la consistenza eventuale) che può essere modificato in caso di stimolo dall’esterno, con un nuovo pettegolezzo.

Il protocollo descritto sembra, a tutti gli effetti, un candidato ideale per essere implementato con gli attori di Akka.NET; costruiamolo insieme.

In questo primo esempio assumiamo che:

• il grafo delle relazioni tra i cittadini sia completamente connesso: ciascun cittadino può comunicare con tutti gli altri;
• la scelta del destinatario della comunicazione sia casuale (in questo esempio non consideriamo la semantica della relazione tra i cittadini, siano essi parenti, amici o semplici passanti);
• un cittadino in stato DIFFUSORE smetta di diffondere il proprio messaggio dopo aver incontrato cinque altri cittadini già a conoscenza della novità.

Iniziamo implementando il nostro attore CitizenActor.

public enum CitizenState
{
    IGNORANT,
    SPREADER,
    STIFLER
}
public record SetCitizens(List<IActorRef> Citizens);
public record Rumor();
public record Feedback(bool AlreadySeen);
public record MakePhoneCall();

public record GetState();
public record StateResponse(string Name, CitizenState State);

public class CitizenActor : ReceiveActor
{
    private List<IActorRef> _citizens;
    private String _name;
    private CitizenState _state;
    private int _rumorAlreadySeen = 0;
    private readonly Random _random = new Random(); 
    private ICancelable gossipTask;

    public CitizenActor(string name)
    {
        _name = name;
        _state = CitizenState.IGNORANT;
        _rumorAlreadySeen = 0;
        _citizens = new List<IActorRef>();

        Receive<SetCitizens>(msg =>
        {
            _citizens = new List<IActorRef>();
            foreach (var a in msg.Citizens)
            {
                if (a != Self)
                {
                    _citizens.Add(a);
                }
            }
        });

        Receive<Rumor>(msg =>
        {
            if (_state == CitizenState.SPREADER)
            {
                Sender.Tell(new Feedback(true));
            }
            if (_state == CitizenState.STIFLER)
            {
                Sender.Tell(new Feedback(true));
            }
            if (_state == CitizenState.IGNORANT)
            {
                _state = CitizenState.SPREADER;
                Sender.Tell(new Feedback(false));


                gossipTask = Context.System.Scheduler.ScheduleTellRepeatedlyCancelable(
                    TimeSpan.Zero,
                    TimeSpan.FromMilliseconds(500),
                    Self,
                    new MakePhoneCall(),
                    Self);
            }
        });

        Receive<Feedback>(msg =>
        {
            if (msg.AlreadySeen)
            {
                _rumorAlreadySeen++;
            }
            if (_rumorAlreadySeen == 5 && _state == CitizenState.SPREADER)
            {
                _state = CitizenState.STIFLER;
                gossipTask.Cancel();
            }
        });

        Receive<GetState>(msg =>
        {
            Sender.Tell(new StateResponse(_name, _state));
        });

        Receive<MakePhoneCall>(msg =>
        {

            if (_state == CitizenState.SPREADER)
            {
                var k = _random.Next(_citizens.Count);
                var randomNeighbor = _citizens[k];
                randomNeighbor.Tell(new Rumor());
            }
            else
            {
                gossipTask?.Cancel();
            }
        });
    }

I messaggi che il nostro attore è in grado di gestire sono:

• SetCitizens: consente di collegare tra loro i cittadini. Nei prossimi esempi creeremo topologie alternative al grafo completamente connesso, per analizzare come il protocollo si comporta;
• Rumor: rappresenta il vero e proprio gossip, che l’attore riceve dall’esterno (innesco) o da un altro attore. Determina il passaggio di stato da ignorante a diffusore. Dopo aver ricevuto il pettegolezzo, l’attore risponde al mittente indicando se fosse già a conoscenza dell’informazione;
• Feedback: è la risposta ricevuta dopo aver effettuato la propagazione del pettegolezzo. Determina il passaggio di stato da diffusore a soffocante. In caso di passaggio di stato, il processo periodico di propagazione del pettegolezzo viene interrotto;
• GetState: utilizzato a fini di testing, restituisce lo stato attuale dell’attore;
• MakePhoneCall: invocato a intervalli regolari, seleziona casualmente uno dei cittadini collegati al nostro attore e procede con la propagazione del pettegolezzo.

Per consentire l’esecuzione periodica, Akka.NET mette a disposizione la possibilità di creare Scheduler in grado di inviare uno specifico messaggio a un attore (in questo caso, a se stesso) a intervalli regolari, dopo una pausa iniziale (in questo esempio di zero millisecondi).

gossipTask = Context.System.Scheduler.ScheduleTellRepeatedlyCancelable(
                    TimeSpan.Zero,
                    TimeSpan.FromMilliseconds(500),
                    Self,
                    new MakePhoneCall(),
                    Self);

Da notare che avrei potuto organizzare il comportamento dell’attore anche utilizzando il costrutto Become, per gestire in modo differenziato i messaggi relativi ai tre stati, realizzando così una macchina a stati finiti.

public class CitizenActorTest : TestKit
{

    private readonly ITestOutputHelper _output;

    public CitizenActorTest(ITestOutputHelper output)
    {
        _output = output;
    }

    [Fact]
    public void Citizen_ShouldStartAsIgnorant()
    {
        var citizen = Sys.ActorOf(Props.Create(() => new CitizenActor("Alice")));
        citizen.Tell(new Rumor()); 
        Assert.True(true);
    }
    [Fact]
    public async Task Citizen_ShouldBecomeSpreader_WhenReceivesFirstRumor()
    {
        var probe = CreateTestProbe();
        var citizen = Sys.ActorOf(Props.Create(() => new CitizenActor("Bob")));
        citizen.Tell(new SetCitizens(new List<IActorRef> { probe.Ref }));

        citizen.Tell(new Rumor(), probe.Ref);

        var feedback = await probe.ExpectMsgAsync<Feedback>(TimeSpan.FromSeconds(1));
        Assert.False(feedback.AlreadySeen);
    }

    [Fact]
    public async Task Spreader_ShouldReplyAlreadySeen_WhenRumorReceivedAgain()
    {
        var probe = CreateTestProbe();
        var citizen = Sys.ActorOf(Props.Create(() => new CitizenActor("Carol")));

        citizen.Tell(new SetCitizens(new List<IActorRef> { probe.Ref }));

        citizen.Tell(new Rumor(), probe.Ref);
        await probe.ExpectMsgAsync<Feedback>();

        citizen.Tell(new Rumor(), probe.Ref);
        var feedback = await probe.ExpectMsgAsync<Feedback>();
        Assert.True(feedback.AlreadySeen);
    }

    [Fact]
    public async Task Spreader_ShouldBecomeStifler_AfterFiveAlreadySeen()
    {
        var probe = CreateTestProbe();
        var citizen = Sys.ActorOf(Props.Create(() => new CitizenActor("Dave")));

        citizen.Tell(new SetCitizens(new List<IActorRef> { probe.Ref }));
        citizen.Tell(new Rumor(), probe.Ref);
        await probe.ExpectMsgAsync<Feedback>();

        for (int i = 0; i < 5; i++)
        {
            citizen.Tell(new Feedback(true));
        }
        citizen.Tell(new MakePhoneCall());
        Assert.True(true);
    }

    [Fact]
    public async Task Rumor_ShouldPropagateThroughNetwork()
    {

        int N = 10000;
        var citizens = new List<IActorRef>();
        for (int i = 0; i < N; i++)
        {
            var c = Sys.ActorOf(Props.Create(() => new CitizenActor($"Citizen_{i}")));
            citizens.Add(c);
        }

        foreach (var c in citizens)
        {
            c.Tell(new SetCitizens(citizens));
        }

        var starter = citizens[0];
        starter.Tell(new Rumor());

        await Task.Delay(8000);

        var states = new List<StateResponse>();
        foreach (var c in citizens)
        {
            var response = await c.Ask<StateResponse>(new GetState(), TimeSpan.FromSeconds(1));
            states.Add(response);
        }

        int nonIgnorant = states.Count(s => s.State != CitizenState.IGNORANT);

        Assert.True(nonIgnorant >= N / 2, $"{nonIgnorant} / {N} non ignorant citizens");
        _output.WriteLine($"{nonIgnorant} / {N} non ignorant citizens");
        _output.WriteLine("== RESULTS ==");
        foreach (var s in states)
        {
            _output.WriteLine($"{s.Name}: {s.State}");
        }
    }
}

Eseguendo i test, possiamo verificare che:

• l’attore definito rispetta i passaggi di stato previsti dal protocollo descritto in precedenza (test da 1 a 4);
• la propagazione raggiunge la maggior parte degli attori, anche con un intervallo di propagazione relativamente breve di 8 secondi (scelto in modo casuale) e con un insieme di 10.000 attori coinvolti;
• i messaggi che abbiamo aggiunto per consentire l’ispezione dello stato dei nostri cittadini misurano il grado di copertura nella diffusione del nostro pettegolezzo all’interno della città.

Spingiamoci ora un piccolo passo avanti, cercando di comprendere meglio i flussi di messaggi che intercorrono tra i vari attori. Per farlo, possiamo adottare la seguente soluzione — la componente visuale è frutto del contributo di ChatGPT, che ha colmato le mie lacune in materia: ogni messaggio Rumor ricevuto da un cittadino verrà aggiunto come nuova riga all’interno di un file CSV, memorizzando il* timestamp di invio, il mittente, il destinatario e lo stato del destinatario prima della ricezione del messaggio.*

A tal fine, definiamo un nuovo attore, CSVActor, e modifichiamo di conseguenza il nostro CitizenActor.

 public record AddRow(DateTime DateTime, String Sender, String Receiver, CitizenState ReceiverState);

 public class CSVActor : ReceiveActor
 {

     public CSVActor()
     {
         var csvPath = Path.Combine(Directory.GetCurrentDirectory(), "rumor_log.csv");
         File.WriteAllText(csvPath, "date_time,sender,receiver,receiver_state\n");

         Receive<AddRow>(msg =>
         {
             var time = msg.DateTime.ToString("HH:mm:ss.fff");

             File.AppendAllText(csvPath, $"{time},{msg.Sender},{msg.Receiver},{msg.ReceiverState}\n");
         });
     }
 }

public class CitizenActor : ReceiveActor
{
    ...
    public CitizenActor(string name, IActorRef csvActor = null)
    {
        ...
        _csvActor = csvActor;

       ...

        Receive<Rumor>(msg =>
        {
            if(_csvActor != null)
            {
                _csvActor.Tell(new AddRow(DateTime.Now, msg.Sender, _name,_state));
            }

            ...
        });

        ...
    }

Il file CSV così ottenuto lo possiamo utilizzare per realizzare la seguente animazione, che ci mostra la propagazione del pettegolezzo e la variazione di stato degli attori nel tempo. In questo caso ho scelto di lavorare con 25 attori; il grafo potrebbe sembrare non completamente connesso, perché creato utilizzando come archi solo le comunicazioni fra i cittadini che hanno avuto luogo nel periodo di osservazione.

[embed]

È interessante notare come evolva il comportamento del sistema nel suo complesso: all’inizio la propagazione è rapida e coinvolge sempre più nodi in contemporanea, poiché ciascun diffusore inizia a sua volta il processo di diffusione del pettegolezzo. In pochi cicli, la maggioranza dei cittadini è raggiunta dal pettegolezzo; ciascuno di essi opera come diffusore o come agente soffocante.

I messaggi scambiati iniziano a diventare progressivamente meno utili, poiché diminuisce la probabilità di selezionare casualmente un cittadino ancora ignorante. I diffusori, a loro volta, tendono a perdere entusiasmo, diventando agenti soffocanti. Il parametro k, che abbiamo fissato a 5 e che determina il passaggio da diffusore a agente soffocante, implica che siano necessari 𝑘𝑛 messaggi inutili per portare il sistema alla quiete.

Poiché abbiamo già tutti i componenti necessari, sarebbe interessante studiare come varia il comportamento del sistema al variare di 𝑛 e 𝑘 È possibile ridurre il numero di messaggi ridondanti senza compromettere la capacità di propagazione del pettegolezzo? Possiamo trovare un trade-off ottimale?

Non vorrei andare fuori tema o ricadere nella mia vecchia abitudine di interventi logorroici, ma ti invito a modificare il codice condiviso e a provare tu stesso diversi scenari.

Possiamo descrivere questo primo caso d’uso, basato su un grafo completamente connesso, con le seguenti proprietà:

• elevata probabilità di raggiungere una copertura prossima al 100% dei nodi;
• tempo di diffusione del messaggio pari a O (log n) cicli, anche se nel nostro caso il tempo ciclo è definito a livello di singolo agente e non tramite un clock esterno;
• elevata robustezza ai guasti: grazie all’elevata ridondanza dei messaggi scambiati (dipendente dal valore di k), anche se un cittadino non è più in grado di propagare il pettegolezzo (ad esempio perché ha esaurito la carica del proprio telefono), il suo ruolo è compensato dall’attività degli altri diffusori presenti nel sistema.

Un articolo interessante su questo tema è il seguente, che confronta performance e complessità computazionale tra diverse varianti dei protocolli di gossip (alcuni dei quali verranno affrontati nelle prossime puntate)

E se invece il nostro grafo non fosse interamente connesso? Ipotizziamo di assegnare a ogni nodo un insieme di vicini casuali, creando così un grafo parzialmente connesso. Come si comporterebbe il protocollo rumor mongering?

In generale, ci si troverà di fronte alle seguenti caratteristiche:

• la diffusione potrebbe non raggiungere il 100% dei nodi, dipendendo fortemente dalla connettività del grafo;
• il tempo di diffusione diventa O (D log n) cicli, con D pari al diametro del grafo;
• la robustezza è messa alla prova: se vengono meno i collegamenti “ponte” più importanti, potrebbe risultare impossibile raggiungere una consistenza eventuale accettabile.

In questi casi, il grado di interconnessione del grafo incide significativamente sul comportamento del protocollo. Per studiarlo è utile conoscere la conduttanza del grafo, ossia una misura di quanto il grafo sia “ben collegato” o, in alternativa, di quanto presenti strozzature che separano il grafo in sottostrutture scarsamente interconnesse.

In pratica, se la nostra IoT City è abitata da cittadini ben connessi tra loro, possiamo ragionevolmente aspettarci che la notizia si diffonda in tempi ridotti, prossimi a O (log n). Se invece ci sono fattori che limitano la connettività tra cittadini — ad esempio la lontananza geografica, pessimi rapporti di vicinato o la mancanza di mezzi di comunicazione — potrebbero essere necessari percorsi molto più lunghi per raggiungere la maggior parte della popolazione.

In ogni caso, non abbiamo mai la garanzia di raggiungere tutti i nodi della rete, nemmeno se il grafo fosse teoricamente completamente connesso.

Prima di concludere, vediamo come si comporta il protocollo in casi particolari. Consideriamo un anello (ring) in cui ciascun cittadino comunica esclusivamente con i due vicini immediati, uno a destra e uno a sinistra.

Cosa può succedere se impostiamo il valore di k troppo basso, ad esempio k=2? La probabilità che un nodo diffusore x selezioni per tre volte consecutive lo stesso vicino (fra i due disponibili), ad esempio x+1, è relativamente elevata (1/8). Dopo il primo messaggio, x+1 diventa a sua volta diffusore, ma risponderà senza interesse ai messaggi successivi di x, smorzandone la spinta a comunicare.

Di fatto, dopo il terzo messaggio x entra in stato soffocante senza aver trasmesso nulla al nodo x−1. L’unico modo perché x−1 sia raggiunto dal pettegolezzo è che il messaggio arrivi dal nodo x−2, e così via lungo l’anello fino a x+1 (considerando sempre gli indici modulo la dimensione dell’anello).

In questo scenario è necessario aumentare il valore di k per introdurre ridondanza e scongiurare il problema. La propagazione del segnale lungo la rete risulta quindi lenta, procedendo in entrambe le direzioni (a destra e a sinistra del nodo iniziale), con un tempo di diffusione pari a O(n). Qui un esempio con 25 nodi e k = 5.

[embed]

Consideriamo ora il caso di una grafo con una struttura a griglia; un nodo in posizione (x,y) è connesso a 4 vicini posizionati in (x-1,y), (x+1,y), (x, y-1) e (x, y+1). I nodi agli estremi della griglia sono collegati ai nodi all’estremo opposto. Come parametri per la nostra simulazione valorizziamo sempre n = 25 e k = 5. In questo scenario, rispetto al caso precedente, la diffusione è più regolare e meno sensibile rispetto alle cause di possibile non convergenza che abbiamo identificato nel caso dell’anello.

[embed]

Come ultimo caso d’uso, analizziamo una rete Small World, basata sul modello di Watts e Strogatz. Un modello che mi ha affascinato molto, così come i lavori di Barabasi, da studente di informatica nei primi anni 2000. Una rete Small World rappresenta una variante dell’anello, in cui ciascun nodo è collegato a un insieme prefissato di vicini adiacenti. Rispetto alla topologia ad anello, tuttavia, il modello introduce un rimescolamento casuale di alcuni archi, creando vere e proprie scorciatoie che riducono la distanza media tra i nodi.

In questo caso possiamo osservare come, in presenza di una scorciatoia, il processo di diffusione acceleri sensibilmente rispetto al caso ad anello: grazie a quell’arco aggiuntivo, infatti, è possibile raggiungere rapidamente aree del grafo ancora non toccate dal pettegolezzo.

[embed]

Ma come potremmo arricchire ulteriormente questo nostro modello? Gli scenari possono essere molteplici e li affronteremo nel prossimo episodio; includono:

• introdurre nei nodi ignoranti la possibilità di inviare una richiesta periodica di “novità” rispetto a un vicino scelto in modo casuale, così da migliorare la copertura nel caso di grafi poco connessi;
• adaptive fanout: quando un nodo nota che alcuni dei suoi vicini sono in stato soffocante, aumenta il numero di destinatari per ciascun ciclo di propagazione;
• propagazione del rumore da più sorgenti;
• assegnamento di precedenza a specifici nodi (e.g.: comunico la novità prima ai miei amici e solo dopo ai conoscenti) rispetto agli altri;
• messaggi con TTL.

Cercheremo di implementare insieme alcune di queste migliorie, prima di passare ai protocolli Anti-Entropia.

Cosa abbiamo visto in questo articolo:

• gli scenari distribuiti decentralizzati richiedono la definizione di protocolli per la propagazione delle informazioni, al fine di garantire la consistenza eventuale, fra tutti i nodi coinvolti. Tali protocolli possono trarre ispirazione da scenari noti come la diffusione dei pettegolezzi o la propagazione delle epidemie;
• il protocollo di gossip rumor mongering consente di propagare le informazioni con relativa rapidità e affidabilità, a patto di accettare un elevato grado di ridondanza. Tale ridondanza si manifesta, nello specifico, nei messaggi inviati da nodi diffusori a nodi già a conoscenza della novità.

Spero di non averti annoiato; ho cercato di limitare gli aspetti più teorici che sono tuttavia molto interessanti e che ti invito ad approfondire sui materiali citati. Grazie mille per l’attenzione :-D

Vi riporto per completezza anche il codice dell’animazione che utilizza le librerie D3.js generato a quattro mani con ChatGPT. Come sempre in questo genere di operazioni di vibe coding è necessario validare tutto il codice prodotto e spesso correggere (come in questo caso) piccoli errori di generazione sparsi nel codice. Il risultato tuttavia è molto interessante, considerando che si tratta di un lavoro di circa un’ora :-D.

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Rumor Pulse Visualization</title>
<script src="https://d3js.org/d3.v7.min.js"></script>
<style>
  body {
    background: radial-gradient(circle at center, #f0f4f8 0%, #dde3ea 100%);
    font-family: "Segoe UI", sans-serif;
    text-align: center;
  }
  h2 { color: #333; margin-top: 1em; }
  svg { width: 90vw; height: 85vh; margin-top: 1em; }
  circle {
    fill: #4b9fea;
    stroke: #fff;
    stroke-width: 2px;
    cursor: pointer;
  }
  circle.spread {
    fill: #ffb347;
  }
  line {
    stroke: #bbb;
    stroke-width: 1.5px;
    opacity: 0.3;
  }
  line.active {
    stroke: #ffb347;
    opacity: 0.9;
    stroke-width: 3px;
  }
</style>
</head>
<body>
<h2>Rumor Propagation — Pulse Animation</h2>
<svg id="viz"></svg>

<script id="csv-data" type="text/csv">
date_time,sender,receiver,receiver_state
22:29:30.955,,Citizen_0,IGNORANT
22:29:30.973,Citizen_0,Citizen_5,IGNORANT
22:29:30.987,Citizen_5,Citizen_18,IGNORANT
...
</script>

<script>

  const csvText = document.getElementById('csv-data').textContent.trim();
  const data = d3.csvParse(csvText, d => ({
    sender: d.sender,
    receiver: d.receiver,
    time: d.time
  }));

  const nodes = Array.from(new Set([...data.map(d => d.sender), ...data.map(d => d.receiver)]))
    .map(n => ({ id: n, infected: false }));

  const links = data.map(d => ({
    source: d.sender,
    target: d.receiver,
    time: new Date(`1970-01-01T${d.time}Z`).getTime()  // converti ora in timestamp
  }));

  links.sort((a, b) => a.time - b.time);

  const svg = d3.select("#viz");
  const width = svg.node().clientWidth;
  const height = svg.node().clientHeight;

  const simulation = d3.forceSimulation(nodes)
    .force("link", d3.forceLink(links).id(d => d.id).distance(150))
    .force("charge", d3.forceManyBody().strength(-500))
    .force("center", d3.forceCenter(width / 2, height / 2));

  const link = svg.append("g").selectAll("line")
    .data(links)
    .enter().append("line");

  const node = svg.append("g").selectAll("circle")
    .data(nodes)
    .enter().append("circle")
    .attr("r", 12)
    .attr("id", d => d.id);

  const label = svg.append("g").selectAll("text")
    .data(nodes)
    .enter().append("text")
    .text(d => d.id)
    .attr("font-size", "10px")
    .attr("dx", 14)
    .attr("dy", 4);

  simulation.on("tick", () => {
    link.attr("x1", d => d.source.x).attr("y1", d => d.source.y)
        .attr("x2", d => d.target.x).attr("y2", d => d.target.y);
    node.attr("cx", d => d.x).attr("cy", d => d.y);
    label.attr("x", d => d.x).attr("y", d => d.y);
  });

  function pulse(nodeSel) {
    const circle = nodeSel.append("circle")
      .attr("r", 12)
      .attr("fill", "none")
      .attr("stroke", "#ffb347")
      .attr("stroke-width", 3)
      .attr("opacity", 0.8)
      .lower();

    circle.transition()
      .duration(800)
      .attr("r", 40)
      .attr("opacity", 0)
      .remove();
  }

  let i = 0;
  function step() {

    if (i >= links.length) return;

    const d = links[i];

    const senderNode = nodes.find(n => n.id === d.source.id);
    const receiverNode = nodes.find(n => n.id === d.target.id);

    const l = link.filter(lk => lk.source.id === d.source.id && lk.target.id === d.target.id);
    l.classed("active", true);
    l.transition().duration(600).attr("opacity", 0.2).attr("stroke-width", 1.5)
      .on("end", () => l.classed("active", false));

    if (!receiverNode.infected) {
      receiverNode.infected = true;
      const n = node.filter(nd => nd.id === d.target.id);
      n.classed("spread", true);
      pulse(n);
    }

    i++;
    setTimeout(step, 400);
  }

  step();

</script>
</body>