Un metodo di estrazione di rete stabilisce il criterio secondo cui ogni nodo stabilisce i propri vicini. Uno di questi `e l’-method[41], che permette di connettere i vettori tra loro se e solo il valore della loro similarit`a del coseno supera una certa soglia :
∃ e = (u, v) ∈ L sse sim(~u, ~v) ≥
Applicato a questo dominio, Lmax corrisponde alla totalit`a delle distanze tra tut-
te le coppie di vettori. Si ha bisogno, quindi, di un metodo che estragga un grafo con L Lmaxin cui L contenga forti relazioni di similarit`a semantica. Col metodo appena
introdotto, ordine e grandezza della rete sono vincolate dal valore posto come soglia. Ipotizzando di aver posto simτ pari a un valore che superi il pi`u alto valore di similarit`a
del coseno di un vettore v1con tutti gli altri vettori della rete, il vettore in questione sar`a
escluso dalla rete. Ne consegue che N 6= |T |. Servirebbe identificare un criterio per il valore di . Questo sar`a discusso nel capitolo successivo.
Per quanto riguarda i limiti epistemologici riguardo alla validit`a delle reti estratte da uno spazio semantico nel riprodurre una reale struttura del significato, la discussione `e aperta.
Alcuni autori sono critici nei confronti di un modello di rete a partire dagli spazi semantici perch´e la sua estrazione (e.g., l’-method), non tiene conto della sua crescita (i.e., growth nel modello BA)[41]. Altri autori, invece, sostengono come la distribuzione di probabilit`a dei gradi di una rete semantica complessa debba seguire una power-law troncata, in particolare perch´e i nodi non possono crescere all’infinito, ed evidenziano come gli spazi semantici riescano a simulare tale realt`a[6].
Un secondo metodo di estrazione di rete `e il cs-method[6], e consiste nello stabili- re i vicini di ogni nodo sulla base del valore pi`u piccolo del rapporto cumulativo della similarit`a del coseno nel momento in cui oltrepassa una determinata soglia R:
P v∈V Ni sim(~u,~v) P v∈V sim(~u,~v) ≥ R dove |VN
i |`e il numero dei vicini del nodo u, in breve k = |ViN|.
In questo caso, N ' |T |. Siamo vincolati a un valore R ma non alla distribuzione di similarit`a stessa. Per un alto valore di R, aumentano le relazioni al numeratore che servono a oltrepassare la soglia, quindi i nodi avranno pi`u connessioni. In sintesi, in entrambi i metodi, si lavora con un numero di nodi non infinito da cui si cerca di far emergere una rete di grandezza variabile.
Venendo a questo lavoro, la metrica di similarit`a utilizzata `e la similarit`a del coseno:
sim( ~v1, ~v2) = kvv~11kkv· ~v22k
Sono state estratte quattro reti utilizzando -method, con due tagli = 0.5 e = 0.65. Come intuibile nella Figura 2.3, la parte pi`u densa della distribuzione di similarit`a si con- centra nei valori compresi tra 0 e 0.4, escludendo i valori minori di 0. Ci`o significa, innanzitutto, che non tutti i vettori possono essere simili con tutti, e questo pu`o essere un punto di partenza verso una giustificazione del valore di . Il metodo del taglio prevede che una struttura complessa emerga escludendo un corposo numero di relazioni non se- manticamente simili tra loro, agevolando il comportamento emergente di una struttura del significato composta esclusivamente da associazoni tra coppie di parole semantica- mente simili. In questo lavoro abbiamo deciso di concentrarci maggiormente su finalit`a pratiche, vale a dire che una rete di grandezza maggiore `e pi`u difficile da analizzare per i task che ci proponiamo di affrontare - community discovery, in particolare. Perci`o, le ragioni del taglio acquistano senso solo da questa prospettiva.
Figura 2.3: Distribuzione dei valori di sim(~u,~v) con SGNS sul corpus Paisa’. Il nu- mero di relazioni comprese nei seguenti intervalli `e un indice di similarit`a del corpus: 0.0=70046466, 0.1=125049680, 0.2=52766555, 0.3=11577928, 0.4=2260289, 0.5=459875, 0.6=96871, 0.7=19293, 0.8=2707, 0.9=210. Significa, ad esempio, che poco meno di 300 relazioni possono essere usate indistintamente negli stessi contesti. Per essere chiari, questo non `e necessariamente indice di sinonimia o di relazioni gerarchica: in un inter- vallo di similarit`a pari a 0.9 `e presente una connessione come padre-madre. Questo `e un indizio di ci`o che ci aspettiamo di trovare estraendo una struttura di significato ta- gliandole relazioni comprese sotto un certo intervallo di similarit`a: parole che possono essere sostituite negli stessi contesti. Cosa emerge analizzando la struttura globale e le comunit`a delle reti?
Capitolo 3
Network analysis
In questa sezione saranno analizzate le propriet`a globali delle reti estratte. Ci concen- treremo su un’analisi generale delle propriet`a che determinano la complessit`a delle reti, sulla distribuzione di probabilit`a dei gradi e sul forte grado di assortativit`a rispetto al grado osservato in tutte le reti estratte.
3.1
Invarianza di scala, propriet`a small-world, assor-
tativit`a
In Figura 3.1 mostro la distribuzione di probabilit`a dei gradi delle differenti reti. Con- siderando la letteratura corrente, non `e chiaro se le reti estratte dagli spazi semantici presentino l’invarianza di scala, ovvero se la distribuzione di probabilit`a dei gradi segua una legge di potenza.
In [41] viene fatto presente come ci`o non sia possibile e che le reti siano meglio descritte da una distribuzione esponenziale, mentre in [6] viene mostrato come le di- stribuzioni possano presentare l’invarianza di scala ma con un taglio esponenziale (la
distribuzione non `e una power law ma una truncated power law). Infine, in [45] viene ag- giunto che in alcuni casi le reti possano essere descritte da una distribuzione lognormale. In sintesi, non sono presenti dati certi a riguardo.
Ho deciso di replicare le analisi utilizzando la libreria powerlaw[49] in Python. Pri- ma di tutto, inferisco il parametro λ e a partire da quale classe di gradi l’invarianza di scala viene mostrata (cfr. Tabella 3.2. Nelle reti estratte da Wikipedia il parametro λ `e minore di 2 nelle reti estratte da Wikipedia, ma il comportamento power law `e visibile sulla quasi totalit`a della distribuzione, mentre l’invarianza di scala nelle reti estratte da Pais`a `e visibile solo nell’ultima parte della distribuzione, nel taglio minore, e da met`a distribuzione, nel taglio maggiore. Tuttavia, l’obiettivo principale `e quello di capire qua- le modello di distribuzione fitta meglio i dati. Per farlo, powerlaw si serve del test del rapporto di verosimiglianza (LR-test). `E un test comparativo che valuta la probabilit`a di due distribuzioni di generare campioni dai dati empirici basandosi sulla funzione di ve- rosimiglianza massima di ciascuna distribuzione. Il valore di R `e la log-likelihood ratio tra due distribuzioni: `e positivo se la prima distribuzione descrive meglio i dati, negati- vo se `e la seconda distribuione a farlo. Le distribuzioni e i risultati sono mostrati nella Figura 3.2 e nellaTabella 3.1. I confronti sono stati effettuati tra le distribuzioni power law, truncated power law, esponenziale e lognormale.
Dai dati emerge che la distribuzione power law non `e la pi`u indicata a fittare i dati empirici. In generale, le pi`u indicate sembrano essere la truncated power law e la lognor- male. Nel dettaglio: per quanto riguarda Wikipedia con il taglio a 0.5, dal grafico emerge che la distribuzione che meglio descrive i dati sia la truncated power law, ma in realt`a sia quest’ultima sia la distribuzione lognormale potrebbero essere indicate a rappresen- tarla (infatti, in TPL vs. logNorm KS=1.09 ma p=0.27); per quanto riguarda Wikipedia
Figura 3.1: Distribuzione di probabilit`a dei gradi, in senso orario dall’alto a sinistra, Wikipedia = 0.50, Wikipedia = 0.65, Pais`a = 0.50, Pais`a = 0.65
con il taglio a 0.65, la situazione `e simile ma i risultati riguardanti la significativit`a del- la truncated power law rispetto alla lognormale `e pi`u forte (TPL vs logNorm KS=1.99 e p=0.04); per le reti estratte dal corpus Pais`a la situazione `e identica: la distribuzione power law non `e il modello adatto rispetto alla lognormale e alla truncated power law, per una propensione verso quest’ultima.
Nella Tabella 3.2 mostro un’analisi generale per quattro reti estratte con tagli dif- ferenti. `E chiaro, sia nel corpus Wikipedia che in Pais`a, come un taglio pi`u alto non inficia sulla presenza di una componente gigante nonostante frammenti la rete in pi`u componenti. Verifichiamo, inoltre, come gi`a anticipato, che N si riduce con i tagli pi`u alti, escludendo una serie di nodi di cui nella successiva analisi qualitativa cercheremo
Figura 3.2: Complementare della funzione cumulativa, in senso orario dall’alto a sinistra, Wikipedia = 0.50, Wikipedia = 0.65, Pais`a = 0.50, Pais`a = 0.65
di valutare il peso. Anche il grado medio hki all’aumentare del taglio si riduce vertigi- nosamente, e questo ci d`a la possibilit`a di riflettere sui valori di C e di hdi, gli indicatori delle propriet`a small-world della rete. Un alto coefficiente di clustering globale rima- ne sempre presente, mentre il cammino minimo medio `e pi`u alto nelle reti estratte con = 0.5e pi`u basso in quelle estratte con = 0.65. Un numero pi`u alto di relazioni crea pi`u scorciatoie tra nodi e diminuiscono sia hdi che dmax, il diametro.
Infine, un dato importante rivela una forte assortativit`a rispetto al grado in termini di coefficiente r. Questo, in particolare, `e un dato di cui non sappiamo spiegare bene i valori. L’assortativit`a pi`u alta si osserva nella rete pi`u corposa (i.e., estratta da Wikipedia e con pari a 0.5) e decresce con il taglio maggiore. Nelle reti estratte da Pais`a, per`o, il
PL vs. TPL PL vs. Exp PL vs. lN TPL vs. Exp TPL vs. lN corpus R p R p R p R p R p Wikipedia 0.5 -2.54 0.00 4.7 0.00 -1.8 0.00 5.1 0.00 1.09 0.27 Wikipedia 0.65 -1.46 0.04 1.03 0.30 -1.1 0.31 1.95 0.05 1.99 0.04 Pais`a 0.5 -4.96 0.00 8.8 0.00 -3.67 0.00 9.74 0.00 3.0 0.00 Pais`a 0.65 -3.5 0.00 -2.56 0.01 -2.24 0.02 -0.75 0.45 0.07 0.03 Tabella 3.1: LR-test (PL sta per Power Law, TPL sta per Truncated Power Law, Exp sta per Exponentiale lN sta per Lognormal): se R `e positivo, i dati sono meglio descritti dalla prima distribuzione, se `e negativo, dalla seconda; p descrive la significativit`a statistica (p < 0.05).
comportamento sembra essere quello opposto: si osserva il pi`u basso valore di r nella rete estratta con il taglio minore e il valore pi`u alto nella rete estratta con il taglio maggiore. In Figura 3.3 mostro la correlazione tra k e knn(k)(cfr. Sezione 1.2).