SVILUPPO DI UNO STRUMENTO PER LA ... - Corrado Monti Monti - SVILUPPO DI UNO... · CAPITOLO 1....

Università degli studi di Milano

FACOLTÀ DI SCIENZE MATEMATICHE, FISICHE E NATURALI

Corso di Laurea in Comunicazione Digitale

SVILUPPO DI UNO STRUMENTO PER

LA VISUALIZZAZIONE INTERATTIVA

DI GRAFI SOCIALI DI GRANDI

DIMENSIONI

Relatore:

Prof. Massimo SANTINI

Correlatore:

Prof. Paolo BOLDI

Presentata da:

Corrado MONTI

Matricola 727133

Anno Accademico 2009-2010

Indice

1 Perché disegnare un grafo sociale? 3

1.1 I gra� sociali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Il World Wide Web . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.3 Design dell'informazione . . . . . . . . . . . . . . . . . . . . . . . 7

2 Librerie e Software 9

2.1 Rappresentare un grafo . . . . . . . . . . . . . . . . . . . . . . . 10

2.1.1 Le strutture dati . . . . . . . . . . . . . . . . . . . . . . . 10

2.1.2 Formati standard . . . . . . . . . . . . . . . . . . . . . . . 12

2.1.3 Il grafo del web . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2 Visualizzare un disegno: Processing . . . . . . . . . . . . . . . . . 20

2.2.1 Il progetto Processing . . . . . . . . . . . . . . . . . . . . 20

2.2.2 L'architettura del software . . . . . . . . . . . . . . . . . . 21

2.2.3 La �loso�a di Processing e l'open source . . . . . . . . . . 22

3 Algoritmi per il disegno di gra� 25

3.1 Il disegno automatico di gra� . . . . . . . . . . . . . . . . . . . . 26

3.1.1 De�nire un'estetica . . . . . . . . . . . . . . . . . . . . . . 26

3.1.2 Gli algoritmi classici . . . . . . . . . . . . . . . . . . . . . 29

3.2 I gra� di grandi dimensioni: il metodo multidimensionale di Harel-

Koren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

3.2.1 Un disegno multidimensionale . . . . . . . . . . . . . . . . 35

3.2.2 Proiezione a due dimensioni . . . . . . . . . . . . . . . . . 36

3.2.3 Motivi di interesse e punti di forza . . . . . . . . . . . . . 37

3.3 Il metodo multiscala di Walshaw . . . . . . . . . . . . . . . . . . 38

1

INDICE 2

3.3.1 Il paradigma multiscala . . . . . . . . . . . . . . . . . . . 39

3.3.2 Costruzione e uso della gerarchia multiscala . . . . . . . . 40

3.3.3 Posizionamento tramite modello �sico . . . . . . . . . . . 43

3.3.4 Aspettative da questo metodo . . . . . . . . . . . . . . . . 49

4 L'applicazione 50

4.1 Architettura dell'applicativo . . . . . . . . . . . . . . . . . . . . . 51

4.2 Layout e algoritmi . . . . . . . . . . . . . . . . . . . . . . . . . . 53

4.2.1 Implementazione e risultati dell'algoritmo di Harel-Koren 55

4.2.2 Implementazione e risultati dell'algoritmo di Walshaw . . 60

5 Conclusioni e futuri sviluppi 70

5.1 Lavoro svolto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

5.2 Risultati ottenuti . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

5.3 Sviluppi futuri . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

Bibliogra�a 76

Capitolo 1

Perché disegnare un grafo

sociale?

3

CAPITOLO 1. PERCHÉ DISEGNARE UN GRAFO SOCIALE? 4

1.1 I gra� sociali

L'uomo è un animale sociale. Rapportarsi con le altre persone è una caratteri-

stica fondante dell'essere umano: se dovessimo raccontare la nostra vita ad un

estraneo, per buona parte del discorso tracceremmo delle relazioni sociali, nella

in�nita varietà in cui la specie umana le ha declinate, dalle amicizie agli stati.

Come causa, mezzo, o conseguenza, queste interazioni sono parte inscindibile di

quasi tutto il nostro agire.

Se non si può parlare quindi della nostra specie senza considerare questa

rete di relazioni, è chiaro come lo studio di queste sia di importanza cardinale

in un vasto numero di campi. Solo recentemente però la matematica, la �lingua

dell'Universo� per Galileo, ha iniziato a cercare le parole per descriverle: il primo

modello formale e valido delle reti sociali è stato formulato in maniera compiuta

negli ultimi anni, ed è noto come �rete ad invarianza di scala�.

Una rete di questo tipo è un particolare genere di quella astrazione matema-

tica chiamata grafo. Un grafo è infatti il modo più ovvio per rappresentare delle

entità connesse fra loro: esso è un insieme di oggetti, chiamati nodi o vertici,

abbinato ad un insieme di archi, ognuno dei quali collega un nodo ad un altro

nodo. Gli archi possono avere una direzione � portare cioè da un nodo di par-

tenza ad uno di arrivo � nel qual caso il grafo e gli archi si diranno orientati; se

invece gli archi non hanno una direzione speci�ca, il grafo si dirà non orientato.

Esistono, oltre a questo, numerosi attributi che un grafo può avere � come essere

connesso, avere una capacità di �usso, permettere circuiti: tutto questo viene

studiato in ciò che si chiama teoria dei gra�.

Nonostante questo strumento teorico sembri già molto e�cace per rappre-

sentare relazioni sociali, è chiaro come il grafo costituito da una rete ferroviaria

sarà profondamente diverso da quello delle relazioni sociali in un gruppo di per-

sone. Quest'ultimo costituisce infatti un grafo sociale: dobbiamo aspettare il

1965 per i primi studi a riguardo. Il primo grafo sociale studiato è stato infatti

la rete delle collaborazioni all'interno della comunità scienti�ca [10]; Derek Pri-

ce, scienziato e storico della scienza, identi�cò infatti in esso una caratteristica

fondamentale di questi gra�: la distribuzione delle connessioni fra i diversi nodi.

Essa infatti non segue una distribuzione normale, come quella di un grafo ca-

suale; in quest'ultimo si riesce ad ottenere una media di connessioni per nodo,


e la quantità di nodi con un numero n di connessioni dipende da quanto n sia

vicino a questa media. Invece, la distribuzione di collaborazioni per scienziato

è ripartita secondo una legge di potenza: la grande maggioranza avrà poche

collaborazioni, una frazione più piccola ne avrà molte di più, una frazione espo-

nenzialmente minore ne avrà un numero esponenzialmente più grande; il che

equivale a dire che esisteranno, in un grafo simile, un piccolo numero di nodi

caratterizzati dall'avere moltissime connessioni.

Per identi�care questa distribuzione come un elemento distintivo dei gra�

sociali, e vedere questa peculiarità sviluppata in un modello matematico, dob-

biamo invece guardare agli studi svolti attorno al 2000 dal prof. Albert-László

Barabási [3, 1]. In essi viene proposta per l'appunto l'idea della rete a invarianza

di scala, una rete caratterizzata appunto dalla distribuzione appena descritta,

in cui pochi nodi � che prendono il nome di hub � sono al centro di un numero

altissimo di archi; in termini matematici, il numero di nodi con k archi è

P (k) ∼ k−γ

L'emergere degli hub viene spiegato con un meccanismo chiamato connessione

preferenziale: le reti di questo tipo tipicamente evolvono nel tempo, e in esse

un nuovo nodo �preferisce� � ovvero, avrà come comportamento più probabile �

connettersi ad un nodo che ha già molte altre connessioni. Poche delle persone

che conosciamo sono eremiti; invece, ognuno di noi ha tra le proprie conoscenze

qualcuno particolarmente popolare, proprio in quanto è più probabile che una

persona con molte connessioni sia connessa anche a noi. Altri studi hanno

confermato come le reti sociali di vari generi � come amicizie, collaborazioni

cinematogra�che, relazioni sessuali (studiate anche al �ne di comprendere il

di�ondersi di patologie come l'AIDS) � tendano a rientrare in questo modello.

Inoltre, è emerso come molte altre variabili di una rete sociale presentino una

distribuzione simile � e vedremo come questo è stato sfruttato da un punto di

vista informatico. Clay Shirky, giornalista e professore di nuovi media nell'Uni-

versità di New York, fa notare ad esempio nel suo libro Here Comes Everybody

[30] come anche il lavoro volontario in una organizzazione sociale autogestita

come Wikipedia sia distribuito con una legge simile: una frazione molto piccola

di persone compie molto lavoro, come scrivere voci complesse su un argomento


speci�co; un numero più grande di persone sarà in grado di e�ettuare modi�che

importanti come aggiungere o migliorare informazioni; e, in�ne, una enorme ba-

se di utenza si occupa di piccole modi�che, come correggere errori di battitura o

di grammatica. Questa distribuzione a legge di potenza è riscontrabile tramite

dati pubblici come il numero e la dimensione delle modi�che e�ettuate da ogni

utente.

1.2 Il World Wide Web

Internet gioca in quest'ambito un ruolo importantissimo. L'analisi di queste

reti, infatti, necessita di dati per poter essere svolta in modo scienti�co: e se

nel 1965 gli unici dati consistenti e disponibili sulle relazioni sociali erano quelli

riguardanti la comunità scienti�ca, oggi Internet � e in particolare il web �

rappresenta una vera miniera di informazioni a riguardo; e proprio queste sono

state la molla scatenante dei lavori sopra citati.

Il web permette infatti di tenere una traccia disponibile e computabile di un

vasto numero di relazioni sociali � pensiamo all'esplosione dei social network,

dove ognuno inserisce in una base di dati l'elenco dei propri contatti. L'aspetto

più interessante è però come anche il web stesso rappresenti una rete sociale:

ogni pagina viene creata (in vari modi) da esseri umani, e sono costoro a scegliere

a quali altre pagine collegarsi � l'ipercollegamento che porta da un blog all'arti-

colo di un giornalista sul sito di un quotidiano è un buon esempio di relazione

sociale (con un verso speci�co). Possiamo quindi vedere l'intero world wide web

come una vasta rete sociale: ogni pagina è un nodo, e ogni collegamento tra

pagine è un arco; questi ultimi avranno una direzione, poiché portano da una

pagina verso un'altra. Ciò che otteniamo prende il nome di grafo del web: esso

rappresenta l'interoWWW, e la sua dimensione è perciò enorme; stime riportate

da Google nel 2008 [2] dicono che esistono mille miliardi di pagine, ognuna con

il proprio indirizzo.

Le indagini compiute su questo enorme grafo sembrano comunque confer-

mare quanto abbiamo detto: il grafo del web ha le caratteristiche proprie di un

grafo sociale [7]. Esso è infatti una rete a invarianza di scala, in cui il numero

di connessioni delle varie pagine � sia in entrata che in uscita � è distribuito


con una legge di potenza; alcune pagine hanno il ruolo di hub e presentano un

numero di connessioni altissimo, mentre la grande maggioranza invece ne ha un

numero esponenzialmente più basso. Dunque, molte delle ricerche valide per i

gra� sociali potrano dirci molto anche sui gra� del web, e viceversa � permet-

tendoci di sfruttare al meglio quella grande quantità di dati che il web mette a

disposizione.

1.3 Design dell'informazione

Ora che abbiamo presentato i suoi principali protagonisti, possiamo introdurre il

soggetto di questo elaborato: la rappresentazione visiva di questa enorme mole

di dati.

Rappresentare i dati può infatti essere molto prezioso, tanto che questo pro-

cesso è oggetto di studi da parte di ciò che viene chiamato information design.

Esso viene de�nito come

L'arte e la scienza di preparare l'informazione in modo che essa

possa venire usata da delle persone in modo e�cace. [22]

È chiaro come una simile disciplina abbia come suo scopo fondamentale, quindi,

la trasformazione di dati in informazione; questa assume un valore ancora più

grande quando i dati in questione sono estremamente voluminosi ed intricati,

come nel caso dei gra� sociali. Qui, la traduzione visiva può fornire un gran-

de aiuto nel rendere la complessità semplice da pensare e da usare. Tradurre

queste strutture matematiche nel linguaggio visivo può far emergere dei pattern

altrimenti trascurati; può aiutare a creare nuove prospettive in chi interpreta i

dati; può insomma aiutare ad orientarsi in questa incredibile rete, trasformando

un grande insieme di numeri in informazione vera e propria.

Ovviamente, bisogna tenere conto che non ci stiamo ponendo un obiettivo

facile: dei dati tanto complessi sono dei pessimi candidati per essere trattati

automaticamente al �ne di diventare un oggetto gra�co interattivo e compren-

sibile; questo sia per le ovvie di�coltà di calcolo, sia per la complessità di

trovarne un'interpretazione gra�ca: la mappa delle relazioni sociali non è come

una mappa di strade � non ha una così ovvia rappresentazione bidimensionale,

e la presenza di hub rende il disegno molto complicato. Ciò nonostante, come


abbiamo detto, sono anche dei dati molto interessanti � oggetto di studi da par-

te di ricercatori di tutto il mondo, nelle aree più disparate � e l'ambizione del

nostro lavoro sarà costruire uno strumento che possa rendere visibili questi dati,

aiutando ad estrarre da essi il loro signi�cato. Tenteremo insomma di osserva-

re dei grossi frammenti di reti sociali � dell'ordine almeno dei milioni di nodi

� fornendone sia una visione di insieme, che permetta di distinguere eventuali

macrostrutture, sia un ingrandimento progressivo e interattivo, per analizzare i

dettagli dei piccoli sottoinsiemi di questo grafo. Se Galileo per studiare il cielo

ha per prima cosa inventato il telescopio, noi tenteremo � nel nostro piccolo �

di imitarlo.

Capitolo 2

Librerie e Software

9

CAPITOLO 2. LIBRERIE E SOFTWARE 10

2.1 Rappresentare un grafo

Il cuore del nostro problema è la traduzione visiva di un grafo: tuttavia, prima

di poter iniziare a lavorarvi, è necessario comprendere in che modo (e con quali

strumenti software) potremo rappresentare all'interno del calcolatore un grafo �

e in particolare un grafo sociale o del web. Infatti, esistono diverse possibilità per

codi�care in memoria questo tipo di dati; per descriverle è necessario introdurre

per prima cosa quali strutture possono riuscire a descrivere completamente un

grafo.

2.1.1 Le strutture dati

Un grafo, ricordiamo, è de�nito come una coppia di insiemi (V,E) dove V è l'in-

sieme dei vertici � le entità che vogliamo connettere � ed E è l'insieme dei lati,

per cui E ⊆ (V ×V ). Per poter descrivere questi due insiemi ad un calcolatore,

dovremo tradurli in una ben precisa sequenza di informazioni, tipicamente nu-

meriche: ad esempio, con una matrice. A questo proposito, esistono due matrici

che possono esprimere completamente il contenuto di un grafo:

• Matrice di adiacenza. Consiste nel rappresentare, tramite una matrice

booleana di dimensioni |V | × |V |, quali coppie di vertici sono collegate da

un lato � ovvero, in altre parole, selezionare quegli elementi e ∈ (V × V )

che appartengono ad E. Questo signi�ca semplicemente che ogni elemento

(i, j) della matrice varrà

di,j =

1 se [i, j] ∈ E

0 altrimenti

Una matrice di questo tipo è particolarmente e�cace nel caso il grafo sia

molto denso (ovvero, se si avvicina ad un grafo completo, in cui tutte le

coppie di vertici sono collegate); in caso contrario, il numero di zeri sarà di

molto maggiore rispetto agli uno, e questo signi�ca una grande quantità

di memoria male utilizzata.

• Matrice di incidenza. È una matrice booleana di dimensioni |V | × |E|

in cui l'elemento l'elemento di,j vale 1 se è il j-esimo lato è incidente nel


vertice i. È evidente come una struttura di questo tipo avrà però soltanto

due valori 1 per ogni colonna: questa matrice è quindi in generale poco

indicata per la memorizzazione e�ciente di un grafo. Va inoltre notato

che, se i gra� sono orientati, in questo caso non sarà più su�ciente una

rappresentazione booleana: ad ogni valore 1 che segnala la presenza di un

arco, andrebbe sostuito un valore −1 oppure +1 a seconda della direzione

dell'arco.

Emerge, comunque, che nel caso di un grafo sparso � ovvero, la stragrande mag-

gioranza delle applicazioni pratiche � una matrice è poco e�ciente. Un modo

naïf di rappresentare un grafo potrebbe essere scrivere una lista di tutti gli ar-

chi, nella forma di coppie di numeri (i, j) che indichino la presenza di un arco che

va dal nodo i al nodo j ; in un tale formato, sarebbe anche necessario indicare il

numero |V | dei nodi, poiché alcuni potrebbero non avere archi collegati. Questa

scrittura è semplice, ed estremamente vicina al modo in cui un essere umano

descriverebbe un grafo in linguaggio naturale, e per questo � come vedremo � è

usata per formati human-readable.

Dal punto di vista di un calcolatore, però, essa è decisamente perfettibile:

suddividere la lista degli archi in |V | liste, ordinate a seconda del nodo di origine,

permetterebbe di �visitarla� più e�cientemente e di evitare la ridondanza del

valore di i in tutti gli archi che partono dal nodo i. Otteniamo quindi una

struttura di questo tipo:

|V | elementi

1 → 2, 4, 5

2 → 4, 1, 9...

Questa rappresentazione prende il nome di lista di adiacenza ed è la stra-

tegia più comune per la codi�ca in memoria di un grafo. Si noti che essa è

particolarmente adatta a rappresentare gra� orientati: nella lista di adiacenza

di un grafo orientato, ogni riga del tipo a → b, c indicherà tutti gli archi che

hanno origine nel nodo a: in questo caso (a, b) e (a, c). Vedremo come questa

struttura sia il fondamento elementare per la descrizione del grafo del web. Ciò

nonostante, rivolgeremo prima di tutto uno sguardo ai formati standard per la


memorizzazione di gra� generici.

2.1.2 Formati standard

Sono nel tempo nati diversi standard per rappresentare i gra� e varie informazio-

ni accessorie: uno degli esempi più signi�cativi e di�usi è GML (Graph Modelling

Language) [21], supportato da un gran numero di applicazioni. Questo consiste

in un �le di testo ASCII, in cui viene descritto ogni nodo ed ogni arco; que-

sti ultimi vengono indicati con la coppia (i, j) degli identi�catori dei nodi che

collegano. Notiamo comunque che ogni nodo ed ogni arco viene esplicitamente

dichiarato e descritto: questo per permettere di associarvi arbitrariamente de-

gli attributi (come nomi, pesi, posizionamento gra�co od ogni altra cosa possa

servire). Questo è un breve esempio:

graph [comment "This i s a sample graph"d i r e c t ed 1l a b e l "Hel lo , I am a graph"node [

id 1l a b e l "Node 1"th i s I sASampleAttr ibute 42

]node [

id 2l a b e l "node 2"th i s I sASampleAttr ibute 43

]node [

id 3l a b e l "node 3"th i s I sASampleAttr ibute 44

]edge [

source 1ta r g e t 3l a b e l "Edge from node 1 to node 2"

]]

Esistono molti formati simili a questo � negli ultimi anni in particolare sono

state proposte diverse codi�che simili basate su XML (eXtensible Markup Lan-

guage), come il Graph eXchange Language (sviluppato, tra gli altri, da IBM,

Bell, Nokia e altri) oppure l'eXtensible Graph Markup and Modeling Langua-

ge, derivazione XML di GML. Tutti condividono con GML molti scopi: essere

contemporaneamente interpretabili sia da una macchina (grazie ad una sintassi

formale ben de�nita) sia da un umano (grazie alla forma testuale, che fa uso di

parole chiave sensate per descrivere i dati); essere estremamente �essibili rispet-

to ai molti attributi che un grafo può avere; prevedere la possibilità di estendere


il linguaggio con nuove caratteristiche. Questi scopi sono dovuti proprio al voler

essere un formato standard, che possa essere utilizzato da qualunque applica-

zione si trovi a lavorare con dei gra�. Purtroppo però, questi vantaggi rendono

questi formati estremamente ine�cienti per delle applicazioni mirate e compu-

tazionalmente costose; e, soprattutto, è impensabile riuscire a gestire gra� di

grande dimensione tramite dei testi che li descrivano. Le sequenze numeriche,

perfettamente traducibili in formati binari, sono le uniche possibili per i nostri

scopi.

2.1.3 Il grafo del web

Anche le liste di adiacenza lasciano però enormi margini di ottimizzazione, di-

versi a seconda del tipo di grafo che è necessario memorizzare. Presso il LAW �

nell'ambito del quale si sviluppa questo elaborato � dell'Università degli Studi di

Milano, è stato realizzato il WebGraph Framework [5], che include un avanzato

formato di memorizzazione compressa per i gra� del web. Un grafo del web,

ricordiamo, è un grafo che ha per vertici delle pagine, e rappresenta tramite

degli archi i collegamenti ipertestuali tra le diverse pagine; notiamo che questi

collegamenti hanno un verso: portano dalla pagina a alla pagina b: perciò, il

grafo che li rappresenta sarà orientato.

Per riassumere brevemente questo studio sui meccanismi di compressio-

ne � base fondamentale per il nostro lavoro � è necessario partire da alcune

caratteristiche proprie di questi gra�, identi�cate dagli autori di WebGraph.

1. Localizzazione. Molti dei link di una pagina web puntano ad altri docu-

menti dello stesso sito: essi servono alla navigazione fra i diversi contenuti.

L'URL di queste pagine perciò avrà il medesimo pre�sso: il dominio del

sito e in generale il percorso comune fra la pagina in questione e quella

collegata. Poiché disponendo le pagine in ordine lessicogra�co i nodi che

condividono l'inizio dell'URL vengono associati ad interi vicini, è probabi-

le che molti dei nodi fra loro adiacenti siano identi�cati da numeri prossimi

fra loro.

2. Somiglianza. Pagine simili condividono molti link. Questa somiglianza

si rivela peraltro essere molto più concentrata di quanto si pensasse: le


liste di adiacenza di due nodi del grafo del web o non hanno quasi nulla

in comune, oppure sono per buona parte identiche; inoltre, essa si rivela

essere tanto più probabile quanto più l'indirizzo delle pagine è simile.

3. Consecutività. Prendendo in esame una singola pagina, è assai fre-

quente che gli URL dei suoi collegamenti siano consecutivi in ordine les-

sicogra�co. Questa è una diretta conseguenza della struttura gerarchica

dei siti web: un URL successivo ad un altro (come per esempio http:

//www.ccdinf.unimi.it/it/corsiDiStudio/2011/F1X/ e http://www.

ccdinf.unimi.it/it/corsiDiStudio/2011/F2X/) è di solito al suo stes-

so livello nella gerarchia, e quando una pagina riporta un link ad uno di

questi due indirizzi, è comune che riporti anche l'altro (ed i successivi).

4. Consecutività trasposta. Questo vale in modo per�no più radica-

to nel trasposto del grafo del web1: una pagina che si trova ad un li-

vello più alto della gerarchia (come http://www.ccdinf.unimi.it/it/

corsiDiStudio/) sarà probabilmente puntata da tutte le pagine dei livel-

li più in basso (come le due sopra): perciò, anche nella lista di adiacenza

del grafo trasposto troveremo molti nodi consecutivi l'uno all'altro (sempre

in ordine lessicogra�co).

5. Dualità. Da quanto detto sopra, si deduce che la somiglianza tra pagine

consecutive è il duale della consecutività dei collegamenti di una pagina.

Per capire questo concetto, può aiutare osservare nella tabella 2.1 cosa

accade trasponendo le liste di adiacenza. Ricordiamo infatti che, se nel

grafo di partenza la forma A→ B,C indica che la pagina A ha un link alle

pagine B e C, nel grafo trasposto la stessa forma indicherà che la pagina

A è collegata dalle pagine B e C; notiamo quindi che la somiglianza nelle

liste di sinistra diviene, trasponendo il grafo, consecutività nelle liste di

destra; al contrario, se il grafo di partenza è quello di destra, avviene il

fenomeno inverso.1Nel trasposto del grafo del web, gli archi sono girati nel senso opposto: un link dalla

pagina a alla pagina b diverrà un arco che parte dal nodo b e arriva al nodo a.


Tabella 2.1: Liste di adiacenza in un frammento di grafo del web e nel suotrasposto

1→ 26, 34, 452→ 26, 34, 45

↔26→ 1, 234→ 1, 245→ 1, 2

2.1.3.1 Il formato WebGraph

Da queste osservazioni, gli autori del framework hanno realizzato un'e�ciente

codi�ca per la memorizzazione del grafo del web. Essa ha per base delle liste

di adiacenza con numeri naturali; ogni pagina viene infatti indicizzata, come

detto sopra, in ordine lessicogra�co, ed è quindi questo ordine a determinare il

numero di un nodo.

La lista di adiacenza di ogni nodo viene suddivisa in tre parti fondamentali:

la prima, chiamata reference list (�lista di riferimenti�) sfrutterà la somiglianza

dei collegamenti tra diverse pagine; la seconda, detta interval list (�lista di

intervalli�) appro�tterà della consecutività dei collegamenti del singolo nodo;

in�ne, esisterà una terza parte, i residuals (�residui�), che dovrà necessariamente

codi�care i collegamenti non espressi nelle due parti precedenti.

È importante notare come questa suddivisione produca ottimi risultati sia

per il grafo del web sia per la sua trasposta. Questo proprio per i principi elen-

cati sopra, ed in particolare per la dualità: quando un grafo avrà una prima

parte compressa molto e�cacemente (grazie ad una buona similiarità), il suo

trasposto avrà spesso un'alta compressione nella seconda parte, e viceversa. Gli

autori evidenziano come WebGraph si comporti addirittura meglio con il gra-

fo trasposto; questo avviene probabilmente per una asimmetria dovuta al web

stesso: se infatti nel grafo del web originale ad essere elencati sono i link in una

pagina, nel trasposto sono tutti i collegamenti che puntano verso una determi-

nata pagina. Perciò, poiché il numero di link in una pagina è limitato dalla

capacità umana di leggere tutti quei collegamenti, il secondo insieme può essere

molto più ampio, consentendo quindi una compressione ancora più e�cace.

Vediamo ora un poco più in dettaglio in che modo WebGraph utilizza le

caratteristiche del grafo del web per realizzare una codi�ca ottimale, analizzando

le tre parti � elencate prima � in cui viene divisa la lista di adiacenza di un nodo.


Reference list. La reference list fa uso del fenomeno � discusso sopra � per

cui è molto probabile che, fra le pagine immediatamente precedenti a quella in

esame, ve ne sia almeno una che condivide con essa un gran numero di collega-

menti. Per trarne vantaggio, codi�cando un nodo x, l'idea è di scegliere un altro

nodo (x − r) tra i W nodi precedenti a quello dato (dove W è un parametro

arbitrario della compressione), per indicare quali tra i suoi collegamenti vanno

ripetuti anche per il nodo in esame2; per codi�care questa selezione, possiamo

inizialmente pensare ad inserire un bit per ogni collegamento del nodo di rife-

rimento, scrivendo 1 se il collegamento viene ripetuto o 0 se non lo è (questa

sequenza di bit prende il nome di copy list). Indicheremo inoltre il nodo (x− r)

indicando semplicemente il parametro r, ovvero la distanza lessicogra�ca che lo

separa dal nodo in esame; se r vale 0, la reference list sarà vuota (non esiste

alcun nodo di riferimento). Ad esempio:

Tabella 2.2: Reference list : un primo esempio.Nodo Collegamenti (in neretto quelli comuni)

15→ 13, 15, 16, 17, 18, 19, 23, 24, 203, 315, 103416→ 15, 16, 17, 22, 23, 24, 315, 316, 317, 3041

↓Nodo r Copy list Altri collegamenti

15 0 - 13, 15, 16, 17, 18, 19, 23, 24, 203, 315, 103416 1 01110011010 22, 316, 317, 3041

Poiché, come abbiamo detto, la somiglianza è un fenomeno largamente dif-

fuso e molto concentrato, è conveniente applicare anche una compressione dif-

ferenziale alla copy list: ovvero codi�carla come sequenze di 1 e di 0 alternate.

Anziché scrivere 01110011010, scriveremo che il gruppo di uno iniziale è lungo

0, poi c'è una sequenza di zeri lunga 1, poi c'è una sequenza di uno lunga 3 e

così via. In pratica scriveremo il numero di questi blocchi e la loro lunghezza;

come nell'esempio appena espresso, possiamo ipotizzare che il primo blocco sia

un blocco di uno (eventualmente di lunghezza nulla) e che poi troviamo alternati

blocchi di zeri e blocchi di uno; ogni lunghezza, a parte la prima che può essere

2Questo meccanismo può generare però delle lunghe catene di riferimenti: il nodo x po-trebbe riferirsi al nodo y, ma questo potrebbe riferirsi al nodo z e così via. Per evitare chequesto allunghi di molto i tempi di accesso all'informazione, WebGraph mette a disposizioneun parametro R che limiti la lunghezza di questa catena di riferimenti. Ponendo ad esempioR = 1 un nodo può far riferimento solo ad un arco direttamente citato in un altro nodo,avremo una compressione minore e un accesso più rapido; al contrario, con R = ∞ avremouna compressione massima e un accesso più lento.


0, verrà scritta diminuendola di uno, in modo da usare al meglio ogni numero

naturale incluso lo zero (che indicherà quindi una sequenza di lunghezza 1);

inoltre, la lunghezza dell'ultimo blocco può essere omessa: viene desunta dalla

lunghezza delle altre e dal numero di blocchi. Seguendo l'esempio sopra, la copy

list diverrà la seguente lista di copy blocks:

Tabella 2.3: Reference list de�nitivaNodo r Numero di blocchi Lunghezze dei blocchi Altri collegamenti

15 0 - - 13, 15, 16, 17, 18, 19, 23, 24, 203, 315, 1034

16 1 7 0, 0, 2, 1, 1, 0 22, 316, 317, 3041

Questo esempio presenta una somiglianza minore a quella spesso riscontrata

nella realtà; facciamo quindi notare che una compressione di�erenziale della

copy list, unita alla codi�ca di numeri interi che verrà usata, può esprimere una

lunga sequenza di collegamenti comuni in pochissimi bit, sfruttando al meglio il

fenomeno della somiglianza.

Lista degli intervalli. La lista degli intervalli codi�ca una parte dei colle-

gamenti non riportati dal nodo di riferimento (quelli nella colonna �altri colle-

gamenti � nelle tabelle 2.2 e 2.3). In particolare, descrive tutti i collegamenti

rimasti che sono espressione della consecutività. Per avvantaggiarsi di questo

fenomeno, i collegamenti non vengono indicati uno per uno, ma vengono espres-

si come intervalli di nodi; se quindi una pagina contiene dei collegamenti alle

pagine indicizzate lessicogra�camente con i numeri 15, 16, 17, 18, 19 � evento

che come abbiamo detto accade spesso nel grafo del web � la lista degli inter-

valli riporterà il punto di inizio (15) e la lunghezza dell'intervallo (5). Questo

avverrà per ogni sequenza che contenga più di Imin nodi, dove Imin è un para-

metro arbitrario. Inoltre, alcuni accorgimenti riducono ulteriormente lo spazio

usato: il punto di inizio viene codi�cato come spostamento rispetto al punto

di �ne dell'intervallo precedente (meno 2, poiché i due intervalli devono essere

separati); la lunghezza l invece viene scritta come di�erenza (l − Imin).

Residui. I nodi rimasti dopo la reference list e la lista degli intervalli pren-

dono il nome di residui; per le caratteristiche elencate prima, questi nodi non

dovrebbero essere troppo numerosi. In ogni caso, essi verrano rappresentati av-


vantaggiandosi della localizzazione descritta sopra: poiché è probabile che un

nodo y collegato da una pagina x gli sia lessicogra�camente vicino, verrà scritta

la di�erenza tra x e y.

Il �le del grafo ( salvato come *.graph) sarà quindi composto dalla serie

di queste sequenze di numeri, una per nodo; ad ognuna viene preposto il grado

in uscita3 del nodo in questione, poiché quando vale zero non sono necessari

altri dati. Queste sequenze numeriche vengono codi�cate in binario da una

diversa parte del framework WebGraph: i codici ζ, un formato di compressione

particolarmente adatto al grafo del web [6].

Come abbiamo già accennato, infatti, molti valori propri di un grafo del

web, e più in generale � e questo è per noi di grande importanza � di un grafo

sociale, sono distribuiti secondo una legge di potenza: questa distribuzione viene

sfruttata dai codici ζ. In particolare, essi riescono a codi�care in modo ottimale

le distanze tra l'indice di un nodo e quello del suo successore (poiché è con

queste che vengono indicati i residuals, ad esempio); è stato infatti dimostrato

che anche queste distanze sono ripartite secondo una distribuzione a legge di

potenza.

L'uso di codici di compressione ha però un difetto: l'accesso casuale ad

un nodo diviene impossibile, poiché per interpretare un bit bisogna ricostruire

la sequenza dall'inizio, in modo da capire a quale nodo ed a quale parametro

esso corrisponde. Il problema viene risolto salvando a �anco del grafo un altro

archivio con estensione *.offsets, che contiene una �mappa� dei punti della

sequenza in cui iniziano i dati relativi ad un certo nodo. Quando si inizia a

leggere un certo grafo e si richiede un accesso casuale, questa mappa può essere

caricata interamente in memoria � consentendo un accesso molto rapido � oppure

si può memorizzare in RAM solo un punto ogni J, rendendo l'accesso più lento

(proporzionalmente al valore di J ).

In�ne, oltre a questi due �le, ne esiste un terzo, chiamato *.properties. Il

suo scopo è salvare vari metadati del grafo, come ad esempio varie statistiche

sulla compressione, i parametri con cui è stato generato, o la classe Java che lo

ha prodotto. Questa ultima informazione consente tra le altre cose di estendere

3Il grado in uscita di un nodo è il numero di archi uscenti da esso.


il formato, implementando una diversa classe di salvataggio più o meno legata

a questo formato e facendo in modo che essa venga riconosciuta.

2.1.3.2 Il framework di WebGraph

Abbiamo visto come WebGraph salverà su disco il nostro grafo. Questa è tut-

tavia solo una parte del framework di WebGraph. Esso infatti si compone

di:

1. I codici ζ, accenati sopra, che consentono la compressione di vari dati, tra

cui le distanze del grafo del web.

2. Gli algoritmi per leggere e scrivere la codi�ca �n qui esposta.

3. Una valida, completa, e ben documentata implementazione in Java di

tutto questo, nonché di varie altre funzionalità per operare con i gra�.

4. Un insieme di dataset relativi ad estesi gra� del web e reti sociali, raccolti

tramite UbiCrawler [27] o generati da dati pubblici.

Queste diverse componenti rendono WebGraph un ottimo fondamento per que-

sto lavoro; esso rende enormi moli di dati, già raccolti ed ottimizzati, disponibili

tramite metodi Java avanzati ma di uso immediato.

2.1.3.3 Altre librerie

Oltre al framework di WebGraph, il LAWmette a disposizione varie altre librerie

Java particolarmente utili per i nostri scopi; esse sono alla base di WebGraph,

e si rivelano molto utili quando si ha a che fare con grandi quantità di dati.

Queste funzionalità sono raggruppate in tre pacchetti software:

• MG4J (Managing Gigabytes for Java), permette di trattare grandi do-

cumenti e di manipolare �le di testo di dimensioni elevate.

• DSI utilities, una libreria contenente un insieme molto vario di metodi e

classi. Contiene il necessario per gestire concretamente un input/output a

livello di bit (ma non solo), ed anche per utilizzare i codici di compressione.

• fastutil, mette a disposizione metodi rapidi ed e�caci per gestire strutture

dati di vario tipo.


Tutti questi software sono ottimamente documentati; sono inoltre rilasciati con

licenza GPL (GNU General Public License), di cui parleremo oltre. Citia-

mo quindi anche le librerie esterne utilizzate in questi software del LAW, in

particolare due di cui ci avvarremo durante lo sviluppo del nostro strumento:

• Log4J, uno strumento sviluppato da Apache per e�ettuare il logging di

una applicazione in modo ottimale.

• Colt, un progetto legato al CERN che ha sviluppato dei metodi per gestire

operazioni matematiche e scienti�che e�cientemente, e se lo si desidera

ad alto livello.

Anche queste librerie sono tutte scritte in Java, ben documentate, pubblicamen-

te disponibili e dotate di una licenza libera.

2.2 Visualizzare un disegno: Processing

Ora che è stato chiarito in che modo possiamo avere i dati di input per il nostro

problema, e con quali librerie potremo interfacciarci con questi dati, esporremo

in che modo il nostro output � il disegno del grafo sociale � giungerà sullo

schermo. Infatti, per fare questo non useremo le librerie standard di Java, bensì

si farà uso di Processing.

2.2.1 Il progetto Processing

Processing [29, 9] viene presentato come un framework costituito da un pro-

prio linguaggio di programmazione, un ambiente di sviluppo ed una comunità

online. Questo complesso progetto è nato nel 2001 con lo scopo di promuove-

re l'alfabetizzazione informatica (software literacy) all'interno delle arti visive;

per questo motivo, esso si è inizialmente presentato � raggiungendo un succes-

so notevole � come un modo per permettere a chiunque di ideare e realizzare

dei piccoli progetti artistici (sketch) utilizzando appieno le possibilità o�erte

da un moderno calcolatore, insegnando quindi al contempo con la pratica cosa

signi�chi programmare. Sviluppato inizialmente presso il Media Lab del MIT

e continuazione del progetto Design By Numbers, il suo uso si è rapidamente

di�uso in molte scuole di alto livello, interessate alla frontiera informatica delle


arti visive. Gli autori riportano come molti studenti di arte del tutto digiuni di

programmazione abbiano acquisito grazie a Processing la capacità di realizzare

progetti e�caci e stimolanti; tuttavia, uno dei principi base è stato quello di

mantenere una complessità scalabile: ovvero, anche se utenti inesperti devono

essere in grado di scrivere software in pochi minuti, le potenzialità per gli utenti

più esperti devono essere comunque le massime possibili. Questo ha permesso a

Processing di allargare il suo bacino di utenza, trasformandosi in uno strumento

professionale per realizzare progetti da cima a fondo.

2.2.2 L'architettura del software

Rispettare questa missione è stato possibile grazie al software di ottima qualità

prodotto dal progetto. Infatti, pur venendo presentato come un linguaggio a sé,

ogni listato Processing viene tradotto in puro codice Java; il cuore del pacchetto

� la libreria core � consiste infatti in un insieme di classi e metodi che estendono

le capacità standard di Java: ogni elemento del linguaggio non è altro che un

rimando più o meno esplicito a questi metodi Java creati nella libreria core [28].

Ad esempio, il punto di partenza di uno sketch di Processing è la sua area di

disegno, su cui ogni comando andrà ad operare; questa altro non è che un oggetto

PApplet, de�nito nel core come estensione dell'oggetto Applet incluso in Java.

Per operare su questa area di disegno è necessario, in Processing, de�nire due

funzioni: setup() � che verrà invocata solo all'inizio � e draw() � richiamata ad

ogni frame; al loro interno possono venire usati tutti i comandi del linguaggio

(ad esempio frame() per de�nire la velocità di aggiornamento, oppure line()

per disegnare una linea). È chiaro come, dal punto di vista di Java, non stiamo

facendo altro che creare una estensione della classe PApplet che ride�nisca i

metodi setup() e draw(), potendo così fare uso al proprio interno dei metodi

che un oggetto PApplet mette a disposizione; tuttavia, questo rimane del tutto

trasparente per l'utente Processing.

Si costituisce quindi un linguaggio quasi identico a Java, ma con in più la

possibilità di poter evitare alcune espressioni o concetti avanzati, i quali ver-

ranno poi eventualmente completati o aggiunti nella fase automatica di tradu-

zione in Java puro. Questa architettura ha vari vantaggi: come è stato detto,

essa permette di realizzare comportamenti anche molto complessi e ottimizza-


ti mantenendo però una assoluta trasparenza agli occhi dell'utente normale;

è facile intuire come, per esempio, l'oggetto PApplet dovrà richiamare anche

concorrentemente i metodi de�niti � magari per gestire l'interattività � dal pro-

grammatore Processing, ed è quindi necessaria una implementazione thread-

safe: il metodo principale dell'oggetto PApplet dovrà richiamare ad ogni frame

il metodo draw(), e contemporaneamente gestire i metodi mouseReleased(),

keyPressed() eccetera. Questa parte rimane però del tutto invisibile per il

programmatore che si rivolge all'ambiente di sviluppo di Processing, che ha

semplicemente de�nito cosa fare nei metodi sopraelencati. La complessità di

Processing è molto alta, ma si è del tutto liberi di scegliere �no a che punto si

è in grado di gestirla.

Una implementazione di questo tipo ha anche un altro vantaggio, di enorme

importanza per il nostro progetto: permette, qualora lo si voglia, di evitare

di usare Processing come linguaggio a sé stante, usando invece le librerie che

lo costituiscono direttamente all'interno di un normale progetto Java. In altre

parole, anziché scrivere del codice Processing all'interno del suo ambiente di

sviluppo e poi lasciare che esso venga tradotto in Java puro che richiami le

librerie di Processing, si può scrivere direttamente quest'ultimo � all'interno del

proprio ambiente preferito e integrandolo come meglio si crede con altre parti di

codice. Così facendo, è come se stessimo rimuovendo dal framework gli strati più

ad alto livello, lasciandoci liberi di usare tutte le librerie interne di Processing,

sfruttandone la migliore qualità � per semplicità e per prestazioni � rispetto alle

librerie gra�che che Java mette normalmente a disposizione (come ad esempio

Swing).

2.2.3 La �loso�a di Processing e l'open source

Come detto, favorire l'alfabetizzazione informatica è stata, dicono i fondatori, la

motivazione iniziale per lo sviluppo di Processing. Per spiegarsi, citano queste

parole di Alan Kay [24]:

La facoltà di �leggere� un medium signi�ca poter accedere a stru-

menti e materiali creati da altri. La facoltà di �scrivere� su un me-

dium signi�ca poter generare strumenti e materiali per gli altri. Per

non essere analfabeta, ma letterato, bisogna possederle entrambe.


Nella scrittura per la stampa, gli strumenti che si generano sono

retorici: possono dimostrare e convincere. Nella scrittura per il cal-

colatore, gli strumenti che si generano sono processi; essi simulano e

prendono decisioni.

La possibilità di poter comprendere questi processi signi�ca poter interagire

attivamente con il software di ogni genere; nel caso di Processing, questa alfa-

betizzazione, oltre ad essere buona cosa in sé, mira a costruire una comunità di

utenti in cui ognuno sia capace di apprezzare il lavoro degli altri, comprender-

ne la realizzazione, e modi�carla, migliorarla, o usarne delle parti per costruire

qualcosa di nuovo. Per questo motivo la comunità online di questo software

è così curata ed incoraggiata: gli autori citano il caso dell HTML, in cui la

possibilità di osservare il codice sorgente delle pagine ha aiutato a di�ondere ra-

pidamente e capillarmente questo linguaggio. Allo stesso modo, di default ogni

progetto di Processing includerà il suo codice sorgente, persino se esportato in

una pagina web. Se ognuno può imparare dagli altri, ed è messo nelle condizioni

di farlo, è chiaro come l'intera comunità ne bene�ci, in termini di qualità dei

progetti creati e di conoscenze acquisite.

Queste idee non sono certamente state generate isolatamente dagli autori di

Processing: sono le idee promosse dal movimento open source. Per maggiori

informazioni si può iniziare a navigare presso il sito della Free Software Foun-

dation http://www.fsf.org/. Anche Processing stesso è stato sviluppato in

questo modo: il codice che vi sta dietro è pubblicamente disponibile, e si invita

chiunque voglia a modi�carlo e migliorarlo.

Facciamo notare in�ne come tutte le librerie utilizzate nel nostro lavoro, non-

ché l'applicativo risultante, sono software libero e con sorgente aperto. Questo

appunto per favorire quel processo di miglioramento collettivo grazie al quale

qualcuno, se interessato e motivato, potrà immediatamente, senza dover chie-

dere alcunché, porre rimedio ad alcune lacune di questo progetto � sicuramente

perfettibile. Questo è di sicuro vantaggio in un ambiente come il nostro, dove

la maggioranza degli utenti � se ce ne saranno � del nostro piccolo software

saranno persone in grado di modi�carlo; ma è importante osservare la lezione di

Processing, per capire che l'open source non solo migliora il software prodotto in

una comunità informaticamente preparata, ma può persino �alfabetizzare� a sua


volta, semplicemente lasciando liberi gli utenti di gettare uno sguardo dentro gli

ingranaggi.

Capitolo 3

Algoritmi per il disegno di

gra�

25

CAPITOLO 3. ALGORITMI PER IL DISEGNO DI GRAFI 26

3.1 Il disegno automatico di gra�

È evidente come un grafo G, de�nito come una coppia di insiemi (V,E), abbia

una sua naturale rappresentazione nel disegno di simboli, solitamente dei piccoli

cerchi, collegati da linee; tuttavia, un grafo non contiene di per sé alcuna infor-

mazione sul posizionamento nello spazio di questi simboli, né sul percorso che le

linee dovrebbero seguire per andare da un simbolo all'altro: contrariamente ad

una funzione y = f(x), che ha una rappresentazione convenzionale in un piano

ben precisa, a partire da un grafo G ogni suo possibile disegno è formalmente

una scelta valida; tuttavia, la capacità del disegno di comunicare le informazioni

contenute nel grafo dipende strettamente da questa scelta.

Se le possibilità sul disegno di un arco e ∈ E sono abbastanza limitate (in

molti casi ci si limita a dei segmenti che uniscono i vertici), ad assumere un

ruolo fondamentale è la disposizione dei nodi nel piano. Possiamo formalizzare

questa �scelta� di layout con una funzione di questo tipo:

LG : V → R2

Questa funzione esplicita in maniera chiara cosa chiederemo qui ad un al-

goritmo di disegno di gra�: che, dato un grafo G, fornisca questa funzione LG

capace di associare ad ogni nodo del grafo una posizione in uno spazio bidi-

mensionale (nel nostro caso, quello di uno schermo). Come è già stato detto,

i lati nei gra� da noi trattati sono dell'ordine di almeno 106 o 107; è pertanto

impensabile computare qualcosa di diverso da segmenti. Per questo motivo, an-

che le linee che rappresentano gli archi sono completamente determinate dalla

nostra funzione L: essa abbinerà ad ogni elemento di E una coppia di punti che

de�niscono per l'appunto un segmento.

3.1.1 De�nire un'estetica

Abbiamo a�ermato che la scelta della funzione di layout avrà un impatto deter-

minante sull'utilità del disegno come veicolo di informazioni; possiamo quindi

distinguere delle funzioni migliori e delle funzioni peggiori. Ciò nonostante, è

importante notare come questa distinzione vari in base al particolare tipo di

informazioni che vogliamo risaltino: essa dipende quindi, in ultima analisi, dal


signi�cato stesso del grafo in questione. Si pensi ad esempio al grafo di un cubo

(�g. 3.1). Se quello che vogliamo rappresentare sono i vertici del solido, oppure

se vogliamo sottolineare l'analogia tra essi ed un certo grafo, il disegno a destra

sarebbe senza dubbio il migliore; se però stiamo visualizzando � ad esempio �

l'architettura di una rete di calcolatori, questo non sarebbe più vero.

Figura 3.1: Grafo di un cubo

Possiamo inoltre a�ermare che, poiché la semantica della comunicazione de-

ve essere chiara a chi ne fruisce, anche il background culturale del ricevente è

importante per la buona riuscita della trasmissione di informazioni da chi dise-

gna il grafo a chi lo dovrà leggere. Un valido esempio è il grafo di una molecola

di propano [26]: è chiaro come chiunque sia a conoscenza della disposizione

reale degli atomi giudicherà migliore il disegno in �g. 3.2c, nonostante un di-

segno apparentemente più ordinato potrebbe essere quello rappresentato nella

�g. 3.2a.

Figura 3.2: Grafo di una molecola di propano

Nonostante tutto ciò, però, se il grafo da visualizzare non ha un signi�cato

così vincolante sul piano gra�co, sono generalmente accettate [4] alcune carat-


teristiche estetiche generiche � de�nibili anche formalmente � che il suo disegno

dovrebbe avere. Esse possono essere viste come gli scopi fondamentali che in

generale un algoritmo valido dovrebbe pre�ggersi, poiché un disegno che possie-

da queste proprietà è di solito facilmente leggibile ed al contempo esteticamente

piacevole. Vediamone le principali.

Simmetria. La simmetria di un disegno è già di per sé esteticamente appa-

gante; nel nostro caso, la simmetria � o anche solo una parziale

simmetria � nel disegno di un grafo permette di rendere visibili una

vasta gamma di informazioni a riguardo della struttura che tentiamo

di visualizzare: parallelismi tra nodi distinti, similarità tra gruppi

di nodi, ripetizione di pattern nella struttura e così via.

Intersezioni. Perché ogni arco rimanga chiaramente visibile è essenziale che le

linee si intersechino il meno possibile; un minor numero di interse-

zioni porta ad un disegno più ordinato, meno caotico e in de�nitiva

sempli�ca la lettura del grafo.

Risoluzione angolare. Perché i lati rimangano chiaramente visibili non è solo

importante che non si intereschino, ma anche che, nei vertici in cui

hanno origine, siano separati da un angolo notevole: questo è par-

ticolarmente importante dal momento che il disegno sullo schermo

del computer diviene (con quel processo noto come rasterizzazione)

una matrice di pixel.

Distribuzione. È un fattore importante anche che i nodi siano distribuiti nel-

l'area disponibile in modo equo: nell'area del piano che contiene il

disegno, non dovrebbero esserci né zone vuote, né sezioni troppo

ricche di vertici.

Lunghezza dei lati. Un buon disegno presenta uniformità anche tra le lun-

ghezze dei diversi archi: una grande disparità � alcuni archi molto

più lunghi di altri � è percepita come esteticamente sgradevole e

di�cilmente leggibile.

Un disegno che rispetti queste proprietà sarebbe capace di far passare, a colpo

d'occhio, una grossa quantità d'informazioni importanti racchiuse nella struttura


del grafo, risultando inoltre gra�camente più piacevole. Tuttavia, progettare un

algoritmo che, semplicemente, massimizzi queste proprietà è reso nella pratica

impossibile. Questo perché molti dei problemi di ottimizzazione di anche uno

solo di questi valori sono NP-di�cili: ad esempio è un problema NP-completo il

minimizzare le intersezioni dei lati, come lo è determinare se un grafo generico

possa essere disegnato simmetricamente (si vedano rispettivamente i lavori di

Michael R. Garey e David S. Johnson [11] e di Joseph Manning [25]). Come se

non bastasse, questi problemi computazionali sono ancora più ardui nel nostro

caso: gra� con carattere di generalità e di grande dimensione.

Se è impossibile quindi progettare un algoritmo in questo modo, l'unica

strada percorribile è trovare delle euristiche che permettano di avvicinarsi � per

quanto possibile � ad un buon disegno, pur senza ricercarlo esplicitamente.

3.1.2 Gli algoritmi classici

Tra gli approcci al disegno automatico di gra�, possiamo distinguere tra algorit-

mi speci�ci per taluni tipi di grafo e algoritmi generali, che tentano di disegnare

ottimalmente un grafo generico.

Per quanto riguarda i primi, tipicamente i risultati migliori si sono avuti

per gli alberi e per i gra� planari (ovvero, che possono essere disposti su di un

piano evitando ogni intersezione tra archi). Gli algoritmi per la visualizzazione

di alberi sono molto numerosi, grazie alla grande semplicità e di�usione dei gra�

di questo tipo; quasi tutte questi metodi si basano prima di tutto sull'identi�-

cazione del nodo radice, e quindi dei vari livelli del grafo � ovvero i sottoinsiemi

di nodi Lk ⊂ V caratterizzati da una certa distanza k dalla radice. Un tipico

algoritmo di disegno è la disposizione gerarchica: essa consiste nel posizionare

il nodo radice in alto ed in centro, per poi collocare ogni livello su di una retta

orizzontale, tanto più in basso quanto più è lontano dalla radice; all'interno del-

lo stesso livello, i nodi verranno a�ancati in modo che ognuno sia il più vicino

possibile al proprio padre. Un'altra alternativa comune per il disegno di alberi

è la disposizione radiale (radial layout, in inglese). Questa è una diretta de-

rivazione dell'algoritmo precedente, poiché basta sostituire nel posizionamento

le coordinate cartesiane con quelle polari; in altre parole, i livelli non verranno

disposti su di una serie di rette parallele, ma su delle circonferenza concentri-


che di raggio proporzionale alla distanza del livello dal nodo radice, che verrà

posizionato quindi al centro.

L'utilità di questi algoritmi non si esaurisce però nel disegno di alberi pro-

priamente detti. Queste tecniche, infatti, sono applicabili anche per visualizzare

e�cacemente l'albero di copertura di un grafo generico, oppure per vederne un

albero derivato da una ricerca in ampiezza o in profondità a partire da un dato

nodo. Ad esempio, per visualizzare il percorso compiuto da un crawler in una

rete si potrebbe usare un layout radiale, nonostante la rete, di per sé, non sia

a�atto un albero.

Anche per quanto riguarda i gra� planari esiste un'ampia scelta di algoritmi

di disegno: tuttavia, la loro applicazione per i gra� generici da noi trattati è quasi

nulla � sebbene in passato siano stati compiuti numerosi tentativi a riguardo.

La planarizzazione di un grafo è infatti un problema ampiamente trattato in

letteratura [4]. Tra le soluzioni tentate, sono di particolare rilievo la minimal

edge deletion (cancellazione minima di lati) che mira a trovare il sottoinsieme

minimo di archi da ignorare per poter considerare il grafo planare; si noti che

il problema è banalmente riconducibile al disegno con un numero minimo di

intersezioni, ed è quindi, come abbiamo detto, NP-completo. Una strada a�ne

è stata anche cercare il massimo sottografo planare; per quest'ultimo, sono state

trovate euristiche che ne permettono il calcolo in maniera e�ciente [8]. Nessuno

di questi tentativi ha però portato a disegni e�caci del grafo così planarizzato.

Modelli �sici. Per il disegno di gra� generici si è infatti a�ermato nel tempo,

come via più comune, il disegno tramite modelli �sici (in inglese, force-driven

methods: letteralmente, �metodi [di disegno] guidati da forze�). Questa euristica

è stata proposta per la prima volta da Peter Eades nel 1984 [15]; l'intuizione è

modellare il grafo come un insieme di corpi che seguano le leggi �siche � senza

doverle per forza rispettare pedissequamente � e lasciare che siano esse, agendo,

a portare il sistema in una disposizione valida.

Dai criteri estetici elencati all'inizio di questo capitolo emergono infatti due

norme generali: i nodi collegati dovrebbero essere separati da una distanza più o

meno �ssa, mentre gli altri dovrebbero in generale stare il più lontano possibile.

Eades ha perciò reso il grafo come un insieme di anelli elettricamente carichi


� i nodi � connessi da molle � i lati. In questo modo, si crea nel modello una

forza repulsiva tra ogni nodo, mentre le molle creano una forza di attrazione

che avvicina i nodi adiacenti, �nché non sono separati dalla lunghezza naturale

della molla; per questo motivo, questo genere di algoritmi viene detto in inglese

spring-embedder, ovvero �a inserimento di molle�. Il sistema, inizializzato ca-

sualmente, rimane perciò in movimento �nché non viene raggiunto uno stato di

equilibrio tra queste forze opposte.

Poiché però l'obiettivo non è simulare la realtà �sica, ma usarne qualche prin-

cipio per disporre i nodi di un grafo, egli apporta numerose modi�che rispetto

alle leggi reali. Ad esempio, uno dei problemi che avrebbe una simulazione fedele

è che potrebbe portare ad un equilibrio dinamico (si pensi al moto oscillatorio

in cui entra una piccola molla con un peso attaccato), anziché ad un equilibrio

statico, in cui ogni nodo resti stabile nella sua posizione. La soluzione adottata

in questo genere di modelli è perciò cambiare il signi�cato �sico di forza: anziché

generare accelerazioni, esse causeranno velocità. Questo sempli�ca l'algoritmo

e gli permette di convergere ad una situazione stabile.

Eades ha apportato anche un altro importante cambiamento rispetto alla

realtà: la legge che governa le molle. Infatti, mentre secondo la �sica la forza è

lineare con l'allungamento (per la legge di Hooke), egli preferisce optare per un

andamento logaritmico.

L'algoritmo di Fruchterman-Reingold. I buoni risultati di questo algorit-

mo hanno indotto molti a proseguire lo studio di queste euristiche. Una versione

dell'algoritmo molto vicina all'idea di Eades, ma particolarmente semplice, coe-

rente ed e�cace è quella proposta nel 1991 da Thomas Fruchterman e Edward

M. Reingold [17].

I due autori hanno prima di tutto messo alla prova diverse leggi per rendere

le forze attrattive e repulsive; sperimentalmente, i risultati migliori sono stati

ottenuti con queste leggi � diverse da quelle di Eades, e computazionalmente

più semplici:

fa(x) = x2/k


fr(x) = k2/x

dove x è la distanza che separa i due nodi, mentre la costante k è la loro

distanza ideale.

Un'altro accorgimento importante dell'algoritmo di Fruchterman-Reingold

è l'introduzione del concetto di ra�reddamento. Esso consiste nell'imporre a

ogni molla una velocità massima, determinata dalla temperatura; abbassando

la temperatura del modello, le molle potranno muoversi sempre di meno. Imple-

mentando questo semplice comportamento, l'algoritmo riuscirà a spostare i nodi

ad alta velocità all'inizio della computazione � quando il layout è ancora molto

compromesso dalla disposizione casuale iniziale � e a passare a spostamenti più

�ni man mano che il layout migliora. In questo modo inoltre, il ra�reddamento

del modello comporta il raggiungimento certo ad un istante predeterminabile di

una situazione di equilibrio, poiché lo spostamento massimo si avvicinerà pro-

gressivamente a zero. Questo consente di essere sicuri che l'algoritmo converga

in un certo tempo � al prezzo però di non sapere se la disposizione così trovata

è davvero ottimale.

Riassumendo, l'algoritmo parte da una disposizione casuale e avanza di un'u-

nità di tempo alla volta; ad ogni istante, trova la somma tra le forze repulsive

che agiscono tra ogni coppia di nodi e le forze attrattive causate da ogni lato,

dopodiché ra�redda la temperatura e sposta i nodi, ripetendo il processo �nché

la velocità dei nodi non giace sotto una certa soglia. La complessità ad ogni

iterazione è perciò O(|V |2+ |E|). Nell'algoritmo 3.1 riportiamo lo pseudocodice.

L'algoritmo di Kamada-Kawai. Un approccio di�erente dai due preceden-

ti, ma simile nell'idea di fondo, è stato ideato da Kamada e Kawai nel 1989

[23]. In esso, le forze repulsive dovute alle cariche elettriche vengono eliminate,

introducendo invece una molla tra ogni coppia di vertici, e non solo tra quelli

adiacenti. Le molle ovviamente non sono identiche: la lunghezza a riposo delle

molle è proporzionata alla distanza tra i nodi nel grafo1. In questo modo, ogni

1Per distanza tra un nodo v e un nodo w intendiamo il numero minimo di archi chedobbiamo attraversare per arrivare da v a w ; per distanza da un insieme di nodi, intenderemola minore delle distanze possibili dagli elementi di quell'insieme.


Algorithm 3.1 algoritmo di Fruchterman-Reingold originale (pseudocodice)

area = W ∗ L ; //Larghezza e lunghezza de l r iquadroG = (V, E) ;k = squareRoot ( area / |V| ) ;

f unc t i on fA t t r a c t i v e ( x ) {re turn x ∗ x / k ;

}func t i on fRepu l s i v e ( x ) {

re turn k ∗ k / x ;}

f o r ( i = 1 ; i < i t e r a t i o n s ; i++) {

// c a l c o l o tu t t e l e f o r z e r e pu l s i v ef o r each v in V {

// ogni v e r t i c e cont i ene due// v e t t o r i : v . pos e v . d i spv . d i sp = 0 ;f o r each u in V {

i f (u != v ) {d = v . pos − u . pos ;v . d i sp = v . d i sp +

( d / | d | )∗ fRepu l s i v e ( | d | ) ;

}}

}

// c a l c o l o l e f o r z e a t t r a t t i v ef o r each e in E {

// ogni l a t o e è c a r a t t e r i z z a t o// dai suo i v e r t i c i e . v e e . ud = e . v . pos − e . u . pos ;e . v . d i sp = e . v . d i sp −

( d / | d | ) ∗ fA t t r a c t i v e ( | d | ) ;e . u . d i sp = e . u . d i sp +

( d / | d | ) ∗ fA t t r a c t i v e ( | d | ) ;}

f o r each v in V {v . pos = v . pos + ( v . d i sp / | v . d i sp | )

∗ min(v . disp , t ) ;v . pos . x = min (W/2 , max( −W/2 , v . pos . x ) ) ;v . pos . y = min (L/2 , max( −L/2 , v . pos . y ) ) ;}

t = coo l ( t ) ;}


coppia di vertici tende a trovarsi ad una distanza proporzionale al percorso più

breve che esiste tra essi.

Le molle vengono qui modellate con la legge di Hooke � ovvero in maniera

corrispondente alla realtà �sica: la forza attrattiva che esercitano è direttamente

proporzionale alla di�erenza rispetto alla loro dimensione originaria. Se lo spazio

tra i nodi nel disegno è eccessivo rispetto alla loro distanza nel grafo, la molla

tenderà ad avvicinarli; se è scarso, è compressa e li allontanerà.

Un'altra novità di questo modello è la formalizzazione in termini di energia

anziché di forze e velocità; esso mira quindi esplicitamente a trovare un minimo

locale rispetto alla posizione dei nodi dell'energia potenziale totale del sistema.

Per questo, la legge di Hooke viene integrata, ottenendo un rapporto quadratico

tra l'energia e la di�erenza tra lunghezza a riposo e lunghezza e�ettiva. Questo

causa anche una di�erenza nell'algoritmo di ottimizzazione: in una singola ite-

razione non vengono spostati tutti i vertici, ma solamente quello che causa un

avvicinamento maggiore all'energia potenziale minima.

Concludendo, notiamo che l'eleganza formale di questo algoritmo è purtrop-

po controbilanciata dalla di�coltà a mantenere in memoria la distanza tra ogni

coppia di nodi.

3.2 I gra� di grandi dimensioni: il metodo mul-

tidimensionale di Harel-Koren

Non è però obbligatorio seguire l'idea del modello �sico per disegnare un grafo.

David Harel e Yehuda Koren hanno presentato nel 2004 un approccio innovativo

al disegno di gra� di grandi dimensioni [14]. Esso si basa su un'osservazione: un

grafo sarebbe disegnabile in maniera più chiara ed e�cace se avessimo a dispo-

sizione molte più dimensioni delle due a cui lo riduciamo. Si pensi, per esempio,

ad un grafo ad anello, in cui ogni elemento è collegato soltanto ai due adiacenti;

tentare di rappresentare questo grafo su una sola dimensione � ovvero, disporre

i suoi nodi su una retta � renderebbe il problema di�cilmente approcciabile.

Allo stesso modo, per riuscire a disegnare correttamente un grafo di un toro

(i suoi vertici e gli spigoli che li collegano) dovremmo prima di tutto renderci

conto che il grafo in questione corrisponde a questa �gura a tre dimensioni, e


poi scegliere il punto di vista migliore per rendere su di un piano questo spazio

tridimensionale. In generale, ipotizzano Harel e Koren, maggiore è il numero

di dimensioni a nostra disposizione più riusciremo a far emergere una struttura

chiara del grafo. Ma le questioni sono a questo punto: quale potrebbe essere

un valido disegno di un grafo in uno spazio a n dimensioni? Come riuscire poi

a rappresentare questo disegno nelle due dimensioni che uno schermo mette a

nostra disposizione?

3.2.1 Un disegno multidimensionale

Il metodo proposto da Harel e Koren mira ad essere e�cace e soprattutto veloce:

non dobbiamo dimenticarci che lo scopo è operare con gra� molto grandi. Per

prima cosa quindi, dobbiamo riuscire ad estrarre dal grafo una funzione che

collochi ogni nodo in uno spazio m-dimensionale, del tipo LG,m : V → Rm. Per

farlo, procederemo in questo modo:

1. Scegliamo un set di nodi pivot . È importante che questo insieme di

nodi sia il più possibile �rappresentativo� dell'intero grafo (sarà più chiaro

in seguito cosa intendiamo con questo); il metodo migliore per ottenere

ciò è identi�care i k-centri del grafo: quel sottoinsieme dei nodi S ⊂ V

che minimizzi maxv∈V mins∈S distanza(v, s), ovvero che renda la distanza

che intercorre tra il nodo più lontano e l'insieme dei centri la più breve

possibile. È stato dimostrato che questo problema è NP-completo, ma

ne esiste fortunatamente una approssimazione polinomiale (di complessità

O(m·(|E|+|V |))); questa consiste nel partire da un nodo casuale, renderlo

il primo nodo di S e aggiungere quindi di volta in volta il nodo più lontano

da S. Per misurare le distanze, è conveniente usare una strategia BFS

(Breadth-�rst search, ricerca in ampiezza). Questo algoritmo è semplice,

rapido, e particolarmente adatto ai nostri scopi.

2. Abbinare una dimensione ad ogni pivot . Scelti i nostri m pivot,

ognuno di essi costituirà l'origine di una delle m dimensioni: la distanza

che separa un nodo v ∈ V dal pivot pi sarà la sua distanza dall'origine

nella i -esima dimensione, ovvero il valore della sua i -esima coordinata. Le

distanze sono inoltre già state calcolate dall'algoritmo precedente: la sua


BFS non dovrà quindi soltanto usare le distanze tra ogni nodo v ∈ V e S

per trovare i k -centri, ma anche memorizzarle in qualche modo.

In sintesi, la i -esima coordinata di un nodo v sarà quindi:

Xi(v) = distanza(pi, v)

3.2.2 Proiezione a due dimensioni

Ora che abbiamo una disposizione valida dei nodi in uno spazio m-dimensionale,

dobbiamo trasformare le nostre m coordinate per nodo in una coppia (x, y). La

scienza statistica mette a disposizione una tecnica e�cace per ridurre un insieme

di variabili ad una serie più piccola; questa tecnica è nota come PCA (Principal

component analysis, analisi delle componenti principali). Essa individua infatti,

dalle variabili di partenza, una serie di loro combinazioni lineari che abbiano la

caratteristica di massimizzare la varianza rispetto al set di valori dati; queste

combinazioni lineari prendono appunto il nome di componenti principali.

L'idea è di utilizzare queste componenti principali per avere una coppia di

coordinate che siano le più signi�cative possibile: massimizzare la loro varian-

za signi�ca distribuire e�cacemente i nodi lungo ognuno degli assi, e quindi

tradurre nel modo migliore possibile le nostre m coordinate su di uno schermo.

Non ci addentreremo in questa sede nella teoria matematica che rende pos-

sibile questa analisi (per la quale rimandiamo alla letteratura speci�ca [12]);

tuttavia, spenderemo qualche parola per descriverne a grandi linee il funziona-

mento. Per prima cosa, dobbiamo rendere trattabili i nostri dati: dopo aver

centrato ogni asse sulla propria media (o, in altre parole, avendo traslato i nodi

in modo che la media di ogni asse sia pari a zero), li disporremo in una matrice

m × n (con n = |V |) dove l'elemento xi,j sia la i -esima coordinata del j -esimo

nodo. Da questa matrice m×n ricaveremo la sua matrice di covarianza, la quale

avrà dimensioni m ×m; è buona cosa notare che, essendo n molto più grande

di m, una matrice di questa grandezza diviene decisamente più trattabile (può,

nei fatti, essere tranquillamente gestita in memoria); tuttavia, calcolarla è di

gran lunga il passaggio computazionalmente più oneroso di questa fase (la com-

plessità dell'algoritmo è O(m2n)). Per i dettagli sul suo calcolo, rimandiamo

all'articolo originale di Harel e Koren [14]. Da questa matrice, sarà possibile


ottenere quindi la matrice dei suoi autovettori, ordinandola in modo da avere

per primi quelli con i maggiori autovalori; chiamiamo questi vettori u1,u2 e così

via.

Ora, le combinazioni lineari delle variabili iniziali a cui siamo interessati

avranno per vettore dei coe�cienti proprio questi autovettori: il primo corri-

sponderà alla combinazione lineare dotata di massima varianza, e quindi alla

prima componente principale, il secondo alla seconda e così via. Le nuove coor-

dinate (x, y) di un nodo v saranno quindi le prime due componenti principali,

ovvero:

(u1 ·X(v),u2 ·X(v))

dove

X(v) =[X1(v) · · · Xm(v)

]Si potrebbe pensare che una riduzione delle m dimensioni originarie a tre

anziché a due possa migliorare i risultati: tuttavia, ciò non considera che lo

schermo di un calcolatore � come la stragrande maggioranza dei dispositivi

di visualizzazione � ha soltanto due dimensioni reali; una eventuale terza di-

mensione virtuale necessiterebbe poi di essere resa sullo schermo tramite una

proiezione. Trovare la proiezione migliore non è compito banale: Harel e Koren

hanno persino suggerito proprio questa seconda parte del loro metodo � la PCA

� come soluzione al problema di rendere bidimensionale un disegno computato

per tre dimensioni.

3.2.3 Motivi di interesse e punti di forza

Vari elementi di quest'algoritmo ne hanno fatto un buon candidato per i nostri

scopi.

Prima di tutto, è veloce: secondo quanto riportato dagli autori e non solo,

è probabilmente uno degli algoritmi più veloci esistenti per il layout di un gra-

fo. Se un algoritmo force-driven ben ottimizzato e ben calibrato impiega una

decina di minuti per disegnare un grafo di 105 nodi, al metodo di Harel-Koren

bastano pochi secondi; nell'implementazione in C degli autori stessi, esso riesce

a computare una disposizione per un grafo di 106 nodi in meno di un minuto.


Un tempo di computazione simile lo rende praticamente l'unico algoritmo in

grado di lavorare con gra� delle dimensioni da noi richieste.

In secondo luogo, è � nonostante ciò � abbastanza semplice da implementare.

Un'implementazione valida della prima parte dell'algoritmo non è né lunga né

complicata (l'unica di�coltà è rappresentata dal minimizzare l'uso della memo-

ria); il calcolo degli autovettori, o per�no l'intera PCA, sono inoltre problemi

standard, che possono essere risolti da librerie esterne. Un altro fattore che sem-

pli�ca l'uso di questo algoritmo è il suo essere quasi privo di parametri arbitrari;

rispetto ad un metodo force-driven che rende necessario trovare il valore migliore

da dare alle sue numerose costanti pseudo-�siche, l'unico parametro da ottimiz-

zare qui è il numero m delle dimensioni, per il quale gli autori suggeriscono un

valore attorno a m = 50.

In�ne, ha generato interesse la prospettiva suggerita dagli autori riguardo

alla possibile interattività di questo metodo. Essi infatti identi�cano due mo-

di in cui l'utente possa interagire con i risultati dell'algoritmo: scegliendo una

zona del disegno e ricalcolando la PCA limitatamente alle coordinate multidi-

mensionali dei nodi selezionati, è possibile ottenere una nuova distribuzione dei

nodi che evidenzi la struttura di quell'area; oppure, scegliendo per gli assi X

e Y componenti principali diverse dalla prima e dalla seconda si può ottenere

(senza alcun calcolo aggiuntivo) una diversa prospettiva del disegno multidi-

mensionale: essi infatti evidenziano come, scegliendo sempre tra le componenti

principali con la massima varianza, si potessero ottenere talvolta dei risultati

migliori scegliendone di diverse dalle prime due.

3.3 Il metodo multiscala di Walshaw

Il metodo proposto da Chris Walshaw [31] viene usato dallo studio precedente

come confronto, venendo de�nito �il più veloce degli algoritmi multiscala�: su

di esso si è concentrata quindi successivamente la nostra ricerca. Introduciamo

pertanto il concetto di euristica multiscala (in inglese multiscale) su cui si basa.


3.3.1 Il paradigma multiscala

Gli algoritmi a modelli �sici (descritti all'inizio di questo capitolo) presentano

un grosso problema, che emerge tanto più drasticamente con la dimensione

dei gra�: essendo algoritmi basati unicamente sulla ottimizzazione iterativa del

disegno, la disposizione iniziale dei nodi è assolutamente casuale. Quando i

gra� sono di dimensioni piccole, basta un numero trattabile di iterazioni per

iniziare ad ottenere un layout valido; ma avendo a che fare con gra� grandi, la

disposizione casuale da cui si parte diviene enormemente lontana dallo scopo.

In molti hanno tentato di a�rontare quello che sembra essere uno dei principali

problemi di questi algoritmi � per esempio, è stato proposto da Paul Mutton

[13] un pre-processore che suggerisca all'algoritmo un posizionamento iniziale

dei nodi. Per gra� delle dimensioni da noi considerate, però, si è recentemente

a�ermata come soluzione a questo problema la strategia multiscala.

Essa consiste nel prendere in considerazione, prima che il grafo vero e pro-

prio, una sua versione approssimativa � �a grossa scala� (coarse graph in lingua

inglese) � composta solitamente da un clustering di qualche tipo del grafo in

esame, dove ogni nodo della versione a grossa scala corrisponde ad un gruppo di

nodi di quella originale, facendo sì che questi gruppi costituiscano un partizio-

namento dei nodi originari. Applicare ad un grafo così ottenuto un algoritmo

a modello �sico diviene perciò più semplice, avendo ridotto arbitrariamente il

numero di nodi, ed è possibile ottenere così una disposizione valida del nostro

grafo a grossa scala; perché questa disposizione dei nodi divenga quindi una di-

sposizione iniziale per il grafo originale, basta sostituire ogni nodo a grossa scala

con il gruppo di nodi a scala �ne da cui è formato: questo punto di partenza è

senza dubbio più vicino al risultato �nale, che richiederà pertanto un tempo di

computazione minore rispetto ad una disposizione casuale dei nodi. Di regola,

questa tecnica viene applicata iterativamente: se il grafo a grossa scala supe-

ra ancora la dimensione richiesta, se ne può trarre una versione a scala ancora

maggiore; il procedimento viene ripetuto �no a che non viene raggiunto un grafo

di dimensione minima.

Questo modo di pensare al grafo non come ad un solo, enorme grafo ma

come ad un sovrapporsi di sue approssimazioni a scala via via più grossa, così da

separare operazioni da eseguirsi �a grossa scala� da operazioni più �ni, è in realtà


antecedente a questa sua applicazione nel disegno; per esempio, è stata messa

in pratica con successo anche con il problema del commesso viaggiatore [32],

riuscendo a dare alla funzione obiettivo del problema un mezzo per aggiustarsi

in modo prima molto grossolano e poi via via più �ne. Nel disegno di gra�,

la sua concretizzazione è stata approcciata da molti2, compresi � tra i primi

� gli stessi Harel e Koren dell'algoritmo descritto precedentemente [19]. La

versione da loro elaborata è particolarmente e�cace: fa in modo non solo di

usare il layout a grossa scala come punto di partenza per il grafo successivo,

ma anche di usare ogni cluster che ne sta alla base per operare modi�che �ni

coinvolgendo solo i nodi che ne fanno parte (tramite il concetto di k -vicinato,

strettamente imparentato con i k -centri dell'algoritmo sopra descritto); tuttavia,

essa ha il grosso punto debole di ritrovarsi costretta � anche per la scelta di usare

l'algoritmo di Kamada-Kawai come modello �sico � a memorizzare le distanze

tra ogni singola coppia di nodi. Per un grafo di solamente 105 nodi, una tabella

di questo genere occuperebbe un centinaio di gigabyte.

Gajer ha tentato di risolvere questo problema [18] calcolando dinamicamente

la distanza tra due nodi ogni qual volta questa veniva richiesta; inoltre, appli-

ca anche il concetto di temperatura del modello �sico. Tuttavia, sembrerebbe

che la scelta più e�cace si sia rivelata quella di Walshaw di cambiare il model-

lo �sico di riferimento, sostituendo l'algoritmo di Kamada-Kawai con quello di

Fruchterman-Reingold. Usare questo metodo elimina la necessità di conosce-

re tutte le distanze possibili, rendendo le richieste dell'algoritmo decisamente

inferiori � specie per i gra� delle dimensioni da noi presi in considerazione.

Descriviamo quindi ora l'algoritmo sviluppato da Walshaw, prendendo in

considerazione i suoi due momenti principali: la realizzazione del metodo mul-

tiscala, e la sua variante del modello �sico di Fruchterman-Reingold.

3.3.2 Costruzione e uso della gerarchia multiscala

La gerarchia multiscala deve essere costituita da una serie di gra�G0, G1, G2 · · ·GL,

dove il G0 è il grafo originale e GL quello di dimensione minima; possiamo de-

2Un'altra applicazione di questa idea è il cosiddetto �disegno multilivello�, che colloca ogniversione del grafo su di un diverso piano, mettendo in cima quelli più a grossa scala ed in fondoil grafo originale, permettendo così di visualizzare in un colpo d'occhio la relazione gerarchicatra i nodi delle diverse versioni. Per informazioni su questa tecnica � particolarmente utilequando si vuole porre l'accento sul clustering stesso � si veda il lavoro di Eades et al.[16].


�nirli come G0 = (V0, E0) . . . , GL = (VL, EL), e dire che � in base a quanto

spiegato prima:

v ∈ Vi ⇒ v ⊆ V0, ∀i : 0 < i ≤ L

Ovvero, ogni vertice di un grafo approssimato è in realtà un sottoinsieme dei

vertici del grafo G0. De�niamo quindi il peso di un nodo v in uno di questi gra�

come |v|, ovvero il numero di nodi del grafo originale che esso contiene.

Il partizionamento di Vi a cui siamo interessati per passare da Gi a Gi+1

deve avere certe carattistiche: prima di tutto, deve essere molto rapido � non

dobbiamo dimenticarci che lo scopo è far risparmiare tempo al modello �sico

del grafo, e che i gra� con cui abbiamo a che fare sono molto grandi. In seconda

battuta, deve riuscire a costruire una serie di gra� in cui la diminuzione di nodi

sia graduale: la disposizione iniziale trarrebbe ben pochi vantaggi da un parti-

zionamento che raggruppa insieme troppi nodi in una volta sola � l'algoritmo a

modello �sico dovrebbe ricomputare quasi da zero il layout del grafo Gi � e il

paradigma multiscala con cui abbiamo costruito Gi+1 diverrebbe quasi inutile.

Al contrario, diminuire troppo poco il numero di nodi signi�cherebbe aumentare

di molto il numero di gra� della nostra gerarchia (poiché dovrebbe comunque

giungere ad un grafo di piccole dimensioni), incrementando la quantità di calcoli

e di algoritmi a modelli �sici da eseguire; in pratica, l'overhead introdotto dal

paradigma multiscala crescerebbe a dismisura. È pertanto molto importante

che il nostro partizionamento trovi una via di mezzo tra questi estremi.

Walshaw suggerisce l'uso di un approccio tipico nel partizionamento di gra�

noto come matching. Esso, formalmente, consiste nel trovare un sottoinsieme

di E che sia indipendente � ovvero che non contenga lati che incidano sullo

stesso vertice � e massimale, cioè tale che non si possa più aggiungere alcun

altro elemento di E senza infrangere il criterio precedente; dopo aver trovato

questo sottoinsieme di E, si congiungono tutti i lati che ne fanno parte: i vertici

collegati da uno di questi archi diverranno, dopo il matching, lo stesso vertice.

Questo procedimento fa sì che non raggrupperemo mai più di due nodi per volta:

il numero di vertici può perciò al massimo dimezzarsi.

Gli algoritmi per risolvere ottimamente questo compito sono stati ben stu-

diati, ma la loro complessità è di almeno O(|V |2.5). Fortunatamente, per i

nostri �ni non importa che il risultato sia ottimale, ma basta che vi si avvicini


a su�cienza. Perciò, Walshaw fa uso di un metodo di soluzione approssimata,

proposta da Hendrickson e Leland [20], semplice ed e�cace.

Essa parte da una lista contenente tutti gli elementi di V ordinati casual-

mente, e li visita a turno. Per ogni nodo visitato, sceglie uno dei suoi vicini che

sia ancora parte della lista, e aggiunge l'arco che li collega all'insieme di archi

da rimuovere; se invece nessuno dei suoi vicini fa ancora parte della lista signi-

�ca che non può essere più abbinato ad alcun nodo, e viene rimosso dalla lista

comunque. Al contrario, nel caso che più di un vicino sia ancora abbinabile, la

soluzione orginale suggeriva di sceglierne uno in modo casuale; tuttavia, Wal-

shaw fa notare che per i nostri scopi è conveniente scegliere sempre, se possibile,

il nodo più leggero (ricordiamo che tutti i nodi dei gra� successivi a G0 nella

nostra serie avranno un peso determinato dal numero di nodi di G0 che essi

raggruppano). In questo modo manterremo il partizionamento più omogeneo

rispetto ai nodi inziali.

Applicando iterativamente questo processo otteniamo così la nostra serie

G0 · · ·GL e avremo un valore di L � il numero di livelli necessari ad arrivare al

grafo di dimensione minima possibile � tale che log2 |V | ≤ L < |V |; pertanto,

sicuramente non �niremo nel primo estremo sopra esposto, raggruppando troppi

nodi insieme; inoltre, il tempo di computazione è accettabile anche per gra� di

grandi dimensioni. Due dei tre criteri che ci eravamo posti sono senza dubbio

rispettati.

Veniamo ora a come useremo la gerarchia multiscala così prodotta; dopo

averla calcolata, avremo infatti a disposizione il grafo GL, il quale, se siamo

partiti da un grafo connesso, avrà un solo nodo3. L'algoritmo procederà quindi

ad assegnare una posizione casuale a questo nodo iniziale; da qui in avanti, per

ogni grafo Gi della serie cominciando da GL−1, si procederà in questo modo:

1. Ottenere una posizione iniziale per i nodi di Gi, assegnando ad ogni nodo

v ∈ Vi la posizione � ormai già calcolata de�nitivamente � del nodo di

Gi+1 che li conteneva.

2. Dare questa disposizione iniziale, con ogni nodo nella stessa posizione del

suo cluster, all'algoritmo a modello �sico, e lasciare che esso computi una

3Notiamo che, invece, per un grafo non connesso, |VL| equivarrà al numero di componenticonnesse di G0.


disposizione de�nitiva per i nodi di Gi.

3. Eseguire di nuovo passando al grafo a scala minore, �nché non si giunge

a determinare una disposizione per G0.

3.3.3 Posizionamento tramite modello �sico

Scopriamo ora cosa abbiamo nascosto dentro la �scatola nera� dell'algoritmo a

modello �sico, al quale passiamo la disposizione iniziale per ottenerne il lay-

out de�nitivo di ogni livello. Esso ha per base, come già detto, l'algoritmo

di Fruchterman-Reingold, apportando però alcune modi�che per ottimizzar-

lo ed adattarlo all'euristica multiscala che abbiamo descritto; lo pseudocodice

modi�cato è riportato, nella sua interezza, nell'algoritmo 3.2.

Il riquadro del disegno. Una modi�ca minore, comune a tutti gli algoritmi

per gra� grandi, è evitare di prendere in considerazione le dimensioni in cui

poi il disegno dovrà avere luogo. La cornice (il frame) del disegno viene infatti

valutata in vari modi dagli algoritmi classici; gli algoritmi qui descritti invece

ignorano questa informazione, demandando l'operazione di scalatura del disegno

ad un momento successivo all'esecuzione dell'algoritmo, velocizzandolo.

L'ordine di aggiornamento delle posizioni. Algoritmicamente, una sem-

pli�cazione importante rispetto all'originale è il modo in cui vengono analizzati

e spostati i nodi ad ogni iterazione. Infatti, l'algoritmo originale mantiene in

memoria lo spostamento di ogni singolo nodo, calcolando prima l'e�etto di tutte

le forze repulsive, poi di tutte quelle attrattive, e in�ne spostando tutti i nodi;

invece, la versione di Walshaw in ogni iterazione prende in esame un singolo

nodo per volta, applicando ad esso tutte le forze che agiscono su quel singolo

nodo e spostandolo prima di passare al nodo successivo. Questo ha la notevole

conseguenza che, dopo aver spostato il nodo v nell'iterazione i, nella medesima

iterazione i i nodi successivi calcoleranno le forze utilizzando la nuova posizione

di v, mentre l'algoritmo originale userebbe le posizioni come erano nell'iterazione

i − 1. In altre parole, se l'algoritmo originale applicava le forze �contempora-

neamente� per tutti i nodi, questo algoritmo le applica ad alcuni nodi prima di

altri. Nello pseudocodice 3.2, per questo meccanismo si usa il puntatore posn,


Algorithm 3.2 algoritmo di F. R. modi�cato da Walshaw (pseudocodice)

t = k ;

func t i on fA t t r a c t i v e ( x ) {re turn x ∗ x / k ;

}func t i on fRepu l s i v e ( x , w ) {

return −C ∗ w ∗ k ∗ k / x ;}

Posn = newPosn ;

whi l e ( ! converged ) {

f o r each (v in V) {oldPosn [ v ] = newPosn [ v ] ;

}

f o r each v in V {// ana l i z z o l e f o r z e su vd i sp = (0 , 0 ) ;

// f o r z e r e pu l s i v e d e g l i a l t r i nodi su vf o r each u in V, u != v {

d = posn [ u ] − posn [ v ] ;d i sp = disp + ( d / | d | )

∗ fRepu l s i v e ( | d | , u . weight ) ;}

// f o r z e a t t r a t t i v e de i v i c i n i d i vf o r each u in v . ne ighbors {

d = posn [ u ] − posn [ v ] ;d i sp = disp + ( d / | d | )

∗ fA t t r a c t i v e ( | d | ) ;}

// sposto vnewPosn [ v ] = newPosn [ v ] +

( d i sp / | d i sp | ) ∗ min( t , | d i sp | ) ;

i f ( | d | > k ∗ t o l ) {converged = true ;}

}

t = coo l ( t ) ;}


che punta al vettore delle nuove posizioni (per riconvertire questo algortimo alla

sua versione originale, basterebbe far puntare posn a oldPosn). Questa modi�-

ca, secondo l'autore, migliora la velocità dell'algoritmo: questo perché gli e�etti

dello spostamento del nodo v hanno luogo già durante la medesima iterazione

in cui esso viene spostato.

Si noti, inoltre, che in questo modo la forza repulsiva tra una coppia di nodi

u, v viene calcolata due volte: una prima volta quando viene preso in esame

il vertice u ed una seconda volta quando si analizza v ; la seconda volta, però,

la posizione di u sarà già aggiornata e sarà da questa nuova posizione che esso

eserciterà la propria forza, contribuendo così alla velocizzazione del processo.

Forze pesate. Dobbiamo notare che, pur partendo tipicamente da gra� non

pesati, avremo a che fare con la serie di gra� a grossa scala che ne avremo

ricavato, ed in essi ogni nodo ha il proprio peso. Questo ha portato Walshaw a

modellare una forza repulsiva tra i vertici che sia direttamente proporzionale al

peso del nodo che la esercita; in particolare, calcolando le forze che agiscono sul

nodo v, la forza repulsiva esercitata da u su v sarà proporzionale a |u|. Infatti,

|u| altro non è che il numero di nodi del grafo originale G0 che sono contenuti

nel nodo u; se prendessimo in analisi non u ma i singoli nodi compresi in esso,

applicheremmo |u| volte questa forza. Un modo e�cace per rendere questo

comportamento è imporre la proporzionalità tra forza replusiva e peso.

In teoria, anche la forza attrattiva generata da un arco e = (u, v) nel grafo Gi

potrebbe corrispondere a diverse forze dei vari archi che attraversavano il taglio

tra i vertici raggruppati in u e quelli raggruppati in v. Ciò nonostante, biso-

gna notare che non vi è un meccanismo così semplice per implementare questa

forza: ipotizzando un peso di e uguale al numero di archi che esso sostituisce,

il rapporto con le forze che esso esercita non sarebbe necessariamente lineare,

ma dipenderebbe dalla struttura interna dei cluster u e v ; inoltre, la questione

diventerebbe ancora più complicata dopo vari passaggi nella serie multiscala.

In ogni caso, l'autore ha provato ad introdurre una proporzionalità tra forza

attrattiva e peso dell'arco che la esercita, secondo la possibile de�nizione data

sopra, ed anche mettendo in rapporto quest'ultimo con i pesi dei rispettivi nodi;

i risultati sono però rimasti � si a�erma � molto simili (o talvolta peggiori),


Figura 3.3: Calcolo della lunghezza naturale k

aumentando per di più il tempo di computazione del 10-20%. Perciò, la soluzione

migliore si è rivelata essere, semplicemente, ignorare i pesi degli archi.

I parametri dell'algoritmo. Vari parametri dell'algoritmo sono, di per sé,

arbitrari, e vanno trovati sperimentalmente. Inoltre, esso verrà applicato in serie

alle varie scale del grafo: alcuni parametri dovranno dipendere dalla versione

che si sta computando.

Questo è il caso della lunghezza naturale k delle molle. Se infatti � elabo-

rando il grafo Gi partendo dalle posizioni trovate per Gi+1 � lasceremo il valore

precedente di k, l'algoritmo �nirà con il dover ricalcolare da capo l'intero disegno

poiché ogni molla si ritroverà troppo compressa. Questo perché, scompattando

i cluster, essi diventeranno un insieme di nodi e si espanderanno; pertanto, le

molle che connettono questi nodi ai nodi adiacenti dovranno occupare meno

spazio di quelle che collegavano il cluster che li conteneva.

Per capire cosa accadrebbe durante il raggruppamento nel passaggio da Gi a

Gi+1, e tentare di lasciare invariate le distanze durante il processo, osserviamo

la �gura 3.34, in cui i nodi v e u vengono raggruppati nel cluster v′.

Ipotizziamo una disposizione ottimale � ovvero, ogni coppia separata da una

distanza k (�g. 3.3 b) � dei due nodi e del nodo w, adiacente a v; il nodo w

sarà posto perciò in una qualunque posizione a distanza k da v su�cientemente

4La �gura è presa dall'articolo originale [31].


lontana da u, e quindi in un punto dell'arco PQR; supporremo una media tra

il caso in cui esso stia in Q e il caso in cui stia in P o R. Ora, se raggruppiamo

v e u, introdurremo il nodo v′ a una distanza intermedia, e l'arco (v, w) diverrà

l'arco (v′, w); la distanza naturale tra questi due nodi non sarà più k ma, in

media, d. Perché quindi le molle non si ritrovino compresse o allungate tra un

passaggio e l'altro, dobbiamo imporre d come nuova lunghezza naturale delle

molle per il grafo Gi+1. Per il teorema del coseno applicato al triangolo w, v′, v

avremo:

d2 = k2 +(k

2

)2

− 2 · k · k2· cos(2π/3) = k2 +

14k2 +

12k2 =

74k2

Ora, poiché nell'algoritmo dovremo passare da Gi+1 a Gi, invertiamo l'e-

quazione, ottenendo la seguente legge:

ki =

√47· ki+1

Potremo applicare questa equazione ad ogni scompattamento dei cluster,

inizializzando kL con un valore del tutto arbitrario.

Gli altri parametri sono stati invece trovati sperimentalmente da Walshaw.

La costante di repulsione C viene posta attorno a 0.2; è stato provato che

aumentando questo valore, il disegno migliora esteticamente, al prezzo di un

tempo di computazione maggiore: valori usabili sono comunque tra 0.1 e 0.5.

La soglia di tolleranza, ovvero il movimento massimo sotto il quale il sistema

viene riconosciuto come fermo (interrompendo il processo), deve essere propor-

zionale a k e viene perciò scritta come tol · k, dando a tol un valore di circa

0.01.

Per lo stesso motivo, la temperatura viene inizializzata ad ogni livello con

t0 = kl; la funzione di ra�reddamento cool(t) ad ogni iterazione sarà invece

t = λt, dove a λ viene dato il valore 0.9.

Da questi ultimi parametri (tol · k, λ, t0) dipende il numero massimo di ite-

razioni che l'algoritmo può compiere: quando infatti il movimento massimo

consentito dalla temperatura diventa comunque inferiorire alla soglia di tolle-

ranza, l'algoritmo trova necessariamente una conclusione. Questo si veri�ca

perciò nella i -esima iterazione se e solo se soddisfa k · λi < k · tol; ovvero, nella


iterazione

i = logλ(tol)

Per i valori trovati sopra, si ha i ' 44, che è vicino alle 50 iterazioni normalmente

usate per l'algoritmo di Fruchterman-Reingold.

Variante a celle Walshaw usa una tecnica avanzata per ridurre il tempo di

computazione dell'algoritmo a modello �sico, chiamata grid variant. Questa è

stata in verità proposta già da Fruchterman e Reingold nel loro articolo originale

[17], mutuandola dall'ambito più generale delle simulazioni di sistemi a n-corpi,

ed è stata sviluppata poi da molti altri per il disegno di gra� con modelli �sici.

Il concetto è semplice. Il tempo di computazione dell'algoritmo è dominato,

in ogni iterazione, dal calcolo delle forze di repulsione tra ognuna delle |V |2

coppie di nodi; nondimeno, la stragrande maggioranza di queste interazioni

saranno trascurabili � poiché i nodi saranno molto distanti fra loro, e la forza

sarà scarsa. Pertanto, l'idea è ovvia: computare le forze repulsive soltanto fra i

nodi che si trovano ad una distanza fra loro minore di una certa soglia. Per fare

ciò, si suddivide all'inizio di ogni iterazione l'area disegnata in un certo numero

di celle quadrate di area R2, con R una distanza arbitraria proporzionata a k;

quindi, analizzando le forze repulsive agenti su di un nodo, si prenderanno in

considerazione solamente i nodi appartenenti alla sua stessa cella ed alle otto

celle adiacenti. Questo permette di ridurre il numero di forze da calcolare, e

quindi il tempo di calcolo. Il valore di R usato in questo algoritmo deve essere

proporzionale al livello analizzato: più il grafo in esame è a grossa scala � ed

ha quindi pochi nodi � più ci si può permettere un valore elevato di R. Il valore

proposto � in seguito alle varie prove dell'autore � è di 2(l + 1)kl dove l è il

livello in esame.

L'implementazione di un meccanismo di questo tipo non è però banale. Wal-

shaw suggerisce di usare delle liste concatenate per memorizzare il contenuto di

ogni cella (va notato infatti che l'insieme di queste liste avrà |V | elementi, un

numero non trascurabile); per memorizzare invece questo insieme di celle in mo-

do da recuperare velocemente quelle adiacenti, viene usata una struttura dati

ad albero, memorizzando però solamente le celle non vuote; infatti, il numero di

celle vuote è elevato e la loro memorizzazione può rendere di�coltosa la gestione


dell'insieme di liste.

3.3.4 Aspettative da questo metodo

Un metodo di questo genere è il frutto di un insieme di molte ottimizzazioni,

innestate sulla base di un algoritmo a modello �sico. Per questo motivo, esso

presenta i difetti di cui parlavano Harel e Koren nella presentazione del loro

metodo: un alto numero di parametri da calibrare e una elevata complessità

nell'implementazione, che è necessariamente molto ricca di particolari. Inoltre,

le tempistiche riportate dall'autore sono maggiori di vari ordini di grandezza

rispetto a quelle dell'algoritmo precedente.

Nonostante tutto questo però, secondo quanto riportato da entrambe le ricer-

che, questo algoritmo o�rirebbe qualità estetiche maggiori rispetto all'approccio

multidimensionale. Va inoltre detto che i parametri e i dettagli dell'implemen-

tazione vengono già �nemente analizzati dall'autore, evitando quindi di dover

reiniziare il processo di calibrazione da zero. La ricchezza di particolarità im-

plementative, inoltre, è anche un vantaggio, rendendo più immediato e�ettuare

piccole variazioni sul tema, senza sradicare del tutto grosse parti dell processo: i

gra� da noi trattati potrebbero non essere dello stesso tipo di quelli sperimentati

dagli autori, e lo stesso Walshaw suggerisce di mettere alla prova e modi�care

l'algoritmo di conseguenza, per adattarlo ai propri scopi.

Capitolo 4

L'applicazione

50

CAPITOLO 4. L'APPLICAZIONE 51

4.1 Architettura dell'applicativo

Abbiamo illustrato nei capitoli precedenti il problema che ci siamo posti � la

visualizzazione di un grafo sociale di grandi dimensioni � e gli strumenti, teorici

e pratici, che lo stato dell'arte mette a nostra disposizione per a�rontarlo. In

questo capitolo ci proponiamo di descrivere l'applicazione che ne è risultata,

nonché come � e con quali risultati � essa ha messo in pratica gli strumenti

teorici descritti nel capitolo precedente.

A questo scopo, illustreremo per prima cosa l'architettura generale dell'ap-

plicativo.

Figura 4.1: Schema informale dell'applicazione

Graphical UserInterface

GraphDrawer

Layout

ProcessingApplet

Perlin NoiseNode DisplacerColor Mapping

File del grafo di input, algoritmo da usare

Opzioni e navigazione

Definizione della

Color Map

DisegnaDisegna

Sfalsamentodelle coordinate

Entità dellosfalsamento

Avvia

Coordinatedei nodi

Coloridei nodi

Lo schema qui esposto vuole essere una �mappa� delle parti principali del no-

stro software; essa ci servirà da guida mentre ne traccieremo un quadro generale,

attraverso una breve analisi di queste componenti1.

1Non si pensi che queste componenti corrispondano alle classi Java dell'applicazione; essacontiene infatti più di 40 classi, per un totale di oltre 6000 righe di codice.


Processing Applet e Graphical User Interface. Il punto di partenza (in

grigio scuro nello schema) è l'applet di Processing; come abbiamo spiegato nella

sezione 2.2.2, è infatti Processing a gestire i vari thread all'interno di una sua

applicazione. In particolare, esso si occupa del disegno di ogni frame e gestisce i

dispositivi di input dell'utente; in questi due eventi � frame e ricezione di input

� viene posta in essere la Graphical User Interface del programma: Processing

costituisce così un unico thread, proprio dell'interfaccia utente. Essa viene conti-

nuamente ridisegnata � chiamando i metodi messi a disposizione dalla applet di

Processing � mentre interagendo con essa è possibile speci�care le varie opzioni

ed i dati di input.

Graph Drawer. Una volta che la GUI ha ricevuto tutti i dati di input, ini-

zializzando così gli oggetti chiamati a gestirli, essa lancia il secondo thread del

programma, la classe GraphDrawer; esso si occupa esclusivamente del disegno

del grafo. Questa rigida separazione tra i due thread (entrambi in grigio chiaro

nello schema) è resa necessaria dalla necessità di combinare il disegno di una

interfaccia utente, necessariamente dinamica, ed il disegno di milioni di nodi di

un grafo � che sarebbe impensabile rieseguire ad ogni frame. In questo modo, il

thread della GUI ripeterà il disegno ad ogni frame � in modo da visualizzare il

movimento di uno slider o la pressione di un pulsante � mentre il GraphDrawer

agirà solamente quando necessario: esso eseguirà il disegno all'inizio non appe-

na sarà possibile, dopodiché cadrà in stato di wait e verrà risvegliato dalla GUI

solamente quando l'utente avrà richiesto un disegno nuovo e di�erente.

Layout. Tuttavia, la classe del GraphDrawer non ha il compito di ricavare, da

sola, tutta la grande quantità di dati necessaria per il disegno del grafo. Essa

prende � quando vengono richiesti � i dati necessari dai vari oggetti inizializzati

dall'interfaccia utente, e li traduce in una serie di comandi di disegno eseguiti

dalla applet di Processing. Tra questi oggetti, il più importante � e forse vero

cuore dell'applicazione � è la classe Layout. Essa è la parte del programma che si

occupa realmente di prendere in input il �le del grafo ed associare ogni suo nodo

ad una coppia di coordinate; parleremo più di�usamente del suo funzionamento

più avanti.


Color Mapping. A �anco di questa classe fondamentale, si rendono neces-

sarie altre informazioni per un disegno completo: prima di tutto, assegnare un

colore di ogni nodo è di fondamentale importanza per moltissime applicazioni

pratiche � e anche per giudicare l'e�cacia degli algoritmi di disegno nel rag-

gruppare nodi logicamente prossimi. Questa funzionalità viene implementata

attraverso una classe ColorMapping, richiamabile dalla GUI, che può produrre

una mappa di colori per un certo grafo a partire da varie informazioni; tipica-

mente, essa assegna un colore ad ogni dominio (o ad ogni sottocartella di un

dominio). Questa color map viene salvata in un �le e verrà quindi letta dal

GraphDrawer quando esso dovrà disegnare un nodo.

Perlin Noise Node Displacer. Questa classe permette di evitare, qualora la

classe Layout determini coordinate identiche per un gruppo di nodi, di disegnarli

tutti nel medesimo punto. È possibile infatti sfalsare ogni nodo rispetto alla

posizione calcolata per esso dall'algoritmo di layout, aggiungendo ad essa un

rumore di Perlin2 che vari di nodo in nodo, rimanendo però costante per un dato

vertice anche in di�erenti interrogazioni. Questa aggiunta, senza considerevoli

costi computazionali, trasforma quei gruppi di nodi che dovrebbero occupare il

medesimo punto del disegno in una �nube� di nodi di diametro arbitrario; in

particolare, la classe Layout può essa stessa �ssare la dimensione della nube a

cui un singolo nodo appartiene � vedremo in seguito meglio il perché.

4.2 Layout e algoritmi

Come abbiamo detto, la classe Layout ha per scopo fornire una coppia di coor-

dinate (x, y) per ogni nodo di un grafo dato. È chiaro che � come abbiamo visto

nel capitolo 3 � esistono moltissimi modi per e�ettuare questa associazione, ed

essi sono per l'appunto gli algoritmi di layout.

Ci è sembrato estremamente importante implementare quindi questa classe

in modo che fosse molto �essibile e soprattutto estensibile. Per farlo, si è scelto

2Il Perlin Noise è un generatore di sequenze pseudocasuali capace di produrre una succes-sione numerica particolarmente naturale ed armonica. È stato inventato da Ken Perlin neglianni '80 e da allora se ne è fatto largo uso nella computer graphics per creare più realistica-mente textures, movimenti naturali, forme ed oggetti come terreni, �amme, e così via. Unasua implementazione è inclusa in Processing.


di creare uno scheletro di funzioni che fossero indispensabili per integrare un al-

goritmo di layout all'interno del nostro software, e di realizzare questo scheletro

come la classe astratta Layout. Essa infatti non dà, di per sé, nessuna informa-

zione su come associare le coordinate a dei nodi, ma contiene i metodi necessari

per realizzare la maggior parte degli algoritmi (come getUndirectedGraph(),

che rende simmetrico il grafo in input) e soprattutto contiene i metodi per adat-

tare delle coordinate generiche alla �nestra speci�cata dall'utente, e per navigare

all'interno di questa visualizzazione.

Poiché è una classe astratta, essa viene quindi ride�nita da un certo numero

di sottoclassi, che rappresentano diversi algoritmi di disegno del grafo: sarà poi

l'utente a speci�care quale usare, all'interno di quelli disponibili. Ogni sotto-

classe in questo modo contiene unicamente l'algoritmo in questione, e dovrà re-

stituire semplicemente delle coordinate generiche: sarà poi la classe Layout ori-

ginale a permettere di inquadrare nella �nestra queste coordinate, calcolandone

eventuali trasformazioni � zoom, traslazioni e così via.

Uno dei compiti fondamentali di questa classe astratta è inoltre, una volta

che l'algoritmo vero e proprio ha computato le coordinate del grafo, quello di

scrivere queste ultime in un �le *.graphlayout. Questo permette di evitare ogni

calcolo alla successiva apertura del grafo, leggendo direttamente questi valori

dal disco; questo anche se un eventuale nuovo algoritmo non implementasse, di

per sé, alcun salvataggio di informazioni. In ogni caso, quelli da noi realizzati

salvano � in forma binaria, evitando sprechi di memoria � i dati intermedi che

richiedono un lungo tempo di calcolo, in modo da replicare se necessario tutta

l'informazione che essi mettono a disposizione, anche al di là delle semplici

coordinate �nali; per esempio, le coordinate multidimensionali dell'algoritmo di

Harel-Koren che permettono di osservare da diverse prospettive il grafo (come

abbiamo anticipato nella sezione 3.2.3).

Layout mette anche a disposizione delle sue sottoclassi una mappa chiamata

UserActions; tramite questa un algoritmo può speci�care quali azioni l'uten-

te può compiere una volta che il layout è stato calcolato. Queste azioni, che

nell'implementazione di un algoritmo vengono speci�cate semplicemente come

dei metodi, verranno automaticamente resi dalla GUI come dei pulsanti. Ad

esempio, usando il metodo di Harel-Koren verranno mostrati dei comandi per


cambiare le componenti principali in uso, permettendo all'utente di sfruttare le

coordinate multidimensionali per cercare una visualizzazione migliore.

In questo modo si è cercato di rendere il più semplice possibile l'implemen-

tazione di nuovi algoritmi di posizionamento all'interno della cornice da noi

sviluppata; i nostri risultati sono sicuramente perfettibili, ma i pilastri su cui si

poggia il nostro software � il framework di WebGraph e la capacità gra�ca di

Processing � lo rendono, speriamo, una buona base di partenza per lo sviluppo

futuro di nuovi metodi di disegno di gra� di grandi dimensioni.

Vediamo quindi ora quali risultati abbiamo ottenuto nell'applicazione dei

due algoritmi principali dell'applicazione, illustrati nel capitolo 3.

4.2.1 Implementazione e risultati dell'algoritmo di Harel-

Koren

4.2.1.1 Risultati

I risultati del metodo multidimensionale dal punto di vista della velocità hanno

soddisfatto le aspettative, nonostante in alcune parti l'ottimizzazione del co-

dice o�ra dei margini di miglioramento. Di seguito riportiamo le tempistiche

ottenute3:

|V | |E| thdl tpca ttotale

67521 508263 16� 6� 22�

325557 3216152 2' 48� 38� 3' 26�

Tuttavia, i risultati del disegno si sono rivelati sotto certi aspetti inadeguati

da un punto di vista estetico ed informativo, specialmente per quanto riguarda

i gra� del web (per esempio, i disegni computati non hanno raggruppato le

pagine degli stessi siti). Le cause sono diverse: prima di tutto, la struttura � o

meglio, la mancanza di una struttura forte � esistente nei gra� da noi analizzati.

Infatti, i risultati migliori riportati nella ricerca di Harel e Koren sono per lo più

gra� mesh-based, ricavati dagli spigoli e dai vertici di una super�cie di qualche

genere, come ad esempio tori o sfere, eventualmente con insiemi di archi o vertici

aggiunti o rimossi; da questo genere di grafo, questo processo riesce comunque

a risalire in qualche modo al solido (od al politopo) originario o ad una sua

3Qui e dove non riportato diversamente, i test sono stati eseguiti su di un Intel Core 2 Duoa 2,53 GHz con Java 1.6.0_17


approssimazione, visualizzandone il grafo di conseguenza. I gra� privi di una

struttura così ben de�nita, come generalmente quelli da noi trattati, si sono

rivelati poco adatti all'algoritmo: la cinquantina di dimensioni ricavate da dei

punti campione è emerso essere un'informazione troppo scarsa per descrivere

la forma che dovrebbe assumere, quasi come se guardando il grafo da questi

(relativamente) pochi punti di vista non si riuscisse nemmeno ad intuire quale

siano le piccole strutture che si nascondono in esso.

In particolare, molti dei nodi del grafo risultano avere dei valori simili od

identici in tutte le coordinate trovate dal disegno multidimensionale, il che si

traduce in una coppia di coordinate (x, y) identiche o quasi, ed in una quantità

di nodi ammassati nel medesimo punto; questo accade perché può capitare che

nodi diversi, in un grafo così grande, �niscano col trovarsi a distanze molto

elevate dai pivot � scelti proprio per la loro lontananza � e la distanza da essi

non può coglierne, da sola, la posizione che essi occupano nella conformazione

della particolare zona in cui essi si trovano. Immaginiamo di dover mappare

le stazioni ferroviarie vicine a quella di Milano Lambrate; se, per disegnarne la

piantina, scegliessimo di misurare per ogni stazione la distanza dalla stazione

di Mosca e dalla stazione di Pechino � e, per rendere il paragone più preciso,

questa distanza venisse misurata come numero di stazioni intermedie � molto

probabilmente il nostro disegno faticherà molto a distinguere le singole stazioni

milanesi: questo è esattamente ciò che avviene quando si tenta di visualizzare

una piccola parte del grafo molto lontana dall'insieme dei pivot.

Una conferma di questa inadeguatezza ed una ulterore causa va ricercata

nell'assetto ad albero � molto abbozzato � che presentano i gra� del web, anche

in virtù del meccanismo di crawling con cui sono spesso ottenuti. Il meto-

do Harel-Koren viene infatti già presentato dagli autori come inadatto ad una

struttura ad albero: la mancanza di un pivot nei sottoalberi provoca infatti una

rappresentazione schiacciata e compressa, quasi una linea, poiché questa man-

canza corrisponde appunto all'assenza di un punto di vista valido che consenta

di distinguere le sue rami�cazioni.

Il grande contenuto statistico e informativo di un simile disegno non è però

del tutto privo di sbocchi. Nei gra� sociali più densi (tallone d'Achille di ogni al-

goritmo di disegno) questo metodo � pur non riuscendo, come detto, a disegnare


le piccole zone del grafo � riesce a darne, considerando la grande complessità

di questi gra�, una rappresentazione di insieme abbastanza valida. Distingue

infatti, perlomeno, le zone principali in cui il grafo potrebbe essere suddiviso:

una zona densamente connessa viene posta al centro del grafo, dando origine

ad un grande ed indistinguibile ammasso di nodi; essa solitamente contiene la

maggior parte degli hub, i quali sono spesso prossimi fra loro, formando al suo

interno delle zone ancora più densamente connesse. Subito oltre questo nucleo

centrale si riesce spesso a distinguere una �periferia� del grafo, con nodi meno

densamente connessi � e quindi rappresentati in modo più sparso � i quali sono

perà tutti posti a una distanza simile dal nucleo. In�ne, si possono facilmente

distinguere in molti di questi gra� dei �tentacoli� che partono da questo nucleo,

i quali sono appunto una rappresentazione e�cace di una catena di nodi che

è unita alla zona densamente connessa solo tramite un piccolo sottoinsieme di

vertici.

Indagare queste aree al loro interno è però, come abbiamo detto, di�cile

con questo algoritmo � la disposizione dei singoli nodi nelle aree più fortemente

connesse è decisamente caotica; e questo lo rende particolarmente inadatto per la

visulizzazione di gra� del web, ricchi di microstrutture degne di nota. Tuttavia,

rendere visivamente in un tempo accettabile i gra� sociali da noi considerati �

molto connessi, a invarianza di scala, poco strutturati, e con grande numero di

nodi (dell'ordine di 106) � non è un obiettivo facile; la visualizzazione globale di

questa enorme struttura che siamo riusciti ad ottenere con questo algoritmo è,

in queste condizioni, di e�cacia e signi�catività non trascurabile.

4.2.1.2 Modi�che e sperimentazioni

Appurato che il disegno multidimensionale di un grafo sociale risente molto della

scelta dei pivot, è stato ritenuto oppurtuno compiere qualche sperimentazione

a riguardo. Una prima idea è stata provare a scegliere un numero maggiore di

questi centri, in modo da introdurre nuove dimensioni che potessero dare una

risoluzione valida ad ogni rami�cazione del grafo; purtroppo, questo test non

ha portato a dei risultati signi�cativi: aumentando il parametro m si ottengono

infatti dei tempi di computazione enormemente più grandi (i due sottoprocessi

dispendiosi, la BFS e il calcolo della matrice di covarianza, hanno infatti un


Figura 4.2: Algoritmo di Harel-Koren - sottografo di DBLP

Il disegno computato dall'algoritmo di Harel-Koren; sono state scelte la primae la terza componente principale; i pivot sono stati designati con il metodooriginale di Harel e Koren, utilizzando però come primo nodo quello con indice dipagerank maggiore. Il grafo è un sottoinsieme connesso di 226413 nodi ricavatodal database di collaborazioni scienti�che DBLP (http://dblp.uni-trier.de).

Figura 4.3: Dettaglio della �gura 4.2: un �tentacolo�

Ingrandimento del �tentacolo� in basso a destra. Questo sottografo è unito al�nucleo� da un insieme relativamente piccolo dei suoi nodi, e pertanto viene dise-gnato dall'algoritmo in questo modo, creando un ��lamento� in cui i vertici sonodisposti in maniera proporzionale alla distanza dall'ammasso centrale. Notiamoche questo corrisponde ad una dimensione del disegno multidimensionale.


Figura 4.4: Dettaglio della �gura 4.2: il �nucleo� �ltrato

Ingrandimento del �nucleo�, applicando un �ltro per visualizzare unicamente inodi con più di 60 archi; in questo modo evidenziamo la presenza degli hub ecome questi siano stati raggruppati dall'algoritmo di Harel-Koren.

tempo di esecuzione proporzionale ad m e ad m2, rispettivamente) a fronte

di risultati qualitativi solo di poco migliori. Questi i risultati con m = 150

(triplicato quindi rispetto al suo valore precedente):

|V | |E| thdl tpca ttotale

67521 508263 48� 1' 43� 2' 31�

325557 3216152 8' 2� 10' 53� 18' 55�

Se per riuscire ad ottenere un incremento apprezzabile della qualità del dise-

gno bisognerebbe aumentare l'ordine di grandezza dim, questo è reso impossibile

dai tempi computazionali proibitivi che questo avrebbe; un aumento di m che

possa comunque essere calcolato in tempi ragionevoli è invece quasi inin�uente

nei risultati.

Un altro approccio è stato studiare quanto in�uisca il criterio di scelta dei

pivot. Per prima cosa, è stato osservato cosa succede imponendo una scelta

casuale di questi dall'insieme dei nodi V. Il risultato è stato uno stravolgimento

del layout : poiché nessuno o quasi di essi è riuscito a fornire un punto di vista

signi�cativo sul grafo la disposizione risultante è stata unicamente un caotico


aggrovigliarsi di nodi. Questo ha provato però che la scelta dei pivot è fonda-

mentale, e che è proprio la loro posizione nel grafo a fornire una chiave di lettura

che porta poi al disegno �nale. Di conseguenza, sono stati e�ettuati diversi ten-

tativi, come provare ad usare come pivot i nodi del grafo con il pagerank più alto

(calcolandolo tramite le librerie sviluppate all'interno del LAW da Paolo Boldi,

Massimo Santini e Sebastiano Vigna); oppure usare i nodi con più connessioni,

per tentare di trovare quegli hub propri dei gra� sociali; o ancora, mescolare

i pivot individuati da queste tecniche con quelli scelti dell'algoritmo originale.

In ogni caso anche queste diverse visualizzazioni, pur con discreti risultati, non

hanno risolto i problemi sopra elencati.

Si è quindi scelto di proseguire nell'implementazione di un algoritmo alter-

nativo, implementando nel mentre un meccanismo immediato e quasi privo di

costi per correggere la sovrapposizione dei nodi: lo sfalsamento dei nodi basato

sul rumore di Perlin. Per riuscire infatti ad evitare che l'a�ollarsi di vertici

nel medesimo punto rendesse illeggibile il disegno, è stato implementato questo

semplice ma e�cace meccanismo � di notevole utilità nel rendere comprensibile

per l'utente il numero di nodi presenti in una certa area, e la distribuzione degli

archi a loro associati. I risultati ottenuti in questo modo � nei quali è possibile

riconoscere gli elementi descritti precedentemente � sono riportati nelle �gure

4.2, 4.3 e 4.4.

4.2.2 Implementazione e risultati dell'algoritmo di Wal-

shaw

4.2.2.1 Implementazione e variazioni apportate

Generazione della gerarchia multiscala. Come abbiamo detto nella se-

zione 3.3.4, mentre il metodo di Harel-Koren è piuttosto monolitico � pochi

parametri da de�nire, poche le scelte implementative da e�ettuare � quello di

Walshaw è molto più ricco di particolari e di possibilità di variazioni. Questo

si è rivelato molto importante: di per sé, l'algoritmo di Walshaw non avrebbe

potuto funzionare con il tipo di gra� da noi studiato.

Il cuore del problema risiede nell'algoritmo di coarsening (sez. 3.3.2); esso in-

fatti deve, per funzionare, riuscire a produrre una serie di gra� G0, G1, G2 · · ·GL


in cui il numero di nodi diminuisca progressivamente: ogni nodo di Gi+1 do-

vrebbe contenere � in media � due nodi di Gi. Se ne contenesse molti di più,

i vantaggi della gerarchia multiscala scomparirebbero: il metodo di Walshaw ci

assicura però che questo è impossibile, poiché impedisce di raggruppare più di

due nodi di Gi nello stesso nodo di Gi+1; ma proprio questo vincolo, nei gra�

di nostro interesse, �nisce con il provocare quasi sempre il caso contrario: una

grande quantità di nodi di Gi che non vengono associati, rimanendo tali e quali

in Gi+1. Questo fa sì che il numero di nodi di Gi+1 sia molto simile al numero

di nodi di Gi, causando una catena G0, G1, G2 · · ·GL lunghissima o addirittu-

ra in�nita � poiché spesso dopo qualche passaggio di coarsening si �nisce con

l'ottenere |Vi+1| = |Vi|.

Per capire per quale motivo accade questo, osserviamo la �gura 4.5. Con essa

possiamo vedere cosa accade ad un grafo quando su di esso opera l'algoritmo

di coarsening di Walshaw; i numeri di ogni nodo indicano l'ordine con cui essi

vengono visitati, e sono del tutto arbitrari. Il nodo 1 viene visitato, si e�ettua

il matching con il nodo 2, ed entrambi vengono rimossi dalla lista dei nodi

disponibili, formando un unico nodo cluster in Gi+1; si procede così per tutti

i nodi rimasti. Così facendo, molti nodi (7, 8, 13, 16 ecc.) restano privi di un

nodo disponibile con il quale unirsi.

Bisogna evidenziare come con i nostri gra� il problema divenga ben più

grave. Questo per due ragioni: per prima cosa, casi come quello del nodo 6

o del nodo 14 � un nodo solo collegato ad una moltitudine di nodi di grado

minore � sono molto più frequenti e la disparità tra i gradi dei due nodi è

molto più grande: come abbiamo avuto già modo di a�ermare, i gradi in un

grafo sociale seguono una distribuzione a legge di potenza ed esisteranno alcuni

nodi collegati ad un numero di archi esponenzialmente più grande degli altri.

Pensiamo ad esempio al nodo 14 della �gura come ad una homepage di un

motore di ricerca: essa sarà collegata e collegherà una miriade di altre pagine,

che saranno tutte molto meno importanti in termini di numero di link. In

secondo luogo, questo algoritmo di raggruppamento viene applicato in serie,

e questo ampli�ca la gravità di questi casi: se pensiamo ad esempio al nodo

http://www.google.it, collegato a migliaia di pagine, questo algoritmo farà sì

che in un singolo passaggio tra Gi e Gi+1 questo nodo venga collegato ad una


ed una sola di esse: ci vorrebbero quindi migliaia di gra� intermedi prima di

giungere a quello di dimensione minima.

Pertanto, la decisione più ovvia è sembrata tentare di associare più di due

nodi alla volta; ovvero, quando nel grafo Gi si visita il nodo A e si decide di

unirlo con il nodo B, non rimuoveremo sia il nodo A che il nodo B dalla lista dei

nodi disponibili; invece, lasceremo il nodo B nella lista � ovviamente, evitando

di visitarlo ancora � in modo che altri nodi si possano unire ad esso, in caso

siano esauriti i loro vicini normalmente associabili. Notiamo che � per evitare

sprechi di memoria � durante l'unione di A e B, nella tabella che indica in quale

nuovo nodo �nisce il nodo A scriveremo l'indice di B, mentre il nodo B andrà a

�nire banalmente nel nodo B stesso; in altre parole, il nodo A verrà �innestato�

sul nodo B, e non il contrario.

La �gura 4.6a ci permette di vedere cosa accade con questo nuovo algorit-

mo: i nodi 7 e 8 riescono ora ad unirsi immediatamente al nodo 6; anche qui,

possiamo immaginare 6 come un caso più consistente, come ad esempio una

persona particolarmente in vista, con migliaia di contatti, in un grafo sociale:

il miglioramento è quindi consistente. Ciò nonostante, questa aggiunta non ha

toccato la sitazione del nodo 14; questo perché quando si visita questo nodo

lo si unisce al nodo 15, lasciando solamente quest'ultimo � e non il nodo 14

� disponibile per altre associazioni (notiamo che e�ettuando la scelta opposta,

ovvero lasciando il nodo A nella lista e rimuovendo B, il medesimo problema si

sposterebbe sui nodi 6, 7, 8).

La soluzione è però intuibile: prima di unire un nodo ad un altro, basta

confrontare i gradi dei due nodi. Il nodo caratterizzato dal grado maggiore sarà

più probabilmente utile per associarvi altri nodi in seguito � come il nodo 14 �

ed è conveniente lasciare quest'ultimo nella lista dei nodi disponibili; se quindi

degree(A) > degree(B) allora �innesteremo� il nodo B sul nodo A, mantenendo

quest'ultimo disponibile. Osservando la �gura 4.6b, notiamo come questo risolva

anche il problema del nodo 14: l'algoritmo, quando unisce il nodo 14 ed il nodo

15, riconosce il primo come più importante e lo preserva per riassociarlo in se-

guito. Se pensiamo al nostro caso reale � un nodo come http://www.google.it

� abbiamo evitato le migliaia di gra� intermedi che ci sbarravano il passo.

Potrebbe sembrare che così facendo siamo caduti nel caso opposto: in un


Figura 4.5: Algoritmo di coarsening : grafo di partenza e algoritmo originale

2

3

4

5

6

8

1

7

9

10

11

1213

16

17

18

19

15

20 2122

14

2

3

4

5

6

8

1

7

9

10

11

1213

16

17

18

19

15

20 2122

14

Figura 4.6: Modi�ca dell'algoritmo: associazioni multiple

a

2

3

4

5

6

8

1

7

9

10

11

1213

16

17

18

19

15

20 2122

14

b

2

3

4

5

6

8

1

7

9

10

11

1213

16

17

18

19

15

20 21

22

14


singolo passaggio stiamo unendo troppi nodi, eliminando i vantaggi della logica

multiscala. Tuttavia, proprio questa particolare conformazione dei gra� da noi

analizzati suggerisce che non sia così. In essi, singoli nodi spesso hanno gradi

molto più alti di quelli circostanti, ma questo non è casuale: segnala che questi

rivestono di una certa importanza logica presso i vicini � nello studio di gra�

sociali essi vengono chiamati hub � e possono essere considerati a ragione dei

cluster in cui raggrupparli.

Uso della gerarchia multiscala. Questa modi�ca rende funzionante il mec-

canismo di coarsening : esso riesce a produrre una serie di gra� G0 · · ·GL, in

cui ogni grafo è una versione a scala più grossa del precedente; ognuno di essi è

accompagnato da un �le che permette di associare i suoi nodi a quelli del grafo

precedente e da uno contenente il peso di ogni suo nodo (ovvero, ricordiamo, il

numero di nodi di G0 in esso contenuti).

A questo punto dovremmo applicare ad ognuno di questi gra� l'algoritmo a

modello �sico descritto nella sezione 3.3.3. I tempi che siamo riusciti ad ottenere

però con la nostra implementazione � priva, del resto, della so�sticata variante

a celle usata da Walshaw � rendono molto lento il procedere �no ai milioni

di nodi del grafo originale G0. E anche se si potrebbe certamente riuscire ad

implementare un sistema per migliorare la risoluzione di questo problema ad n-

corpi, dobbiamo comunque prestare attenzione alle tempistiche riportate negli

articoli [31, 14]: un grafo di 105 o 106 nodi non potrebbe essere disegnato in meno

di 10 minuti; e questa, ricordiamo, è indicata da Harel e Koren come la più veloce

implementazione di un paradigma multiscala a modello �sico. Riuscire quindi

anche a rendere la nostra implementazione il più avanzata possibile lascerebbe

comunque, per i gra� delle dimensioni con cui ci proponiamo di lavorare, delle

tempistiche davvero poco sostenibili.

Nonostante questo, il nostro modello �sico riesce comunque velocemente a

calcolare una disposizione per i primi gra� della serie (GL, GL−1, GL−2 . . .).

In particolare, �no a circa un migliaio di nodi l'algoritmo si comporta bene e

restituisce un layout in meno di un minuto.

Riuscire a computare la gerarchia multiscala �no ad avere un disegno valido

per un grafo intermedio ci fornisce comunque un'informazione non da poco: un


grafo Gi con un migliaio di nodi non è altro che una vista globale, a grossa

scala, del nostro grafo originale G0. Se quest'ultimo ha 106 nodi, ad esempio,

ogni nodo di Gi corrisponde a circa mille nodi del grafo originale; e, abbiamo

detto, noi possediamo una tabella di matching che associa ad un nodo di Gi

ogni nodo dei gra� a scala più �ne, �no a G0. Esprimendola come funzione essa

è:

Mi : V → Vi

E possiamo computare un layout per Gi:

LGi: Vi → R2

Questo ci permette di trasformare il nostro disegno di Gi in un vero e pro-

prio disegno di G0, sfruttando il Perlin Noise Node Displacer. Se infatti noi

uniamo le due funzioni di cui sopra nella funzione di layout LGi ◦Mi, possiamo

disegnare ogni nodo del grafo originale G0 nelle coordinate che abbiamo trovato

per il nodo di Gi che lo contiene. Questo disegno sovrapporrà però tutti i nodi

di G0 che si trovano nel medesimo nodo cluster di Gi: per questo motivo ci è

di nuovo utile il Perlin Noise Node Displacer. Sfalseremo infatti le coordinate

dei nodi in modo che non occupino la medesima posizione, ma vengano disposti

pseudocasualmente in varie �nubi� (si veda pag. 53); ognuna avrà centro nel

punto calcolato per il nodo di Gi corrispondente. Possiamo anche determinare

l'entità dello sfalsamento, ovvero il diametro di ogni nube: esso sarà dato sem-

plicemente dal peso di quel nodo a grossa scala, cioè dal numero di nodi originali

che questa nube dovrà contenere. Basterà che al nodo v, contenuto nel nodo v′

di Gi, imporremo uno sfalsamento Sv tale che sia Sv ∝√peso(v′) per avere,

all'interno delle diverse nubi, una densità più o meno costante di vertici.

Questa semplice soluzione ci permette di ottenere una vista globale di G0,

con un tempo di computazione sostenibile. Ovviamente, il problema di una

simile visualizzazione è che all'interno di ogni �nube� i nodi non sono disposti

correttamente ma pseudocasualmente; tuttavia, queste disposizioni a scala più

piccola del grafo sono piuttosto inin�uenti nella visualizzazione a grossa scala:

anche se fossimo riusciti a disporle correttamente, nella vista di insieme queste

particolarità ci sarebbero sfuggite. È vero, d'altra parte, che a noi interessa an-


che esplorare il grafo nelle sue piccolezze e andarne a vedere e distinguere i singoli

nodi: ma se da una visualizzazione come questa non sarebbe possibile, possiamo

sfruttare l'interattività che il software mette a disposizione. Basterà ingrandire

un'area del disegno globale per evidenziarne una microstruttura; ricalcolando

il layout limitatamente a questa area più piccola potremo distinguere tutti i

suoi dettagli, raggruppando anche qui il sottografo che abbiamo evidenziato in

una sua versione ad un migliaio di nodi; il procedimento può essere ovviamente

ripetuto a piacere. Il problema iniziale � calcolare un layout per milioni di nodi

� diviene quindi perfettamente a�rontabile, semplicemente scomponendolo in

una serie di sottoproblemi � disporre un migliaio di cluster con un algoritmo

e�cace, e i nodi al loro interno in modo casuale. Selezionando di volta in volta

la scala del sottoproblema riusciremo a ottenere, interattivamente, quello di cui

l'utente ha bisogno.

4.2.2.2 Risultati dell'algoritmo

Questo procedimento ha dato dei buoni risultati nella visualizzazione dei gra�

del web. In particolare, le strutture simili ad alberi sono spesso ben visibi-

li, persino a scale molto grosse. Ad esempio, l'algoritmo raggruppa spesso in

maniera molto chiara le pagine di uno stesso sito; se vari siti, di diversa impor-

tanza, sono ordinati nel grafo in modo somigliante ad un albero, questo viene

reso gra�camente attraverso una adeguata disposizione dei loro gruppi di pa-

gine. Riportiamo come esempio in �g. 4.7 la prima disposizione calcolata, in

modo totalmente automatico, per il grafo cnr20004 di 325557 nodi; per maggio-

re chiarezza, gli archi sono stati omessi. La cromaticità è da interpretare come

un'associazione tra un colore ed una sottocartella di un dominio (per esempio, le

sottopagine di http://www.unimi.it/studenti/ avrebbero un colore, mentre

quelle di http://www.unimi.it/didattica/ un altro).

Le strutture più piccole vengono evidenziate e calcolate correttamente, una

volta selezionata la sottoarea di interesse. I siti web che presentano una struttura

di qualche genere vengono mostrati in maniera ordinata; un caso tipico è una

homepage che collega tra loro una grande quantità di sottopagine, che viene

resa come un cerchio di sottopagine con al centro la pagina principale (�g.

4Parte dei dataset del LAW, è disponibile su http://nexus.law.dsi.unimi.it/webdata/

cnr-2000/


Figura 4.7: Il grafo cnr-2000

4.9). È stato comunque possibile individuare anche strutture più curiose nel

disegno del grafo; abbiamo notato come esse siano spesso espressione di una

particolare struttura dei collegamenti all'interno di un sito. L'esempio in �g.

4.8, costituito da un frammento ingrandito e ricomputato del grafo di cui sopra,

è dovuto ad un sito web in cui la navigazione tra le pagine di contenuti � i

nodi al centro � è aiutata dalla presenza di due calendari � le �gure a destra

e a sinistra. All'interno di queste ultime possiamo identi�care un centro � la

pagina principale di navigazione del calendario � e delle altre forme, identiche

nella disposizione tra i due calendari; esse corrispondono ai mesi (nell'arco di

più anni) all'interno del calendario.

Questo banale esempio ci può aiutare a comprendere come è possibile dare

un senso ad alcune conformazioni particolari di un certo grafo, semplicemente

guardando ed esplorando il disegno (completo di informazioni accessorie, come

gli URL) che viene computato dal nostro piccolo software.


Figura 4.8: Strutture all'interno del grafo cnr-2000

Figura 4.9: Altre microstrutture all'interno del grafo cnr-2000

Un insieme di 3341 nodi ingrandito e ricalcolato; un colore qui rappresentauna singola cartella del tipo http://dominio/dir/dir; si noti quindi come lepagine appartenenti alle diverse sottoaree così de�nite siano state automatica-mente raggruppate dall'algoritmo di layout ; la computazione di quest'ultimoovviamente non ha considerato gli URL o altri metadati, per non perdere ingeneralità.


Figura 4.10: Sottografo di india-2004: vista globale di 400065 nodi

Un sottografo tratto da un crawling delle pagine con dominio .in disponibilesu http://nexus.law.dsi.unimi.it/webdata/in-2004/. Gli archi sono statiomessi; un dominio è associato ad un colore.

Figura 4.11: Microstrutture all'interno del grafo india-2004: 5211 nodi

Un dettaglio, ingrandito e ricomputato, del grafo in �g. 4.10; qui, ogni colore èassociato ad una subdirectory di quarto livello di un dominio.

Capitolo 5

Conclusioni e futuri sviluppi

70

CAPITOLO 5. CONCLUSIONI E FUTURI SVILUPPI 71

5.1 Lavoro svolto

Lo scopo della nostra attività era realizzare uno strumento che potesse visua-

lizzare un grafo sociale. Prima di iniziare, ci siamo pre�ssati vari obiettivi: una

visualizzazione interattiva, tale da permettere non solo di vedere, ma anche di

esplorare ed indagare; ma, al contempo, la capacità di lavorare con gra� di

grandi dimensioni.

Oltre a questi obiettivi � irrinunciabili � è emersa anche la volontà di costrui-

re qualcosa che rappresentasse un grande grafo nel suo complesso, fornendo una

sorta di vista d'insieme. L'idea di poter vedere la totalità delle relazioni di un

gruppo (o di un medium) sociale in un singolo colpo d'occhio, come è possibile

orientarsi in una grande città osservandola dall'alto o attraverso una mappa,

ha costituito una prospettiva estremamente interessante. Certamente, non ab-

biamo pensato fosse un compito banale: per elaborare gra� anche dell'ordine

di 105 − 106 nodi sono necessarie delle risorse tecnologiche e scienti�che non

del tutto indi�erenti. Trovare nello stato dell'arte queste risorse � e veri�care

che esse esistano e siano sfruttabili per i nostri scopi � è stata una importante

domanda durante il nostro lavoro.

Le risorse tecnologiche e software sono state analizzate nel capitolo 2; ab-

biamo identi�cato nel pacchetto WebGraph uno strumento indispensabile per

reperire e manipolare i dati di partenza per il nostro software; grazie ad esso

abbiamo potuto avere accesso ai gra� sociali che ci interessavano, caricarli in

memoria, trasformarli, analizzarli. Per quanto riguarda la parte gra�ca, abbia-

mo invece fatto a�damento sul framework di Processing, in modo da sopperire

a numerose carenze di Java da questo punto di vista. Esso ci ha evitato di

dover reinventare la ruota per quanto riguarda moltissime funzioni indispensa-

bili per un applicativo essenzialmente gra�co: funzioni più o meno avanzate,

dall'antialiasing al rumore di Perlin. L'uso di questo insieme di tecnologie si è

rivelato molto funzionale ai nostri scopi, spingendoci all'uso del linguaggio Java

per ogni parte dell'applicazione.

Le risorse teoriche e scienti�che sono state invece descritte nel capitolo 3; il

problema di disegnare un grafo infatti è stato ampiamente a�rontato in lettera-

tura, e abbiamo tentato perciò di presentare una panoramica di queste tecniche

standard � in particolar modo quelle più vicine agli strumenti attualmente in


uso. Abbiamo quindi individuato nelle ricerche degli ultimi anni gli algoritmi

che avessero più potenzialità rispetto ai gra� da noi presi in considerazione: la

letteratura riguardante i gra� di grande dimensione è stata studiata per cercare

gli algoritmi più e�caci. Questa indagine ha portato alla scelta di due algorit-

mi su cui basare l'applicazione: l'algoritmo multidimensionale di David Harel

e Yehuda Koren � entrambi molto attivi in quest'area del graph drawing � e il

metodo multiscala di Chris Walshaw.

Nel capitolo 4 abbiamo descritto come da queste risorse siamo arrivati al-

l'applicazione �nale. Abbiamo infatti implementato da zero questi algoritmi,

poiché erano privi di un'implementazione pubblica, in Java, e interfacciabile

con WebGraph. Durante la realizzazione, ci siamo scontrati � oltre che con le

ovvie di�coltà di gestione della memoria, lavorando con gra� molto grossi �

anche con alcuni problemi dovuti all'applicare questi metodi su gra� sociali: in

particolare, si è rivisto il metodo di coarsening dell'algoritmo di Walshaw per

farlo operare con questo genere di gra�, caratterizzati dall'invarianza di scala.

In�ne, abbiamo fatto fronte alle grandi esigenze in termini di tempo di calcolo

di questo algoritmo, facendo leva sull'interattività: a patto di non disporre tutti

i nodi �n da subito nella loro posizione ottimale, abbiamo ottenuto una disposi-

zione globale più veloce, rendendo al contempo possibile ingrandire e migliorare,

con semplicità e rapidità, il layout nelle zone di interesse.

5.2 Risultati ottenuti

I risultati ottenuti da questi algoritmi sono stati discussi nelle sezioni 4.2.1 e

4.2.2. Tirando le somme, potremmo dire che la scelta di due approcci così

diversi tra loro ha dato luogo ad un confronto e ad una valutazione più corret-

ta. Infatti, laddove il metodo di Harel-Koren crea una disposizione sulla base

di statistiche relative alla distanza dei nodi all'interno del grafo, l'algoritmo di

Walshaw tenta di suddividerlo in varie macrosezioni via via più grandi, e applica

a questi gruppi di nodi delle forze repulsive ed attrattive. Queste due euristiche

sono estremamente diverse, ed appartengono a due strade ben separate del-

l'indagine sul graph drawing : la prima, più formale e matematica, mentre la

seconda per approssimazioni e tentativi, modellati su leggi �siche.


Quest'ultimo, nella sua versione sviluppata da Walshaw e qui modi�cata,

ha portato ad un disegno molto e�cace di vari gra� del web, lavorando molto

bene (su macchine di uso comune) anche con 106 nodi. In molti esperimenti

da noi fatti, questo algoritmo è riuscito a raggruppare le pagine dello stesso

sito in gruppi di nodi vicini, e a disporre questi ultimi in modo e�cace tutte le

volte che le loro connessioni � anche su grande scala � potevano suggerire un

qualche ordinamento. Sulla piccola scala l'algoritmo ha dimostrato di lavorare

in modo eccellente: ridisporre le migliaia di pagine che sono state poste vicine

nella vista globale ha spesso portato a molti risultati validi; quando la struttura

di queste pagine è caratterizzata da qualche particolare conformazione, questa

emerge chiaramente dal disegno computato.

Meno fortuna si è avuta applicandolo a gra� sociali generici e molto connes-

si, oppure a frammenti del web particolarmente densi. Il clustering alla base

dell'algoritmo non riesce infatti a separare le varie zone del grafo, producendo

talvolta degli ammassi poco e�caci di nodi. Va fatto notare però che i gra-

� molto connessi sono sicuramente la situazione peggiore per un algoritmo di

graph drawing : quello da noi usato non fa eccezione.

Considerando questa premessa, anche i risultati dell'algoritmo di Harel-

Koren � pur con i numerosi difetti descritti nel capitolo 4 � non sono insensati,

e in particolare riescono a generare un disegno di una qualche e�cacia proprio

per quei gra� altrimenti impossibili da trattare. Pur se questa euristica non

riesce a essere e�ciente nel cogliere le �nezze delle piccole zone di un grafo, né

a distinguere le articolate strutture che caratterizzano un grafo del web sulla

grande scala, essa arriva comunque a computare un disegno non caotico persino

quando opera su gra� molto densi e privi di una vera e propria struttura, come

i gra� sociali più connessi. Esso riesce infatti a dare una forma a gra� di questo

tipo, distinguendo un �centro� � imperniato su raggruppamenti di nodi hub � da

una �periferia�, e persino delle concatenazioni di nodi che ne fuoriescono. Una

distinzione del genere, per un grafo dalla complessità così elevata, non è a�atto

triviale.

È anche possibile, con il software prodotto, combinare facilmente questi due

risultati: la grande pecca del metodo di Harel-Koren, non riuscire a computare

un disegno adeguato per le strutture non macroscopiche, può essere risolta sfrut-


tando l'algoritmo di Walshaw per risolvere queste situazioni, selezionando l'area

del disegno da ride�nire e lasciando che un algoritmo supplisca alle mancanze

dell'altro.

5.3 Sviluppi futuri

Come è naturale, i risultati ottenuti dai nostri algoritmi sono perfettibili. Solo in

questi anni, infatti, le tecniche tradizionali di disegno di gra� si sono scontrate,

per la prima volta, con i gra� sociali � grazie anche a quella esplosione di dati

dovuta al web 2.0 � e con quelli di grande dimensione � grazie alle capacità di

calcolo �nalmente adatte ad un simile compito.

Molto lavoro si può fare in questo campo: l'integrazione tra gli studi teorici su

questi gra� � e in particolare quelli sulla community detection, l'identi�cazione

delle comunità presenti nella rete � e gli algoritmi di disegno è ancora molto poco

sfruttata. Questo perché, come dicevamo, anche il layout di gra� molto grandi

è ancora relativamente giovane: il paradigma multiscala che abbiamo discusso

ha mosso i primi passi negli ultimi dieci anni. Un'unione di questi due approcci,

che sfrutti meglio clustering e community detection per elaborare la gerarchia

multiscala, appare come una buona via per migliorare i nostri risultati. Inoltre,

anche l'identi�cazione degli hubs potrebbe essere impiegata per disporre i nodi

in modo da relazionarsi con essi, creando nuovi algoritmi di disegno che siano

realizzati appositamente per i gra� sociali.

Anche le indagini compiute più nello speci�co sui gra� del web potrebbero

portare a nuovi algoritmi specializzati per essi. Ad esempio, gli studi compiuti

per identi�care le macrostrutture presenti nel WWW [7] non hanno ancora tro-

vato applicazione � anche forse per il loro stato embrionale, oggetto di correzioni

e dispute � nel disegno del grafo del web. Le tre parti fondamentali identi�cate

da questo studio � una grande componente fortemente connessa centrale, un

insieme di siti che presenta collegamenti verso questa componente (come siti

personali o blog minori), ed un insieme che invece è collegato da questa com-

ponente (sottopagine di siti) � potrebbero essere un'interessante base per un

algoritmo disegnato speci�catamente per il grafo del web; ad un metodo di que-

sto tipo resterebbe comunque il problema di disegnare poi l'interno di queste


componenti, ma per farlo potrebbe integrare al suo interno le tecniche da noi

sviluppate, demandando semplicemente ad esse questo compito.

Per questi motivi, abbiamo posto un forte accento � durante l'implemen-

tazione � sull'estensibilità nel nostro codice, specialmente per quanto riguarda

la realizzazione di nuovi algoritmi; abbiamo tentato di rendere un compito il

più lineare possibile lo scrivere una classe che estenda Layout; è su�ciente che

questa riesca a resituire una coppia di numeri reali (le coordinate) per un dato

grafo, per vedere perfettamente integrato un nuovo algoritmo con il resto del

pacchetto software.

Oltre alla disposizione dei nodi, anche altre parti della visualizzazione seguo-

no questa �loso�a, e l'esempio migliore è la color map dei nodi: basta passare

un vettore di numeri (uno per nodo) alla classe NaturalArrayFile per poter

salvare e caricare una nuova mappa cromatica per il grafo � ad esempio, per ve-

dere come si dispone una certa proprietà al suo interno, oppure per veri�care i

risultati di un certo algoritmo di clustering rispetto ad una data visualizzazione.

In questo modo, speriamo di rendere possibile l'uso dello strumento da noi

creato � che unisce molte risorse all'avanguardia, come WebGraph e Processing

� come un vero e proprio laboratorio per le ulteriori ricerche in questo campo.

Un laboratorio in cui indagare e mettere alla prova sia gli stessi algoritmi di

disegno sia ciò che rappresentano: quei gra� sociali con cui la scienza tenta di

avvicinarsi, �nalmente, all'in�nita complessità dei rapporti umani.

Bibliogra�a

[1] Réka Albert, Hawoong Jeong, and Albert-László Barabási. The diameter

of the world wide web. CoRR, cond-mat/9907038, 1999.

[2] Jesse Alpert and Nissan Hajaj (software engineers at Google). We knew

the web was big... http://googleblog.blogspot.com/2008/07/we-knew-web-

was-big.html, July 2008.

[3] Albert-László Barabási. Linked: The new science of networks. J. Arti�cial

Societies and Social Simulation, 6(2), 2003.

[4] Giuseppe Di Battista, Peter Eades, Roberto Tamassia, and Ioannis G. Tol-

lis. Algorithms for drawing graphs: an annotated bibliography. Comput.

Geom., 4:235�282, 1994.

[5] Paolo Boldi and Sebastiano Vigna. The webgraph framework i:

compression techniques. In WWW, pages 595�602, 2004.

[6] Paolo Boldi and Sebastiano Vigna. The webgraph framework ii: Codes for

the world-wide web. In Data Compression Conference, page 528, 2004.

[7] Andrei Z. Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sri-

dhar Rajagopalan, Raymie Stata, Andrew Tomkins, and Janet L. Wiener.

Graph structure in the web. Computer Networks, 33(1-6):309�320, 2000.

[8] Jiazhen Cai, Xiaofeng Han, and Robert Endre Tarjan. An o(m log n)-time

algorithm for the maximal planar subgraph problem. SIAM J. Comput.,

22(6):1142�1162, 1993.

[9] Processing Community. A short introduction to the processing software

and projects from the community. http://processing.org/about/.

76

BIBLIOGRAFIA 77

[10] Derek J. de Solla Price. Networks of scienti�c papers. Science,

149(3683):510�515, 1965.

[11] Michael R. Garey e David S. Johnson. Crossing number is np-complete. J.

on Algebraic and Discrete Methods, 4:312�316, 1983.

[12] B. S. Everitt e G. Dunn. Applied Multivariate Data Analysis. Arnold, 1991.

[13] Paul Mutton e Peter Rodgers. Spring embedder preprocessing for www

visualization. In IV, pages 744�749, 2002.

[14] David Harel e Yehuda Koren. Graph drawing by high-dimensional

embedding. Journal of Graph Algorithms and Applications, 8.

[15] P. Eades. A heuristic for graph drawing. In Congressus Numerantium,

volume 42, pages 149�160, 1984.

[16] Peter Eades, Qing-Wen Feng, and Xuemin Lin. Straight-line drawing al-

gorithms for hierarchical graphs and clustered graphs. In Graph Drawing,

pages 113�128, 1996.

[17] Thomas M. J. Fruchterman and Edward M. Reingold. Graph drawing by

force-directed placement. Softw., Pract. Exper., 21(11):1129�1164, 1991.

[18] Pawel Gajer, Michael T. Goodrich, and Stephen G. Kobourov. A multi-

dimensional approach to force-directed layouts of large graphs. Comput.

Geom., 29(1):3�18, 2004.

[19] David Harel and Yehuda Koren. A fast multi-scale method for drawing

large graphs. In Advanced Visual Interfaces, pages 282�285, 2000.

[20] Bruce Hendrickson and Robert W. Leland. A multi-level algorithm for

partitioning graphs. In SC, 1995.

[21] Michael Himsolt. Gml: A portable graph �le format. Technical report,

Universitat Passau, 1995.

[22] Robert E. Horn. Information Design: Emergence of a New Profession.

MIT Press.

BIBLIOGRAFIA 78

[23] T. Kamada and S. Kawai. An algorithm for drawing general undirected

graphs. Inf. Process. Lett., 31(1):7�15, 1989.

[24] Alan Kay. User interface: a personal view. The art of human-computer

interface design, page 191. Addison-Wesley.

[25] Joseph Manning. Computational complexity of geometric symmetry detec-

tion in graphs. Proceedings of Great Lakes Computer Science Conference,

507:1�7, 1989.

[26] Peni Nissani. Tecniche di visualizzazione per gra� di grande dimensione.

Master's thesis, Università degli studi di Milano, Milano, Italy, 2008.

[27] Massimo Santini Sebastiano Vigna Paolo Boldi, Bruno Codenotti. Ubi-

crawler: A scalable fully distributed web crawler. Software: Practice &

Experience, 34(8):711�726, 2004.

[28] Processing Community. Processing Java Documentation.

[29] Casey Reas and Benjamin Fry. Processing: programming for the media

arts. AI Soc., 20(4):526�538, 2006.

[30] Clay Shirky. Here Comes Everybody: The Power of Organizing Without

Organizations. Penguin Group, 2008.

[31] Chris Walshaw. A multilevel algorithm for force-directed graph-drawing.

J. Graph Algorithms Appl., 7(3):253�285, 2003.

[32] Chris Walshaw. Multilevel re�nement for combinatorial optimisation

problems. Annals OR, 131(1-4):325�372, 2004.

SVILUPPO DI UNO STRUMENTO PER LA ... - Corrado Monti Monti - SVILUPPO DI UNO... · CAPITOLO 1....

Documents

Transcript of SVILUPPO DI UNO STRUMENTO PER LA ... - Corrado Monti Monti - SVILUPPO DI UNO... · CAPITOLO 1....