Strumenti Utente

Strumenti Sito


dm:sna.ingegneria2011.esercizio

Esercizio 1

L'esercizio consiste nella creazione di una rete, e nella sua completa analisi, basata su domande analitiche interessanti da porsi sulla rete stessa.

Per semplificare la creazione della rete, diamo un crawler, scritto in linguaggio Perl, degli articoli del New York Times. Per prima cosa, scaricare il crawler crawlernewyorktimessections.zip , scompattarlo, e accertarsi di avere installato perl.

Su macchine Linux o Mac, aprire un terminale e controllare di avere il comando “perl”. Altrimenti, bisognerà installarlo (su Ubuntu: sudo apt-get install perl). Su Windows, dovrete presumibilmente installarlo. Per fare questo avete due opzioni: installare il pacchetto ActivePerl, oppure installare CygWin e installare il pacchetto perl. Accertatevi alla fine del processo di essere in grado di eseguire perl dal prompt dei comandi, o dal terminale di CygWin.

A questo punto, il crawler viene invocato in questo modo: perl CrawlerNewYorkTimeSections.pl source.txt target.txt Year0 Year1 output.txt

e funziona così: il crawler si aspetta di trovare due file in input, “source.txt” e “target.txt”, ciascuno contenente una lista di parole (una parola per riga), che saranno i vostri nodi della rete. In generale, potete mettere le parole che volete in source e target, ma considerate che il crawler creerà archi fra parole contenute in source e parole contenute in target. Quindi, se volete una rete bipartita, è sufficiente che i due file contengano parole diverse (ad es., nel primo file può esserci una lista di calciatori, e nel secondo una lista di squadre). Se invece volete una rete che non sia biparita, mettete sia in source che in target lo stesso elenco di parole, e il crawler creerà tutti gli archi possibili.

I parametri Year0 e Year1 servono a specificare la finestra temporale entro cui volete creare la rete. Mettete uno stesso anno nei due parametri se volete la rete solo di uno specifico anno.

In output.txt poi ci sarà il risultato, fatto così: una riga di intestazione con la descrizione delle colonne, poi una riga per ogni coppia parola-parola. La prima colonna specifica la parola sorgente, la seconda la parola destinazione (ignorate l'ordinamento e considerate la rete come non diretta), in terza colonna avete il numero totale di co-occorrenze, poi c'è il numero di co-occorrenze in ogni sezione rappresentata dalle rimanenti colonne.

Esempio di sessione completa di utilizzo del crawler:

Entrambi i file source.txt e target.txt hanno il seguente contenuto:

italy

france

germany

per un totale di tre righe. Dal terminale (o prompt del comandi), invoco il comando:

perl CrawlerNewYorkTimeSections.pl source.txt target.txt 2008 2009 output.txt

il comando produce un po' di righe di output a schermo, ma riempie anche il file output.txt col seguente contenuto:

TARGET CANDIDATE TOTAL Arts Automobiles Books Business Corrections DiningAndWine EditorsNotes Education FrontPage Health HomeAndGarden JobMarket Magazine Movies NewYorkAndRegion Obituaries Opinion RealState Science Sports Style Technology ThePublicEditor Theater Travel US Washington WeekInReview World

italy italy 5004 856 34 212 575 0 163 0 41 115 98 29 0 121 322 375 130 209 57 109 825 322 91 0 35 167 125 94 30 614

italy france 1288 180 3 66 226 0 31 0 8 45 20 5 0 24 68 49 17 69 12 22 261 53 17 0 2 46 15 37 8 200

italy germany 1019 92 8 32 241 3 7 0 0 46 14 0 0 11 26 44 25 49 10 24 216 17 18 0 3 20 17 42 7 174

france france 8972 1559 0 429 1461 44 135 0 60 213 162 53 0 167 532 496 218 513 48 173 1152 359 214 0 70 206 204 300 81 1615

france germany 1950 208 3 72 534 0 7 0 11 84 30 0 0 17 64 55 45 160 7 42 235 17 52 0 5 26 56 133 15 442

germany germany 6969 946 50 265 1546 0 36 0 43 214 159 0 0 84 341 359 198 510 39 179 941 136 234 0 76 100 245 295 72 1024

A questo punto, sfruttando le prime due colonne, e una (o più) qualsiasi altra colonna, potrete creare la vostra rete tenendo presente che:

  1. occorre scartare i self-loop (nell'esempio, rimuovete le righe italy italy, france france e germany germany) poichè poco significative
  2. a meno che non siate riusciti a trovare una coppia di parole perfettamente scorrelate, in “total” ci sarà sempre un numero maggiore di zero. questo vuol dire che se prendete tutte le coppie, vi viene fuori una rete completa, ossia un'unica gigantesca cricca formata da tutte le parole

Procedete quindi come segue: create dei filtri sulle colonne scelte (per semplicità, ipotizziamo che abbiate scelto di usare solo la colonna TOTAL) in modo da abbassare considerevolemente il numero di archi, e producete un file con tre colonne: id1, id2, peso, dove peso è il numero di co-occorrenze nella/e colonna/e scelta/e. Create filtri incrementali, in modo da creare un insieme di reti con numero di archi sempre minore. Caricare tutte le reti su Cytoscape (una per volta magari) e scegliere quella che rispetta qualcuna delle caratteristiche tipiche delle reti viste a lezione (usate il plugin NetworkAnalyzer e ad esempio scegliete la rete il cui AverageShortestPath sia intorno a 6, oppure diametro intorno a 15, o una qualsiasi altra proprietà a scelta).

A questo punto, trovate un interessante problema analitico sulla rete e cercate di darvi delle risposte utilizzando tutti i metodi che conoscete (visualizzazione, statistiche, clustering col plugin ClusterOne o altro, ecc).

Ricapitolando l'esercizio richiede di:

  1. scegliere un elenco di parole di N parole (a seconda del problema che vi immaginate di risolvere) e creare i due file di testo da passare al crawler
  2. utilizzare il crawler per creare una rete fatta dalle vostre parole scelte
  3. filtrare la rete in modo da poterla trattare significativamente
  4. porsi un problema analitico e risolverlo coi mezzi visti a lezione
  5. discutere tutti i passi compiuti durante l'orale

Domande tipiche :

  1. che tipo di lista di parole posso creare? Risposta: la lista di parole in qualche modo è già parte del problema che vi porrete alla fine. se nella lista di parole mettete nomi di giocatori, specie di animali, e modelli di auto fiat, probabilmente alla fine avrete una rete che vi darà poche informazioni. Esempi interessanti possono essere invece: lista di organizzazioni internazionali e lista di paesi del mondo (magari sia in modo bipartito che non), lista di termini scientifici, lista di personaggi politici, lista di attori del cinema, lista di attori e registi, lista di attori e film, ecc. Come vedete una lista può anche essere eterogenea, dando spunti per interessanti problemi analitici dopo.
  2. quante parole devo mettere nella mia lista? La risposta più ovvia sarebbe: tutte quelle che riuscite a trovare, poi potrete filtrare in seguito. Tenete presente che magari Cytoscape non riesce a farvi lavorare bene con più di 5k-10k nodi, e che magari una rete di 20 nodi non è così interessante. Tenete anche presente che n parole nella lista porteranno a n*(n-1)/2 interrogazioni del crawler, via Internet.
  3. in che lingua devono essere le parole? Risposta: generalmente Inglese, in quanto gli articoli in cui vengono cercate le co-occorrenze sono presi dal New York Times. Potete anche provare a mettere parole in Italiano o altra lingua, semplicemente potreste ritrovarvi con pochi archi alla fine.
  4. da dove prendo le parole? Risposta: ci sono tantissime sorgenti per rispondere a questa domanda: potreste partire con una pagina a caso di wikipedia in inglese e seguire via via i link, e usare tutte le parole contenute nelle pagine che trovate, o scaricare una lista di persone, posti, associazioni, ecc cercando su un qualsiasi motore di ricerca.
  5. posso usare il crawler da casa? Risposta: certo, solo che dato che il crawler cercherà di creare tutti gli archi (se mettete n parole, farà n*(n-1)/2 interrogazioni, vi consigliamo di accertarvi di avere una buona connessione Internet.
  6. visto che ci sono due parametri corrispondenti agli anni, posso usare l'informazione temporale nella mia analisi? Risposta: certo, in almeno due modi: o create una serie di snapshot temporali della stessa rete nel tempo, oppure un'unica rete, con gli archi etichettati col primo anno di comparsa. A questo punto usare anche la dimensione temporale nella propria analisi vi porta ad analisi più ricche di informazioni
  7. come faccio a filtrare velocemente il file? Risposta: se il file non è gigantesco, è molto probabile che possiate importarlo in un foglio di calcolo. a questo punto potrete usare le capacità del foglio di calcolo. Per chi è pratico con i comandi Unix/Linux/Mac, dal terminale potete usare una qualsiasi combinazione di cat, grep, awk, cut, ecc.. per filtrare righe e colonne. Esempio: in un terminale di Linux, per prendere solo le prime tre colonne, scartare l'header, filtrare i self-loop e selezionare solo gli archi con peso maggiore di 300, è sufficiente la seguente combinazione di comandi: tail -n +2 output.txt | awk '{if($1!=$2) { if($3>300) print $1, $2, $3 }}' > outputFINALE.txt . questa riga, eseguita sull'esempio precedente, produce il file outputFINALE.txt con le seguenti tre righe:

italy france 1288

italy germany 1019

france germany 1950

Per ulteriori chiarimenti, scrivere a michele [dot] berlingerio [at] isti [dot] cnr [dot] it

dm/sna.ingegneria2011.esercizio.txt · Ultima modifica: 14/04/2011 alle 11:14 (9 anni fa) da Fosca Giannotti