Home

Documentazione

Le funzioni implementate sono:

sampleDistance(g::AbstractGraph, precision::Int64)

La funzione prende come argomento un grafo connesso e un numero intero usato per calcolare la grandezza del sample size. Per testare la funzione si usa un grafo che rappresenta un'instantanea della struttura di Internet a livello di sistemi autonomi, ricostruita dalle tabelle BGP pubblicate dall'Università di Oregon (Link). Formato da:

• Numero nodi 22963
• Numero archi 48436

Per calcolare la distanza esatta lo script Julia impiega 10 minuti

Distanza precisa
3.842426273858345
elapsed time: 599.227492509 seconds

Il valore della distanza è stato calcolato poi su un campione di 10, 1000 e 10000 nodi del grafo, che equivalgono al valore del logaritmo del numero dei vertici moltiplicato con i valori precision 1,100 e 1000. I nodi del campione sono stati presi in modo casuale, ma comunque senza controllare due volte lo stesso nodo.

Già per 10 nodi si può vedere che la distanza è molto simile a quella esatta. C'è un errore dello 0,008% che è molto meglio dell'errore sull'unità che ci si poteva aspettare dato il piccolo valore del campione.

Distanza approssimata con 10 nodi
elapsed time: 0.306798446 seconds
3.809655082309903

L'errore su 1000 nodi diminuisce e arriva allo 0,004%, ma il tempo di computazione sale a 26 secondi.

Distanza approssimata con 1000
elapsed time: 26.268962878 seconds
3.827348605751196

Esaminando quasi la metà dei nodi del grafo si arriva al un errore pari allo 0,001% però il tempo di calcolo è di circa 5 minuti.

Distanza approssimata 10000
elapsed time: 272.883007912 seconds
3.838361537485526

I campioni molto grandi producono risultati più precisi, ma il tempo impiegato rispetto ai campioni piccoli è molto meno conveniente.

iFub(g::AbstractGraph, u::Int64)

La funzione calcola il diametro del grafo, l'argomento u indica il vertice da cui parte l'algoritmo. Utilizzando il diametro di Lightgraphs sul grafo di internet viene restituito questo output:

elapsed time: 273.147031908 seconds
Diameter 11

Il programma impiega quasi 5 minuti per controllare tutti i nodi.

Utilizzando invece l'algoritmo basato sull'analisi delle frange di un visita in ampiezza i risultati sono totalmente diversi. In ogni caso il programma è più veloce dell'algoritmo con ricerca esaustiva, ma la scelta del nodo di partenza nel secondo caso risulta molto importante.

Prendendo come nodo di partenza il nodo più connesso abbiamo il seguente risultato:

1  8724
2  9200
3  14633
4  16852
elapsed time: 0.080959525 seconds
Diameter 11

I primi numeri indicano i nodi esaminati. In questo caso sono stati controllati solo 4 nodi invece che 22963 e la ricerca del diametro si è conclusa in solo 0.08 secondi.

Prendendo il nodo con meno connessioni invece impiega più tempo:

1  16852
2  9200
3  10994
4  11227
5  11291
6  11527
.
.
.
216  21901
217  22007
218  22099
219  22511
220  22583
221  22730
222  22788
223  22797
elapsed time: 2.65926177 seconds
Diameter 11

Il diametro ovviamente rimane invariato, ma il tempo impiegato è di 2.6 secondi e sono stati esaminato 223 nodi.

Cercando la media su un campione di 10 elementi scelti casualmente abbiamo:

1.6610603
5.6646657
1.3717076
32.109867
6.2312164
3.3367977
1.7527943
1.8665112
3.8030324
1.1471504
Tempo Massimo    32.109867
Tempo Minimo 	 1.1471504
Tempo Medio 	 5.89448

Dati questi risultati sembra che almeno empiricamente la scelta del nodo con più connessioni come nodo di partenza sia quella che restituisce il diametro in meno tempo.

triangleCountingDegree(g::AbstractGraph)

La funzione prende come argomento un grafo connesso e conta il numero totale dei triangoli basandosi sul metodo dei gradi (http://theory.stanford.edu/~tim/s14/l/l1.pdf).

Per ogni vertice si controlla i suoi vicini. Se il grado di altri due nodi è più alto del nodo preso in considerazione si controlla anche se c'è un edge che li collega delegando così il conteggio ai vertici con grado più basso.

In una nota dell'articolo di specifica: "Ties between vertices with equal degree are broken in some consistent way, for example alphabetically by the “name” of a vertex.". Per questo motivo si è scelto di rompere i legami dei vertici con grado uguale controllando l'etichetta del vertice e basandosi sull'ordine numerico.

Esempio:

Il nodo che conterà il triangolo formato dai vertici (1,2,3), è 2 perché è il nodo con il grado più basso dei tre.

Per il triangolo formato da (1,4,5) si deve scegliere un vertice tra 4 e 5 (1 viene subito escluso perché ha grado maggiore). Il vertice 4 e il vertice 5 hanno lo stesso grado e quindi la funzione basa il conteggio sull'ordine numerico e sceglie 4.

Tempi di esecuzione:

Per un grafo formato da 22963 nodi e 48436 archi il tempo di esecuzione si dimezza, in quanto per l'algoritmo standard implementato in LightGraphs si raggiungono tempi di circa 0.098 secondi, mentre l'algoritmo implementato nel nostro pacchetto è circa 0.049 secondi.

elapsed time: 0.098321 seconds
elapsed time: 0.049203 seconds

ccSample(g::AbstractGraph, k::Int64, u::Int64)

La funzione prende come argomento un grafo, un intero che indica la grandezza del campione di vertici e il vertice su cui si vuole calcolare la closeness approssimata.

Per valutare la precisione del risultato la funzione è stata calcolata su un grafo creato con il metodo di Barabasi Albert con 10000 nodi. Calcolando l'errore medio assoluto sui valori della closeness approssimata si ha:

• 0.01868158577782819 prendendo un campione con 10 elementi
• 0.005776755979943999 prendendo un campione con 100 elementi

Closeness completa
elapsed time: 79.124125 seconds

Closeness sample = 10
elapsed time: 22.226807 seconds
0.01868158577782819

Closeness sample = 100
elapsed time: 22.041176 seconds
0.005776755979943999

La funzione con un campione di 100 elementi riesce a restituire un valore di closeness molto vicino a quello vero e il tempo impiegato è quasi un quarto.

topKcc(g::AbstractGraph, k::Int64)

La funzione prende come argomento un grafo e restituisce i top k vertici secondo la closeness centrality. La funzione si basa su questo metodo https://arxiv.org/abs/1704.01077.

L'algoritmo fa uso di una Pruned BFS che, ad ogni livello dell'albero di BFS si calcola un bound, se questo bound superiore è minore del valore passatogli in input allora si interrompe in quanto la CC del nodo da cui è partita non potrà avere closeness maggiore. Questo porta ad un efficienza maggiore, in quanto molte BFS vengono interrotte prima della fine, risparmiando così preziose iterazioni.

Ad esempio per trovare il nodo con la closeness più alta su un grafo di 10000 nodi e 497500 archi generato con il metodo di Barabasi Albert sono necessari solamente 162 secondi contro i 185 richiesti dal metodo tradizionale.

{10000, 497500} undirected simple Int64 graph
elapsed time: 162.781562584 seconds
elapsed time: 185.208930054 seconds