ˆ "The structure of Borders in a Small World" (Novembre 2010)[?]

Capitolo 1

Rassegna della Letteratura

In letteratura, la questione di come poter ridenire i conni territoriali sul- la base di informazioni relative alla mobilità umana, è stata arontata re- centemente in vari articoli, prendo in considerazione quelli più attuali e rilevanti:

ˆ "The structure of Borders in a Small World" (Novembre 2010)[?]

ˆ "Redrawing the Map of Great Bretain from a Network of Human Inte- ractions" (Dicembre 2010)[?]

ˆ "Regions and borders of mobile telephony in Belgium and in the Brus- sels metropolitan zone" (Ottobre 2010)[?]

ˆ "The worldwide air transportation network: Anomalous centrality, com- munity structure, and cities' global roles" (Maggio 2005)[?]

ˆ "Uncovering space-indipendent communities in spatial network" (Mag- gio 2011) [?]

Nel seguito riassumo brevemente l'idea che sta dietro agli articoli, le carat- teristiche salienti e i risultati ottenuti. Si rimanda agli articoli citati per una trattazione più dettagliata.

1

1.1 The structure of Borders in a Small World

Nel primo articolo intitolato "The structure of Borders in a Small World"

[?], gli autori, hanno ricavato una rete per la mobilità urbana a partire dal- la circolazione geograca delle banconote negli Stati Uniti. Tali dati so- no stati raccolti utilizzando il gioco online di tracciamento delle banconote www.wheresgeorge.com[?]. Le persone che partecipano a questo gioco pos- sono marchiare ogni banconota di cui vengono in possesso e rimetterla in circolazione; altre persone che ricevono casualmente la banconota possono rendere noto questo ritrovamento online indicando anche la loro attuale ubi- cazione (C.A.P.). L'analisi si basa sul concetto intuitivo che la forza di ac- coppiamento tra due posizioni i e j aumenta con w ij ^H , ossia con il numero di persone che viaggiano tra una coppia di luoghi per l'unità di tempo e che il

usso di persone è proporzionale al usso di banconote, denotato da w ij . Al

wheresgeorge dataset vengono poi applicati i risultati di teoria delle reti per

individuare una partizione P dei nodi in k moduli M n tale che l'intraconnet-

tività fra i moduli della partizione sia elevata e l'interconnettività fra di loro

sia bassa rispetto ad un modello causale nullo. Come misura standard per

valutare la struttura comunitaria di una partizione P è stata utilizzata la mo-

dularità. La massimizzazione della modularità in reti di grandi dimensioni è

un problema NP-hard[?] ma sono stati elaborati una varietà di algoritmi per

esplorare sistematicamente e campionare lo spazio delle possibili suddivisioni

in modo da indenticare partizioni con alta modularità. Gli autori utilizza-

no l'algoritmo del Simulated Annealing [?] della classe di metodi stocastici

Monte-Carlo[?] per approssimare una partizione della rete con la massima

modularità, un'immagine di tale rete è mostrata in Figura 1.1.

Figura 1.1: La mobilità umana derivata dalla rete del usso di banconote.

Una mobilità umana multi-scala è caratterizzata da un modello di connettività (pattern) in cui domina la breve distanza e nel quale la lunga distanza è signicativa. La rete mostrata rappresenta un proxy per la mobilità umana, il usso di banconote tra 3.109 contee di 48 Stati Uniti (escludendo Alaska e Hawaii).

Ogni collegamento W

> 0 è rappresentato da una linea, i colori codicano l'intensità di un collegamento:

da piccoli valori di w

(rosso scuro) a grandi valori (giallo chiaro); i valori di w

spaziano su quattro ordini di grandezza.

Essendo il processo di ottimizzazione stocastico, la partizione risultante varia ad ogni esecuzione del processo, tre esempi di partizioni ad alta modularità sono mostrati in Figura 1.2a.

Da notare che, sebbene la modularità tenga conto solo della struttura della matrice dei pesi W e sia espressamente non sensibile alla località geogra-

ca dei nodi, i moduli ottenuti risultano geogracamente compatti in ogni mappa. Si noti tuttavia che, nonostante ogni mappa mostri somiglianze qua- litative tra grandi aree e sebbene ciascuna delle mappe possieda un alto grado di modularità, esistono evidenti dierenze strutturali (problema della dege- nerazione della modularità (si veda la sezione ??)[?]). Gli autori, a questo punto, hanno messo in discussione il fatto che un'unica mappa potesse es- sere considerata la singola partizione più attendibile e hanno quindi deciso di prendere in considerazione un'insieme di 1000 partizioni; questo permette di superare anche il problema del limite della risoluzione (si veda la sezione

??)[?]. La Figura 1.2d mostra una sovrapposizione lineare dell'insieme di

partizioni risultanti, un conne è tanto più signicativo, ossia è più frequen-

Figura 1.2: L'eettiva suddivisione dei conni negli Stati Uniti.

a) Le suddivisioni determinate dalla massimizzazione della modularità Q condividono valori simili di Q

(dall'alto al basso: Q=0.6807, 0.6808 e 0.6804, tutti con k = 14 moduli). In tutte le mappe i moduli

sono geogracamente compatti. Sebbene queste soluzioni abbiano caratteristiche comuni, esse presentano

dierenze signicative nella struttura dei moduli. b) Statistiche di insieme delle suddivisioni geograche

per un insieme di N = 1.000 partizioni. Il numero di moduli k in ogni suddivisione è strettamente distribuito

intorno a 13 (barre grigie), e così sono le distribuzioni di modularità (nel diagramma sovraimposto). La

media dell'insieme è Q=0.674 ± 0.0026. c) Sulla distribuzione dell'ampiezza lineare dei 48 stati (in media

329 ± 125 km) e i moduli geograci nelle suddivisioni eettive (644 ± 215 km). d) I conni eettivi

emergono dalla sovrapposizione lineare di tutte le mappe nell'insieme (linee blu). L'intensità codica la

signicatività del conne (vale a dire la frazione di mappe che espongono il conne). Le linee nere indicano

le frontiere statali. Sebbene il 44% delle frontiere statali coincida con le frontiere eettive (graco a torta

a sinistra), circa il 64% dei conni eettivi non coincidere con le frontiere statali. Questi conni sono

caratteristiche statisticamente signicative dell'insieme delle mappe ad alta modularità, sono parzialmente

correlati con i conni amministrativi, le caratteristiche topograche, e spesso stati di separazione. e) Primo

piano sulla regione del Missouri, mostra la frontiera eettiva tra Kansas City e St. Louis che divide lo

stato. f) Primo piano sulla frontiera corrispondente alle Montagne Appalaci con i corrispondenti conni

che si estendono a nord suddividendo la Pennsylvania. Questo conne è il più solido nella mappa.

te nella partizioni risultanti, quanto più la linea blu è marcata. I conni individuati rappresentano caratteristiche topologiche statisticamente signi-

cative della sottostante rete di mobilità umana. Esaminando i conni di

mobilità individuati più accuratamente, vediamo che, benché siano correlati

signicativamente con i conni territoriali degli stati, spesso si trovano in

luoghi inattesi. I Monti Appalaci (Figura 1.2f ) rappresentano una barriera

topograca naturale per la maggior parte dei mezzi di trasporto, l'estensione

di tali monti coincide solo parzialmente con i conni di stato, ma l'eettiva

frontiera di mobilità è chiaramente correlata con essi. I graci a torta della

Figura 1.2d mostrano che il 44% delle frontiere amministrative sono anche

reali conni, mentre il 64% di tutti i reali conni non coincidono con i conni

di stato.

1.2 Redrawing the Map of Great Bretain from a Network of Human Interactions

Nel secondo articolo considerato, intitolato "Redrawing the Map of Great Bre- tain from a Network of Human Interactions" [?], gli autori propongono un nuovo approccio a "grana ne" alla delineazione dei conni regionali, basato sull'analisi di una rete di transazioni umane individuali. Il dataset utilizzato è composto da 20.8 milioni di nodi e 85.8 milioni di archi ed è stato inferito a partire da un ampio database telefonico contenente 12 miliardi di telefonate eettuate in un mese che si stima copra il 95% delle telefonate residenziali e aziendali della Gran Bretagna. A partire da un'area geograca e da alcu- ne misure di signicatività dei link fra i suoi abitanti, gli autori mostrano come partizionare l'area considerata in piccole regioni non sovrapposte, mi- nimizzando l'interruzione dei links esistenti fra due persone. L'algoritmo di partizionamento permette di ottenere regioni geogracamente coese che corri- spondono sensibilmente alle regioni amministrative, permettendo di scoprire anche zone inaspettate e solamente ipotizzate nella letteratura. Gli autori quanticano gli eetti del partizionamento ottenuto mostrando, ad esempio, che le conseguenze di una eventuale secessione del Galles dalla Gran Bre- tagna sarebbe due volte più distruttiva, in termini di link interrotti, per la rete di interazione umana rispetto alla secessione della Scozia. Per il par- tizionamento utilizzano come metrica la massimizzazione della modularità, alti valori di modularità occorrono quando la rete è suddivisa in modo che ci siano molti links fra elementi appartenenti ad una stessa comunità e po- chi links fra diverse comunità, rispetto ad una rete generata casualmente.

L'approccio degli autori consiste nell' utilizzare le caratteristiche della rete per partizionare la geometria sottostante alla topologia della rete, piutto- sto che partizionare la rete stessa, garantendo l'adiacenza spaziale, una della caratteristiche essenziali di una regione geograca. Gli autori inizialmente non impongono l'adiacenza spaziale nel loro metodo, per vedere le caratte- ristiche delle partizioni ricavate, e sorprendentemente ottengono comunque delle regioni coese. Apparentemente i link telefonici individuali e le relazioni interpersonali che essi catturano sono così relazionati alla geograa da pro- durre un partizionamento dello spazio geograco particolarmente accurato, confermando altresì l'adiacenza delle partizioni ottenute a partire dalla rete di mobilità. Come base per il loro metodo, gli autori, utilizzano l'algoritmo di ottimizzazione spettrale di Newman [?] applicato alla modularità (Figura 1.3)

Utilizzando come funzione la modularità, si ottengono diversi partiziona-

menti, tutti con un alto valore di modularità (problema della degenerazione

Figura 1.3: Denizione delle regioni attraverso l'ottimizzazione della modularità spettrale della rete di telecomunicazione.

a sebbene siano presenti solo tre regioni, la modularità è 0.31, che indica un buon partizionamento della rete. b la partizione nale della Gran Bretagna ha una modularità di 0.58. c partizione nale ulteriormente migliorata utilizzando il processo suggerito da Newman[?]che ha permesso di ottenere conni più delineati e minor rumore.

della modularità (si veda la sezione ??)[?]); per ottenere i conni, vengono utilizzati vari metodi di partizionamento (Figura 1.4) sempre basati sulla modularità.

I conni risultanti presentano alcune dierenze ma hanno la caratteristica

comune di produrre sempre regioni coese centrate approssimativamente negli

stessi punti; inoltre, se intersechiamo tutte le regioni ottenute con i dierenti

metodi, otteniamo 11 nuclei stabili che sono sempre separati dagli altri da

regioni periferiche e che presentano conni ambigui e non ben delineati (Fi-

gura 1.5). I nuclei individuati sono aree densamente popolate e contengono la

maggior parte della popolazione della Gran Bretagna (85%) mentre le regioni

periferiche sono poco abitate. Un'altra cosa interessante da evidenziare è che

la mappa costituita dai nuclei, basata sulle interazioni umane, divide la Gran

Bretagna approssimativamente nel numero uciale di regioni (Nomenclature

of Territorial Units for Statistics1 (NUTS1)), ossia in 11 regioni con conni

che coincidono all'incirca con quelli tradizionali (Figura e Tabella 1.4).

Figura 1.4: Confronto fra vari metodi di ottimizzazione della modularità

Figura 1.5: Le principali regioni della Gran Bretagna.

La rappresentazione è stata ottenuta combinando diversi metodi di ottimizzazione della modularità. La

linea nera indica le suddivisioni regionali uciali insieme alla Scozia e al Galles. I punti in nero mostrano

le città della Gran Bretagna, in cui le maggiori sono indicate esplicitamente.

1.3 Regions and borders of mobile telephony in Belgium and in the Brussels metropolitan zone

Nel terzo articolo intitolato "Regions and borders of mobile telephony in Bel- gium and in the Brussels metropolitan zone" [?], gli autori si interrogano sull'esistenza di regioni e di conni della telefonia mobile in Belgio. Il da- taset utilizzato contiene 2.6 milioni di clienti di cui si conosce il comune di appartenenza, utilizzato per l'identicazione geograca dei clienti, inoltre è noto anche il numero e la durata delle chiamate fatte e ricevute. Il databa- se è composto da più di 200 milioni di comunicazioni mobili relative ad un periodo di sei mesi (tra il 1 Ottobre 2006 e il 31 Marzo 2007). Per l'analisi, gli autori, hanno adottato un metodo matematico per suddividere la rete in gruppi coerenti in modo naturale e automatico. Il risultato ottenuto è una mappa delle comunicazioni mobili ricavata considerando la frequenza relativa delle chiamate oppure la durata delle stesse. Utilizzando la frequenza delle comunicazioni hanno ottenuto una mappa del Belgio composta da 17 gruppi di "aree telefoniche", ognuna delle quali contiene solo comuni adiacenti; in questa mappa l'area di Bruxelles è la sola che supera i conni linguistici e copre le tre regioni istituzionali del paese. Considerando, invece, la durata delle chiamate, si ottiene una mappa costituita da due gruppi, uno nel nord e uno nel sud del paese; questi due gruppi riguardano il 98% delle telefonate, infatti solo il 2% delle chiamate sono fra un gruppo e l'altro. Il gruppo del sud include 19 comuni di Bruxelles, tutti i comuni nella regione del Walloon oltre a otto comuni con industrie nella regione del Flemish. In particola- re, tutti i comuni con industrie nella periferia di Bruxelles (ad eccezione del Wemmel) fanno parte del gruppo del sud del paese. Non sempre è facile denire esattamente cosa si intenda con il termine "conni", il signicato varia a seconda degli obiettivi pressati dall'analisi, dalla scala considerata e dai criteri utilizzati per denirli. Alcuni studi prendono in considerazione la signicatività dei conni, in altri la denizione delle aree è basata sull'identi-

cazione di un centro dell'area e sulla nozione di accessibilità a questo centro.

L'articolo ha l'obiettivo di proporre un topologia del Belgio basata sul usso

del traco telefonico mobile. I Comuni vengono raggruppati attraverso un

metodo statistico (algoritmo di ottimizzazione spettrale di Newman [?]). Gli

autori si pongono delle domande: "Le persone telefonano di più alle persone

vicine rispetto a quelle lontane?". "Questi conni eettivi fanno parte del

Belgio?". "Come sono fatti?". "La suddivisione del Belgio ottenuta rispetto

alle abitudini telefoniche degli utenti, rappresenta un nuovo partizionamento

del territorio oppure i gruppi ottenuti sono modellati sulla base delle gerar- chia urbana, sui luoghi di lavoro e sulle suddivisioni amministrative (province, regioni, ecc)?".

Figura 1.6: Frequenza delle chiamate dal Comune di Arion

Nella Figura 1.6 e nella Figura 1.7 è possibile osservare che la frequenza delle chiamate diminuisce notevolmente con l'aumentare della distanza. L'obbiet- tivo è vedere se ci sono gruppi di comuni che hanno una frequenza di chiamate o una durata più alta della media. Per fare questo si usa come metrica la mo- dularità. Il metodo utilizza un algoritmo greedy per raggruppare i nodi della rete (in questo caso rappresentati dai Comuni) in passi successivi, costruendo una gerarchia di reti. Al livello più basso della gerarchia i nodi coincidono con i gruppi; poi, ad ogni iterazione, il metodo seleziona un nodo di un gruppo e lo aggiunge al gruppo che massimizza la modularità della partizione della rete risultante, se porta un miglioramento rispetto alla situazione precedente.

Quando ogni modica dei gruppi di nodi riduce la modularità, viene creata

una nuova rete in cui i nodi sono raggruppati secondo quanto ottenuto nella

rete precedente e tale processo è ripetuto sulla nuova rete.

Figura 1.7: Frequenza delle chiamate dal Comune di Ostend

Figura 1.8: Aree telefoniche denite in base alla frequenza delle chiamate fra Comuni

(1) regional city. (2) major city. (3) provincial borders.

La Figura 1.8 mostra la partizione della rete basata sulla frequenza delle telefonate fra i Comuni. Si possono fare alcune considerazioni in merito:

1) Senza ssare il numero di gruppi o la loro dimensione, i gruppi ottimali (secondo la misura di modularità considerata) risultanti sono spazialmente bilanciati, 17 "aree telefoniche" composte da un numero di Comuni che varia da 15 a 66

2) Sorprendentemente, i gruppi di Comuni sono sempre composti da Comuni adiacenti; sebbene il metodo per raggrupparli non abbia imposto vincoli sulla prossimità o sulla contiguità ai gruppi di Comuni.

3) I conni delle "aree telefoniche" ottenuti seguono il conne linguistico ad eccezione dell'area di Bruxelles (in rosso nella Figura 1.8) e dei Comuni forte- mente industrializzati come Espierre-Helchin, Comines-Warneton, Herstappe e Fourons. E' da evidenziare che il metodo non considera in alcun modo la lingua con cui sono eettuare le telefonate. La lingua perciò sembra essere una forte barriera per le comunicazioni telefoniche.

4) La più grande area ottenuta (formata da 66 Comuni) corrisponde - non sor- prendentemente - alla città più grande: Bruxelles. E' da notare che Bruxelles, come molte altre città nel mondo, tende ad estendere, con il tempo, i propri conni amministrativi e questo è evidenziato anche dalle "aree telefoniche"

di Bruxelles.

Figura 1.9: Aree telefoniche denite in base alla durata media delle chiamate fra Comuni

La Figura 1.9 mostra la partizione della rete basata sulla durata media delle telefonate fra i Comuni. Si possono fare alcune considerazioni in merito:

1) Il metodo permette di individuare due gruppi: uno nel nord ed un nel sud del paese. Considerando, nell'analisi, più di 200 milioni di comunicazioni, abbiamo che solo l'1.05% sono fra il gruppo del nord e quello del sud e l'1.04% sono fra il gruppo del sud e quello del nord. In altre parole, più del 98% delle telefonate è fra clienti appartenenti allo stesso gruppo.

2) Anche qui la suddivisione nord/sud segue il conne linguistico salvo al-

cune eccezioni. Non soprendentemente queste eccezioni sono tutti Comuni

industrializzati.

1.4 The worldwide air transportation network

Nel quarto articolo intitolato "The worldwide air transportation network:

Anomalous centrality, community structure, and cities' global roles" [?] gli autori analizzano la struttura globale della rete di trasporto aereo, una infra- struttura critica con un enorme impatto sull'economia locale, nazionale ed internazionale deducendo che è una scale-free, small-world network. Scale- free network indica che il grado della rete segue una distribuzione di tipo power law, almeno asintoticamente. Small-world network è un tipo di grafo nel quale la maggior parte dei nodi non ha altri nodi vicini, ma la maggior parte dei nodi è raggiungibile da ogni altro attraverso un piccolo numero di hops o passi. In particolare, una small-world network è denita come una rete dove la distanza caratteristica L fra due nodi scelti casualmente cre- sce proporzionalmente con il logaritmo del numero di nodi della rete stessa L ∝ Log(N ) .

Il dataset utilizzato comprende i voli di linea di più di 800 compagnie aeree mondiali del periodo compreso tra il 1 Novembre 2000 e il 31 Ottobre 2001.

Il database è stato compilato dalla OAG Worldwide (Downers Grove, IL) ed

include tutti i voli di linea e charter sia di grandi aerei (air carrier) che di

piccoli velivoli (aerotaxi). Gli autori utilizzano una rete di città, non una rete

di aereoporti, quindi considerano tutti gli aeroporti di una stessa città come

singoli nodi della rete. Contrariamente a quanto aspettato per un modello

di scale-free network, gli autori, hanno trovato che le città più connesse non

sono necessariamente le più centrali e questo porta ad ottenere un valore

anomalo della centralità. Per una rete costruita in modo casuale, il grado di

un nodo e la sua centralità all'interno della rete, sono fortemente correlate,

cioè i nodi altamente connessi sono anche quelli più centrali (come mostrato

in Figura 1.10a)). In contrasto, nella rete di mondiale di trasporto aereo ci

sono città che non sono hubs, cioè che hanno un basso grado, ma che tuttavia

presentano una alta betweeness (vedi Figura 1.10a)). Per meglio illustrare

questo risultato, confrontiamo la mappa delle 25 città più connesse con quella

delle 25 città più centrali in accordo alla loro beetweeness (vedi Figura 1.10

b) e c)).

Figura 1.10: Le città più connesse e quelle più centrali della rete mondiale di trasporto aereo

a) Betweeness in funzione del grado, per le città della rete di trasporto aereo mondiale (cerchi). Per una

randomized network, la beetweeness è ben descritta dalla funzione del quadrato del grado (linea tratteg-

giata) con il 95% dei dati che cadono all'interno della regione grigia. In contrasto alla forte correlazione

fra il grado e la beetweeness delle randomized networks, la rete di trasporto aereo comprende molte città

che sono altamente connesse ma che presentano una bassa beetweeness e, al contrario, molte città che

hanno un piccolo grado ma un'alta beetweeness. Gli autori deniscono un'area blu contenente le 25 città

più centrali nel mondo e un'area gialla contenente le 25 città più connesse. Sorprendentemente, gli autori,

trovano che esistono solo poche città con un alto valore di beetweeness e grado (regione verde, intersezione

delle due regioni blu e gialla) b) Le 25 città più connesse del mondo. c) Le 25 città più centrali del mondo.

Sebbene le città più connesse siano localizzate principalmente nell'Europa Occidentale e nel Nord America, le città più centrali sono distribuite uni- formemente fra tutti i continenti. In particolare, ogni continente ha almeno una città centrale, che è tipicamente fortemente connessa rispetto alle altre città del continente, ad esempio Johannesburg in Africa o Buenos Aires e San Paulo in Brasile nel Sud America. Inoltre, fra queste città con un grado relativamente alto, ce ne sono altre, come Anchorage (AK) e Port Moresby (Papua Nuova Guinea), che nonostante abbiano un grado basso, sono fra le città più centrali nella rete.

I nodi che hanno un grado basso e una grande centralità possono essere considerati come anomali. Altre reti complesse che sono state descritte nella letteratura come Internet, non hanno questo comportamento e nodi con un alto grado presentano anche un alto valore di beetweeness. In principio, è facile da costruire articialmente una rete nella quale i nodi hanno un piccolo grado e un un alto valore di centralità; basta prendere una rete formata da due comunità che sono connesse ad un'altra attraverso un singolo nodo con solamente due links. La domanda da porsi è "Quale meccanismo generale e plausibile può dare luogo ad una rete scale-free che ha una tale distribuzione anomala della centralità? Per rispondere a tale domanda è utile considerare una regione come l'Alaska. L'Alaska è scarsamente popolata, isolata ed ha un numero di aeroporti che è sproporzionatamente altro rispetto alla sua popolazione. La maggior parte degli aeroporti dell'Alaska sono connessi solo con altri aeroporti dell'Alaska e questo fatto è giusticato dal punto di vista geograco; tuttavia, rispetto alla distanza, avrebbe senso anche che alcuni aeroporti dell'Alaska fossero connessi agli aeroporti dei Territori del Nord del Canada. Queste connessioni sono, però, assenti. Invece alcuni degli aeroporti dell'Alaska, come Anchorage, sono connessi agli Stati Uniti. Il motivo è chiaro, la popolazione dell'Alaska necessita di essere connessa ai centri politici, che sono localizzati negli Stati Uniti, mentre sono presenti dei vincoli politici che rendono dicile la presenza di connessioni con città del Canada pur essendo più vicine geogracamente. Per questo motivo ora è chiaro perché la centralità di Anchorage sia così alta. Invece, la presenza di nodi con una centralità anomala è relativa all'esistenza di regioni con una alta densità di aeroporti ma poche connessioni verso l'esterno. L'anomalia del grado dei nodi rispetto alla centralità è perciò dovuta all'esistenza di comunità nella rete.

Per identicare le comunità nella rete di trasporto aereo, gli autori utilizzano

la denizione di modularità [?]. La modularità di una data partizione di

nodi in gruppi è massima quando i nodi che sono densamente connessi fra

loro sono raggruppati insieme e separati dagli altri nodi nella rete. Per tro-

Figura 1.11: Comunità nella giant component della rete di trasporto aereo mondiale. Ogni nodo rappresenta un aeroporto ed ogni colore rappresenta una comunità.

vare la partizione che massimizza la modularità, gli autori hanno utilizzato l'algoritmo del Simulated Annealing[?]. Nella Figura 1.11 sono mostrate le comunità identicate dall'algoritmo nella rete mondiale di trasporto aereo.

Come gli autori avevano supposto, l'Alaska e Papua New Guinea formano comunità separate, questo spiega il motivo per cui Anchorage e Port More- sby abbiano un alto valore di centralità: queste due città forniscono molti link verso il mondo esterno per le altre città nella comunità. Un altro risul- tato signicativo è che, sebbene le distanze giochino un ruolo signicativo nella denizione delle comunità, la composizione di alcune di tali comunità non può essere spiegato semplicemente attraverso considerazioni geograche.

Per esempio la comunità che comprende le principali città europee, contiene anche i maggiori aeroporti della Russia Asiatica. Similmente, le città del- la Cina e del Giappone sono principalmente raggruppate con i paesi della Penisola Arabica e con i paesi dell'Africa Nordorientale. La causa di questi fatti è consistente con l'importante ruolo che rivestono i fattori politici nella determinazione delle strutture comunitarie.

Gli autori, inoltre, identicano il ruolo di ogni città in base ai pattern di

comunicazione all'interno delle comunità (intercomunità) e fra comunità (in-

tracomunità). Prima vengono distinti i nodi che assumono il ruolo di hubs

nella loro comunità da quelli non-hubs. Si noti che alcune città come An-

chorage sono hubs per la loro comunità, ma non essere hubs se consideriamo tutti i nodi della rete. Gli autori utilizzano un coeciente di partecipazione P _i di un nodo i, per determinare i diversi ruoli assunti dai nodi hub e non, in base alla presenza di connessioni a molti nodi appartenenti ad altre comunità (il coeciente di partecipazione tende ad 1 se i suoi link sono uniformemente distribuiti fra tutte le comunità, mentre è 0 se tutti i links fanno parte della propria comunità).

Con tale coeciente, gli autori, classicano i nodi non-hub in quattro die- renti ruoli:

ˆ ultraperipheral nodes: nodi in cui tutti i links sono all'interno del proprio modulo (P ≤ 0.05)

ˆ peripheral nodes: nodi con la maggior parte dei link all'interno del proprio modulo (0.05 < P ≤ 0.62)

ˆ non-hub connector nodes: nodi con molti links ad altri moduli (0.62 < P ≤ 0.80)

ˆ non-hub kinless nodes: nodi con link omogeneamente distribuiti fra tutti i moduli (P > 0.80)

ed i nodi hub in tre dierenti ruoli:

ˆ provincial hubs: nodi hub con la maggior parte dei link all'interno del proprio modulo (P ≤ 0.30)

ˆ connector hubs: nodi hub con la molti link alla maggior parte degli altri moduli (0.30 < P ≤ 0.75)

ˆ kinless hubs: nodi hub con link omogeneamente distribuiti fra tutti i moduli (P > 0.75)

Associando i ruoli deniti alle varie città abbiamo che il 94% delle città nella

rete di trasporto aereo sono classicate come peripheral nodes o ultraperi-

pheral nodes e che solo una piccola percentuale è rappresentata da non-hub

connector nodes (0.5%). Questi risultati suggeriscono che le città che non so-

no hub nello loro rispettive comunità, raramente hanno collegamenti a molte

altre comunità nella rete di trasporto aereo. Il rimanente 4.1% dei nodi sono

hubs. Il numero di provincial hubs e di connector hubs è approssimativa-

mente lo stesso. I provincial hubs includono città che per ragioni storiche,

politiche o geograche non sono ben connesse alle altre comunità, come ad

Figura 1.12: Connessioni non-hub (verde), provincial hub (giallo), connector hubs (marrone) nella rete di trasporto aereo mondiale.

esempio, Denver, Philadelphia, Detroit, Barcellona, Brasilia, ecc.; mentre i connector hub comprendono gli hub aeroportuali più facilmente riconoscibi- li nel mondo, ad esempio, Chicago, New York, Los Angeles, Mexico City, Londra, Parigi, Roma, ecc.

La percentuale di città per ogni ruolo della rete di trasporto aereo è in con-

trasto con la percentuale corrispondente della rete casuale (Figura 1.12). In

questo caso, l'algoritmo per l'identicazione delle comunità permette ancora

di individuare certe comunità, ma la rete è priva della "reale" struttura co-

munitaria. L'identicazione dei ruoli permette agli autori di rendersi conto

che queste comunità sono in qualche modo articiali. Invece, molte città

sono o kinless hubs o non-hubs kinless nodes perché la rete è priva della reale

struttura comunitaria e non contiene essenzialmente nessun provincial hub o

connector hub

1.5 Uncovering space-indipendent communities in spatial network

Nel quinto articolo intitolato "Uncovering space-indipendent communities in spatial network" [?] gli autori mostrano come sia possibile utilizzare le carat- teristiche spaziali per rivelare con maggiore chiarezza le similarità strutturali nascoste fra i nodi. Il dataset utilizzato per testare il metodo è un'ampia rete di telefonia mobile ed un benchmark generato dal computer dove ven- gono considerati gli eetti dello spazio. Per determinare un partizionamento della rete di telefonia mobile del Belgio in comunità, vengono utilizzate due denizioni di modularità: la modularità Newman Girvan (NG) e la modula- rità spaziale (SPA). Entrambe le versioni della modularità sono ottimizzate usando il metodo spettrale [?]. La Figura 1.13 mostra le partizioni risultanti, utilizzando rispettivamente la modularità NG (gura in alto) e quella SPA e (gura in basso). In particolare la modularità NG permette di individuare una partizione composta da 18 moduli spazialmente compatti, simili a quelli osservati in altre reti e determinati principalmente dalle interazioni a breve distanza fra comunità. Sebbene i conni di tale partizione coincida con la separazione linguistica del paese [?], non è possibile individure, a partire da questa, le due comunità linguistiche. Attraverso la modularità spaziale è pos- sibile determinare, sorprendentemente, un dierente tipo di struttura: una partizione del paese in due aree che rappresentano le due comunità maggiori e che complessivamente coprono il 75% di tutte le comunità. Tale partizio- ne evidenzia precisamente la separazione linguistica del paese, ad esempio Bruxelles è assegnata alla comunità francese, in quanto approssimativamen- te l'80% della popolazione parla francese, nonostante Bruxelles faccia parte delle Fiandre. Le piccole comunità restanti (composte da non più di 10 comu- ni ciascuna) sono originate dai vincoli imposti dal partizionamento, che non tiene di conto delle sovrapposizioni fra comunità e potrebbe quindi classi- care male le comunità Flamminghe che hanno forti interazioni con Bruxelles e presentano una popolazione che parla più lingue.

Il valore per la modularità ottimale può essere trovato nella Tabella 1.1 E' importante notare che il confronto diretto delle due modularità Q N e Q SP A

è signicativo poichè la modularità è una misura che permette di comparare

dierenti partizioni dello stesso graco, per tale confronto il valore assoluto

della modularità non sarebbe necessario. Tuttavia il valore della modularità

sarà più basso quando il null model è vicino alla reale struttura dei dati, in

questo caso utilizzando la modularità spaziale (SPA). Per poter valutare la

signicatività della partizioni individuate è necessario ricorrere a test stati-

stici confrontando la modualarità di un insieme di random networks[?].Gli

Figura 1.13: Decomposizione della rete di telefonia mobile del Belgio in comunità.

Ogni nodo rappresenta un comune e la sua dimensione è proporzionale al numero di clienti N

. (sopra) Partizione formata da 18 comunità trovate ottimizzando la modularità NG (Newman Girvan). (sotto) Partizione formata da 31 comunità trovate ottimizzando la modularità spaziale.

Tabella 1.1: Confronto statistico della modularità del dataset originale

rispetto a quella delle random networks

Tabella 1.2: Confronto dei valori di VI del dataset originale (null model) e di quelli delle random networks

La colonna Orig-Rand mette a confronto il valore di VI del dataset orginale e quello delle random networks, mentre la colonna Rand-Rand confronta il valore di VI delle due random networks.

autori hanno costruito due tipi di random networks: 1) reti in cui i pesi dei link sono scelti casualmente; 2) reti dove è scelta casualmente la posizione geograca dei nodi, lasciando però il peso dei link inalterato.

Nella prima tipologia di reti, a partire dalla funzione empirica f(d), vengono generati i pesi fra due comunità i e j in accordo alla binomiale di media ρN i N j f (d ij ) . Nel seguito verrà considerato ρ=1 in modo da conservare (a meno di qualche uttuazione) il numero totale di chiamate nel sistema e la dipendenza spaziale fra i nodi. ρ infatti permette di stabilire l'importanza da attribuire alle piccole uttuazioni in modo che:

lim A _ij ρ

ρ→∞

= N _i N _j f (d _ij )

Il secondo insieme di random networks è radicalmente dierente dal primo tipo poichè esso mantiene inalterata la topologia della rete rendendo causali solo gli attributi dei nodi. Poichè la modularità NG non utilizza informazioni geograche, questa modica non ha eetto su di essa. Per costruzione, l'eet- to della modularità SPA è di rendere la posizione spaziale meno sensibile ai cambiamenti della funzione f(d), in modo da ottenere una espressione simile a quella della modularità NG.

Per ognuno dei due tipi di reti causali, vengono create N = 100 reti in cui si ottimizzano le modularità Q N G e Q SP A . La signicatività delle partizioni trovate nei dati originali, è valutata comparando la modularità con quella delle random network attravero un z score [?], denito come:

z = Q − Q _{RAN DOM}

ρ

dove ρ è la deviazione standard sulle 100 reti. I risultati sono riassunti nella Tabella 1.1 e mostrano chiaramente che i dati originali sono signicativamen- te più modulari rispetto alla rete in cui i pesi sono scelti in modo casuale. Per quanto riguarda la rete in cui la posione spaziale è casuale, contrariamente, lo z score è negativo; questo riette il fatto che delle informazioni utili sono state perse scegliendo casualmente le posizioni dei nodi e che il null model è più lontanto dalla realtà rispetto a quello originale.

E' interessante anche considerare la variabilità delle partizioni individuate,

per fare questo è necessario utilizzare una variazione di informazioni (VI)

normalizzata, ossia una misura della distanza fra le partizioni. La varizione

di informazioni è uguale a zero solo quando due partizioni sono identiche,

altrimenti è compresa tra 0 e 1. I risultati sono riassunti nella Tabella 1.2,

da questa è possibile osservare che le partizioni ottenute dalla modularità

NG e SPA sono molto dierenti. Per quanto riguarda le reti con pesi casuali,

il valore di VI delle partizioni individuate è molto più piccola per NG (0.09)

rispetto a SPA (0.58), questo indica che con NG sono state generate partizioni

molto simili a quelle delle random networks (tenendo di conto solamente delle

interazioni spaziali fra i comuni). Inoltre le partizioni individuate da NG nei

dati originali e da SPA nelle reti in cui le posizioni dei nodi sono scelte

casualmente, sono molto simili, come si può notare dal basso valore di VI

(0.16); questo è motivato dal fatto che SPA tende ad essere simile a NG

quando lo spazio è irrilevante. Quanto appena osservato è confermato dai

valori simili di VI per le partizioni generate da NG e SPA nei dati originali,

come mostrato in Figura 1.13 (0.38), e fra le partizioni individuate da SPA

nei dati originali e quelle dove sono scelte casualmente le posizioni dei nodi,

come si nota nella Tabella 1.2 (0.35).