Estrazione di sottografi relativi a depositi

Per poter analizzare parti del grafo appena creato occorre estrarre archi e nodi che appartengono al grafo e che ne condividono alcune caratteristiche. Partendo da un nodo deposito cerchiamo di catturare il sottografo ad esso connesso prelevando gli archi uscenti da quel deposito, successivamente preleveremo gli archi uscenti soltanto dai nodi clienti figli e così via, fino a raggiungere la copertura completa del sottografo. Questo metodo ha un grosso punto debole: se i nodi cliente sono tutti connessi tra loro, l'algoritmo descritto li raggiunge tutti. Solitamente, per questo tipo di reti, questo inconveniente può accadere per uno o pochi nodi che fanno da hub tra un sottografo ed un altro. Nel nostro caso gli hub dovrebbero essere i depositi, utilizzeremo comunque una tecnica per evitare questo problema.

Chiamiamo parametro di sbarramento la serie di controlli che, se non superati, porteranno ad un interruzione sulla ricerca di nuovi nodi.

Controllo 1: La percentuale di clienti “nuovi” inseriti sul numero di clienti individuati nell'ultima passata deve maggiore di una certa soglia di sbarramento alfa.

Controllo 2: La percentuale di clienti “nuovi” inseriti sul numero di clienti individuati in totale deve essere maggiore di una certa soglia di sbarramento beta.

Controllo 3: Il trend dei clienti nuovi individuati nell'ultima passata ha un preciso andamento. Tende ad aumentare nella fase di espansione (dai pochi nodi limitrofi al deposito si accede alla maggior parte dei nodi nel sottografo) per poi

diminuire (il sottografo tende a completarsi).

Dopo aver raggiunto un minimo però, il trend tende a risalire, in quanto si raggiunge un nuovo sottografo. Il controllo 3 verifica che non si superi questa soglia.

Passiamo all'illustrazione dell'algoritmo vero e proprio

1. Preleva tutti gli archi uscenti dal deposito di nome nome_deposito ed inseriscili nella tabella archi.

2. Preleva tutti i nodi destinazione dalla tabella archi. Inseriscili in

clienti_new.

3. Crea la tabella clienti copiando il contenuto della tabella clienti_new 4. DO{

1. Crea primary key sulla tabella clienti_new

2. Preleva gli archi uscenti dai nodi presenti in clienti_new, inseriscili in una nuova tabella archi_temp. Accoda i nuovi archi anche alla tabella archi.

3. Preleva tutti i nodi destinazione che corrispondono a clienti da

archi_temp, crea una nuova tabella clienti_temp contenente tutti i

clienti individuati, crea una nuova tabella clienti_new contenente soltanto i clienti nuovi.

4. Calcola l'indice INDICE1 = #clienti_new / #clienti_temp * 100 5. Calcola l'indice INDICE2 = #clienti_new / #clienti_totali * 100 5. }WHILE(parametro di sbarramento)

Come prima prova abbiamo estratto il sottografo relativo al deposito denominato

Goiania. In questo particolare caso, dopo poche iterazioni l'indice1 raggiunge il valore

6.6.1 Sottografo relativo al deposito Goiania

Utilizzando il metodo appena descritto, estraiamo un sottografo relativo al deposito di Goiania.

Il sottografo estratto conta 1234 archi, 161 nodi, di cui un solo deposito (Goiania). Il sottografo è completamente sconnesso dalla parte restante del grafo.

Andiamo a visualizzare i nodi del grafo su M-Atlas, per renderci conto di quali nodi stiamo analizzando.

Carichiamo dunque l'insieme degli archi su Cytoscape16 _{ed eseguiamo un analisi della} rete.

16 Programma utilizzato per il Web Mining, serve per visualizzare ed analizzare grafi e reti sociali.

Grazie all'utilizzo di Cytoscape possiamo modificare la grandezza ed il colore dei nodi in base a caratteristiche individuate in fase di analisi.

Coloriamo in tonalità dal verde al rosso i nodi in base alla betweennes centrality maggiore. Tale proprietà misura il grado di centralità del nodo rispetto al grafo. Nodi con betweenness centrality maggiore hanno la possibilità di raggiungere tutti i nodi in minor tempo rispetto ai nodi con betweenness centrality minore.

Utilizziamo poi una misura maggiore del diametro dei nodi in base al grado dei nodi. Il grado rappresenta il numero di archi uscenti/entranti nel nodo.

Per quanto riguarda gli archi, coloriamo ed evidenziamo con una misura maggiore gli archi con numero di osservazioni maggiori.

Il grafo visualizzato è mostrato in illustrazione 6.2.

Come si osserva, il nodo corrispondente al deposito è di colore rosso acceso, ciò significa che dal deposito è possibile raggiungere i clienti con sforzo minore rispetto a Illustrazione 6.2: Sottografo relativo al deposito di Goiania. Il colore dei nodi rappresenta beetweenness centrality maggiore, la grandezza invece è direttamente proporzionale al numero di archi collegati direttamente al nodo. Il colore e la grandezza degli archi varia in base al numero di osservazioni fin'ora catturate su quella tratta.

quello che si dovrebbe fare se il deposito fosse localizzato in corrispondenza di uno degli altri nodi.

Nodi clienti che sono più centrali rispetto al grafo sono i nodi “Reis & Bernandes

LTDA”, “GAS-TECH INSTALAA ES DE GAS LTDA-ME”, “METALLURGICA UNIVERSO LTDA”, “RARUZ SADORS LTDA” … , nodi che solitamente possiedono

anche un alto numero di collegamenti.

Dalle informazioni relative agli archi, si nota che i collegamenti maggiori sono in corrispondenza di coppie di nodi importanti.

Osservando il colore dei nodi maggiormente collegati e degli archi che li uniscono, appare evidente che la proprietà di betweenness centrality viene riflessa sul numero di osservazioni registrate sugli archi. Maggiore è la centralità del nodo rispetto alla rete e maggiore è il numero di volte che il nodo viene raggiunto.