- 1 -

Scuola Politecnica e delle Scienze di Base

Corso di Laurea in Ingegneria Informatica

relatore

Ch.mo prof. Vincenzo Moscato

correlatore

prof. Giancarlo Sperlì

candidato

Fabrizio Cannavale

matr. N46002224

elaborato di laurea

Social Network Analysis

Anno Accademico 2017-2018

- 2 -

Sommario Social Network Analysis.................................................................................... - 1 -

Introduzione ……………………………………………………………………………………- 4 -

Capitolo 1: Online Social Network .................................................................... - 6 -

Capitolo 2 : Social Network Analysis ............................................................... - 11 -

Capitolo 3: Influence Diffusion and Maximization .......................................... - 24 -

Capitolo 4 : Esempi di Influence Diffusion and Maximization ......................... - 36 -

Conclusioni………………. ................................................................................. - 43 -

- 3 -

Ringrazio mia madre e a mio padre, che sono il mio punto di riferimento e che mi hanno accompagnato e sostenuto durante tutto l’arco di questo percorso;

Ringrazio mio fratello, il mio migliore amico, che ha reso il mio percorso meno impervio e che mi ha aiutato nei momenti di difficoltà e che mi ha consigliato sempre nel modo giusto nelle scelte più complicate;

Ringrazio i miei nonni, chi ancora è qui e chi mi guarda dall’alto, per aver sempre creduto in me;

Ringrazio Gianluca, Kerim, Angelo, Alessio, Andrea, Aurelio, Vincenzo e Luca, che avete reso questi anni indimenticabili e gioiosi;

Ringrazio me stesso per la determinazione e l'impegno nel raggiungere questo traguardo e per averci provato ed esserci riuscito;

Grazie di tutto ciò che mi avete dato.

Non è la fine, è solo un nuovo inizio.

Ad maiora semper.

- 4 -

Introduzione

Al giorno d’oggi la crescente popolarità degli Online Social Network, sopra

tutti Facebook e Twitter, ha fatto sì che questi siano diventati un

importante piattaforma per la diffusione di notizie, idee, opinioni, ecc.

Il ruolo predominante di questi nella vita di tutti i giorni e di tutte le

persone nel mondo ha suscitato l’interesse nel comprendere tutti i legami

e le relazioni che si vengono a creare tra gli utenti che usufruiscono dei

Social Network: l’insieme di questi studi è detta Social Network Analysis,

che ha come obiettivo principale quello di proporre una moderna

metodologia di analisi delle relazioni sociali; proprio per il legame che ha

con quest’ultime, la SNA si è sviluppata a partire dai contributi di Jacob

Levi Moreno, il fondatore della sociometria, scienza che analizza le

relazioni interpersonali e quindi affine all’argomento trattato in questa

tesi.

La SNA (dall'inglese Social Network Analysis) trova ora applicazione in

diverse scienze sociali, come la sociologia, l'antropologia, la psicologia e

l'economia, così come nel management, ed è stata utilmente impiegata

nello studio di diversi fenomeni, come il commercio internazionale, la

diffusione dell'informazione, lo studio delle istituzioni e il funzionamento

delle organizzazioni.

Tutti gli studi esistenti riguardo la Social Network Analysis(SNA) si

concentrano spesso riguardo i lati positivi di questa innovazione, come ad

esempio il poter creare amicizie nuove, stabilire nuovi rapporti; non

- 5 -

vengono dunque spesso considerati i lati negativi, tra i quali diffondere

inimicizia, la possibilità di dichiarare frasi offensive e provocatorie che

hanno poi grande visibilità, senza dimenticare la problematica tutt’oggi in

auge del cyberbullismo.

Nella teoria delle reti sociali, la società è vista e studiata come rete di

relazioni, più o meno estese e strutturate. Il presupposto fondante è che

ogni individuo si relaziona con gli altri e questa sua interazione plasma e

modifica il comportamento di entrambi. Lo scopo principale della SNA è

appunto quello di individuare e studiare tali legami tra gli individui.

Gli strumenti a disposizione per l’analisi delle reti sociali analizzano ed

effettuano delle comparazioni tra i flussi informativi esistenti all’interno di

una rete, attraverso principalmente l’ampio uso di una branca della

matematica nota come teoria dei grafi e dei principi dell’algebra lineare e

della statistica.

Questo lavoro dapprima si propone di effettuare una presentazione sugli

Online Social Networks(OSN) per poi introdurre i concetti cardini della

Social Network Analysis, descrivendone il processo attraverso lo studio dei

dettagli riguardo la sequenza di attività; dopo questa prima presentazione,

si procede nel descrivere le principali applicazioni utilizzate per l’analisi

della relazione dei network.

Successivamente si illustra un esempio di “Influence Diffusion and

Maximization” tratto da uno studio effettuato da alcuni studenti della

“University of Tokyo” riguardo questi due fenomeni e i risultati del loro

esperimento.

- 6 -

Capitolo 1: Online Social Network

1.1 Cosa sono gli Online Social Network

Per Online Social Network (che abbrevieremo con la sigla OSN) si intende

quel settore di applicazioni e interfacce web, accessibili sia attraverso i

browser web sia tramite applicazioni mobili, che permettono a chi ne

usufruisce di connettersi con tutti gli altri utenti registrati e stabilire nuovi

legami. Più precisamente ogni OSN offre uno o più servizi, che possono

essere classificati a seconda del tipo di relazione che l’utente ha

intenzione di stabilire con altri contatti.

Possiamo senza dubbio affermare che la rapida diffusione dei Social

Network è dovuta all’incredibile progresso tecnologico, che ha offerto ad

una grande percentuale della popolazione mondiale la possibilità di

accedere a queste reti sociali e che ha reso questi il più importante mezzo

di comunicazione mediatica.

Grazie agli Online Social Network infatti qualsiasi persona è in grado di

connettersi con chiunque per i motivi più disparati in un tempo molto

rapido; questo poiché i Social Network permettono per esempio, tra i vari

servizi, di restare aggiornati e partecipare in diretta online ad eventi anche

a migliaia di km di distanza: questo senza dubbio è un utilizzo che ci può

far capire l’importanza mediatica degli OSN, dato che ogni utente può

condividere un evento o pubblicare una notizia in breve tempo, godendo

di un’altissima visibilità.

Un secondo utilizzo non meno importante è la capacità dei Social Network

di essere in grado di permettere a chi usufruisce di questi di stabilire veri e

- 7 -

propri legami sociali, dove con questa espressione intendiamo un insieme

di relazioni che spaziano dal poter costruire un rapporto di amicizia ad

addirittura sostenere un colloquio di lavoro: molte aziende infatti usano

Social Network (ad es. LinkedIn) che permettono all’utente di poter

caricare il proprio curriculum vitae e alle aziende di selezionare i profili per

un’opportunità di lavoro.

In conclusione si può tranquillamente affermare che i Social Network sono

diventati oramai parte della vita quotidiana di tutti proprio per l’efficienza

di questi nel saper soddisfare le richieste e i desideri di ogni utente.

1.2 Principali Social Network: caratteristiche e la loro diffusione

E’ possibile distinguere i Social Network a seconda delle funzionalità

offerte e della classe di utenti utilizzatrici: ad esempio abbiamo OSN come

Facebook, Instagram e Twitter utilizzati principalmente dagli utenti per

condividere proprie esperienze, media, stati d’animo e restare aggiornati

su eventi in tutto il mondo.

I tre Social Network sopra citati sono senza dubbio i più utilizzati,

soprattutto tra gli adolescenti, in quanto permettono con grande rapidità

e semplicità di stabilire legami e connessione fra i vari utenti e ,come

abbiamo già sottolineato nell’introduzione, la peculiarità di questi è la

velocità con cui è possibile trasmettere un messaggio: infatti molto spesso

accade che vengano utilizzate le chat fornite da queste piattaforme

- 8 -

semplicemente per comunicare in modo veloce ed avere una rapida

risposta.

Altri Social Network molto famosi sono quelli che facilitano la connessione

delle persone con il mondo lavorativo: esempio di gran rilievo è LinkedIn,

una rete sociale professionale che permette di pubblicare sul proprio

profilo il proprio curriculum vitae e diffonderlo su questa piattaforma,

facilitando di gran lunga la ricerca di un’offerta lavorativa.

Nonostante abbiamo discusso la diversità dei servizi offerti dai singoli

Social Network, questi hanno caratteristiche significative che li

accomunano.

Infatti tutti gli OSN sono servizi web che consentono a chiunque si voglia

registrare la possibilità di:

Creare un proprio profilo contente le informazioni personali all’interno

della rete e rendere lo stesso pubblico o privato a seconda delle necessità

dell’utente.

Avere a disposizione una lista di contatti con cui interagire attraverso i

servizi offerti.

Usufruire della possibilità di scorrere l’elenco di amici dei propri

contatti.

Inviare e ricevere messaggi di testo e/o allegati (es. file .mp3,

immagini, file .doc, ecc.)

Stabilire uno tra i vari tipi di interazione offerti dall’ OSN con qualsiasi

altro utente (es. richiesta di amicizia, richiesta di lavoro ecc.)

- 9 -

Pubblicare contenuti di vario tipo sulla piattaforma, a partire da un

semplice testo anche al condividere link di altri siti.

Accedere a forum o altre piattaforme web usando le stesse

credenziali.

Oltre a queste funzioni, i Social Network sono accomunati da un metodo

di registrazione pressoché simile: infatti un utente per registrarsi ha

bisogno di inserire nel “form” disposto dal singolo Social Network

sicuramente un indirizzo e-mail, utilizzato ad esempio per ricevere le

notifiche se qualche altro utente desidera mettersi in contatto oppure,

uno dei casi più importanti, quando si vogliono cambiare e/o resettare le

credenziali d’accesso.

Successivamente viene chiesto di immettere i propri dati personali, quali

nome, cognome, data di nascita, luogo di nascita, sesso, e, a seconda

dell’OSN, anche di pubblicare altre informazioni, ad esempio il proprio

curriculum vitae, lo stato lavorativo, la propria situazione sentimentale

ecc.

- 10 -

Il concetto fondamentale da non trascurare è sicuramente la grande

accessibilità che queste piattaforme hanno grazie alla crescita tecnologica

che stiamo vivendo in questi anni permettendo dunque a chiunque sia

dotato di un dispositivo in grado di connettersi ad Internet di accedere alle

stesse; in più grazie ai tanti servizi e funzionalità previste dai singoli Social

Network li pongono al centro della comunicazione mediatica e della vita

sociale di un altissima percentuale, se non della totalità, della popolazione

mondiale.

- 11 -

Capitolo 2: Social Network Analysis

2.1 Social Network Analysis

L’interesse accademico e scientifico nei Social Network è stato a lungo

studiato sin dagli anni ’30.

Innanzitutto è opportuno fare chiarezza su cosa si intende con il termine

Social Network Analysis: questa è l’insieme di tutti gli studi riguardo i

rapporti interpersonali che si vengono a creare nelle reti sociali.

Questa branca della sociologia fa ampio uso della teoria dei grafi: gli attori,

in questo caso, sono gli utenti dei Social Network o qualsiasi cosa viene

condivisa attraverso questi; gli attori vengono definiti nodi, mentre i

collegamenti tra gli stessi vengono definiti legami(ties).

La nascita della SNA (acronimo di Social Network Analysis) è dovuta agli

studi compiuti da Jacob Moreno e Helen Jennings negli anni 30: le tesi da

loro elaborate erano incentrate principalmente sull’importanza di

focalizzarsi sulle relazioni costruite dagli attori.

All’inizio era questo lo scopo principale di questa scienza, ma con lo

svilupparsi dei Social Network è diventato fondamentale studiare le

conseguenze della nascita di questi legami e quindi cosa essi comportano;

questi studi hanno trovato particolare affermazione sia in ambiti

accademici, sia in problematiche reali quali il riciclaggio di denaro e il

terrorismo.

- 12 -

Attualmente la SNA è assimilabile ad un settore della sociologia poiché si

concentra sull’influenza delle relazioni sociali in un contesto collettivo.

La SNA ha due tipi di approcci fondamentali: il primo basato a livello

individuale, il secondo “variable-based”.

Nel primo caso, gli studi affermano che gli attori prendono decisioni e

agiscono senza pensare al comportamento degli altri attori: si va ad

analizzare le ragioni per cui una persona ha determinati atteggiamenti, tra

cui esperienze passate che vanno a modificare le scelte future ignorando

le azioni delle altre persone.

Se invece si procede secondo il metodo “variable-based”, si assume che gli

attori si trovano in un contesto sociale connettendosi l’un l’altro,

considerando che le relazioni che si vengono a creare hanno grande

influenza sul comportamento degli altri.

Essendo dunque posta l’enfasi sullo studio delle strutture relazionali poste

dai Social Network, viene considerato molto più importante il secondo

approccio.

Discutiamo quindi i criteri alla base del metodo “variable-based”: oltre ai

concetti fondamentali già espressi, aggiungiamo altre nozioni tra le quali:

Gli attori e le loro azioni sono viste come “interdipendenti” più che

indipendenti, unità autonome.

A livello relazionale i legami (le connessioni) tra attori sono canali per

trasferire o “far fluire” risorse (sia materiali che non materiali) dall’uno

all’altro.

- 13 -

I modelli con cui vengono costruite le connessioni stabiliscono quali

opportunità offrire agli attori e quali vincoli imporre su un’azione

individuale.

Infine è d’obbligo specificare come i metodi di connessione si basino o su

una diade attori-connessioni (due attori e le relative connessioni) , o su

una triade attori-connessioni(tre attori e le relative connessioni), o su

sistemi più ampi(sottogruppi di individui, o intere reti). Dunque sono

necessari metodi “ad – hoc”:

Descrizione Formale: La SNA entra in un processo di sviluppo e

definizione di un determinato modello, effettuando vari test: in questo

primo contesto descrittivo l’analisi della rete sociale offre un vocabolario e

un insieme di definizione formali per esprimere proprietà e concetti

teoretici.

Modello di Valutazione e Testing (Statistico)

In alternativa, modelli di connessione potrebbero essere utilizzati per

testare teorie riguardo processi o strutture relazionali. Queste teorie

danno specifici esiti strutturali che poi possono essere valutati e

confrontati rispetto al modello sotto esame.

Ad esempio, se una teoria sostiene che la tendenza nel reciproco supporto

e scambio di beni tra famiglie in una comunità stia crescendo

frequentemente, una supposizione del genere può essere testata

adottando un metodo statistico e studiando quanto spesso questa

tendenza cresca empiricamente.

- 14 -

La principale caratteristica delle teorie e delle tesi sulle connessioni è che

queste richiedono concetti, definizioni e processi dove le singole unità

sociali sono collegate l’un l’altra da varie relazioni.

Dunque il metodo descrittivo e quello statistico richiedono concetti e

procedure analitiche che sono diverse dalle statistiche e dall’analisi

tradizionali dei dati.

2.2 Concetti fondamentali della SNA

Ci sono diversi concetti fondamentali della Social Network Analysis che

sono fondamentali se si vuole discutere delle reti sociali. Questi sono:

attore, legame relazionale, diade, triade, sottogruppo, gruppo, relazione,

rete sociale e il “clustering”.

In questa sezione verranno definiti alcuni di questi concetti chiave e

andremo a delineare livelli differenti di analisi nelle reti sociali.

Attore: Come abbiamo già detto, la SNA si occupa di capire le

connessioni tra entità a livello sociale e le implicazioni di queste

connessioni. Queste entità vengono chiamate attori: rappresentano un

singolo individuo, un’azienda oppure un collettivo di singoli.

Esempi di attori sono persone in un gruppo, o di un settore di un’azienda,

agenzie pubbliche in una città, o stati se considerassimo un modello

globale. L’uso del termine attore non implica che queste entità abbiano

necessariamente la volontà o l’abilità di interagire. In più, molte

applicazioni della SNA si concentrano su una classe di attori che sono dello

- 15 -

stesso tipo (ad es. colleghi in un gruppo di lavoro): raggruppamenti di

questo genere sono definiti “one-mode networks”. Nonostante ciò, alcuni

schemi ci consentono di differenziare gli attori in base a vari tipi o livelli.

Legame Relazionale. Gli attori sono connessi l’un l’altro attraverso

connessioni che definiamo a livello sociale. Il range di questi legami, come

abbiamo discusso nell’introduzione, è veramente ampio.

La caratteristica peculiare di un legame è quella di stabilire una

connessione tra una coppia di attori.

Alcuni degli esempi più comuni di legami nell’analisi delle reti sociali sono:

1. Rapporto tra una persona e un’altra (ad es. amicizia, di piacere, di

rispetto ecc.).

2. Trasferimento di risorse materiali (ad es. transazioni economiche,

prestare e/o richiedere cose).

3. Associazione o affiliazione (ad es. partecipare insieme ad un evento

sociale o appartenere ad uno stesso gruppo sociale)

4. Interazione (ad es. parlare insieme, inviare e ricevere messaggi).

5. Relazioni formali (ad es. rapporti con autorità).

Diade. In questo caso parliamo del caso più basilare, ovvero la

connessione tra due attori. Il legame è naturalmente una proprietà di una

coppia e quindi non viene ritenuto pertinente semplicemente ad un

singolo attore. Molti tipi di analisi delle reti sociali si concentrano sul

comprendere connessioni riguardo le coppie e tutti questi approcci

prendono la diade come unità da analizzare.

- 16 -

Una diade è costituita da una coppia di attori e il possibile o i possibili

legami tra loro. Le analisi riguardo le diadi si concentrano sulle proprietà di

relazioni di parità, come stabilire la reciprocità dei legami, o se più classi di

connessioni occorrono contemporaneamente.

Triade. Molti importanti metodi e modelli delle reti sociali si basano su

relazioni di più soggetti: quindi in questo specifico caso si va ad analizzare

un gruppo di attori e i possibili collegamenti fra loro. La differenza

principale rispetto la diade infatti è quella che due attori se collegati,

posso non essere collegati direttamente, ma attraverso un terzo

intermediario.

Questa è la peculiarità della triade ed il motivo principale per cui viene

studiata: è rilevante capire la differenza e saper distinguere se una triade è

transitiva o bilanciata.

Esempio di triade transitiva: se ad un attore a “piace” l’attore b, e

all’attore b “piace” l’attore c, direttamente all’attore a “piace” l’attore c.

Esempio di triade bilanciata: se agli attori a e b “si piacciono” allora a e b

dovrebbero avere un giudizio simile verso un terzo attore, mentre nel caso

in cui “non si piacciano”, allora dovrebbero avere giudizi contrastante

rispetto ad un terzo attore.

Sottogruppo. Le diadi sono un paio di attori e i relativi legami, le triadi

sono un insieme di tre attori e le relative connessioni. Dunque ne

consegue che possiamo definire un sottogruppo una qualsiasi sottoclasse

di attori, e tutti i collegamenti relativi. Definire e studiare i sottogruppi

utilizzando specifici criteri è stato di grande interesse nell’analisi delle reti

sociali.

- 17 -

Gruppo. La Social Network Analysis non si interessa solamente dei

legami creati nelle diadi, triadi o sottogruppi. Ampliando il discorso su

larga scala, l’efficienza dell’analisi delle reti sociali consiste nell’abilità di

riuscire a modellare le relazioni attraverso sistemi composti dagli attori

dove identifichiamo la collezione di legami tra i membri di un gruppo (che

può essere chiuso o aperto). In questo studio, un gruppo è l’insieme di

tutti gli attori dove i legami devono essere ancora classificati: con questa

definizione si intende che bisogna avere la possibilità di stabilire criteri

teoretici, empirici o concettuali che spieghino le relazioni tra gli attori nel

gruppo così da dividerli in sottoclassi. Quindi quando viene deciso di

raggruppare dati in un gruppo, è necessario anche definire una qualità che

accomuna questi. Andremo dunque a definire definitivamente un gruppo

come l’insieme di attori che vengono scelti secondo precisi criteri

concettuali, teoretici ed empirici. L’ipotesi che sia un gruppo finito è una

specifica analitica: anche se qualcuno potrebbe pensare a legami estesi ad

attori compresi in un gruppo infinito di attori, si avrebbero grandi difficoltà

ad analizzare dati in una così grande rete. Nonostante ciò è importante

sottolineare come modellare gruppi finiti sia uno dei problemi più difficili

da affrontare nell’analisi delle reti sociali, in quanto includiamo la

necessità di stabilire confini ben definiti tra le reti, la difficoltà nel

campionare esempi di connessione e quindi la conseguente definizione di

gruppo. Per questo motivo il campionamento delle reti e la specifica delle

differenze tra una rete e l’altra sono di importanza rilevante.

Relazione: La collezione dei legami di uno specifico tipo tra i membri di

un gruppo viene chiamata relazione. Ad esempio, si può prendere in

considerazione il livello di amicizia tra coppie di bambini di una classe,

- 18 -

oppure della diplomazia tra le nazioni: questi sono legami che definiscono

le relazioni. Per ogni gruppo di attori, potremmo definire diversi stati di

relazioni (tornando all’esempio della diplomazia tra varie nazioni,

possiamo ad esempio registrare la somma di denaro che commerciano in

un determinato periodo di tempo). È dunque importante notare come una

relazione si riferisca alla collezione di legami secondo un determinato

criterio riguardo specifici attori. È ovvio infatti che l’esistenza dei legami è

strettamente dipendente da quella degli attori.

Rete Sociale. Avendo già definito cos’è un attore, un gruppo e una

relazione ora si può dare una definizione più esplicita di rete sociale.

Questa infatti è definita come un insieme finito di classi o attori e la

relazione o le relazioni definite tra loro. La presenza dell’informazione

riguardo i legami è critica e definisce la peculiarità di una rete sociale.

Clustering. Il Clustering dei dati consiste nella ricerca di similarità tra

ciò che compone una grande collezione di dati.

- 19 -

2.3 Proprietà dei Social Network

È necessario ora, per meglio comprendere i concetti che saranno espressi

in seguito, introdurre delle unità di misura, riprese dalla teoria dei grafi,

che vengono utilizzate per studiare una rete classificata come Social

Network.

Unità di misura basiche

1. Node degree. Una prima misurazione per un attore individuale in una

rete è il grado del nodo corrispondente. Dalla teoria dei grafi il grado k-

iesimo è definito come segue:

dove N indica il numero di nodi nel network, aij l’elemento della matrice A

definita come: aij = 1 se i nodi i e j sono interconnessi, aij = 0 altrimenti.

2. Shortest path. Un problema critico in grafici su larga scala è la stima

del percorso più breve (dato un network il percorso tra due nodi di

connessione). Il percorso più breve in media per tutto il network viene

calcolato molto spesso nello studio dei Social Network per individuare

caratteristiche specifiche di questi network. Questo è calcolato come

segue:

- 20 -

dove N denota il numero dei nodi in un network, d(i,j) il percorso più

breve tra i nodi i e j, k segnato il grado medio dei nodi calcolato come nel

punto 1.

3. Clustering coefficient. Il coefficiente di Clustering Gi di un nodo i è

definito come la frazione dei margini tra i vicini del nodo i, e tutti i margini

che possibilmente esistono tra i vicini. Nel caso di network indiretti, il

massimo numero di margini è dato da:

dove ki indica il grado dell’i-esimo nodo.

Il coefficiente di Clustering del nodo i è calcolato come segue:

dove {ejk} indica il gruppo di margini che connettono i vicini del nodo i.

Possiamo anche calcolare il coefficiente di Clustering medio in un network:

con N che indica il numero dei nodi.

- 21 -

Proprietà più comuni dei Social Network

Le proprietà più comuni dei social network sono:

-elevata scalabilità,

- clusterabilità,

- “small-world” networks.

I Social Network sono strutturati secondo l’elevata scalabilità che consiste

nel costruire reti con pochi nodi con grado alto, e lunghe code di nodi a

grado basso.

Inoltre verranno sempre elaborate reti tali che il valore medio di

clusterabilità (definito sopra) sia alto (molto vicino ad 1): questa quindi è

definibile come condizione necessaria affinché un Social Network sia

altamente clusteralizzabile.

È stato anche dimostrato che la maggior parte delle reti che si

costruiscono in natura, come piccole comunità di persone, sono i

cosiddetti “small-world” networks. La principale caratteristica di

quest’ultimi è che il percorso più breve in media è molto piccolo

relativamente al numero dei nodi N che formano la rete.

- 22 -

2.4 Applicazioni della Social Network Analysis

L’analisi delle rete sociali trova applicazione pratica in moltissimi campi: le

più importanti di queste sono quelle affiliate all’aggregazione e

l’estrazione dei dati, al modellare la crescita delle connessioni, al

campionamento delle reti, all’analisi degli attributi e del comportamento

dell’attore e delle interazioni basate su geo-localizzazione, alla

condivisione e filtraggio dei materiali scambiati tra gli attori.

Nel settore privato, le compagnie utilizzano l’analisi delle reti sociali per

supportare e monitorare attività come l’interazione con i clienti, l’analisi

del sistema informativo, per il marketing, per l’assunzione di nuovi

impiegati, ecc.

Applicazioni della SNA si trovano anche in attività di spionaggio, di

reclutamento e più in generale nell’ambito della criminologia e della lotta

al terrorismo.

Uno dei più importanti ambienti in cui la SNA è molto utilizzata è quella

nello studio dell’apprendimento collettivo tramite computer. In questo

ambito, la Social Network Analysis è usata per aiutare a comprendere

come chi deve apprendere collabora in termini quantitativi e qualitativi,

come anche la qualità e le strategie di comunicazione: in più, la SNA si

concentra su specifici aspetti della connessione della rete, o sul network

intero. Per far ciò si serve di rappresentazioni grafiche, rappresentazioni

scritte, e rappresentazioni di dati così da facilitare la disamina delle

connessioni in reti di questo genere.

- 23 -

Tra le tante applicazioni SNA troviamo anche quella che copre gli aspetti

dell’“Influence Diffusion” e dell’”Influence Maximization”, argomenti

principali di questa tesi e che andremo ora ad introdurre.

- 24 -

Capitolo 3: Influence Diffusion and Influence Maximization

L’ “Influence Analysis” è la branca della Social Network Analysis che più

interessa per questo studio, poiché gli obiettivi di questa sono due: il

primo è quello di modellare o individuare modelli dettagliati che

descrivono il processo di diffusione dell’influenza nella rete; il secondo è

quello di definire attraverso il modello di diffusione scelto, un insieme

ristretto di vertici (utenti) ritenuti influenti in uno specifico contesto.

Dunque è opportuno scindere quest’analisi in due singole parti: la prima

tratterà del fenomeno dell’”Influence Diffusion”, mentre successivamente

si tratterà dell’”Influence Maximization”.

3.1 Influence Diffusion

Abbiamo già presentato l’importanza dei Social Network nel permettere a

persone in tutto il mondo di scambiarsi le proprie idee, opinioni ecc., e dei

motivi della rapida diffusione di questi; non abbiamo però analizzato con

precisione gli effetti su larga scala che questa nuova forma di

comunicazione può causare: si è accennato alla diffusione “a cascata” di

idee o di altri fenomeni in qualche modo collegati al concetto del

passaparola senza però discuterne con accuratezza.

- 25 -

Nell’affrontare questo tema è necessario dare determinate definizioni e

spiegare alcuni concetti che derivano dalla teoria dei grafi, affinché si

possano comprendere i meccanismi di influenza interni ad una rete.

Il modello a grafo dei social network determina un’alterazione nel

processo di diffusione dell’influenza in particolare le proprietà

sopracitate di elevata scalabilità e di "small-world", insieme alla

presenza di nodi "notevoli" nella rete, contribuiscono all’aumento

della velocità di diffusione dell’influenza sociale fra gli utenti. Se infatti

un nodo altamente connesso, viene influenzato, esso diffonderà la

propria influenza alla maggior parte dei nodi vicini.

Dunque sia G = (V, E, p) un grafo orientato con V che indica un insieme di

vertici di dimensione n, E l’insieme di archi di dimensione m e p : E → [0, 1]

la funzione che associa ad ogni arco un peso che rappresenta la

probabilità di propagazione dell’influenza su quell’arco: si consideri inoltre

un insieme S0 ⊂ V di vertici iniziali (che chiameremo seed set o early

adopters) che considereremo attivi, mentre tutti gli altri li classificheremo

come inattivi.

Dopo questa suddivisione, è necessario creare dei modelli di diffusioni di

informazioni, opinioni, ecc. in modo da simulare il comportamento di una

particolare struttura delle reti sociali, tra le quali il seed set di partenza e

come evolve nel tempo l’attività di diffusione.

- 26 -

Negli anni sono stati strutturati vari modelli, che sono classificabili in due

grandi categorie:

•Modelli esplicativi: hanno come obiettivo quello di chiarire la

propagazione dell’informazione nella rete, osservando le sequenze di

attivazione dei nodi.

•Modelli predittivi: strutturati con lo scopo di fornire previsioni

sull’evoluzione del processo di diffusione su una particolare rete.

Nonostante ciò, due sono i modelli di base che vengono seguiti per

studiare la diffusione dell’influenza sul grafo di un Social Network: il Linear

Threshold Model (LTM) e l’Independent Cascade Model.

Per ambedue i modelli, il processo viene eseguito per passi di tempo

discreti fino a quando non ci sono più vertici da attivare: inoltre, entrambi

i modelli sono progressivi, nel senso che una volta che un nodo diventa

attivo (o è già stato attivato), resta attivo e non può più disattivarsi.

Ora andremo a discutere brevemente riguardo questi due modelli:

Linear Threshold Model : Secondo questo modello un vertice i viene

influenzato da ogni vertice adiacente j in base ad una probabilità di

influenza p( j, i) tale che:

j ∈ N(i) p( j, i) ≤ 1

dove N(i) indica l’insieme dei vertici adiacenti al vertice i considerando

solo gli archi entranti nel vertice i.

Il processo di “influence diffusion” si svolge secondo questa sequenza:

ogni nodo i seleziona una soglia θi secondo una distribuzione casuale

uniforme nell’intervallo [0, 1] che rappresenta la frazione di vertici

- 27 -

adiacenti che devono diventare attivi al fine di attivare i ; dopo aver

definito l’insieme delle soglie θi casuali e l’insieme dei vertici iniziali, il

processo di diffusione prevede che tutti i vertici che risultano attivi

all’istante t − 1 continuino ad esserlo all’istante t ed inoltre tutti quei

vertici i per i quali si verifica che :

j ∈ N attivi(i) p( j, i) ≥ θi

vengono attivati, dove N attivi(i) = N(i)∩St−1 è l’insieme dei vertici attivi

adiacenti ed incidenti con un arco in i.

In definitiva, il calcolo delle soglie θi è determinate per il nostro scopo

finale in quanto indicano la propensione dei singoli vertici ad essere

influenzati da i vertici ad essi adiacenti, già influenzati a loro volta da altri

vertici. La selezione casuale uniforme di queste soglie è necessaria quando

non si ha conoscenza dei loro valori effettivi.

Independent Cascade Model : A differenza del modello appena

studiato, questo schema presenta un funzionamento molto più semplice:

infatti all’inizio del processo di diffusione è previsto, ai nodi in quel

momento attivi e quindi appartenenti all’insieme St con t = 0, 1, . . ., che ci

sia una sola occasione di attivare i propri nodi vicini che risultano inattivi. Il

successo nell’attivare quest’ultimi dipende dalla probabilità di attivazione

p(i, j) posta sul generico arco (i, j) : inoltre, la probabilità che il generico

nodo i possa attivare un altro generico nodo j è indipendente da ciò che è

successo prima dell’attivazione di i e di conseguenza l’ordine con cui i nodi

sono stati attivati non influisce sui risultati del processo di diffusione.

- 28 -

Nell’eventualità in cui ci siano più vertici attivi aventi un arco verso un

vertice inattivo, i loro tentativi di diffusione verso quel nodo vengono

messi in coda in ordine sparso. Il processo termina quando nessun altro

vertice viene attivato.

È stata già discussa l’importanza di questa caratteristica dei Social

Network, sia per l’impatto che ha su una comunicazione mediatica da

parte di un singolo, ma soprattutto nel campo pubblicitario e di “viral-

marketing” per le aziende che sfruttano l’alta visibilità per far

conoscere a nuove persone i propri prodotti o servizi.

Dopo questa prima panoramica riguardo l’influence diffusion, ora

viene presentata in linea generale la tematica dell’influence

maximization.

3.2 Influence Maximization

La seconda fase della SNA abbiamo detto essere quella della ricerca di

un metodo per massimizzare l’influenza, e far dunque far sì che ciò che

si vuole condividere, qualunque cosa sia, goda della massima visibilità

possibile.

Andremo quindi ad introdurre delle unità di misura, sempre facendo

riferimento alla teoria dei grafi, dette misure di centralità: essendo ora

il nostro obiettivo principale quello di identificare i più importanti attori in

una rete, inizieremo a distinguere anche i nodi “normali” da quelli

“notevoli”, o nodi “hub” , ovvero quei nodi di rete (attori) che sono

- 29 -

grandemente coinvolti in legami con altri nodi che formano un social

network. Oltre a ciò, l’importanza dei nodi è nel numero di questi nodi

“notevoli” , che sono connessi al nodo sotto esame. I metri di centralità

sono stati definiti in modo da mostrare le differenze fra l’importanza dei

vari attori. Per calcolare queste misure dirette e indirette, bisogna

considerare le connessioni tra i nodi. Ora presenteremo le misure più note

e utilizzate di questo tipo, a cui aggiungeremo il Node Degree, già spiegato

nel capitolo 2 .

1. Betweennesses Centrality. La Betweennesses Centrality è una misura

molto importante se si considerano i flussi in un network. Il valore di

larghezza della Betweennesses ci indica che l’attore sotto esame è

connesso con molti altri attori (direttamente e indirettamente). La

Betweennesses Centrality per l’i-esimo nodo è calcolata in questo modo:

dove gjik è il numero di percorsi più brevi che collegano i nodi j e k

passando attraverso il nodo i, gjk il numero di percorsi che non includono

nel loro tragitto il nodo i.

Di solito, Cbi è un valore compreso nell’intervallo [0,1] moltiplicato per la

quantità 2÷(N-1)(N-2), con N uguale al numero di nodi.

2. Closeness Centrality. Un modo per vedere la centralità di un nodo è

quello di vedere la sua distanza o vicinanza rispetto agli altri nodi. Il

problema è quanto vicino si trova un nodo rispetto a tutti gli altri nodi del

- 30 -

network. Questa misura è molto importante e comunemente utilizzata

nella teoria dei grafi.

In generale, la vicinanza Cci del nodo i è definita come l’inverso della

somma delle distanze tra il nodo i e tutti gli altri nodi del network:

dove d(i,j) indica il percorso più breve tra i nodi i e j. La misura che indica

invece la vicinanza può essere vista come il tempo richiesto per diffondere

un’informazione da un nodo a tutti gli altri nodi raggiungibili nel network.

3. Eigenvector Centrality. La Eigenvector Centrality è una misura che

determina l’influenza di un nodo in un social network. Il valore di questa

misurazione dipende dal numero di nodi “notevoli” che sono collegati al

nodo i. La Eigenvector Centrality corrisponde alla matrice coincidente A

del network.

È stata scritta una formula per calcolare questa misura, secondo il quale la

centralità del nodo i è proporzionale alla somma delle centralità di tutti i

nodi che sono connessi all’i-esimo nodo, che dice dunque che:

dove Cej è la “Eigenvector Centrality” del j-esimo nodo, N è il numero di

nodi nella rete, λ è il valore costante, aij un elemento della matrice

coincidente A.

- 31 -

3.3 Algoritmi per la SNA

Per studiare quindi questi due fenomeni sono stati introdotti e sviluppati

degli efficienti algoritmi: ora andremo a delineare le caratteristiche di due

dei principali algoritmi più diffusi nella SNA.

Il primo è il metodo Monte Carlo, ovvero un algoritmo simulation-based di

tipo greedy : attraverso questo algoritmo, la soluzione ottimale per il

problema di influence maximization può essere approssimatà, per

entrambi i modelli di diffusione trattati, di un fattore pari a (1 − 1/e − z)

dove e è la base del logaritmo naturale e z è un valore positivo reale. Ciò

consente di avere sempre una garanzia di performance uguale o superiore

al 63%.

Questo algoritmo segue una strategia di tipo hill-climbing. Spesso si ricorre

a metodi di questo tipo per risolvere molti problemi riguardo

l’ottimizzazione e calcoli su larga scala, in particolare problemi di flusso su

rete. L’algoritmo parte con una soluzione che inizialmente è classificata

come migliore, e procede iterativamente finché non è più possibile trovare

migliorie all’ultima soluzione ottenuta.

La generalizzazione dell’algoritmo di hill-climbing per l’analisi

dell’influenza risulta migliore delle strategie basate sugli indici di centralità

visti nel paragrafo precedente.

- 32 -

La garanzia di approssimazione è fornita dalle proprietà della funzione di

diffusione dell’influenza σ (S). È dimostrato, infatti, che essa è sub-

modulare e monotona, ovvero:

σ(S ∪ {v}) − σ(S ) ≥ σ(T ∪ {v}) − σ(T )

σ(S ∪ {v}) ≥ σ(S )

per tutti i vertici v ed ogni coppia di insiemi S ⊆ T.

Ogni nodo V ha associato un peso W non negativo che indica quanto è

importante che tale nodo venga attivato al termine dell’algoritmo: inoltre

il peso viene usato dal processo di diffusione e confrontato con le

probabilità presenti sugli archi per l’eventuale attivazione dei vertici.

Dunque, dato un grafo orientato G = (V, E, p), un modello di diffusione su

G ed la dimensione del seed set k, l’algoritmo procede come segue:

1. Inizializza un seed set S vuoto;

2. Finché la dimensione del seed set è minore di k calcola la diffusione

dell’influenza partendo da un vertice v ∈ V \ S ;

3. Se il numero di vertici attivati da V è maggiore di quello trovato in

precedenza, aggiungi v al seed set, ovvero S = S ∪ v.

4. Si ricomincia dal punto n°2 e si procede iterativamente finché non si

ha una soluzione migliore.

Dunque il metodo d’evoluzione dell’influenza sceglie in maniera del tutto

casuale le diverse probabilità di diffusione lungo gli archi, per migliorare la

stima dei k vertici più influenti: esso può essere rieseguito più volte a

partire dallo stesso generico vertice v ∈ V / S e, seguendo questo

- 33 -

procedimento, il confronto viene fatto con la media del numero di nodi

attivati σ¯ (v).

L’algoritmo Monte Carlo che prevede dunque una soluzione greedy offre

risultati migliori rispetto ad altri procedimenti ma d’altro canto , viene

considerato inefficiente a causa dell’alto numero di processi di diffusione

che bisogna eseguire sul grafo.

Il secondo metodo proposto consta di un algoritmo che cerca di colmare

l’inefficienza del procedimento visto prima: stiamo parlando del Reverse

Influence Sampling (RIS).

Questo è un algoritmo “sketch-based” che si basa sul modello di diffusione

Independent Cascade e su due principi fondamentali:

• “Reverse Reachable Set”: (abbreviato in seguito RR set) è l’insieme dei

nodi in g che possono raggiungere v tramite un certo percorso, dove g è

un nuovo grafo ottenuto dalla rimozione di tutti gli archi e in G aventi

probabilità 1 − p(e).

• “Random Reverse Reachable Set ” : è un Reverse Reachable Set

generato a partire da un grafo g campionato in modo casuale da G, per un

nodo selezionato da g secondo una distribuzione casuale uniforme.

Partendo da un nodo u appartenente ad un RR set di v ed avviando un

processo di diffusione considerando S = {u}, può accadere che u sia in

grado di attivare v.

Se un nodo u è contenuto in una grande quantità di RR set scelti

casualmente da G allora significa che ha maggior probabilità di attivare un

- 34 -

numero elevato di nodi. Questo può essere visto come un indice di

influenza.

Allo stesso modo, se un seed set di k nodi S è contenuto in una grande

quantità di RR set presi casualmente da G allora S è una buona

approssimazione della soluzione del problema di influence maximization

su G.

L’algoritmo opera, dunque, in due fasi:

1. Generazione di un certo numero di RR set a partire dal grafo G.

2. Selezione dei k nodi che "coprono" il maggior numero di RR set

generati.

Il RIS riscontra due grandi difficoltà: mentre la prima dipende

strettamente dalla scelta del numero di RR set da generare, la seconda è

legata all’eventuale correlazione che può esistere fra i vari RR set.

Nel primo caso, viene suggerito di creare continuamente RR set finché il

numero di nodi ed archi non raggiunge una soglia predefinita: in questa

situazione, viene provata la linearità rispetto la soglia dell’esecuzione

dell’algoritmo, una volta posta tale soglia a Θ(k(m+n) log n/z^3).

Nonostante ciò, questo metodo non risolve interamente il problema.

Per risolvere tali difficoltà è stato proposto l’algoritmo “Two-phase

Influence Maximization” (TIM), una piccola variante del RIS: infatti questa

si diversifica dalla sua versione originale poichè calcola a priori una stima

di θ, ovvero del numero di RR set da generare, il cui valore garantisce

anche la loro indipendenza.

- 35 -

Le due fasi dell’algoritmo sono:

1. Calcolo di un limite inferiore rispetto la massima diffusione

raggiungibile sugli insiemi di k nodi ed utilizzo di tale limite per il calcolo di

θ.

2. Generazione di θ RR set a partire dal grafo G e selezione dei k nodi che

"coprono" il maggior numero di RR set generati.

La generazione dei singoli RR set avviene mediante un algoritmo di ricerca

in ampiezza casuale (random breadth first search) che consiste nei

seguenti passi:

1. Dato un nodo v ∈ G di partenza, viene generato un valore casuale per

ogni arco e entrante in v.

2. In base alla probabilità p(e) viene selezionato il nodo u sorgente

dell’arco e viene inserito in una coda.

3. Viene prelevato un nodo vj dalla coda e viene rieseguito il primo punto

finché non si svuota la coda.

- 36 -

Capitolo 4: Esempi di Influence Diffusion and Maximization

4.1 Introduzione

Ora verrà analizzato un esempio di “Influence Diffusion “ e di “Influence

Maximization “ prendendo come riferimento uno studio effettuato da

alcuni ricercatori dell’università di Tokyo: questi hanno proposto alla base

del loro studio un esempio di struttura dati composto da un indice “real-

time” e completamente dinamico programmato con lo scopo di analizzare

la diffusione e la massimizzazione dell’influenza in reti in evoluzione.

Per raggiungere questo fine, è stata introdotta una tecnica “reachability-

tree-based” e un metodo “skipping”, che riducono in modo significativo il

tempo di calcolo richiesto per l’eliminazione e l’addizione di vertici, e

“generatori di numeri casuali basati su un contatore”, che migliorano

l’efficienza a livello spaziale.

Il risultato dell’applicazione di questo metodo ottenuto dopo esperimenti

eseguiti usando come campione vere reti dinamiche con decine di milioni

di vertici dimostra l’efficienza, la scalabilità e l’accuratezza del metodo

proposto: ad esempio, è infatti possibile calcolare una stima accurata della

diffusione dell’influenza di un “vertex set” in un millisecondo e selezionare

- 37 -

i vertici che hanno un alto tasso di influenza almeno dieci volte più

velocemente di altri algoritmi.

Concettualmente, l’idea principale che viene proposta è che mentre le

strutture dati intermedie che sono utilizzate negli altri algoritmi non

vengono più considerate dopo ogni calcolo, in questo caso vengono

mantenute e i risultati delle stesse riutilizzati dopo la loro costruzione.

Tuttavia, poiché la struttura dati originale non contiene sufficienti

informazioni per un efficiente e corretto aggiornamento dinamico, la sfida

principale è quella di ridisegnare attentamente la struttura dati: ciò

avviene esaminando l’informazione necessaria che deve essere conservata

e dimostrando la non-decrescenza dell’accuratezza della stima dopo un

numero arbitrario di aggiornamenti.

4.2 Schema e costruzione indice dinamico

Ora dunque viene presentato dapprima la struttura dell’indice e poi come

viene costruito così da soddisfare le due query proposte, quella della “

Influence Diffusion “ e della “Influence Maximization “ .

La base è quella di un classico grafo G =(V,E,p).

Supponiamo ε > 0 essere un preciso parametro. Il nostro indice consta di

un set di tuple I = {(zi ,xi , Hi)}i , dove zi ϵ V è il vertice target, xi : E ->[0,1] è

- 38 -

una funzione di attivazione, e Hi è un sottografo di G composto da apici

attivi rispetto ad x .

In questo caso, ogni vertice in V(Hi ) può raggiungere zi in Hi: ognuno di

questi (zi ,xi , Hi ) viene chiamato “sketch”.

Il numero di “sketches” in I viene determinato come segue: il peso di un

sottografo H, identificato come w(H), è definito come :

ed indica lo spazio richiesto per conservare H.

Successivamente, considereremo sempre la condizione secondo cui

avremo sia che :

,

sia che:

dove W :

.

Per un vertice v, indichiamo con Iv il set di indici i ϵ [|I|], con v ϵ V(Hi),

e per un set di vertici S, indichiamo con IS il set di indici i ϵ [|I|] con

l’intersezione dell’insieme S con V(Hi) diversa dall’insieme vuoto. Dunque ,

IS =UvϵS Iv .

Il nostro indice conserva Iv per ogni vertice v, cosìcchè si possa

velocemente riportare gli “sketch” che includono un particolare vertice.

Per ciò che concerne invece la costruzione dell’indice, si inizia da un grafo

statico. Dato un grafo G =(V,E,p), si inizia con un indice vuoto I = Ø, e si

sono ripetutamente creati nuovi “sketches” e aggiunti in I fino a quando il

- 39 -

peso totale dell’indice corrente è minore di W . Uno “sketch” viene

costruito secondo il seguente metodo: in primis, si considera un

determinato vertice zi ϵ V in modo omogeneo a caso e aggiunto in una

coda vuota; viene considerato anche un xi ϵ E →[0,1] sempre preso in

modo casuale.

Ora viene fatto un controllo sulla coda: se la coda è vuota, allora bisognerà

rimuovere un vertice v dalla coda. Se invece è la prima volta che v viene

“visitata”, allora per ogni bordo attivo uv, noi aggiungiamo u alla cosa.

Infine , viene settato V(Hi) ai vertici visitati e E(Hi) i bordi attivi visitati.

Dunque costruire uno “sketch” (zi ,xi , Hi ) richiede O(w(Hi)) tempo,

e di conseguenza la costruzione dell’intero indice richiede O(W) tempo.

4.3 Query di Influence Diffusion e di Influence Maximization

L’”Influence Diffusion” viene studiata attraverso una query che va ad

approssimare il numero di vertici che un vertice v può influenzare con una

quantità uguale a n · |Iv|/|I|; poiché in questo studio viene simulato il

processo di diffusione molte volte per poi stimarne una media , il valore

stimato è esattamente uguale all’influenza σ({v}). In maniera simile, per

un set di vertici S, il numero di vertici che S influenza può essere

approssimato da n · |IS|/|I|. Dato un semplice vertice v, si può calcolare la

sua influenza su altri vertici in un tempo costante attraverso la formula

sopra scritta, siccome IV è stato conservato nell’indice. Per un set di vertici

S di grandezza maggiore di uno normale, immagazzinando ogni V(Hi)

- 40 -

attraverso l’utilizzo di un segno come un cancelletto così da segnare v ϵ

V(Hi) in un tempo costante, la complessità temporale della “influence

diffusion” è limitata da una quantità uguale a O(|S|·|I|).

Tuttavia è possibile migliorare il tempo di esecuzione utilizzando IV , il

quale è stato salvato nell’indice.

Detto ciò, viene poi calcolato , come detto nell’introduzione a questo

studio, IS =UvϵS Iv ; questa tecnica riduce il tempo di esecuzione ad una

quantità pari a O(∑vϵS Iv), e attraverso il seguente algoritmo viene

dimostrato che |IV| è molto più piccolo di |I| :

.

Questo studio ha anche presentato i risultati dell’applicazione del loro

algoritmo per quanto riguarda la influence diffusion , confrontando i

risultati ottenuti con la costruzione dell’ indice dinamico sopra presentato

rispetto ai valori che si otterrebbero attraverso un analisi normale.

I valori ottenuti sono rappresentati in questa tabella, ed evidenziano

l’efficienza e la grande scalabilità di questa procedura:

- 41 -

Per quanto concerne invece la query di “Influence maximization” invece,

bisogna concentrarsi sul trovare un set di vertici S di dimensione k che

massimizza il numero di vertici influenzati da S, dove k è un parametro di

input. L’utilizzo di un “greedy-algorithm” è l’approccio standard per un

problema del genere : per un vertice v, definiamo il grado dI(v) di v in I

come il numero di i ϵ [|I|] con v ϵ V(Hi) e quindi, in altre parole,

inizialmente si ha dI(v) = |IV|.

Dunque, come prima cosa viene scelto il vertice avente il grado più alto in

I e viene denominato v1: dopo ciò, esaminando ogni sketch , questo verrà

rimosso se v1 ϵ V(Hi) . In seguito, viene scelto il vertice con il grado

massimo nell’indice finale, e viene contrassegnato come v2 per poi

ripetere la stessa operazione di prima: vengono di nuovo valutati tutti gli

sketch, e questo vertice verrà rimosso se v2 ϵ V(Hi).

Questo procedimento verrà ripetuto k volte, e alla fine come output

avremo un set di vertici {v1,v2,….. ,vk}.

- 42 -

Ecco l’algoritmo proposto dallo studio a cui si fa riferimento, e i relativi

risultati da loro ottenuti per questa query utilizzando come campioni

social Network come Flickr ed Enron:

- 43 -

Conclusioni

In questo elaborato è stata dunque sottolineata l’importanza dello studio

delle tecniche per la Social Network Analysis in quanto questo

rappresenti sia una sfida e una prerogativa nel campo delle innovazioni

tecnologiche, poiché lo studio soprattutto delle due query oggetto di

questa tesi possono avere risvolti importanti nei più disparati ambiti.

Ad esempio, basti pensare che l’apertura delle piattaforme dei Social

Network e la ricchezza dei contenuti, la possibilità per l’utente di

interagire con altri utilizzatori e tutte le caratteristiche peculiari di questi,

hanno dato inizio a sistemi on-line intelligenti e al concepimento di virali

tecniche di marketing: infatti, se un’azienda volesse promuovere un nuovo

prodotto, attraverso i Social Network può identificare una classe di utenti

, chiamati “influencer“ , in grado di influenzare il gusto di più utenti, e

fornire loro dei campioni di questi prodotti gratuiti .

Questa tecnica è adoperata da molte compagnie in modo che questi

utenti possano promuovere ad altri utilizzatori dei Social Network, a

partire dagli amici, le loro idee sul prodotto in questione, creando così una

catena atta a far aumentare la visibilità di quest’ultimo e incrementando

così il numero dei potenziali clienti del prodotto promosso.

Situazioni simili possono essere considerate quando si vogliono proporre

idee oppure opinioni: un caso può essere considerato quello in cui

candidati politici cercano di trovare in breve tempo sostenitori per i loro

fini politici oppure quello dove autorità governative o aziende cercano di

- 44 -

guadagnarsi un supporto pubblico con lo scopo di ottenere consensi

rispetto i propri fini.

Proprio per la grande varietà di applicazioni in cui si possono utilizzare i

risultati degli studi della Social Network Analysis , possiamo senza dubbio

affermare che i progressi fatti in questo studio crescono

contemporaneamente, se non addirittura migliorano, con il progresso

tecnologico e permettono di e facilitano la vita quotidiana di gran parte

della popolazione mondiale.

- 45 -

Bibliografia______________________________________

[1] WIKIPEDIA, https://it.wikipedia.org/wiki/Rete_sociale

[2] TECNICHE DI INFLUENCE ANALYSIS PER I SOCIAL NETWORK, tesi di laurea magistrale in Big Data Analytics and Business Intelligence di Luigi di Guida

[3] Teoria dei Grafi, https://it.wikipedia.org/wiki/Teoria_dei_grafi

[4] Esempio di Influence Diffusion and Maximization, http://www.vldb.org/pvldb/vol9/p1077-ohsaka.pdf

[5] SOCIAL NETWORK ANALYSIS, tesi di laurea triennale in Basi di Dati di Giuseppe Corbisiero.

[6] TECNICHE DI SOCIAL NETWORK ANALYSIS, tesi di laurea triennale in Basi di Dati di Laura Baruffini.