Corso di Laurea in Business Informatics

Analisi Reti Sociali

Last Fm Advanced Analysis

A.A. 2015-2016 Alessandro Romano (537128) Tommaso Furlan (538049)

1. Data Crawling Questa fase preliminare dello studio ha permesso di recuperare i dati utili all’analisi delle caratteristiche generiche della rete e per l’analisi avanzata successiva. Avremo quindi la rete e i data set ausiliari associati. Sarà necessario fornirsi di una Last FM API key1 e di una Spotify API key2. Utilizzando lo script network.py senza limitazioni sul numero di nodi (max_users) abbiamo ottenuto la rete Last FM desiderata, da cui come vedremo nel paragrafo relativo alla Data Analysis andremo ad estrarre la Giant Component, il cui nodo radice sarà l’utente Stryder1980 (risulterà essere anche quello con più amici sul social). Questo processo di crawling si divide in tre fasi, nello specifico:

• Network crawling: creazione della rete attraverso lo script Network.py, ottenendo prima il file lastfm_net16.csv, e successivamente attraverso lo script Nertworkcleaned.py un data cleaning sulla rete.

• Listening crawling: recupero degli ultimi 100 brani ascoltati da ogni utente della rete, utilizzando lo script Listening.py ottenendo il file listenin100.csv

• Artist Genres crawling: recupero delle informazioni relative al genere di ogni artista presente in listening100.csv, con il relativo indice di frequenza di ricerca e il peso. Ad ogni artista è stato inoltre attribuito un indice (hotness) relativo alla popolarità. Per fare ciò è stato utilizzato lo script echonest.py

1www.lastfm.it/api2https://developer.spotify.com/

2. Data Semantics

• listenings.csv : contiene gli ultimi 100 brani ascoltati da ogni utente. Ogni record sarà caratterizzato da:

o user_id: identifica gli users o date: timestamp dell’ascolto o track: titolo della canzone ascoltata o artist: cantante o album: album a cui appartiene il brano

• genres.csv : contiene un'associazione dei principali generi per un dato artista secondo dei

pesi dati da LastFM:

o artist: autore del brano o genre: genere dell’autore o freq: indice che determina la frequenza con la quale il genere viene utilizzato per

ricercare l’artista o weight: indice che determina l’importanza che uno specifico termine ha nel ricercare

l’artista

• hotness.csv: contiene il nome dell’artista e il relativo indice di popolarità

o artist: nome dell’artista/gruppo che ha prodotto la traccia o hotness: indice che determina la popolarità attuale di un artista

• network.csv : contiene la rete degli utenti che sono presenti almeno una volta nella listening

file:

o user_id1: l’id dell’utente contenuto nella lista degli ascolti o user_id2: user amico dell’user1 (ma non necessariamente contenuto nella lista degli

ascolti)

3. Network Analysis 3.1 Basic Measures

Last Fm Network N 733631 L 21531993

Connected Components 60 Max Connection 2691106855265

AVG Degree 5.869961 Density 0.0000080012

Clustering Coefficient 0.071 Le prime due misure riportate sono di tipo quantitativo e danno un idea della dimensione della rete e del grado di collegamento dei nodi. Il Clustering Coefficient punta a quantificare l'esistenza di una comunità all'interno della rete, quindi misura la densità locale, ovvero la probabilità che due nodi adiacenti ad un nodo comune siano connessi tra loro. Il valore sarà di 7.1%, che rispecchia gli standard delle reti reali. La Network Diameter rappresentà il cammino più lungo tra due nodi della rete quindi si può definire come la distanza massima tra ogni coppia di nodi, mentre Average Path Lenght sarà la distanza media. Procederemo quindi ad isolare la Giant Component principale, eseguendo su di essa il resto dell’analisi.

Giant Last Fm Network N 4897 L 45917

Connected Components 1 Max Connection 11987856

AVG Degree 18.7531 Density 0.00383029

Clustering Coefficient 0.11012059 Average Path Lenght 3.438968

Isolata la componente Giant, potremo notare come le metriche restino ovviamente in linea con quelle analizzate nella rete principale completa. Ci soffermiamo sull’ Average Path Lenght che si collega ad una proprietà di grande importanza nelle reti sociali, come il grado di separazione che hanno tra loro i nodi della rete. Come si può vedere nella tabella soprastante, il valore è pari a 3.438968, ciò significa che mediamente un nodo può raggiungere un qualsiasi altro nodo in 4 "passi". Questo fenomeno è detto Small World.

3.2 Degree Distribution Analizziamo la Degree Distribution, che ci permetterà di comprendere meglio la forma della rete. L'istogramma seguente, permette di capire come il grado (= il numero di neighbors) sia distribuito sui nodi della rete. La distribuzione presenta un forte addensamento di nodi con basso grado ed una lunga coda caratterizzata da pochi hub con grado più alto. Questo andamento tipico delle reti naturali, è definito Power Law.

(Degree Distribution)

(Degree Distribution Log Log)

Come è possibile vedere dalla figura, la distribuzione avrà un andamento lineare decrescente, comunemente riscontrabile come già detto nelle reti naturali. Inoltre distribuzioni di questo genere vengono anche definite Scale Free, ovvero mantengono la proprietà evidenziata dal grafico log-log per un numero di nodi tendente ad infinito. 3.3 Centrality Measures Le misure di Centrality ci aiutano ad identificare i più importanti nodi della rete, evidenziando cosa rende un nodo importante. Degree Centrality

Questa misura determina il numero di archi incidenti in un determinato nodo della rete, ovvero il numero di legami che un utente possiede. Attraverso la Degree Distribution riusciamo ad individuare quei nodi con grado maggiore rispetto ad altri, che nei casi di reti naturali ci aiuterebbero ad evidenziare la presenza di hub, una caratteristica chiave che contraddistingue le reti naturali. Nella tabella potremo vedere quale sia il nodo con maggiore grado di centralità (Turkishunicorn2).

Betweenness Centrality

Questa misura ci darà indicazioni sulla centralità e influenza di un nodo all'interno della rete. Per ognuno di essi, tale misura viene definita come il numero totale di cammini minimi che lo attraversano. In pratica è una misura che calcola l'influenza di un nodo sul flusso di informazioni tra altri nodi, nel caso in cui il flusso segua un percorso minimo. Anche in questo caso, viene riportato l'elenco dei primi nodi messi in ordine secondo il loro valore di betweennes. E' possibile notare come l'indice di Betweenness assume valori elevati per pochissimi nodi, come da immagine.

Node Degree Centrality Turkishunicorn2 0.0649509803922 AllanDemigod 0.0616830065359 ChAelitaNicole 0.0604575163399

Mic_28 0.0494281045752 juhansen 0.0484068627451

wdtds 0.047589869281 Brabantze 0.0404411764706 J-I-N-X 0.0402369281046 sw1ne 0.0402369281046

slaykarth 0.0394199346405

Node Betweenness caredu1 0.0691775682133 Mic_28 0.0442723896018 Stryder1980 0.0426835834726 Turkishunicorn2 0.036485860738 andrepyk 0.0262383312982 ChAelitaNicole 0.0207536762628 juhansen 0.0203159701406 JMLKAIGUN 0.0200830522127 nacholorient 0.0191420387678 Brabantze 0.0173916042703

Closeness Centrality

Questamisuraesprimeilgradoincuiunnododellareteèvicinoatuttiglialtri,ovveropuòessererappresentatocomel'inversodellasommadegliShortestDistancetraogninodoeognialtronodonellarete.Rispettoalladistribuzionedell'indicediBetweenness,siosservaunamaggiore compattezzadella rete, come sipuònotaredalminorscostamentotracoppiediutenti.

Node Closeness Stryder1980 0.406307053942 Brabantze 0.394266387502 juhansen 0.391742678829 AllanDemigod 0.390524048816 nacholorient 0.388047871919 Mic_28 0.385754806177 slaykarth 0.384966189652 Turkishunicorn2 0.381873488807 NikosKontovas 0.379123431934 J-I-N-X 0.37745740498

4.Community Discovery

Questa analisi permette l'estrazione di informazione da reti sociali più o meno complesse. Con ilconcetto di community in una rete si intende un insieme di individui che sono molto simili o prossimitra loro più che a chiunque altro al di fuori della comunita. Quindi le community sono gruppi di entitache presumibilmente condividono tra loro le stesse proprieta comuni e/o giocano ruoli similari entro unfenomeno interattivo che e stato rappresentato. Per community discovery si intende, quindi, la ricercadi insiemi di nodi fortemente interconnessi tra loro e scarsamente collegati con il resto della rete e puoessere considerata come una variante del problema di clustering nel data mining. Le reti sociali delmondo reale tendono ad essere organizzate secondo una struttura a community. Ogni individuotipicamente appartiene simultaneamente a diverse community, come ad esempio colleghi di lavoro,colleghi di universita e compagni di ballo. Per reti di piccole dimensioni le aree più dense sono facilmente identificabili mediante un'ispezionevisiva, ma il problema si fa molto più arduo per le reti di medie e grandi dimensioni. Pertanto sieffettuera un'analisi visiva con l'unico scopo di sostenere e comprendere un approccio più strutturato.Tra i vari algoritmi presenti nello scenario della community discovery ne abbiamo selezionati tre:DEMON, K-Clique e Louvain. La scelta e stata guidata dalla semplicita di utilizzo di questi utili, inquanto gia implementati e testati. Nel seguito del capitolo si descriveranno gli algoritmi selezionati esuccessivamente i risultati emersi dalla loro applicazione alla nostra rete. Una volta identificate lecommunity, grazie ad opportune distribuzioni ottenute da diverse metriche si andranno a delineare lecaratteristiche strutturali della rete. Questo per poter comprendere i tipi di comportamenti e relazioni inessa. Infine si cerchera di validare tali risultati attraverso dataset addizionali, effettuando unavalidazione a campione delle community ottenute.

4.1 DEMONL’algoritmo DEMON si basa sull’idea che ogni nodo ha una visione locale della rete, per cui enecessario trovare un meccanismo che permetta di individuare le community nonostante l’assenza diinformazioni relative alla struttura globale della rete. Dato un grafo G(V, E) e un nodo v∈V sidefinisce come EgoNetwork di tale nodo, indicata come EN (v, G), il sotto-grafo G'(V', E' ) dove V' el’insieme che contiene il nodo v e tutti i suoi vicini ed E' e il sottoinsieme di E contenente tutti gli archi(u, v) con u∈V ' e v∈V ' . Per ogni nodo v la sua rete EgoMinusEgo(v, G) e definita come la suaEgoNetwork in cui il nodo centrale e tutti gli archi a lui connessi sono stati rimossi. A questo punto epossibile individuare i gruppi che si vengono a formare attorno al nodo centrale. Tale approccio e dettodemocratico in quanto ogni nodo fornisce la propria prospettiva della comunita circostante esuccessivamente le varie prospettive vengono unite. L’algoritmo procede come segue, per ogni nodo

v∈G :1. calcolo EgoN etwork(v, G)2. calcolo EgoM inusEgo(v, G)3. esecuzione dell’algoritmo LabelPropagation applicato alla EgoM inusEgo(v, G)4. inserimento del nodo v in tutte le comunita trovate e unione delle comunita in base ad un certo

criterio di similaritaIn particolare l’algoritmo LabelPropagation permette di individuare tutte le comunita presenti nel grafoa cui viene applicato, classificando un nodo grazie alle etichette dei suoi vicini. Il criterio di similaritautilizzato per effettuare la fusione tra due comunita e il seguente: date due comunita C1 e C2 vengonounite se e solo se al più ɛ% della più piccola non e inclusa nella più grande.

4.1.1 Parametri e risultati

L'algoritmo DEMON, come spiegato precedentemente, necessita di due parametri fondamentali perl'esecuzione:

• ɛ – tolleranza richiesta per unire le community• minimun community size – numero minimo di nodi necessari per formare una community

Il secondo parametro, secondo quanto suggerito dalla letteratura, sara uguale a 3 per ogni esecuzionedell'algoritmo.Assegnare un valore ad ɛ risulta impossibile senza un adeguata ispezione empirica, difatti i risultatisaranno valutati in base alla variazione di quest'ultimo che, per valori bassi, risultera più restrittivonell'individuazione delle community, viceversa per valori elevati. Pertanto si fa variare nell'intervallo[0.001,0.4], selezionando, ad intervalli regolari, 60 valori.In fig. 1 viene riportato il risultato dell'esecuzione. Questa distribuzione si dimostra crescente poicheall’aumentare di ɛ aumenta anche il numero di community. Al diminuire di ɛ la distribuzione sembrastabilizzarsi intorno ad un valore di circa 40 community. Il valore massimo di ɛ considerato e 0.4 erestituisce oltre 500 community. Infine osserviamo che nell’intervallo ɛ∈[0.25,0.4 ] si evidenzia unforte aumento del numero di community ottenute che si discosta dagli altri risultati.

Non e semplice capire quali valori di ɛ identifichino la struttura sociale delle community, quindi siapprofondisce ulteriormente l'analisi dei risultati ottenuti per ɛ∈{0.034,0 .234,0.301,0 .368 } inquanto identificano comportamenti eterogenei. Si esegue l'algoritmo e si collezionano le 30 communitypiù grandi. Si analizza la distribuzione del numero di nodi al variare delle community ordinate pernumero di nodi decrescente.Vediamo in fig. 2 che le curve con ɛ = 0.234 e ɛ = 0.301 presentano un comportamento molto simile esolo con valori di ɛ molto distanti riusciamo ad ottenere significative discriminazioni tra community.

Figura 1: Numero di community al variare di ɛ nell'intervallo [0.001,0.4]

Per valutare i risultati utilizziamo le metriche density e transitivity, valutando le comunita ottenute inrelazione al grafo di partenza.La densita e definita come:

2 mn(n−1)

dove m rappresenta il numero di archi e n il numero di nodi. La densita nelle reti sociali puo essere unparametro che rappresenta l’efficienza nello scambio di informazioni e l’utilita per i singoli individui.Tale metrica assume valori compresi tra 0 e 1: valori prossimi allo 0 indicano bassi livelli di coesione,mentre valori vicino ad 1 indicano alti livelli di coesione della rete. A livello locale permette di rilevarequanto i vicini di un nodo siano interconnessi tra loro. A livello globale rappresenta invece la media ditutti i coefficienti della rete.

Figura 2: Prime 30 community in ordine decrescente per numero di nodi

Figura 3: Density per le prime 30 community in ordine decrescenteper numero di nodi

In fig. 3 e mostrata la distribuzione della densita, si nota un andamento crescente della distribuzione adimostrazione del fatto che al diminuire del numero di nodi per community aumenta il valore didensita. Per ɛ = 0.034, questo fenomeno e chiaramente accentuato, difatti dal nodo 18 si registra unincremento quasi esponenziale del valore di density, causato dalla dimensione molto ridotta dellecoummunity su cui e calcolata la densita.Il coefficiente di clustering (o transitivita) e la misura del grado in cui i nodi di un grafo tendono adessere connessi fra loro, in questo caso calcolato localmente.

Analogamente a quanto rilevato per il calcolo della densita, anche in questo caso, ɛ = 0.034 ha unandamento molto più oscillatorio in confronto alle altre curve, crescendo rapidamente nella parte finale,caratterizzata da community con pochi nodi.

4.1.2 Community OverlapNell’ottica di scegliere un piccolo campione di community su cui effettuare una validazione con datiesterni, si analizza una possibile sovrapposizione tra community. Sempre considerando le 30community più popolose ordinate per numero di nodi, costruiamo una heatmap che per ogni coppia dicommunity esprima un indice di sovrapposizione. Come metrica di overlap si utilizza il JaccardCoefficient. Questo aspetto potra aiutarci nella selezione di community in un trade-off tra popolosita esovrapposizione delle stesse, infatti il nostro obiettivo e individuare community con molti nodi che allostesso tempo abbiano un basso numero di nodi in comune.Il coefficiente di Jaccard puo assumere valori nell'intervallo [0,1], dove 1 indica la massima similaritatra gli insiemi confrontati. In fig. 5, questi valori, sono mappati con una scala di colore rosso. Difatti,sulla diagonale si rileva una similarita massima caratterizzata da una tonalita di rosso più scura.Si nota una maggior intensita di colore rosso nella regione in basso a sinistra della matrice, stante adindicare che le community più popolose sono le più sovrapposte, mentre le più piccole sono menosovrapposte in linea generale. Nella parte alta della matrice infatti notiamo un comportamento opposto,ovvero valori di Jaccard che tendono a zero. Il comportamento che emerge globalmente utilizzandoquesta misura non sorprende, poiche community grandi hanno una maggior probabilita di esseresovrapposte. Le community 7,8,9 si discostano dai comportamenti generali appena descritti,mostrando un'intensita di colore leggermente più bassa in confronto ai loro vicini. Pertanto, vista la loroeterogeneita, le successive analisi si concentreranno su queste.

Figura 4: Coefficiente di clustering per le prime 30 community

4.1.3 Visualizzazione del grafoPer rafforzare le analisi effettuate, si riporta una rappresentazione grafica delle community trovateall'interno del grafo. I nodi verdi appartengono alla community 7, quelli gialli alla numero 8 e quelliblue alla 9. Infine, i nodi bianchi sono quei nodi che appartengono a tutte e tre le community.

Entrambe le rappresentazioni si riferiscono allo stesso grafo, ma nel primo caso si evidenzia il degreedi ogni nodo. Solo la community 7 e facilmente individuabile, le altre due risultano sovrapposte.

4.1.4 Validazione con dati esterniSi sono scelte le community 7,8,9 per il loro reciproco livello di eterogeneita rispetto ad altre e per laloro significativa popolosita. Adesso esamineremo queste community con dati ausiliari. Questi daticaratterizzano il nodo con attributi diversi come le traccie ascoltate, artisti, ore ascolto brano, generimusicali ecc. In particolare si esaminano gli attributi artista e genere, in quanto risultano essere i piùcompleti e significativi. LastFM da la possibilita agli utenti di inserire nuovi generi per i brani ascoltati,

Figura 5: Matrice di Jaccard calcolata sulle 30 community più popolose

aumentando esponenzialmente il numero di classi per quell'attributo. Quindi, er questioni divisualizzazioni, l'attributo other sara pari al 50% dei dati.Quindi, per ogni community si riportano i primi 7 artisti/generi più ascoltati, raggruppando i restanti inuna classe “other” per questioni di rappresentazione.

Figura 6: Primi sette artisti/generi per community 7

Figura 7: Primi sette artisti/generi per community 8

Figura 8: Primi sette artisti/generi per community 9

Per tutte le community, il genere rock e l'artista Duft Punk, sono i più ascoltati, pertanto non forniscono un informazione molto discriminante. Spostandosi sulle restanti classi si possono delineare le seguenti caratteristiche:

• community 7: artisti come Depeche Mode e Pink Floyd registrano una frequenza di ascolti pari al 6%, inoltre una grande fetta di ascolti e assegnata ai Beatles. Difatti e l'unica comunita ad ascoltare canzoni e musiche degli anni 80' con una frequenza superiore al 4%. Queste caratteristiche spiegano chiaramente la distanza e la differenza tra le altre community. La soprannominiamo “nostalgica”.

• community 8: i generi predominanti sono alternative rock, experimental e alternative, con una percentuale di ascolti di circa il 5% per gruppi come MGMT e The xx. Si tratta appunto di generi e artisti alternativi, di conseguenza definiamo questa community come “alternativa”

• community 9: gli artisti Coldplay, Lana del Ray e Radiohead, discriminanti per questo community, hanno un carattere romantico e giovanile, caratteristico del pop e della musica alternativa. Pertanto definiamo la community come “giovanile”.

4.2 K-CliqueL’algoritmo K-Clique si basa sul metodo della percolazione per l’individuazione delle comunitaall’interno di reti complesse. Per definizione, una K-Clique e un sotto-grafo completamente connessocomposto da K nodi e da k(k-1)/2 link. Il metodo si basa sull’idea che le comunita formano piccoleclique, che condividono i propri nodi con altre clique, sempre appartenenti alla stessa comunita. Insostanza una clique o grafo completo e caratterizzato dall’avere tutti i suoi nodi a due a due adiacenti.Dunque Una k-clique e il sotto-grafo di massima estensione in cui ogni nodo ha un numero minimo dinodi adiacenti pari a k. Infatti due k-clique si definiscono adiacenti se condividono k-1 nodi.Concludendo, una comunita si puo definire come la massima unione di k-clique adiacenti. Per quantoriguarda il settaggio del parametro K, generalmente ci si concentra tra 3 e 6, ma l’attribuzione epiuttosto soggettiva.

4.1.1 Parametri e risultatiSi esegue l'algoritmo iterando su k ∈{2,3,4,5,6,7,8} , riportando nell'istogramma in fig. 9 i risultatiottenuti.

k n° community

2 1

3 444

4 312

5 73

6 12

7 9

8 1

Figura 9: Istogramma numero di comunità al variare di k per k-clique

L’esecuzione con k pari a 1 e 8 ha individuato una sola community. Le ragioni di tale risultato sonodiametralmente opposte nei due casi, nel primo infatti k risulta troppo poco restrittivo e comecommunity emerge banalmente l’intero grafo. Nel secondo caso invece il k e molto restrittivo epermette di rilevare solo una piccola community di 10 nodi. Si nota che, impostando k pari a 3,l’algoritmo K-Clique individua il maggior numero di community tra tutti i risultati ottenuti, vale a dire444 community. Infine analizzando l’andamento della distribuzione, nella globalita, osserviamo chel’andamento e decrescente. Da tale distribuzione emergono scenari interessanti quando K assume valoritra 3 e 6, poiche otteniamo diversi tipi di community per grandezza e densita. Pertanto, per le analisisuccessive, si prendono in considerazione le community create per k ∈{3,4,5,6 } .Come per l'algoritmo DEMON, si riportano il numero di nodi per ogni k e le due metriche di density etransitivity.

Si registra un andamento uniforme per tutti e quattro i campioni, ovvero le community con il minornumero di nodi hanno un valore maggiore di density. Inoltre confrontando ogni singolo andamento, alvariare del parametro k, notiamo che le community con k maggiore ottengono un valore maggiore di

Figura 11: Prime 10 community in ordine decrescente pernumero di nodi

Figura 12: Density per le prime 10 community in ordinedecrescente per numero di nodi

Illustration 13: Figura 3: Transitivity per le prime 10community in ordine decrescente per numero di nodi

density. Unica eccezione la si nota tra community 6 e 8 quando k assume valori pari a 3 e 4, in cui ladensita della distribuzione con k pari a 3 e maggiore di quella con 4.

4.2.2 Visualizzazione del grafoUna validazione visuale dei risultati ci permette di confrontare più intuitivamente i dati relativi aidiversi k. Differentemente da DEMON, in questo caso possiamo considerare questa fase come una verae propria validazione, principalmente grazie al “basso” numero di nodi per ogni grafico. Quindi siriportano 5 community per ogni k ∈{4,5,6,8} , mappando la grandezza del nodo con il suo degree.

In fig. 17 emerge una sola cricca, che permette di mettere in evidenza il tipo di pattern ricercatidall’algoritmo k-clique dove ogni nodo appartiene ad un'unica grande community, quindi e colorato dibianco. Infine il risultato maggiormente apprezzabile e il settaggio con K pari a 6 in fig. 18, in quanto sievidenzia la classica struttura community. In particolare notiamo che l'hub principale della rete el'utente RadyoAtmosfer che e collegato a tutte le community presenti nel grafico.

Figura 14: K-Clique per k=4 Figura 15: K-Clique per k=5

Figura 16: K-Clique per k=6 Figura 17: K-Clique per k=8

4.2.3 Validazione con dati esterniIn questa fase, differentemente da quanto fatto per l'algoritmo DEMON, effettuiamo una validazionecon dati esterni senza una preventiva ricerca di overlapping tra comunita, utilizzando semplicemente letre più popolose per k=4, caratterizzato da un numero complessivamente medio di community.

• community 1: in fig. 18 osserviamo una community partizionata in maniera più uniformerispetto alle community di DEMON. Tra le percentuali più alte spiccano Duft Punk, Radioheade Artic Monkeys, continuando con percentuali di circa il 4% rimanendo in un genereprevalentemente Rock, nello specifico anni 90. Visto il carattere di questo gruppo di nodi, sipotrebbe soprannominare la community come Rock 90'

• community 2: anche in questo caso, le percentuali di ascolto più alte, appartengono agli artistiDuft Punk e Artick Monkeys. Nonostante cio, si registra un'alta percentuale di artistiappartenenti al jazz ed al rock anni 80, come confermano i generi esaminati. Pertantoetichettiamo questa community come Jazz/Rock 80

• community 3: questa community presenta interessanti differenze in confronto a quelleosservate fino ad ora, difatti osservando la fig. 20 e caratterizzata da artisti come Moby e JonhLegend che fino ad ora non ha mai superato una percentuale del 2%. Anche i restanti simantengono nel contesto dance e soul, delineando un profilo che possiamo definire romantico.

Figura 17: K-Clique con k=6

Figura 18: Primi sette artisti/generi per 1 con k=4

Figura 19: Primi sette artisti/generi per 2 con k=4

Figura 20: Primi sette artisti/generi per 2 con k=4

4.3 LouvainE' un metodo per l'estrazione di comunita da reti di grandi dimensioni. Si basa sull'ottimizzazione dellamisura di modularita, per il calcolo della densita all'interno ed all'esterno di una community. Unamodularita ottimale, teoricamente, ci fornisce dei gruppi di nodi che massimizzano questa misura, maper questioni di complessita ci si affida ad approcci euristici per evitare tutte le possibili iterazioni suinodi di un grafo.Semplicemente, l'algoritmo parte con la ricerca di piccole community i cui nodi massimizzanolocalmente la modularity measure, quindi si raggruppano le community trovate in una più grande e siritorna al primo step.

4.3.1 Parametri e risultatiDifferentemente da DEMON e K-Clique, questo algoritmo non necessita di alcun parametro, tranne chedel grafo in cui cercare le community. Per questo motivo, il numero di community create saratotalmente arbitrario e dipendente solo dalla morfologia del grafo stesso su cui verra applicata la misuradi modularity.Il numero di community trovate varia intorno ad un valore di circa 13, quindi prendiamo in analisiquesto risultato.

In fig. 21 si registra una forte diminuzione del numero di nodi a partire dalla community 4 e lerispettive metriche density e transitivity valida ulteriormente questo comportamento. In fig 22 si notaun incremento della desita a partire esattamente dalla community 4, con una pendenza sempremaggiore continuando verso la numero 12. Il fenomeno rispecchia esattamente la definizione didensita, che aumenta al diminuire dei nodi all'interno di una community. Analogamente, in fig. 23notiamo un incremento del grado di connessione tra i nodi al diminuire del numero dei nodi stessi.

4.3.2 Visualizzazione del grafo

Figura 21: 13 community in ordine crescente per numero dinodi

Figura 22: Density calcolata su 13 community ordinate pernumero nodi

Figura 23: Transitivity calcolata su 13 community ordinate pernumero nodi

Per rafforzare l'analisi dei risultati ottenuti si riporta il grafo evidenziando le community ottenute,limitate ad un massimo di 5, ovvero quelle significativamente più grandi. Inoltre, questa limitazione,permette una visualizzazione più chiara.

Nonostante la sovrapposizione, si possono identificare abbastanza chiaramente le 5 community, inparticolare quella più piccola, di colore giallo, caratterizzata da una sparsita maggiore.

4.3.3 Validazione con dati esterniIn fine, per tutte le community trovate con Lauvain, si procede con una validazione utilizzando glistessi dati gia analizzati per le analisi fatte sui precedenti algoritmi.

• community 1: come riportato in fig. 24, ci troviamo davanti ad una community molto simile aquella calcolata con l'algoritmo DEMON, ovvero la numero 7 “nostalgica”. In questo caso emolto più evidente il carattere di quest'ultima, grazie all'artista Artick Monkeys posizionato alterzo posto con una percentuale inferiore al 5%.

• community 2: anche nelle percentuali riportate in fig. 25, possiamo ritrovare molte similitudinicon la community 9 calcolata con DEMON, soprannominata “giovanile”. Ed anche in questocaso, con un valore aggiunto dato dall'artista Muse, fino ad ora mai incontrato.

• community 3: in fig. 26 per la prima volta, si analizza una community con un carattereperfettamente visibile e delineato da artisti appartenenti a generi metal,hard rock e heavy metal.Banalmente, soprannominiamo questa community “metal”.

Figura 24: Grafo risultato Louvain per le prime 5 community più popolose

Figura 24: Primi sette artisti/generi per 1 con k=4

Figura 25: Primi sette artisti/generi per 1 con k=4

Figura 26: Primi sette artisti/generi per 1 con k=4

5. Epidemics L'epidemie sono sempre stato un argomento in cui si mischiavano moltissime aree diverse, in cui però alla fine si poteva riscontrare ambiti strettamente connessi. Nello specifico facciamo una rapida panoramica delle principali epidemie che si possono incontrare:

• Biologico: consideriamo le epidemie basate su malattie che si propagano via aerea (influenza, SARS, tubercolosi), malattie trasmesse per contatto (parassiti, peste), malattie trasmesse attraverso fluidi corporei (ebola, HIV), malattie infettive, etc...

• Digitale: si tratta principalmente di virus informatici, programmi che si auto-riproducono,

che si propagano copiandosi da un computer all'altro. La diffusione ricorda molto quello degli agenti patogeni (epidemia biologica), ma si differenziano soprattutto per ciò che sta alla base del virus. Si annoverano anche i virus per i dispositivi mobile, fra i più conosciuti avremo i worm, trasmessi attraverso tecnologia bluetooth o pacchetti mail.

• Sociale: il concetto di epidemia nelle reti sociali assume i connotati di diffusione e

assimilazione di conoscenze, innovazioni, comportamenti, etc... Le piattaforma social offrono possibilità senza precedenti di monitorare tali fenomeni

Procediamo con l'analisi, a livello teorico simuleremo il fenomeno dell'epidemia sulla nostra rete Last Fm, attraverso l'applicazione dei due principali modelli epidemici (SIR e SIS), con l'obiettivo di studiare i relativi comportamenti all'interno della rete. Verificheremo se il numero degli infetti sarà destinato ad innalzarsi o calare durante l'epidemia, partendo dal presupposto che essa sia influenzata da due fattori:

• Struttura della rete • Probabilità che un nodo venga contagiato

Proprietà fondamentale dell'epidemia è che un nodo v si infetterà se e solo se esisterà un percorso da v ad uno dei nodi precedentemente infettati, quindi ciò denota non soltanto il fondamentale ruolo del grado di infettività presente nella rete, ma soprattutto l'importanza che avrà la struttura di essa. A livello pratico, le implementazioni verranno fatte grazie alla libreria python NepidemiX1. 5.1 SI (Susceptible - Infected ) Model

Figura 27: SI model

1http://nepidemix.irmacs.sfu.ca/

Si consideri una malattia che si diffonde in una popolazione di N individui, si denoterà con S(t) il numero di individui che sono susceptible (sani) al momento temporale t, e I(s) gli individui infetti. Al tempo t=0, avremo che tutti i nodi saranno suscettibili [S(0)=N] e nessuno sarà infetto [I(0)=0]. Supponiamo inoltre che un tipico individuo della popolazione abbia <k>contatti e che la probabilità di infezione venga trasmessa da un infetto ad un suscettibile in un unità di tempo sia β. Se un singolo individuo diventa infetto al tempo t=0 [I(0)=1], sarà necessario considerare diversi fattori per capire quante persone saranno infettate in un determinato lasso di tempo t. Per semplicità considereremo la frazione di popolazione sana e infetta al tempo t, rispettivamente:

𝑠 = 𝑆(𝑡) 𝑁 𝑖 = 𝐼(𝑡)

𝑁 La probabilità che una persona infetta incontri una persona sana è 𝑆(𝑡) 𝑁, quindi la persona infettata entrerà in contatto con < 𝑘 >∗ 𝑆(𝑡) 𝑁 soggetti sensibili in una unità di tempo. Dal momento che I(t) individui infetti stanno trasmettendo l'agente patogeno (infezione), ciascuno con tasso β, il numero medio di nuove infezioni dI(t) durante un intervallo di tempo dt è:

(𝛽 ∗< 𝑘 >∗ 𝑠 ∗ 𝑡)𝑑𝑡 Conseguentemente I(t) cambierà al tasso

𝑑𝑖𝑑𝑡 = 𝛽 ∗< 𝑘 >∗ 𝑠 ∗ 𝑡 →

𝑑𝑖𝑑𝑡 = 𝛽 ∗< 𝑘 >∗ 𝑖(1 − 𝑖)

Il prodotto 𝛽 ∗< 𝑘 > , verrà definito come Transmission rate (o Transmissibility). Integrando entrambi i membri dell’equazione poco sopra, otterremo

𝐿𝑛𝑖– 𝐿𝑛 1 − 𝑖 + 𝐶 = 𝛽 ∗< 𝑘 > che con le iniziali condizioni di 𝑖9 = 𝐼 0 potremo quindi assegnare a 𝐶 = 𝑖9 (1 − 𝑖9) , ottenendo quindi che la frazione di individui infetti aumenta in tempo t

𝑖 = 𝑖9 ∗ 𝑒<=>?@

1 − 𝑖A + 𝑒<=>?@

Dall'equazione potremo dedurre che la frazione di individui infetti aumenta esponenzialmente, questo perchè nelle fasi inziali un infetto incontra solo soggetti suscettibili, in cui l'agente patogeno può facilmente diffondersi.

Figura 28: time evolution of the fraction of infected individuals

5.2 SIS (Susceptible - Infected - Susceptible) Epidemic Model

Figura 29: SIS model

Questo modello è tipico dell’epidemie che coinvolgono le malattie sessualmente trasmissibili e malattie ricorrenti. Questo modello si basa sull'asserzione che un individuo infetto possa comunque tornare suscettibile, cioè che in un intervallo di tempo possa ricevere ulteriori informazioni senza dimenticarsi di quelle inerenti all'infezione precedente. Quindi potremo dedurre come la classe suscettibile sia continuamente riassortita da individui malati che guariscono. Quindi la differenza sostanziale sarà la presenza di un death rate (𝛿), che farà diventare l'equazione vista nel modello SI come segue:

𝑑𝑖𝑑𝑡 = 𝛽 ∗< 𝑘 >∗ 𝑖 1 − 𝑖 − 𝛿𝑖

dove avremo che 𝜇𝑖 rappresenterà la velocità con la quale la popolazione recupera dalla malattia. Da qui potremo ricavare la frazione degli individui infetti per questo modello:

𝑖 = 1 −𝜇

𝛽 ∗< 𝑘 > ∗𝐶𝑒(<=>?DE)@

1 − 𝐶𝑒(<=>?DE)@

dove le condizioni iniziali saranno 𝑖9 = 𝐼 0 e 𝐶 = 𝑖9

(1 − 𝑖9 − 𝜇/𝛽 ∗< 𝑘 >) Possiamo quindi concludere che mentre nel modello SI alla fine tutti si infettavano, nel modello SIS l'epidemia ha due possibili esiti:

• Endemic State (𝜇 < 𝛽 < 𝑘 >): In qualsiasi momento solo una frazione limitata della popolazione è infetto. In questo stato stazionario o endemica il numero di individui contagiati uguale al numero di individui che recupera dalla malattia, quindi la frazione infetta della popolazione non cambia con il tempo.

• Disease Free State (𝜇 > 𝛽 < 𝑘 >): per un tasso di recupero sufficientemente elevato, l'esponente dell'equazione per ricavare la frazione degli individui infetti, sarà negativo. Pertanto i decresce esponenzialmente, indicando che una infezione iniziale terminerà esponenzialmente. Questo perchè il numero di individui curati supera il numero di individui infetti.

La nostra analisi tratterà di considerare l'evoluzione nel tempo di questa condizione, partendo dal presupposto che su 4897 nodi (utenti) saranno tutti infettati, seppur come già visto in precedenza i progressi di una infezione dipenderanno dalla struttura della rete e dal grado di contagiosità.

Quest'ultimo, sarà identificato attraverso due fattori2: Virus Strenght (reproductive number): dato dal rapporto fra 𝛽 (trasmission rate) e 𝛿 (death rate), sta ad indicare il numero medio di individui infetti contagiati da un solo individuo infetti in una popolazione completamente suscettibile.

𝜆 = 𝛽𝛿

Epidemic Threshold: è il numero critico (o densità) di individui suscettibili richiesto perchè si verifichi una epidemia. Valore dato dal rapporto fra Average Degree della rete e Average of Degree Squares della rete.

𝜆H =< 𝑘 >DI Quando 𝜆 risulta maggiore di 𝜆H, otterremo un Endemic State mentre in caso contrario si avrà un Disease Free State. Nello specifico, maggiore sarà il valore 𝛿 rispetto a 𝛽, e maggiore sarà il decremento nell'andamento della curva degli infetti rispetto al tempo (e viceversa).

Figura 30: time evolution of the fraction of infected individuals

Per verificare il funzionamento del modello e le sue principali misure, applicheremo questo a due diversi tipi di rete: Last Fm Network e Random Network. Tale confronto è stato pensato per garantire una differenziazione di valori e analizzare due situazioni tendenzialmente differenti. Prima di cominciare, ridefiniamo l’equazione dell’Epidemic Threshold per le reti Random:

𝜆H = 1

< 𝑘 > +1

2https://en.wikipedia.org/wiki/Compartmental_models_in_epidemiology

Procediamo con la simulazione dei quattro stadi epidemici3, indicando innanzitutto i parametri utilizzati:

SIS model statistics 𝛽 𝛿 𝜆 𝜆H SIS epidemic

0.047 0.0086 5.4651 0.05332 Endemic weak

0.000695 0.0086 0.08081 0.05332 Endemic strong

0.0000005 0.15 0.0000034 0.05332 Disease Free weak

0.000051 0.0086 0.00593 0.05332 Disease Free Strong

In questo grafico si evidenzia un quadro fortemente endemico per entrambe le reti. Potremo subito notare come nella rete Barabasi, l’epidemia satura quasi subito (t=4.8) coinvolgendo tutti i nodi presenti dopo la creazione. Nella rete Last Fm, la distribuzione evidenzia come ci sia un’infezione più lenta, seppur al tempo t=50 raggiunga quasi tutti i nodi presenti. Questo comportamento è spiegato, come già visto a livello teorico, dal fatto che 𝜆 > 𝜆H, ossia abbiamo un alto valore di transmission rate rispetto al tasso di mortalità del virus.

Figura 31: Endemic strong [SIS] Si rileva un comportamento epidemico abbastanza discostante fra le due reti, come accadeva anche nel caso Endemic Strong. La differenza starà nel fatto che in entrambe le reti, il tasso di crescita sarà molto più lento (a causa della diminuzione del transmission rate), questo porterà ad una diffusione della malattia molto più lentamente.

Figura 32: Endemic weak [SIS]

3http://goo.gl/uS3605

Ci troveremo di fronte ad un “decesso epidemico”, tipico dello stato epidemico Desease Free strong. Questo sarà a causa dell’alto valore di mortalità del virus rispetto al 𝛽

Figura 33: Disease Free strong [SIS] Gli andamenti come da immagine, sono identici. Questo perché il valore di 𝛿 è più basso rispetto al precedente caso epidemico strong. Avremo che l’epidemia recederà più lentamente, dato che le possibilità di contrarre il virus diminuiscono.

Figure 34: Disease Free weak [SIS]

5.3 SIR (Susceptible - Infected - Recovered) Epidemic Model

Figura 35: SIR model

Questo modello lo troveremo nei casi di malattie infettive di lunga durata. Ogni nodo della rete potrà transitare attraverso tre stati diversi durante l'epidemia:

• Suscettibili (S): ne fanno parte gli individui sani, ma a rischio contagio. • Infetti (I): ne fanno parte gli individui ammalti, e in grado di contagiare gli altri. • Rimossi (R): ne faranno parte quegli individui che sono stati rimossi poichè completamente

guariti (diventati immuni) o deceduti (epidemia o cause naturali). I modelli SI, SIS e SIR sono d'accordo nelle fasi iniziali di una epidemia, infatti quando il numero di individui infetti è basso, la malattia si diffonde liberamente e il numero di individui infetti aumenta in maniera esponenziale. I risultati finali saranno diversi, infatti nel modello SI ognuno si infetterà alla fine, nel modello SIS si potrà raggiungere uno stato endemico (una frazione di individui è sempre infetta) oppure l'epidemia si blocca, infine nel modello SIR ogni individuo recupererà alla fine. Quindi la differenza sostanziale sarà la presenza di un recover fixed rate (𝜇), che farà diventare l'equazione vista nel modello SI come segue:

𝑑𝑖𝑑𝑡 = −𝜇𝑖 𝑡 + 𝛽 < 𝑘 >∗ 𝑖 𝑡 ∗ [1 − 𝑟 𝑡 − 𝑖(𝑡)]

A livello pratico, rispetto al modello SIS, cambierà solo la formulazione dell'equazione dell'Epidemic Threshold, riscritta come segue:

𝜆H = 1

< 𝑘 > −1 Come per il modello SIR, effettueremo diverse prove analizzando nello specifico casi di epidemie Endemic (strong e weak) e Disease Free (strong e weak), in questo caso però evidenziando gli andamenti delle curve relative alle persone suscettibili, infette e rimossi della sola rete Last Fm.

SIR model statistics 𝛽 𝜇 𝜆 𝜆H SIR epidemic

0.21 0.03 7 0.05633 Endemic weak

0.00128 0.03 0.043 0.05633 Endemic strong

0.00045 1.69 0.000267 0.05633 Disease Free weak

0.00045 0.03 0.015 0.05633 Disease Free Strong

Avremo come atteso, un quadro fortemente endemico, soprattutto nelle curve I e R. Sono evidenti i due relativi intervalli dove avviene l’incremento: per la curva degli infetti sarà in t∈[0 , 6.9] visto che SàI, mentre nell’intervallo t∈[6.9 , 131.1] avremo un forte incremento della classe R dato che IàR. Possiamo quindi affermare che il transmission rate dà un grande apporto alla crescita rapida della classe R, ottenendo una quasi saturazione della rete.

Figura 36: Endemic strong [SIR] Notiamo una crescita più lenta rispetto al caso precedente, questo perché il transmission rate è più piccolo. Tutto ciò è quindi dato dalla conseguente minore differenza fra 𝛽 e 𝜇, che comporta la già citata crescita lenta dell’epidemia.

Figura 37: Endemic weak [SIR]

Si può comprendere di essere in un caso epidemico Desease Free strong a causa dell’alto tasso di mortalità del virus. Come si può notare dal grafo, addirittura pare che nessun individuo sia stato infettato dal virus.

Figura 38: Disease Free strong [SIR] Al contrario del caso precedentemente analizzato, fissando un valore più basso di recovery rate, si è ottenuto un basso numero di contagi ma con rapida evoluzione dell’epidemia.

Figura 39: Disease Free weak [SIR]

Link al repository GitHub:

https://github.com/pigna90/lastfm_network_analysis