Capitolo 1
Simulated Annealing Algorithm
Il Simulated Annealing (di seguito indicato con SA) è un algoritmo che è stato descritto indipendentemente da Kirkpatrick S., Gelatt C.D., Jr., Vecchi M.P. nel 1983 [?], e da erný V. nel 1985 [?]. Il metodo è un riadattamento dell'algoritmo di Metropolis-Hastings [?], un metodo Monte Carlo [?] per generare semplici stati di un sistema termodinamico, inventato da Metropolis M. e Ulam S. nel 1953.
Il SA è un algoritmo probabilistico di tipo metaeuristico (metodo euristico per determinare la soluzione di una classe molto ampia di problemi computa-zionali combinando diverse procedure a loro volta euristiche, con l'obiettivo di ottenere una procedura più robusta ed e ciente). E' utilizzato per risolve-re problemi di ottimizzazione, iterando per cercarisolve-re di migliorarisolve-re la soluzione corrente rispetto ad una data metrica, e permettendo di ottenere una buona approssimazione dell'ottimo globale rispetto ad una data funzione anche nel caso in cui lo spazio di ricerca sia molto vasto. Per certi problemi, in cui siamo maggiormente interessati a trovare una soluzione "accettabilmente buona", è preferibile utilizzare un algoritmo come il SA rispetto ad un algoritmo di ricerca esaustivo.
Il metodo che utilizziamo si basa sul fatto di trovare dierenti partizioni con alta modularità, questo riduce notevolmente il numero dei possibili algoritmi utilizzabili. Ad esempio l'algoritmo deterministico descritto da Newman M. E. J. e Girvan M.[?] non può individuare dierenti massimi locali utilizzando la funzione di modularità. Invece, l'algoritmo Monte Carlo restituisce dif-ferenti partizioni con probabilità monotonicamente crescenti rispetto al cor-rispondente valore della modularità, uno di questi algoritmi è il Simulated Annealing descritto da Guimerà e Amaral[?]. In particolare questo algoritmo è stato riconosciuto come il migliore, per quanto riguarda la corretta
cazione dei moduli in una network con una struttura comunitaria arti ciale, in un confronto eettuato da Danon L. ed altri[?] e questo ci ha portato a decidere di utilizzare tale algoritmo per il nostro lavoro.
Il nome e il comportamento dell'algoritmo derivano dalla tecnica di tempra in metallurgia, che consiste nel riscaldare e rareddare, in modo controllato, un materiale per incrementare la dimensione dei suoi cristalli e ridurne i difet-ti. Il riscaldamento causa uno spostamento degli atomi dalla loro posizione iniziale facendoli muovere casualmente fra strati con alta energia; il lento raf-freddamento dà agli atomi una possibilità maggiore di trovare con gurazioni con energia interna più bassa rispetta a quella iniziale.
Analogamente a questo processo sico, ogni iterazione dell'algoritmo di SA permette di sostituire, con una certa probabilità data dalla dierenza tra il valore della funzione e un parametro globale (temperatura T ), la soluzio-ne corrente con una soluziosoluzio-ne scelta in modo causale fra soluzioni "vicisoluzio-ne"; il valore della temperatura è gradualmente decrementato durante il proces-so. L'algoritmo è fatto in modo tale che la soluzione corrente vari quasi casualmente quando il valore della temperatura è elevato, ma sempre più "in discesa" al tendere di T a zero. La possibilità di eseguire mosse "in sali-ta" permette al metodo, potenzialmente, di non rimanere bloccato su ottimi locali, che è lo svantaggio principale degli algoritmi di tipo greedy.
Vediamo brevemente i passi principali dell'algoritmo in modo da capire per-ché si presta bene al problema che vogliamo trattare.
Ad ogni iterazione, l'euristica del SA considera lo stato di alcuni vicini s' dello stato corrente s, e probabilisticamente decide se far transire il sistema ad uno stato s' o rimanere nello stato s. Queste probabilità permettono in ne di far transire il sistema in stati con livelli di energia più bassa. Tipicamente questo passo è ripetuto no a quando il sistema non raggiunge uno stato che è abbastanza buono per il tipo di applicazione, oppure dopo aver eseguito un certo numero di iterazioni stabilito.
La probabilità con cui si accetta di eettuare la transizione dallo stato cor-rente s ad nuovo stato s' è speci cata da una acceptance probability function P (e, e0, T ), che dipende dai livelli di energia e = E(s) e e0 = E(s0) dei due stati, e da un parametro globale di temperatura T che viene fatto diminuire nel tempo di un certo fattore (cooling factor).
Un requisito essenziale per la funzione di probabilità P è che sia diversa da zero quando e0 > e, con il signi cato che il sistema può transire in un nuovo
stato anche se questo risulta peggiore (ha un'energia più alta) rispetto allo stato corrente. Questa caratteristica permette al metodo di non bloccarsi in
minimi locali, ossia in stati che sono peggiori del minimo globale ma migliori di qualsiasi altro vicino.
D'altronde decrementando il valore della temperatura T di un certo fattore di rareddamento, quando T tende a zero, la probabilità P (e, e0, T ) deve
tendere a zero se e0 > e e deve assumere valori positivi se e0 < e. In questo
modo, per valori su cientemente piccoli di T, il sistema favorisce le mosse verso stati "più in basso" (con livelli di energia più bassi) evitando quelli che sono "più in alto" (con livelli più alti di energia). In particolare, quando T diventa 0, l'algoritmo diventa di tipo greedy e quindi eettua transizioni in stati "più in basso" (con livelli di energia più bassi).
1.1 Metropolis-Hastings Algorithm
L'algoritmo Metropolis-Hastings è semplicemente una catena di Markov Mon-te Carlo, che è utilizzata frequenMon-temenMon-te per deMon-terminare una sequenza di campioni casuali a partire da una distribuzione di probabilità per la quale è di cile ottenere un un campionamento diretto.
Vediamo ora come funziona tale algoritmo.
A partire da una data distribuzione obiettivo Q, che rappresenta la pro-babilità condizionata di una applicazione Bayesiana, vogliamo costruire una catena di Markov {xi}∞i=0 che abbia Q come distribuzione stazionaria. Se
Xn = xn è lo stato corrente della catena, allora l'algoritmo di
Metropolis-Hastings procede simulando un valore candidato y a partire dalla densità condizionata, q(x,). Lo stato successivo, Xn+1, è assegnato in modo casuale
a y con probabilità α(xn,y), oppure a xn con probabilità 1 − α(xn, y), dove
α(xn, y) = min
π(yj)q(y, x) π(xj)q(x, y)
, 1
è l'acceptance probability, ossia la probabilità di accettare il nuovo stato. E' facile veri care che la transizione dalla stato Xn allo stato Xn+1
eettiva-mente lascia la probabilità Q invariata. Scegliendo fra le varie transizioni proposte q(, ) è possibile ottenere dierenti catene di Markov Monte Car-lo, ad esempio il Gibbs sampler, il Langevian alghoritm, il random walk Metropolis algorithm e molti altri.
Nel caso in cui Q sia una distribuzione invariante e continua su R, il funziona-mento del random walk Metropolis algorithm è descritto di seguito. Lo stato candidato è ottenuto aggiungendo rumore allo stato corrente; in particolare, q(x, y) = f (y − x), per una certa funzione di densità f che sia simmetrica rispetto allo zero. Come densità f, frequentemente si sceglie una funzione che sia normale, ossia che abbia media e varianza σ2 nulle, in tal caso l'algoritmo
per aggiornare lo stato da Xn = xn a Xn+1 = xn+1 può essere espresso da:
y ←nxn+ z, dove z ∼ N (0, σ2) α ← min π(y) π(xn) , 1 xn+1← ( y con probabilit`a α xn con probabilit`a 1 − α
Da notare che la proprietà simmetrica della transizione proposta, q(x, y) = q(y, x), permette di sempli care la forma per la acceptance probability. I problemi di reale interesse coinvolgono distribuzioni obiettivo con un'alta di-mensionalità, ma gli algoritmi per l'invarianza della distribuzione continuano ad essere utilizzati. Come con il Gibbs sampler, gli aggiornamenti invarianti possono essere applicati a loro volta alla completa distribuzione condizionale associata all'obiettivo. Più precisamente, xi è aggiornato con una
transi-zione basata sulla distributransi-zione obiettivo Q(x1|x2, . . . , xp) e x2 è aggiornato
usando Q(x2|x1, x3, . . . , xp), e così via. Dato che ogni transizione
individua-le lascia Q invariata, anche la transizione composta, basata sull'iterare taindividua-le transizione su tutti i componenti, lascia Q invariata. Questo utilizzo de-gli aggiornamenti invarianti è riferito come aggiornamento "componente per componente". La maggior parte degli approcci ai problemi Bayesiani utilizza questo metodo.
1.2 Monte Carlo Algorithm
1.2.1 Un po' di storia
Nel 1777 il matematico francese George Louis Leclerc de Buon descrive nel-la sua opera Essai d'Arithmetique morale un esperimento di stima del valore tramite una simulazione casuale basata sul lancio di un ago, ottenendo un risultato di buona precisione numerica per l'epoca. Lo stesso Enrico Fermi all'inizio degli anni `30 sosteneva di utilizzare stime ottenute con tecniche di campionamento statistico per lo studio del moto dei neutroni. Il metodo Monte Carlo fu formalizzato negli anni '40 da J. Von Neumann e S. Ulam che partecipavano al Progetto Manhattan per lo studio della dinamica del-le esplosioni nucdel-leari. Lo stesso Von Neumann è considerato l'inventore del calcolatore elettronico. A quanto pare, il nome Monte Carlo fu coniato da Nicholas Constantine Metropolis in riferimento alla capitale del Principato di Monaco, Montecarlo, dove ha sede il celebre casinò, sede per antonoma-sia dell'aleatorietà, dove, la fortuna o la rovina di coloro che per vizio, noia o altro si cimentano nel gioco, sia decretata dalla assoluta casualità che si manifesta nell'uscita di questo o quel numero. Negli esprimenti nucleari una particella muovendosi ad alta velocità colpisce in pieno il nucleo di un atomo. Questo si frantuma in molte particelle, che vanno a colpire i nuclei di altri atomi vicini, che si frantumano a loro volta, secondo una reazione a catena, nel corso della quale si libera una gran quantità d'energia. Il processo durerà no a coinvolgere l'intero universo o si arresterà, dopo un certo numero di reazioni? Sappiamo già che il secondo caso è quello che ci si attende, come è stato confermato sperimentalmente dai sici. Con quale stato d'animo è stato tuttavia possibile eseguire il primo esperimento? I sici erano certi del fatto che la reazione avrebbe avuto termine? In realtà, l'esperimento sico fu preceduto da una serie di simulazioni. Una volta introdotti alcuni parametri iniziali, il fenomeno fu simulato da un calcolatore per mezzo di valori casua-li, trattati con metodi statistici. Si poteva così stimare la probabilità che, dopo un certo numero di "generazioni", le particelle emesse nel corso delle reazioni a catena, cessassero di generare altre particelle. Le simulazioni det-tero su cienti garanzie e gli esperimenti reali furono eseguiti con una certa tranquillità. Un primo esempio di utilizzo del metodo Monte Carlo è rap-presentato dall'esperimento dell'ago di Buon e forse il più famoso utilizzo di tale metodo è quello di Enrico Fermi, quando nel 1930 usò un metodo ca-suale per calcolare le proprietà del neutrone. Sono tanti ormai i campi in cui si utilizzano metodi statistici per ottenere informazioni e stime su fenomeni legati al caso. Non occorre che i dati siano raccolti durante un esperimento
reale in cui tali fenomeni avvengono. Ciò potrebbe richiedere troppo tempo e, in ogni caso, non sempre la natura è disposta a fornirci situazioni alea-torie... a comando. I dati possono allora provenire da simulazioni fatte per mezzo di un computer, in grado di generare sequenze di numeri casuali. Esse sono quindi utilizzate per simulare per migliaia di volte il fenomeno aleato-rio, raccogliendo così rapidamente una serie di dati che, trattati con metodi statistici, forniscono stime che diventano tanto più attendibili quanto più è grande il numero delle prove fatte. Oggi il metodo Monte Carlo trova appli-cazione in vari ambiti scienti ci dall'analisi del rischio nella valutazione degli investimenti a molti problemi sici in cui gli esperimenti sono molto di cili da realizzare, e richiedono molto tempo per essere riprodotti. In questi casi il metodo Monte Carlo è uno strumento fondamentale per l'interpretazione di dati sperimentali e la veri ca di nuove teorie.
1.2.2 In cosa consiste
Spesso ci si trova di fronte a situazioni in cui si ha bisogno di conoscere la probabilità di un certo evento, ma le variabili che lo condizionano sono trop-pe e non è possibile svolgere i calcoli analitici. In tali situazioni si fa ricorso a metodi di campionamento simulato, cioè si simula la situazione nella quale si vuole calcolare la probabilità di un certo evento. La simulazione stoca-stica si attua riproducendo il meccanismo preso in esame, sostituendo alla valutazione analitica l'osservazione empirica del fenomeno e traendo da que-sta le informazioni non rilevabili per via analitica. Ad esempio, la frequenza osservata di un certo evento costituisce una valutazione della probabilità di quell'evento (a patto che il campionamento sia stato simulato per un con-sistente numero di volte). Questa simulazione prende il nome di metodo Monte Carlo. Il metodo Monte Carlo consiste nel cercare la soluzione di un problema, rappresentandolo come un parametro di una ipotetica popolazione e stimando tale parametro tramite l'esame di un campione della popolazione ottenuto mediante sequenze di numeri casuali. Il metodo Monte Carlo è una procedura numerica usata in sica per riprodurre lo stato di un sistema. In generale questo metodo permette di generare eventi secondo un'opportuna distribuzione di probabilità, quindi può essere applicato a qualsiasi fenome-no di cui si cofenome-nosca la probabilità di occorrenza. Per esempio supponiamo che I sia il valore incognito da calcolare e che si possa interpretare quale valore medio di una variabile casuale X. Il metodo Monte Carlo consiste, in questo caso, nello stimare I mediante il calcolo della media di un campione costruito determinando N valori di X; ciò si ottiene tramite un procedimen-to che prevede l'uso di numeri casuali. Il meprocedimen-todo della simulazione Monte
Carlo è una tecnica numerica per la trattazione di problemi caratterizzati da una sostanziale intrattabilità analitica. Inoltre, ha particolare successo per risolvere il problema della rappresentazione dei portafogli composti da stru-menti nanziari ad alto contenuto opzionale o non lineare e la distribuzione dei rendimenti del portafoglio stesso. Il metodo Monte Carlo è una valida alternativa agli approcci parametrici nel caso in cui il portafoglio comprenda posizioni con andamento di prezzo non lineare. La seconda caratteristica interessante riguarda la possibilità di adattare per la generazione degli sce-nari random, distribuzioni di probabilità dei fattori di rischio non normali. Rimane fondamentale, comunque, la scelta delle funzioni di valutazioni ap-propriate, il rischio di scegliere un modello di valutazione errato è chiamato model risk. Il metodo Monte Carlo fa parte della famiglia dei metodi statisti-ci non parametristatisti-ci. È utile per superare i problemi computazionali legati ai test esatti (ad esempio i metodi basati sulla distribuzione binomiale e calcolo combinatorio, che per grandi campioni generano un numero di permutazio-ni eccessivo). Il metodo è usato per trarre stime attraverso simulaziopermutazio-ni. Si basa su un algoritmo che genera una serie di numeri tra loro incorrelati, che seguono la distribuzione di probabilità che si suppone abbia il fenomeno da indagare. La non correlazione tra i numeri è assicurata da un test chi quadro. La simulazione Monte Carlo calcola una serie di realizzazioni possibili del fe-nomeno in esame, con il peso della probabilità di tale evenienza, cercando di esplorare in modo esaustivo tutto lo spazio dei parametri del fenomeno. Una volta calcolato questo campione rappresentativo, la simulazione esegue delle 'misure' delle grandezze di interesse su tale campione. La simulazione Monte Carlo è ben eseguita se il valore medio di queste misure sulle realizzazioni del sistema converge al valore vero. Da un altro punto di vista le simulazioni Monte Carlo non sono altro che una tecnica numerica per calcolare integrali. L'algoritmo Monte Carlo è un metodo numerico che viene utilizzato per tro-vare le soluzioni di problemi matematici, che possono avere molte variabili e che non possono essere risolti facilmente, per esempio il calcolo integrale. L'e cienza di questo metodo è più alta, rispetto ad altri metodi, e cresce all'aumentare della dimensione del problema da trattare.
1.2.3 Utilizzi del metodo
Non si tratta di un metodo molto e ciente per il calcolo di p, ma illustra il concetto. Un matematico direbbe che il Monte Carlo serve a calcolare in-tegrali, in particolare integrali che sono di cili da calcolare numericamente per altra via perché per esempio l'integrando varia molto rapidamente. In sica tante cose si esprimono tramite integrali per cui il metodo Monte
Car-lo è di uso abbastanza comune. Uno dei primi casi in cui il Monte CarCar-lo fu usato fu il calcolo delle reazioni nucleari a catena. Quando un neutrone urta un nucleo non si può dire con certezza se il nucleo si scinda o meno, né quanti neutroni verranno prodotti: conosciamo solo la probabilità di questi eventi. Allora simuliamo l'urto generando un numero casuale (i primi calcoli vennero fatti usando una roulette come generatore di numeri randomici) ed a seconda del numero uscito diciamo "è avvenuto questo o quell'evento". Per esempio, poniamo che si sappia che in ogni urto la probabilità di generare un neutrone è il 45%, quella di generarne due è il 30%, e quella di non generarne nessuno è il 25%. Allora estraiamo per esempio un numero fra 1 e 100 e diciamo: "se esce un numero fra 1 e 45 supponiamo che sia stato prodotto un neutrone; se esce un numero fra 46 e 75 supponiamo che ne siano sta-ti prodotsta-ti due; e se esce un numero fra 76 e 100 supponiamo che non ne sia stato generato nessuno." La simulazione dunque procede come segue: si parte con un certo numero di neutroni; si calcola la probabilità che ciascun neutrone ne produca altri, col metodo descritto sopra; si calcolano le altre grandezze a cui si possa essere interessati (p.es. l'energia rilasciata in ogni scissione); per ognuno dei nuovi neutroni si calcola la probabilità di generar-ne altri, e si ripete... Metodi di questo tipo sono tuttora usati in ingeggenerar-neria nucleare, ed altri simili si usano per descrivere il moto degli elettroni nei dispositivi elettronici al ne di predirne o studiarne il funzionamento. Altri esempi importanti riguardano il calcolo di proprietà della materia conden-sata (solidi e liquidi) e no (plasmi etc). In un sistema che non sia allo zero assoluto atomi e molecole sono agitati in continuazione ed in modo sostan-zialmente casuale (moto Browniano). Con il metodo Monte Carlo si simula questa agitazione generando numeri casuali e spostando gli atomi/le molecole di conseguenza. Come esattamente vengono eettuati gli spostamenti è un argomento un po' tecnico e non sto a descriverlo. La simulazione consiste nello studio del comportamento di un sistema mediante la sua riproduzione in un contesto controllabile. Nella simulazione al calcolatore si costruisce un modello matematico costituito da equazioni che descrivono le relazioni tra le componenti del sistema oggetto di studio e il loro legame con il suo funzio-namento/comportamento, con l'obiettivo di eettuare esperimenti virtuali sul modello matematico assumendo che i risultati di tali esperimenti costitui-scano una riproduzione su cientemente accurata del comportamento che avrebbe il sistema. Questo allo scopo di accrescere la comprensione del suo funzionamento, veri care (o negare) la validità di ipotesi su di esso, racco-gliere informazioni per poter formulare possibili previsioni, per implementare meccanismi di controllo del sistema modellato, ecc. Oggi il metodo Monte Carlo viene usato per moltissime nalità, dalla decisione di dove eettuare perforazioni petrolifere all'ottimizzazione della compattazione dei ri uti
ne-gli impianti di trattamento. Apparentemente è semplice ma è molto potente. La base è il lancio dei dadi. Se si lancia un dado 100 volte e se ne registrano i risultati si scoprirà che i numeri presenti sulle sei facce usciranno circa un sesto di volte per uno, ma non esattamente. Questo perché i risultati sono casuali. Se si lancia il dado mille volte e poi un milione di volte, i risultati si avvicineranno sempre di più a quelli teorici. È la cosiddetta legge dei grandi numeri. Il dado rappresenta i rischi, predicibili e distribuiti in modo eguale: ogni faccia/rischio ha un sesto di probabilità di accadere e cinque sesti di non accadere. Ora, supponiamo che ogni dado sia un rischio di progetto e le facce rappresentino i possibili accadimenti. Esempio: un dado rappresenta il rischio che un progetto venga ritardato a causa di cambiamenti nello sta. Una faccia potrebbe portare la possibilità che il progetto ritardi sei mesi a causa di un turnover del 20%, un'altra un ritardo di due anni a causa di un turnover dell'80%. Si possono introdurre dei pesi, per cui il dado potrebbe essere sbilanciato in modo da rendere più o meno probabili certi risultati. Ogni rischio avrebbe il suo dado: sviluppo con molti errori, tagli di budget. I simulatori che usano il metodo di Monte Carlo lanciano tutti i dadi/rischio assieme e ne registrano i risultati combinati. Più volte si tira il dado, più la distribuzione dei possibili risultati è esatta. Se si mettono i risultati su un gra co cartesiano ne risulta una curva che sembra un formicaio, dove il punto più elevato rappresenta il risultato combinato più probabile e le terminazioni laterali i risultati sempre possibili ma meno probabili.Una volta determinato in questo modo il pro lo di rischio di un progetto, è possibile inserire nel progetto ulteriori risorse (denaro e tempo, per esempio) per mitigare i rischi che si trovano nei punti più alti della curva. Se, ad esempio, la distribuzione originaria evidenzia che il progetto ha il 50% di probabilità di subire un ri-tardo di sei mesi, si può decidere di prevedere ulteriori tre mesi di tempo di sviluppo per mitigare questo rischio. Le simulazioni Monte Carlo permetto-no di eettuare analisi di sensibilità, ossia lanciare un solo dado tenendo fermi gli altri su un certo risultato per vedere cosa succede quando cambia un solo rischio. Questo può consentire di scoprire che solo una piccola parte dei rischi presi in considerazione rappresenta la stragrande maggioranza delle probabilità globali di rischio di un progetto, e quindi concentrare su quelli le energie. Le simulazioni Monte Carlo dovrebbero essere eettuate su tutti i progetti presenti a portafoglio, per classi carli in ordine di rischio. Ciò con-sente di generare una frontiera della massima e cienza, ossia una linea che collega la combinazione di progetti che garantisce i maggiori bene ci a un livello di rischio predeterminato. La frontiera e ciente permette di evitare i rischi non necessari e impedisce che venga scelto un portafoglio con rischi uguali ma bene ci più bassi di un altro.
1.3 Modularità, Acceptance Probability e
Mos-se
E' esperienza comune che le reti sociali siano composte da comunità di nodi fortemente interconnessi rispetto ai nodi appartenenti ad altre comunità. Questa struttura modulare è stata riscontrata non solo per le reti sociali, ma anche per Internet, in food webs e in reti biochimiche. E' una credenza diusa che la struttura modulare delle reti reali rivesta un ruolo critico nella funzionalità della rete stessa. Nasce quindi l'esigenza di sviluppare degli algoritmi per identi care accuratamente tali moduli. Guimerà e Amaral[?] hanno proposto un metodo basato sulla massimizzazione della modularità. La modularità di una partizione, i cui moduli sono a loro volta formati dai singoli nodi di una rete, è de nita come:
M ≡ NM X s=1 " ls L− ds 2L 2# (1.1) dove NM è il numero di moduli, L è il numero di links della rete, ls è il
numero di links fra nodi di un modulo s, e ds è la somma dei gradi dei nodi
di un modulo s. La logica che sta dietro a questa de nizione di modularità è la seguente. Una buona partizione di una rete in moduli deve avere molti links fra nodi di uno stesso modulo e il minor numero possibile di links fra nodi di moduli diversi. Tuttavia, provando a minimizzare solo il numero di links fra moduli dierenti (o equivalentemente, massimizzare il numero di links all'interno dei moduli) la partizione ottimale è formata da un singolo modulo e nessun links fra moduli. L'equazione (1.1) risolve questo problema imponendo che M = 0 se i nodi sono assegnati ai moduli in modo casuale o se tutti i nodi sono nello stesso cluster.
L'obiettivo di un algoritmo di identi cazione di moduli è trovare la parti-zione che massimizzi la modularità. Sono stati proposti diversi metodi per raggiungere questo obiettivo, molti di questi utilizzano procedure euristiche e usano M, o misure simili, per stimare la propria performance. A dierenza di questi approcci, noi utilizziamo il Simulated Annealing (SA)[?] per deter-minare la migliore con gurazione dei moduli della rete attraverso una diretta massimizzazione di M.
Per l'identi cazione dei moduli, l'obiettivo è di minimizzare il costo dato da: C = −M dove M è la modularità come de nita nell'equazione 1.1. Ad ogni livello di temperatura, viene eseguito un numero di aggiornamenti causali che sono accettati con un probabilità (acceptance probability) data da:
p = (1 se Cf ≤ Ci exp −Cf−Ci T se Cf > Ci (1.2) dove Cf è il costo dopo l'aggiornamento e Ci è il costo prima
dell'aggiorna-mento.
In particolare, per ogni livello di temperatura T abbiamo considerato due tipi di mosse per transire dallo stato corrente a quello successivo:
• ni = f S2 movimenti individuali di nodi da un modulo ad un altro
• nc = f S movimenti collettivi che consistono nel raggruppare (merge)
due moduli o suddividerne (split) uno
dove f è scelto tipicamente f = 1 e S rappresenta il numero di nodi della rete.
Dopo che le mosse sono state valutate (vedi equazione 1.2) rispetto ad una certa temperatura T, il sistema è "rareddato" di un certo cooling factor c = 0.995 e quindi la nuova temperatura è data da T0 = cT.
Sia i movimenti individuali di nodi da un modulo ad un altro che per rag-gruppare più moduli insieme, sono semplici movimenti. Il movimento per suddividere due moduli è invece più interessante. In linea di principio, sareb-be su ciente una qualsiasi procedura euristica non-deterministica che generi una suddivisione ragionevole del modulo considerato in più moduli - ossia uno split - con una probabilità nita di essere accettato. Abbiamo consi-derato alcuni schemi possibili per eettuare lo split. Quello che ha dato risultati migliori consiste nell'isolare il modulo dal resto della rete ed ese-guire un Simulated Annealing "annidiato", completamente indipendente da quello "globale". Inizialmente viene isolato il modulo da suddividere, poi i nodi di tale modulo sono partizionati in due gruppi casuali e la temperatura iniziale del "nested" SA è settata ad un valore alto; a questo punto ven-gono eseguiti dei movimenti individuali di nodi in accordo alla modularità del modulo isolato e la temperatura del "nested" SA è diminuita di un coo-ling factor. Il "nested" SA è eseguito nché la temperatura dello stesso non raggiunge quella del SA "globale", a questo punto il risultato del "nested" SA è la suddivisione voluta del modulo in due nuovi moduli. Questi split deve però essere accettato o ri utato in accordo all' acceptance probability, che, come abbiamo visto nell'equazione 1.2, dipende dalla modularità e dalla temperatura globali.
Utilizzando M come " tness function", il metodo risulta più "trasparente" rispetto a quelli che utilizzano procedure euristiche. Inoltre, il SA ci permette di eettuare una ricerca esaustiva e nello stesso tempo minimizza il problema di ottenere partizioni sub-ottimali, in presenza di minimi locali. E' inoltre da far notare che questo metodo non necessita di speci care a priori il numero di moduli, ma piuttosto, tale valore è ottenuto come risultato dell'algoritmo.
1.4 Limiti della Modularità e come superarli
Una caratteristica fondamentale del nostro metodo è quella di permettere di estrarre proprietà statisticamente signi cative da un insieme di partizioni, invece di concentrarci su una singola partizione. Questa caratteristica è moti-vata dal fatto che molte partizioni potrebbero avere alti valori di modularità pur essendo molto diverse come struttura. In realtà, è semplice costruire re-ti nelle quali a parre-tizioni diverse corrispondano uguali valori di modularità. Questa degenerazione della modularità, come viene indicato in letteratura, è un limite che è stato individuato indipendentemente da Good ed altri[?]. Il metodo proposto combina un insieme di partizioni ponendo l'attenzione sui bordi ("Quali nodi adiacenti sono separati in dierenti moduli?") piut-tosto che sui loro volumi ("Quali nodi sono raggruppati insieme?") e poi calcolando per ogni con ne il numero di partizioni nel quale tali con ni sono presenti. Poiché noi siamo interessati a reti che hanno una propria geogra a e i moduli sono sempre spazialmente compatti nel nostro caso, potremmo limitarci a considerare solo i limiti che sono anche bordi geogra ci fra nodi. Tuttavia, l'idea può essere facilmente generalizzata a reti non geogra che uti-lizzando un'adeguata e semplice visualizzazione. Dato che, tutte le partizioni dell'insieme hanno un alto valore di modularità, questo metodo permette evi-denziare similarità e dierenze in partizioni degeneri, producendo un'unica partizione (o più precisamente, una mappa) della rete e così superando il problema della degenerazione.
Un altro problema della modularità è conosciuto in letteratura come limi-te della risoluzione, ed è stato reso noto per la prima volta da Fortunato e Barthélemy[?]. Gli autori presentano due reti arti ciali non pesate, che mostrano un chiara e intuitiva struttura comunitaria, tuttavia esistono delle partizioni che non ri ettono questa struttura ma hanno il più alto valore di mobilità che la partizione possa avere. In particolare, queste reti sono co-struite connettendo più gra completamente connessi (clique) con link singoli (Figura 1.1)
Figura 1.1: Due reti che mostrano il problema del limite della risoluzione[?].
Le aree ombreggiate indicano una geogra a arti ciale per una visualizzazione dei bordi nelle prossime gure. A sinistra: un anello di 34 cliques, ognuna composta da 6 nodi e connessa alle altre cliques da un singolo link. A destra: una rete di due cliques formate da 20 nodi ciascuna e due cliques composte da 5 nodi.
E' chiaro che ogni clique dovrebbe essere raggruppata in un proprio modulo, ma la migliore partizione in accordo alla modularità raggrupperà più clique insieme. Questa situazione occorre solo se le clique sono piccole, in termini di numero di links, rispetto all'intera rete, di conseguenza la modularità non può individuare correttamente le comunità sotto un certo limite di risoluzio-ne. Nel nostro metodo ogni singola partizione ovviamente sore del limite di risoluzione, tuttavia tale problema può essere alleviato considerando un insieme piuttosto che una singola partizione, sempre che esistano moduli ab-bastanza piccoli per cui tale degenerazione possa manifestarsi. Per valutare come si comporta il nostro metodo rispetto a questo tipo di degenerazione, lo applichiamo alle reti proposte in [?].
La Figura 1.1 (a sinistra) mostra un anello di 34 clique di 6 nodi ciascuna, tutte connesse ai propri vicini da un singolo link. La partizione intuitiva nella quale ogni clique è nel proprio modulo ha una modularità Mreal =
0.9081 mentre una partizione che raggruppa coppie di clique insieme ha una modularità Mopt = 0.9099. Tuttavia, esistono due distinte partizioni che
raggruppano coppie di clique, quindi un insieme di partizioni ottimali sarà composto da queste due partizioni, producendo una mappa dei con ni nella quale ogni frontiera fra due clique appare nel 50% dell'insieme delle partizioni. Per chiarire meglio quanto detto, mostriamo una struttura arti ciale della rete e ne determiniamo le partizioni e i con ni, (Figura 1.2).
Figura 1.2: Struttura arti ciale della rete per determinare le partizioni e i con ni
A sinistra: la partizione ottimale nell'anello di clique raggruppa coppie di clique insieme (lo stesso colore è usato per moduli multipli). Al centro: esempio di partizione generata dall'algoritmo di ottimizzazione della modularità. A destra: I con ni individuati nell'anello di clique, non sono sola a coppie ma fra ogni clique. La scala cromatica indica la percentuale di partizioni nelle quali il con ne è stato individuato.
La seconda rete proposta in [?], è composta da due cliques, una di 20 nodi ed una di 5 (Figura 1.1 a destra). Le due piccole cliques sono raggruppate in uno stesso modulo dal partizionamento ottimale (Mopt = 0.5426) sebbene
ci aspettassimo, anche in questo caso, che ognuna sia nel proprio modulo (Mreal = 0.5416). Il nostro metodo, in questo caso, non è capace di
cattu-rare l'intuitiva struttura comunitaria (Figura 1.3), poiché non esiste alcuna degenerazione (la partizione nella quale solo una delle due piccole clique sono raggruppate con una delle grandi, ma non l'altra, sono troppo lontane dalla partizione ottimale prodotta dall'algoritmo, Mdeg = 0.4959)
Figura 1.3: Con ni individuati nella rete mostrata in Figura 1.1
A destra: L'algoritmo in questo caso non è capace di trovare i con ni fra le due cliques piccole.
Se noi estendiamo la rete precedente aggiungendo altre due piccole cliques, la partizione che raggruppa tutte le clique in un proprio modulo è ancora sub-ottimale rispetto ad ogni partizione che raggruppa insieme più che una delle piccole clique, ma in questo caso esiste una degenerazione e l'insieme di partizioni rivela la reale struttura comunitaria in queste rete (Figura 1.4)
Figura 1.4: Estensione della rete di clique mostrata in Figura 1.1
A destra: Poiché sono presenti molte partizioni con alta modularità che raggruppano le piccole cliques a coppie, in questo caso, il nostro metodo può individuare la corretta struttura comunitaria.
Concludendo, il nostro metodo è capace di dissolvere sia il problema del-la degenerazione deldel-la modudel-larità che quello del limite di risoluzione deldel-la stessa, ammesso che ci siano moduli abbastanza piccoli per introdurre tale degenerazione.
![Figura 1.1: Due reti che mostrano il problema del limite della risoluzione[?].](https://thumb-eu.123doks.com/thumbv2/123dokorg/7540441.108102/15.892.193.700.206.404/figura-due-reti-mostrano-problema-limite-risoluzione.webp)
