Negli articoli precedenti abbiamo introdotto la teoria dei giochi (https://orbyta.it/teoria-dei-giochi/) e la teoria dei grafi (https://orbyta.it/teoria-dei-grafi/) e abbiamo visto come quest’ultima possa essere usata per risolvere giochi dall’equilibrio controintuitivo.

In questo articolo approfondiremo le reti andando a studiare i giochi dinamici e situazioni più complesse che ci permetteranno di analizzare la propagazione delle strategie all’interno di un network.

Giochi dinamici

Consideriamo i giochi in cui l’interazione tra i giocatori è intrinsecamente dinamica, cioè in cui i giocatori sono in grado di osservare le azioni degli altri giocatori prima di scegliere la loro miglior risposta [6].

Questo genere di giochi rientra nella categoria dei cosiddetti giochi dinamici insieme a quelli detti sequenziali nei quali i partecipanti prendono decisioni osservando a turno l’azione dell’avversario e stabilendo di conseguenza l’azione ottimale da adottare.

Si noti che l’attenzione non è posta all’alternanza sequenziale dei turni, bensì al fatto che i giocatori effettuano la loro scelta dopo che altri giocatori hanno già mosso, come nel gioco della briscola dove l’alternanza dei turni è stabilita di volta in volta in funzione di chi si è aggiudicato la mano precedente.

Si intuisce che la caratteristica principale di questi giochi è il fatto che le azioni di un giocatore possano influenzare le azioni ottimali degli altri, e questo incrementa il numero delle loro possibili strategie che adesso non coincidono più con le possibili azioni, infatti, a queste vanno aggiunte le cosiddette strategie condizionali.

È importante che i giocatori successivi abbiano informazioni sulle scelte precedentemente effettuate dagli altri giocatori, altrimenti la differenza di tempo non avrebbe alcun effetto strategico.

Esempio dinamico delle aziende

Finora abbiamo lavorato con quella che è chiamata forma normale di rappresentazione di un gioco in cui si specifica un insieme di giocatori e per ognuno di essi un insieme di strategie con i relativi payoff. Per descrivere un gioco dinamico necessitiamo, per esempio, di esplicitare quando e come i vari giocatori possono muovere.

Utilizziamo a tale scopo la cosiddetta forma estesa (o ad albero) della rappresentazione del gioco.

Immaginiamo che ci siano due aziende, P1 e P2, ognuna delle quali sta cercando di decidere in quale, tra due regioni A e B disponibili, focalizzare la propria pubblicità. P1 può decidere prima e supponiamo che:

  • Se P2 scegliesse di seguire P1 nella stessa regione allora P1 otterrebbe i 2/3 del profitto ricavabile da tale regione, mentre P2 solo il rimanente terzo;
  • Se P2 scegliesse l’altra regione allora entrambe le aziende otterrebbero il massimo ricavabile dalle zone.

Si assuma però che A abbia un potenziale di guadagno di 12 mentre B di 6. Rappresentiamo tale gioco col seguente diagramma ad albero da leggere dall’alto verso il basso.

Il nodo superiore rappresenta la mossa iniziale di P1 che può essere o A o B, da cui i due rami. I nodi sul secondo livello rappresentano le scelte di P2 che sono a loro volta A e B. I nodi inferiori coincidono con le possibili conclusioni del gioco e sotto di essi vengono riportati i rispettivi payoff di P1 e P2.

Notiamo che, una volta che P1 ha fatto la prima mossa, il comportamento di P2 è facilmente prevedibile:

  • Se P1 avesse scelto A, a P2 converrebbe scegliere B (questo perchè P2 compara gli output 4 e 6);
  • Se P1 avesse scelto B, P2 avrebbe dovuto scegliere A.

Ora cerchiamo di prevedere la mossa iniziale di P1.

  • Se P1 scegliesse A allora ci si aspetterebbe che P2 scelga B e quindi un guadagno di 12;
  • Se P1 scegliesse B, P2 sceglierebbe A e otterrebbe un guadagno di 6.

Concludiamo perciò che P1 sceglierà A e P2 B.

Generalizziamo ora la metodologia di risoluzione appena usata. Tale risoluzione, utile allo studio dei giochi dinamici, consiste nei seguenti passaggi:

  • Costruito l’albero iniziamo a considerare i penultimi nodi partendo dall’alto (backward induction). In essi il giocatore che muove ha diretto controllo sul risultato delle vincite. Questo ci permette di prevedere ciò che l’ultimo giocatore farà in tutti i casi;
  • Ci si sposta al livello superiore e, ragionando nello stesso modo, cerchiamo di capire cosa farà il giocatore nella mossa precedente;
  • Itero il processo fino ad arrivare a stabilire il comportamento del primo giocatore.

Può sembrare strano, ma il precedente risultato implica che teoricamente il vincitore di un incontro di scacchi (o un eventuale esito di parità) sia noto a priori. Siccome un tale albero ha un numero di nodi al di là di ogni possibile rappresentazione e computazione, la procedura ricorsiva delineata non è fattibile e quindi il gioco degli scacchi continua a mantenere il suo interesse.

In alcuni casi, come in questo esempio, possiamo descrivere il gioco dinamico tramite una forma normale di rappresentazione. Purtroppo, il voler convertire una rappresentazione di tipo esteso in una di tipo normale a volte provoca la perdita di alcune informazioni e non permette, dunque, di preservare la struttura del gioco.

In generale, possiamo assumere che la forma normale sia più usata nel caso di giochi a mosse simultanee, mentre quella estesa sia spesso più opportuna nella descrizione di giochi sequenziali [15].

In riferimento all’esempio, per la conversione ragioniamo come segue.

Supponiamo che, prima che la partita inizi, ogni giocatore faccia un piano per capire quali mosse effettuare considerando ogni possibile evenienza. Tutte le possibili modalità di gioco sono (indicando con XY il fatto che P2 sceglierà X se P1 sceglie Y) (AA, AB), (AA, BB), (BA, AB) e (BA, BB).

A questo punto possiamo calcolare le vincite risultanti dalle varie combinazioni di strategie e otteniamo il seguente schema:

Notiamo che per P1 A è la strategia strettamente dominante, mentre P2 non ha una strategia del genere ma le sue migliori risposte sono (BA,AB) e (BA,BB). Poiché P1 sceglierà A avremo che, proprio come ci aspettavamo, P2 sceglierà B.

Diffusione di una strategia

Potremmo in prima approssimazione pensare che l’importanza di un nodo in una rete sia data meramente dal suo grado, cioè dal numero di archi a esso collegati.

L’esempio della seguente figura ci fa notare che ciò non è necessariamente vero, infatti se si vuole far passare un’informazione nella rete, abbiamo che il comportamento del nodo centrale è fondamentale per il raggiungimento o meno del nostro scopo anche se ha un grado basso rispetto a quello di altri nodi.

La centralità di un nodo può essere più proficuamente usata come misura dell’importanza di un nodo nella rete e tale concetto è formalizzato da quello di betweeness. La betweeness di un nodo i è il numero dei cammini minimi passanti da i. In particolare la betweeness centrality del nodo v è la somma, al variare della coppia di nodi s e t, dei rapporti tra il numero di cammini minimi tra s e t passanti per v e il numero di cammini minimi totale tra s e t.

A seguito di quando detto, supponendo di essere un’azienda che voglia diffondere il più possibile una nuova tecnologia A, per scegliere i “nodi chiave” (ovviamente limitati) a cui fornire gratuitamente il prodotto affinché si diffonda in tutto il territorio, dovremmo tenere in considerazione la betweeness centrality dei vari nodi a disposizione.

Il concetto di connessione (o densità) di una rete è esplicato da quello di coefficiente di clustering[11]. Il coefficiente di clustering del nodo i, Ci ∈ [0, 1] rappresenta la densità di connessioni nelle vicinanze del nodo stesso, in particolare Ci = 1 se tutti i nodi a esso collegato sono tra loro connessi a due a due e Ci = 0 se tutti i nodi a esso connessi sono tra loro isolati.

Si può calcolare un coefficiente medio di clustering per i nodi della rete per avere una visione più generale della stessa. Se C è piccolo ci aspettiamo un grafo con poche connessioni.

Vedremo che, per il diffondersi di una nuova tecnologia, in generale è auspicabile che la rete non sia fortemente connessa (a differenza di quanto avveniva per il sorgere di una rivolta negli articoli precedenti).

Presentiamo alcuni esempi.

Esempio di reazione a catena [9]

Supponiamo di avere un grafo in cui ogni nodo possa scegliere tra due possibili comportamenti e che se due nodi sono tra loro collegati essi sono incentivati ad adottare la stessa strategia, in particolare se entrambi

scegliessero A otterrebbero un guadagno individuale di a, se entrambi scegliessero B di b, ma se scegliessero strategie distinte di 0. Se ci fossero più nodi vicini, per esempio d, e una percentuale p di loro usasse A, mentre la restante (1-p) usasse B, avremmo che A risulta una strategia efficace da usare se dpa > d(1 − p)b ossia se la somma dei payoff individuali (a) ottenuti dai nodi (d*p) che scelgono A, è maggiore della somma dei payoff individuali (b) ottenuti dal gruppo di nodi d*(1-p) che sceglie B. In sintesi, la strategia A è vincente se p> b/(a+b) , cioè la percentuale di nodi che scelgono A deve superare la percentuale del payoff b rispetto al guadagno totale possibile (a+b). Chiameremo p valore soglia.

Quindi più la connessione di un grafo aumenta (mantenendo fisso il numero di nodi) più è difficile che una nuova strategia, che segue queste regole di profitto, si diffonda partendo da pochi iniziatori.

Si pensi al caso in cui, nel grafo in questione, una parte di nodi scelga A e la restante B. Seguendo il ragionamento precedente alcuni nodi potrebbero cambiare comportamento e si innescherebbe di  conseguenza un processo di mutazione della strategia dei nodi della rete che terminerebbe al raggiungimento di una condizione di stabilità.

Si prendano per esempio a=3 e b=2 e si consideri il seguente grafo

dove all’istante iniziale tutti i nodi scelgono B, tranne v e w che scelgono A. Denotando con p il

valore soglia b/(a+b) notiamo che q = 0.4, quindi se almeno il 40 per cento dei vicini di un nodo avesse una data strategia anch’esso la adotterebbe.

Notiamo che r ha come vicini v, w, s. Di questi ne abbiamo 2 su 3 che scelgono A (cioè il 66 per cento), quindi r passerà alla strategia A e a quel punto farà la stessa cosa anche s (avendo 2 vicini su 3 che scelgono A) e di conseguenza w e v la manterranno. Si arriverà rapidamente alla propagazione totale del comportamento A. Otteniamo dunque una “reazione a catena”.

 

Esempio di non-propagazione

Si consideri la situazione precedente ma in riferimento al grafo sottostante, in cui i nodi evidenziati hanno adottato la strategia A.

E’ facile verificare, con l’iterazione del ragionamento precedente, che non vi sarà una cascata ma solo i nodi 4, 5, 6, 7, 8, 9 e 10 avranno, una volta stabilizzata la situazione, scelto A.

Per ampliare la diffusione di A quel che si può fare è

  • Diminuire il valore di q, per esempio aumentando a;
  • Focalizzarsi su alcuni nodi chiave a cui far adottare la strategia A, ma come sceglierli?

Un cluster di densità P è un insieme di nodi tali che ognuno di loro ha almeno una frazione P dei suoi vicini in tale insieme. Una cascata si conclude quando entra in un cluster sufficientemente denso.

Si consideri un insieme iniziale X di individui che adottano la strategia A con una soglia q, definita come prima, che se superata porta i nodi rimanenti (raggruppati nell’insieme Y) ad adottare anch’essi tale strategia. Se e solo se Y contiene un cluster di densità maggiore a 1-q, l’insieme X non riuscirà a realizzare un effetto a cascata completo e quindi a diffondere la strategia A.

Esempio di massimizzazione della soglia

Data una rete possiamo chiederci quale sarà la soglia q più elevata che a essa si potrà applicare ottenendo comunque un effetto a cascata. Questa quantità è chiamata capacità di diffusione, per esempio la capacità di diffusione della seguente rete, in cui i nodi che hanno adottato la nuova strategia A sono indicati in nero, è 1/2 (se raggiunta, infatti, farà sì che A si diffonda come un’onda sulle code).

In particolare si può dimostrare che nessuna rete può avere capacità maggiore a 1/2. Supponiamo ora di avere la seguente matrice di payoff

ove ogni nodo può scegliere se adottare la tecnologia A, la B o entrambe. Nel caso in cui lui e un suo vicino scelgano entrambi la strategia AB il payoff per entrambi sarà del massimo tra a e b meno un costo aggiuntivo c.

Prendiamo per esempio c=1, a=2 e b=3. Partendo dalla situazione START sottoindicata abbiamo i seguenti sviluppi:

e quindi la strategia A si diffonderà sempre di più all’aumentare delle iterazioni. È intuitivo aspettarsi che se a è molto maggiore di b la tecnologia A si diffonderà rapidamente, ma come influisce c? La sua influenza, in relazione a quella di a è sintetizzata nelle immagini sottostanti.

I giochi ripetuti

Oltre ai giochi sequenziali menzioniamo brevemente che all’interno dei giochi dinamici esistono anche i giochi ripetuti che si ripetono più volte con gli stessi giocatori e le stesse azioni/strategie tra cui scegliere. Possiamo per esempio riprendere il dilemma del prigioniero descritto nel precedente articolo sulla teoria dei giochi (https://orbyta.it/teoria-dei-giochi/). In uno scenario “one-shot” il dilemma si risolve con un equilibrio di Nash non pareto-ottimale, infatti i due prigionieri si tradiscono a vicenda, subendo entrambi la condanna. Se invece il gioco venisse ripetuto, vengono prese in considerazione la reputazione dei giocatori, basata sulle decisioni da loro prese in passato, e la punizione/reazione dell’avversario nel turno successivo. L’esito finale in questo caso dipende dal numero di turni nel gioco. Se il numero di turni è predefinito, si può dimostrare che il gioco si conclude esattamente come nel scenario “one-shot”, in un equilibrio non-pareto efficiente, perché gli giocatori sono spinti comunque a tradire. Se invece il numero di turni è sconosciuto, i giocatori sono incentivati a cooperare temendo la reazione dell’avversario nel turno successivo arrivando così ad una conclusione di equilibrio pareto-ottimale.

In questo articolo abbiamo studiato i giochi dinamici e come si risolvono tramite la metodologia di backward induction. Abbiamo visto inoltre i concetti di centralità (betweeness centrality) e del coefficiente medio di clustering per i nodi all’interno di una rete. In particolare abbiamo visto tramite alcuni esempi che per la diffusione di una strategia è importante che la rete non sia fortemente connessa. Infine abbiamo introdotto i giochi ripetuti e come si può arrivare ad una risoluzione pareto-ottimale al loro interno.

 

Bibliografia e Sitografia

[1] R. Dawkins, Il gene egoista, I edizione collana Oscar saggi, Arnoldo Mondadori Editore, 1995.

[2] D. Easley e J. Kleinberg, Networks, Crowds, and Markets: Reasoning about a Highly Con- nected World, Cambridge University Press, 2010.

[3] R. Gibbons, Teoria dei giochi, Bologna, Il Mulino, 2005.

[4] E. Martìn Novo  e A. Mendez Alonso, Aplicaciones  de la teoría  de grafos a algunos juegos   de estrategia, numero 64 di Suma, Universidad Politécnica de Madrid, 2004.

[5] S. Rizzello e A. Spada, Economia cognitiva e interdisciplinarità, Giappichelli Editore, 2011.

[6] G. Romp,Game Theory: Introduction and Applications, Mishawaka, Oxford University Press, 1997

[7] T. C. Schelling, The Strategy of Conflict, Cambridge, Massachusetts: Harvard, University Press, 1960.

[8] P. Serafini, Teoria dei Grafi e dei Giochi, a.a. 2014-15 (revisione: 28 novembre 2014).

[9] I. S. Stievano e M. Biey, Cascading behavior in networks, DET, Politecnico di Torino, 2015.

[10] I. S. Stievano e M. Biey, Interactions within a network, DET, Politecnico di Torino, 2015.

[11] I. S. Stievano, M. Biey e F. Corinto, Retie sistemicomplessi… , DET, Politecnico di Torino, 2015.

[12] A. Ziggioto e A. Piana, Modello di Lotka-Volterra, reperibile all’indirizzo http://www.itismajo.it/matematica/Lezioni/Vecchi%20Documenti%20a.s.%202011-12/Modello

%20di%20Lotka-Volterra.pdf, consultato il 15/05/2015.

[13] http://it.wikipedia.org/wiki/Equilibrio_di_Nash consultato il 12/05/2015.

[14] http://www.oilproject.org/lezione/teoria-dei-giochi-equilibrio-di-nash-e-altri-concetti-introduttivi-2471.html consultato il 13/05/2015.

[15] http://web.econ.unito.it/vannoni/docs/thgiochi.pdf consultato il 14/05/2015.

[16] https://www.youtube.com/watch?v=jILgxeNBK_8 consultato il 19/01/2021.

[17] http://www.andreaminini.it/teoriadeigiochi/giochi-ripetuti consultato il 06/07/2021.

[18] https://www.ed.ac.uk/files/atoms/files/lecture_8_game_theory.pdf consultato il 06/07/2021.

Articolo a cura di Carla Melia (Head Data Scientist), Augusto Cadini (IT Business Analyst) e Angeni Uminga (Software Developer), Orbyta Tech, 10.07.2021

#jointherevolution

  1. Introduci la tua esperienza professionale fino all’ingresso in ORBYTA.

Già da bambina avevo capito che la creatività era la mia strada, quando a 7 anni alcuni problemi di salute mi hanno costretta a trascorrere molte ore di degenza in ospedale.

Per non annoiarmi ho cominciato a disegnare le pubblicità prese dalle riviste di moda che venivano lasciate sul mio comodino. Così la mia mente ha cominciato a strutturarsi sempre di più nel comprendere la pubblicità e da lì è nato il mio stile. Una volta dimessa ho abbandonato i disegni, che poi successivamente ho scoperto essere esposti nelle sale d’aspetto. 

Ho poi studiato grafica e mi sono diplomata in comunicazione pubblicitaria. Dopo le primissime esperienze lavorative, ho deciso di specializzarmi e intraprendere la mia carriera nel mondo della comunicazione: il mio grande trampolino di lancio è stato lavorare per l’azienda cosmetica Kelemata, dove mi sono affermata da subito come creativo di spicco lavorando con due direttrici francesi. Non capivo nulla di francese, ma ho capito, invece, che la creatività è una lingua universale. 

Poi il passo nelle grandi agenzie dove ho avuto l’onore di lavorare per importanti clienti internazionali, Johnson & Johnson, L’Oreal, Conserve Italia, Amadori, Condorelli, Banca Zurich, sono alcuni dei grandi marchi per cui ho lavorato in 10 anni di carriera.

In tutte queste esperienze ho avuto la fortuna di apprendere da grandi Art Director, facendo una dura gavetta dal punto di vista tecnico e gestionale.

All’arrivo dei miei bellissimi figli decido di cambiare: mi metto in proprio e fondo la mia realtà. Ad oggi questa decisione mi ha portata ad essere Direttore Creativo di CREO, agenzia del Gruppo ORBYTA.

2. Di cosa ti occupi e che valore porti all’azienda?

In ORBYTA il mio compito è quello di portare un’eccellenza, fatta di anni di esperienza, competenza e di imbattibile senso estetico ed emotivo. 

Nella parte più pratica gestisco i clienti nella comunicazione, dal brand al web design, dal packaging al social media management. La mia è una figura di riferimento, che deve capire le necessità del cliente e aiutarlo a guardare oltre, il tutto coordinando le varie competenze e risorse che sono di supporto nello sviluppo dei progetti. 

3. Perché ti piace lavorare in ORBYTA?

Mi piace lavorare in ORBYTA perché ci accomuna l’entusiasmo, il fare parte di un gruppo forte e dinamico, inoltre è un’azienda che si pone obiettivi vincenti e uno spazio dove poter “fare”. 

#jointherevolution

Introduzione

Un sistema esperto (o basato sulla conoscenza) è un software in grado di riprodurre in modo artificiale le prestazioni di una o più persone “esperte”  in un determinato campo di attività e trova la sua applicazione nella branca dell’intelligenza artificiale.

Una delle particolarità di un sistema esperto è quella di essere in grado di mettere in atto autonomamente delle procedure di inferenza, un processo induttivo o deduttivo che permette di giungere a una conclusione a seguito dell’analisi di una serie di fatti o circostanze adeguate alla risoluzione di problemi particolarmente complessi.

Un tipico sistema esperto ha due funzioni principali: quella di trarre delle conclusioni e quindi compiere o suggerire delle scelte (COSA) e quella di spiegare in che modo, con quale ragionamento è pervenuto a quelle conclusioni (CONTROLLO).

Un sistema esperto è composto da una base di conoscenza, una memoria di lavoro, un motore inferenziale e un’interfaccia utente

Nella base di conoscenza sono contenute le regole deduttive e i dettami procedurali di cui il sistema si serve nel suo operato. Il motore inferenziale è necessario per indirizzare il programma a  interpretare, classificare e applicare la base di conoscenza e le relative regole per ogni singolo aspetto o scenario dello specifico campo disciplinare. La memoria di lavoro, o memoria a breve termine, contiene i dati e le conclusioni raggiunte dal sistema. Infine, l’interfaccia utente permette l’interazione fra il soggetto umano e il programma che deve dare risposta ai suoi problemi.

Queste informazioni sono piuttosto generiche ed estremamente flessibili. Il programma non è un insieme di istruzioni immutabili che rappresentano la soluzione del problema, ma un ambiente in cui rappresentare, utilizzare e modificare una base di conoscenza. 

Caratteristico dei sistemi esperti è imitare l’esperto umano non solo nelle prestazioni ma anche nel modo di eseguire inferenze. La maggior parte di essi fa uso del cosiddetto ”ragionamento di superficie” o fuzzy logic, basato sull’impiego di un gran numero di strategie o regole empiriche, dette euristiche, che legano direttamente i fatti noti con quelli da inferire, senza una vera comprensione del tipo di legame esistente.

Subentra lo stratagemma dell’euristica qualora le componenti che presiedono alle procedure di inferenza, non riescono ad ottenere il rigore connaturato ad un algoritmo, in quanto nelle situazioni altamente complicate sarebbe troppo dispendioso analizzare ogni possibilità.

È nella natura stessa delle euristiche il fatto che non si possa dimostrare che siano corrette in quanto ciò sacrificherebbe risultati altamente probabili, ma comunque fallibili, non dando sempre nella pratica il risultato migliore; tuttavia consentono agli esperti di prendere decisioni quando non sono disponibili criteri più ”forti”.

Come già detto in precedenza, per elaborare le proprie conclusioni, i sistemi esperti possono fare affidamento su una base di conoscenza, la conoscenza viene immagazzinata nella memoria a lungo termine del sistema ed è organizzata e rappresentata sotto forma di regole, ad esempio definite come strutture “if-then” (“se-allora”), che comprendono una premessa o condizione (if) e una conclusione o azione (then), e descrivono la risoluzione di un dato problema.

Un sistema esperto basato su alberi, invece, parte da un insieme di dati ed alcune deduzioni per poi creare un albero di classificazione attraverso il quale i nuovi dati verranno analizzati portando alla deduzione rappresentata dal nodo di arrivo.

Ora ci focalizzeremo sui sistemi esperti basati sulle regole. E’ quindi doverosa un’introduzione alla logica matematica. 

Sistemi esperti e logica matematica

La logica ha lo scopo di formalizzare i meccanismi di ragionamento. Faremo un breve accenno sulle proposizioni, cioè espressioni che rappresentano affermazioni che nell’ambito di questo articolo potranno essere solo o VERE o FALSE. Per quanto ciò possa sembrare scontato, esistono in verità settori in cui si può attribuire a ciascuna proposizione un grado di verità diverso da 0 e 1 e compreso tra di loro (ovvero che usano logica sfumata). 

Ad ogni proposizione elementare viene associata un variabile proposizionale. Per esempio:

  • P1: Se fa caldo ed è umido, allora pioverà. 
  • P2: Se è umido ed è estate, allora fa caldo. 
  • P3: Adesso è umido. 
  • P4: Adesso è estate. 

Se chiamo A = FA CALDO, B = È UMIDO, C = È ESTATE, D = PIOVERÀ. 

La rappresentazione in formule diventa

  • F1: A ∧B →D, 
  • F2: B ∧C →A
  • F3: B
  • F4: C

Si può voler dimostrare che da questi 4 fatti segue logicamente P5: Pioverà, ovvero F5: D. Di ciò si può occupare un sistema esperto.

Come vediamo una formula è composta da formule atomiche (o atomi) (ovvero A, B, …) e connettivi logici

I connettivi logici più comunemente usati sono: 

  • ¬(NOT: negazione)
  • ∨(OR: disgiunzione)
  • ∧(AND: congiunzione)
  • →(IMPLIES o IF…THEN…: implicazione)
  • ↔(IF AND ONLY IF: bi-implicazione)

Una formula è ben formata (FBF) se e solo se essa è ottenibile applicando le seguenti regole:

  • un atomo è una FBF
  • se F è una FBF, allora (¬F) è una FBF
  • se F e G sono FBF, allora (F∨G), (F∧G), (F→G), (F↔G) sono FBF

Semplificando  in questa trattazione una FBF è una formula a cui è possibile attribuire un valore di verità, vero o falso.

Le regole viste esprimono la SINTASSI (vincoli strutturali) delle formule del calcolo proposizionale. Stabilendo un ordinamento tra i connettivi è possibile eliminare alcune parentesi. L’ordine che verrà adottato è il seguente: 

  1. ¬ 
  2. ∧, ∨ 
  3. →, ↔

Così, La formula ((((A∨B)∧C)→D)↔(((¬D)→A)∨E) può essere riscritta (eliminando le parentesi esterne) come ((A∨B)∧C→D)↔(¬D→A)∨E.

La SEMANTICA della logica proposizionale richiede l’introduzione dei valori di verità. L’insieme dei valori di verità (che indicheremo con B) include VERO e FALSO, rappresentati da B= {T, F}. 

Un’interpretazione I consiste in un mapping tra l’insieme delle formule e B (specificando cioè, per ogni formula, se essa è vera o falsa). 

Come si può ricavare il valore di verità di una formula? 

Per esempio se ci chiediamo se (P ∧Q) ∨R →(P ↔R) ∧ Q possiamo porre

α= (P ∧Q) ∨R

β= (P ↔R) ∧Q 

e quindi chiederci se α →β consultando la seguente classica tavola di verità (intuitivamente, ogni riga di una tabella di verità corrisponde ad una diversa possibile situazione (interpretazione)).

Alcune formule sono vere in tutte le interpretazioni. Esse sono dette formule valide o tautologie. Altre formule sono false in tutte le interpretazioni. Esse sono dette formule inconsistenti o contraddizioni

Poiché ogni formula è finita e quindi contiene un numero finito di formule atomiche, è sempre possibile determinare se essa è valida, inconsistente o né l’una né l’altra. La logica proposizionale è quindi decidibile.

Alcune formule valide sono controintuitive (e sono chiamate paradossi). In esse compare il connettivo →.  

Un esempio è ¬P→(P →Q) che è sempre vera. 

Due formule F e G sono equivalenti (scritto F ⇔G) se e solo se esse hanno lo stesso valore di verità in tutte le interpretazioni. 

Il modus ponens (MP) è una semplice e valida regola d’inferenza, che afferma in parole: “Se p implica q è una proposizione vera, e anche la premessa p è vera, allora la conseguenza q è vera”, ovvero (p ∧(p →q)) →q.

Si ribadisce che l’implicazione non ha nulla a che vedere con la causalità. La logica proposizione infatti si occupa solo di “combinazioni” e non di significati di “causa-effetto”.

Non ci addentreremo nella logica dei predicati in quanto, seppur sia uno strumento  più potente e flessibile, è anche molto più complicato e non adatto alle finalità di questo articolo. 

Per poter trattare in modo meccanico, le fbf devono essere poste in forma a clausole. I passi da seguire sono

  1. Eliminazione delle implicazioni
  2. Riduzione del campo dei segni di negazione
  3. Standardizzazione delle variabili
  4. Eliminazione dei quantificatori esistenziali: ogni variabile esistenzialmente quantificata è rimpiazzata con una funzione di Skolem
  5. Conversione in forma prenessa
  6. Trasformazione della matrice in forma normale congiuntiva
  7. Eliminazione dei quantificatori universali
  8. Eliminazione dei segni di congiunzione

ESEMPIO

Si applicano in successione alcune operazioni, illustrate mediante il seguente esempio:
( ∀x){P(x) →{( ∀y){P(y) →P(f(x,y))} ∧ ¬ ( ∀y){Q(x,y) →P(y)}}}

1) Eliminazione delle implicazioni, ovvero A → B è sostituito da:

 ¬A ∨ B Pertanto: ( ∀x){P(x) →{( ∀y){P(y) →P(f(x,y))} ∧ ¬ ( ∀y){Q(x,y) →P(y)}}} 

diventa: 

( ∀x){ ¬P(x) ∨{( ∀y){ ¬P(y) ∨P(f(x,y))} ∧ ¬ ( ∀y){ ¬Q(x,y) ∨P(y)}}}

2) Riduzione del campo dei segni di negazione (la negazione applicata ad una sola lettera predicativa). 

In pratica: 

Intelligenza Artificiale – Problem Solving 2 101

 ¬(A ∧ B) è rimpiazzata da ¬A ∨ ¬ B 

¬(A ∨ B) ” ¬A ∧ ¬ B

¬¬ A ” A

 ¬ ( ∀x)A ” ( ∃x){ ¬A } 

¬ ( ∃x) A ” ( ∀x){ ¬A }

Pertanto: 

(∀x){¬P(x)∨{(∀y){¬P(y)∨P(f(x,y))}∧ ¬(∀y){¬Q(x,y)∨P(y)}}}

diventa: 

(∀x){¬P(x)∨{(∀y){¬P(y)∨P(f(x,y))}∧ (∃y){¬{¬Q(x,y)∨P(y)}}}} 

e poi: 

(∀x){¬P(x)∨{(∀y){¬P(y)∨P(f(x,y))}∧ (∃y){Q(x,y)∧¬P(y)}}} 

3) Standardizzazione delle variabili: si ribattezzano le variabili quantificate in modo che ogni quantificatore abbia una variabile apparente unica. 

In pratica: 

( ∀x){P(x) → ( ∃x)Q(x)} diventa: ( ∀x){P(x) → ( ∃y)Q(y)}

 Pertanto: 

(∀x){¬P(x)∨{(∀y){¬P(y)∨P(f(x,y))}∧ (∃y){Q(x,y)∧¬P(y)}}} 

diventa: 

(∀x){¬P(x)∨{(∀y){¬P(y)∨P(f(x,y))}∧ (∃w){Q(x,w)∧¬P(w)}}} 

4) Eliminazione dei quantificatori esistenziali: ogni variabile esistenzialmente quantificata è rimpiazzata con una funzione di Skolem. 

Per esempio supponiamo che la fbf 

( ∀ y ∃x)P(x,y) 

possa essere interpretata come: “per tutti gli y esiste un x tale che x è maggiore di y”. 

NB: x può dipendere da y! 

Allora si cerca una funzione g(y) (detta funzione di Skolem) che manda ogni valore di y nell’x che “esiste”. Quindi la fbf diventa 

( ∀y)P(g(y),y) 

Si osservi ancora.

• ∃z si elimina in: 

{( ∀w)Q(w)} → ( ∀x){( ∀y){( ∃z){P(x,y,z) → ( ∀u)R(x,y,u,z)}}} 

ottenendo: 

{( ∀w)Q(w)} → ( ∀x){( ∀y){P(x,y,g(x,y)) → ( ∀u)R(x,y,u,g(x,y))}}} 

Se il quantificatore esistenziale non si trova nel campo di un quantificatore universale, la funzione di Skolem ha zero argomenti. 

Esempio: 

( ∃x)P(x) è sostituito da P( a ) dove a è una costante che sappiamo “esistere”. 

L’esempio che stiamo seguendo diventa da così: 

( ∀x){ ¬P(x) ∨{( ∀y){ ¬P(y) ∨P(f(x,y))} ∧ ( ∃w){Q(x,w)∧¬P(w)}}}

 a così: 

( ∀x){ ¬P(x) ∨{( ∀y){ ¬P(y) ∨P(f(x,y))} ∧ {Q(x,g(x))∧¬P(g(x))}}} 

dove g(x) è una funzione di Skolem. 

5) Conversione in forma prenessa: tutti i quantificatori universali (che sono tutti diversi) vengono spostati all’inizio della fbf (forma prenessa). 

L’esempio da: 

(∀x){¬P(x)∨{(∀y){¬P(y)∨P(f(x,y))}∧ {Q(x,g(x))∧¬P(g(x))}}} 

diventa: 

(∀x∀y){¬P(x)∨{{¬P(y)∨P(f(x,y))}∧ {Q(x,g(x))∧¬P(g(x))}}} 

dove: 

(∀x∀y) è detto prefisso e {¬P(x)∨{{¬P(y)∨P(f(x,y))}∧{Q(x,g(x))∧¬P(g(x))}}} è detta matrice Intelligenza 

6) Trasformazione della matrice in forma normale congiuntiva: la matrice viene scritta come congiunzione di un numero finito di disgiunzioni di predicati e/o negazioni di predicati (forma normale congiuntiva). (In parole povere, AND di OR, ovvero prodotti di somme, ovvero, maxterm). 

Esempi di forma normale congiuntiva: 

{P(x) ∨Q(x,y)} ∧{P(w)∨¬R(y)} ∧Q(x,y) P(x) ∨ Q(x,y) P(x) ∧ Q(x,y) ¬R(y) 

In pratica si applica ripetutamente la relazione: 

A ∨ (B ∧ C) ≡ { A ∨ B } ∧ { A ∨ C} 

L’esempio 

(∀x∀y){¬P(x)∨{{¬P(y)∨P(f(x,y))}∧ {Q(x,g(x))∧¬P(g(x))}}} 

diventa: 

(∀x∀y){{¬P(x)∨ ¬P(y)∨P(f(x,y))}∧ {¬P(x)∨Q(x,g(x))}∧ {¬P(x)∨¬P(g(x))}} 

7) Eliminazione dei quantificatori universali: resta la sola matrice in cui, essendo le variabili legate, sono tutte universalmente quantificate. 

8) Eliminazione dei segni di congiunzione. I segni di congiunzione (cioè ∧; esempio: A ∧ B) sono eliminati dando luogo a due fbf (nell’esempio, A e B). Applicando ripetutamente questo rimpiazzo si ottiene una lista finita di fbf, ognuna delle quali è una disgiunzione ( ∨) di formule atomiche e/o di negazioni di formule atomiche.

Esempio trasformazione in clausola “Tutti i romani che conoscono Marco o odiano Cesare o pensano che tutti quelli che odiano qualcuno sono matti”

fbf corrispondente: ∀x [romano(x) ∧ conosce (x, Marco)] → [odia(x, Cesare) ∨ ( ∀y ( ∃z odia(y, z)) →credematto (x, y))] 

1. eliminazione segni implicazioni: 

∀x ¬[romano(x) ∧ conosce (x, Marco)] ∨ [odia(x, Cesare) ∨ ( ∀y ¬ ( ∃z odia(y, z)) ∨ credematto (x, y))] 

2. riduzione portata negazione: 

∀x [ ¬romano(x) ∨ ¬conosce (x, Marco)] ∨ [odia(x, Cesare) ∨ ( ∀y ∀z ¬odia(y, z) ∨ credematto (x, y))] 

3. Standardizzazione variabili: qui nessuna modifica: ogni quantificatore lega già una variabile differente 

4. Spostamento dei quantificatori: 

∀x ∀y ∀z [eccetera] 

5. Eliminazione quantificatori esistenziali: non ce ne sono

6. Eliminazione prefisso: (resta la matrice) 

[ ¬romano(x) ∨ ¬conosce (x, Marco)] ∨ [odia(x, Cesare) ∨ ¬odia(y, z) ∨ credematto (x, y))] 

7. Trasformazione in congiunzione di disgiunzioni (AND di OR): 

¬romano(x) ∨ ¬conosce (x, Marco) ∨ odia(x, Cesare) ∨ ¬odia(y, z) ∨ credematto (x, y)) (1 sola clausola)

Una clausola di Horn è una disgiunzione di letterali in cui al massimo uno dei letterali è positivo. Esempio: ¬L∨¬B e ¬L∨¬B∨C sono clausole di Horn, ¬L∨B∨C non lo è. Sono importanti perché si possono scrivere come implicazioni la cui premessa è una congiunzione di letterali positivi e la cui conclusione è un singolo letterale positivo. Ad esempio, ¬L∨¬B∨C è equivalente a (L∧B)→C.

Per risolvere i problemi di logica esistono molti modi, useremo il modus ponens come esempio.

La risoluzione è un processo iterativo che, ad ogni passo, confronta (risolve) due clausole genitori e permette di inferire una nuova clausola. Per la risoluzione si considerano due clausole che contengono la stessa formula atomica, una volta affermata e una volta negata. La risolvente è ottenuta combinando tutte le formule atomiche delle clausole genitori eccetto quelle che cancella. Se si produce la clausola vuota, si ha una contraddizione. Il tentativo sarà quello di trovare una contraddizione, se esiste. Se non esiste, la procedura può non avere mai termine.

Risoluzione nella logica proposizionale usando il MP: il procedimento è il seguente: 

Procedimento: 

  1. Trasformare tutte le proposizioni in F in forma a clausole. 
  2. Negare S e trasformare il risultato in forma a clausole. Aggiungerlo all’insieme di clausole ottenute al passo 1).
  1. Ripetere fino a quando viene trovata una contraddizione o non si può più andare avanti i passi seguenti:
    1. Selezionare due clausole. Chiamarle clausole genitori. 
    2. Risolverle insieme. La clausola risultante, chiamata la risolvente, sarà la disgiunzione di tutte le formule atomiche di entrambe le clausole genitori con la seguente eccezione: se vi sono coppie di formule atomiche L e ¬L, tali che una delle clausole genitori contenga L e l’altra contenga ¬L, allora eliminare sia L che ¬L dalla risolvente. 
    3. Se la risolvente è la clausola vuota, allora è stata trovata una contraddizione. In caso contrario, aggiungerla all’insieme di clausole a disposizione della procedura.

ESEMPIO

siano dati i seguenti assiomi: 

Assiomi: 

(p ∧ q) → r 

(s ∨ t) → q 

Convertiti in forma a clausole: 

p

¬p ∨ ¬q ∨ r

¬s ∨ q 

¬t ∨ q

 t 

Si voglia dimostrare r. 

Dopo aver trasformato gli assiomi in forma a clausola, si introduce nella lista ¬r (già in forma a clausola). 

Poi si selezionano le clausole a 2 a 2 e si risolvono (conviene scegliere clausole che contengono la stessa forma atomica una volta affermata e una volta negata).

Si ottiene, ad esempio: 

Nota: la proposizione 2 è vera se sono vere ¬p, ¬q, r 

Al primo passo si assume che ¬r sia vera, insieme alla preposizione 2. 

Ciò può accadere solo se è vera 

¬p oppure ¬q. 

È quello che afferma la risolvente! 

Conclusione: 

per provare r, si prova che ¬r crea contraddizione. Si inserisce quindi ¬r nella lista di forme a clausola e si cerca, mediante risoluzione, se esiste questa contraddizione (metodo della refutazione).

Ci siamo concentrati per semplicità su un esempio di meccanismo performato da un SE usando la logica classica ma i tipi di ragionamento sono tanti, per esempio, potremmo utilizzare:

  • La logica non monotona: permette di cancellare e aggiungere enunciati alla base dati. In questa logica la credenza in un enunciato si può basare sulla mancata credenza in qualche altro enunciato (ragionamento by default).
  • Il Ragionamento probabilistico: rende possibile rappresentare inferenze probabili ma incerte.
  • La Logica sfumata (fuzzy logic): permette di rappresentare proprietà di oggetti continue (non binarie) o sfumate.
  • Il Concetto di spazi di credenza: permette di rappresentare modelli di insiemi di credenze inserite l’uno nell’altro.

Concludiamo l’articolo dando qualche indicazione sul problema della rappresentazione della conoscenza, fondamentale in questo ambito. 

Rappresentazione delle conoscenza

La rappresentazione della conoscenza è una branca dell’intelligenza artificiale che studia il modo in cui avviene il ragionamento umano, e si preoccupa di definire dei simbolismi o dei linguaggi che permettano di formalizzare la conoscenza al fine di renderla comprensibile alle macchine, per potervi fare dei ragionamenti automatici (inferendo le informazioni presenti) ed estrarre così nuova conoscenza. 

Attraverso il linguaggio scelto si andranno ad effettuare una serie di asserzioni sul mondo, che andranno insieme a costituire una base di conoscenza (KB, Knowledge Base). È inoltre importante che il linguaggio scelto per fare le asserzioni sia anche in grado di operare sulla KB per estrarre nuova conoscenza e per aggiungerne di nuova.

I metodi di rappresentazione della conoscenza schematicamente si suddividono in impliciti ed espliciti. In generale occorre rappresentare: collezione di oggetti, collezione di attributi (proprietà degli oggetti) e insiemi di relazioni (tra gli oggetti). La scelta della rappresentazione influenza lo sforzo di ricerca, in quanto può permettere di riconoscere concetti semplificanti (simmetrie, analogie, ecc.) e formare macro operatori (può essere utile utilizzare variabili nella descrizione degli stati). 

Un problema connesso, detto problema del contorno o frame problem, è quello di rappresentare un mondo in cui ci sono cose che cambiano e cose che non cambiano. Per ovviare il problema si può, per esempio, tenere traccia solo dei cambiamenti (lo stato di partenza è descritto in modo completo) o modificare lo stato iniziale con operatori “invertibili” in modo che si possa tornare indietro “annullando” i passi effettuati.

Caratteristiche di un buon sistema di rappresentazione:

  • Adeguatezza rappresentativa: poter rappresentare tutti i tipi di conoscenza relativi a un dominio. 
  • Adeguatezza inferenziale: poter manipolare le strutture rappresentative in modo da inferire nuova conoscenza
  • Efficienza inferenziale: poter incorporare informazioni in più da usare come guida verso gli obiettivi nei meccanismi di inferenza (focalizzazione dell’attenzione/euristica)
  • Efficienza nell’acquisizione: capacità di acquisire facilmente nuova conoscenza.

Occorre che il sistema possieda e sappia manipolare una grande quantità di conoscenza del mondo (semantica e pragmatica) e conosca la sintassi e possieda il vocabolario del linguaggio. E’ desiderabile ma complicato tenere separati i due livelli (ma alcune interpretazioni sintattiche non sono possibili se non si conosce il contesto).

Classificazione delle tecniche:

  • metodi dichiarativi: la conoscenza viene rappresentata come collezione statica di fatti, affiancata da un piccolo insieme di procedure generali per la manipolazione (esempio: logica dei predicati). Vantaggi: 
  • Ogni fatto va immagazzinato solo una volta, indipendentemente dal numero di modi in cui può essere usato.
  • È facile aggiungere nuovi fatti al sistema, senza cambiare né gli altri fatti né le procedure.
  • metodi procedurali: la conoscenza viene rappresentata come procedure per il suo uso. Vantaggi:
  • È facile rappresentare la conoscenza su come fare le cose
  • È facile rappresentare la conoscenza che non si inserisce facilmente in molti schemi dichiarativi semplici, come ad esempio il ragionamento per default e quello probabilistico
  • È facile rappresentare la conoscenza euristica su come fare le cose in modo efficiente

La maggior parte dei sistemi funzionanti usa una combinazione dei due metodi. 

La descrizione delle strutture di conoscenza avviene mediante schemi, ovvero un’organizzazione attiva di relazioni passate, o di esperienze passate, che devono supporre siano operanti in ogni risposta organica adattiva. Senza entrare nel dettaglio elenchiamo di seguito alcuni tipi di schemi.

  • Frame (quadri), spesso usati per descrivere una collezione di attributi che un determinato oggetto, per esempio, una sedia, in genere possiede.
  • Script (copioni), usati per descrivere sequenze di eventi comuni, come ad esempio ciò che succede quando si va al ristorante.
  • Stereotipi, usati per descrivere insiemi di caratteristiche che spesso nelle persone sono presenti contemporaneamente.
  • Modelli a regole, usati per descrivere caratteristiche comuni condivise all’interno di un insieme di regole in un sistema di produzioni.

In questo articolo abbiamo visto alcuni concetti base dei sistemi esperti, estremamente potenti anche se poco conosciuti nell’ambito dell’IA. Abbiamo anche introdotto in maniera intuitiva concetti propri della logica matematica e del problema della rappresentazione della conoscenza. Per approfondire l’argomento consigliamo i seguenti testi:

  • Stuart J. Russell, Peter Norvig, “Intelligenza Artificiale. Un approccio Moderno”, Pearson Education Italia, Milano.
  • E. Rich, “Intelligenza artificiale”, McGraw Hill, Milano.
  • N.J. Nilsson, “Metodi per la risoluzione dei problemi nell’intelligenza artificiale”, Angeli, Milano.
  • Nils J. Nilsson, “Intelligenza Artificiale”, Apogeo,Milano.
  • I. Bratko, “Programmare in prolog per l’intelligenza artificiale”, Masson Addison Wesley, Milano.

FONTI:

  • Slide del corso GESTIONE DELLA CONOSCENZA E INTELLIGENZA ARTIFICIALE, Politecnico di Torino, Elio Piccolo, 2017.
  • https://it.wikipedia.org/wiki/Sistema_esperto, consultato il 20.05.2021
  • Roger Schank e Robert Abelson, Scripts, Plans, Goals, and Understanding: An Inquiry Into Human Knowledge Structures, Lawrence Erlbaum Associates, Inc., 1977.
  • https://www.treccani.it/enciclopedia/sistemi-esperti_%28Enciclopedia-della-Scienza-e-della-Tecnica%29/#:~:text=Insiemi%20di%20programmi%20software%20in,’ambito%20dell’intelligenza%20artificiale, consultato il 09.07.2021.

Articolo a cura di Carla Melia, Lucia Campomaggiore e Ludovico Dellavecchia, 01.08.2021

#jointherevolution

Introduci la tua esperienza professionale dall’università fino all’ingresso in ORBYTA.

In sei anni ne ho percorsi di kilometri. Inizialmente lungo tutta la Calabria, offrendo la mia consulenza da imprenditore per i miei clienti. Lavoravo in una banca, trattavo tutti i servizi finanziari. 

Decido poi e mi sposto, capovolgendo lo Stivale. La voglia di mettermi in gioco non mi manca. Entro così a far parte di un’assicurazione sanitaria storica italiana. 

La mia esperienza mi ha insegnato a mettere davanti le persone, i clienti, ai miei titoli. Ho imparato ad ascoltare e a relazionarmi con diverse tipologie di interlocutori. 

Di cosa ti occupi e che valore porti all’azienda?

Sono un anello in una catena. Mi piace portare entusiasmo e voglia di fare. Mi piace mettermi in gioco sfruttando le mie competenze tecniche-informatiche e funzionali dei processi assicurativi. 

Analizzo i processi informatici e ne modello le soluzioni presenti. Con il mio team costruiamo le soluzioni future. Facciamo in modo che gli ERP societari rispondano a pieno alle esigenze degli utilizzatori, nel rispetto delle caratteristiche tecniche del prodotto. 

Perché ti piace lavorare in ORBYTA?

Sarà che per anni ho lavorato in una società cui lo slogan è “Costruita intorno a te”, ma in ORBYTA sento davvero la vicinanza della struttura e la loro presenza.

È una società dinamica e proattiva ed è in continua evoluzione. Caratteristiche che rispecchiano il mio modo di intendere il lavoro per non perdersi le opportunità di business.

Scelta che rifarei, rifarei mille volte ancora! 

#jointherevolution

The chosen one: .NET 5

.NET 5, il successore di .NET Core 3.1 e .NET Framework 4.8, mira a fornire agli sviluppatori .NET una nuova esperienza di sviluppo multipiattaforma. Mette ordine alla frammentazione dell’universo .NET che si è verificata nel corso degli anni e apporta nuove straordinarie funzionalità. Di seguito i cinque punti su cui concentrarci per capire agevolmente quali sono i punti di forza dell’ultima release per gli sviluppatori di casa Microsoft.

1. Piattaforma Unificata

La prima cosa che c’è da sapere è che .NET 5 offre una nuova visione unificata del mondo .NET.

Se abbiamo già lavorato con .NET, dovremmo essere a conoscenza della sua frammentazione di piattaforme sin dalla sua prima versione nel 2002. .NET Framework è stato inizialmente progettato per Windows, ma la sua specifica di runtime, nota anche come Common Language Infrastructure (CLI), fu standardizzata come ECMA 335.

Questa standardizzazione consentì a chiunque di creare la propria implementazione del runtime .NET. Infatti non si attese molto per veder comparirne i primi all’orizzonte: abbiamo Mono per sistemi basati su Linux, Silverlight per applicazioni basate su browser, framework .NET Compact e Micro per dispositivi mobili e con risorse limitate e così via.

Per questi motivi, Microsoft decise di scrivere .NET Core da zero pensando esclusivamente alla compatibilità multipiattaforma. Queste diverse implementazioni hanno sollevato la necessità di capire “dove” potrebbe essere eseguito un pacchetto .NET.

Dovresti creare versioni diverse della tua libreria per distribuirla? La risposta a questa domanda fu .NET Standard, ovvero una specifica formale delle API comuni che dovresti aspettarti tra le implementazioni della CLI. In altre parole, se crei la tua libreria per uno specifico .NET Standard, avrai la garanzia che verrà eseguita su tutti i runtime che implementano tale specifica.

Si comprende dunque che, in questa situazione disordinata, la compatibilità di implementazione desiderata non era così facile da ottenere. Questo è il motivo per cui .NET 5 appare in scena.

La nuova piattaforma .NET è il successore unificato delle varie versioni .NET: .NET Framework, .NET Standard, .NET Core, Mono, ecc. È ufficialmente la prossima versione di .NET Core 3.1, ma sostanzialmente determina la fine di .NET Framework, .NET Standard e le altre varianti che hanno causato grossi grattacapi agli sviluppatori .NET.

.NET 5 fornisce un set comune di API che allinea le diverse implementazioni di runtime. Questo set di API è identificato dal Net5.0 Target Framework Moniker (TFM), che è il token impostato nel progetto .NET per specificare il framework di destinazione. Ciò consente l’esecuzione dell’applicazione su qualsiasi implementazione di runtime che supporta .NET 5. Tuttavia, è comunque possibile compilare applicazioni per una piattaforma specifica. Ad esempio, per creare un’applicazione che utilizza l’API di Windows, è necessario specificare il TFM net5.0-windows. In questo modo, la creazione di un’applicazione specifica per la piattaforma è una tua scelta, non una scelta che dipende dall’implementazione di runtime che stai utilizzando per sviluppare la tua applicazione.

Naturalmente, realizzare questa piattaforma unificata ha richiesto uno sforzo significativo e una riorganizzazione dell’architettura interna. Alcune funzionalità sono state rimosse dal set di API di base, come vedrai più avanti, ma la piattaforma ha ottenuto un miglioramento generale delle prestazioni.

Mentre il nuovo .NET 5 viene fornito con l’obiettivo di unificazione della piattaforma, il piano iniziale è cambiato a causa del COVID-19. In effetti, .NET 5 pone le basi dell’unificazione, ma sarà completato con .NET 6 a novembre 2021. Con tale rilascio, otterremo la versione stabile della nuova Universal UI ed anche il supporto per i TFM specifici per Android ( net6.0-android) e iOS (net6.0-ios).

2. Nuove funzionalità in C#

La seconda cosa da tenere a mente riguarda C#. .NET 5 include C# 9, la nuova versione del principale linguaggio di programmazione della piattaforma .NET. Ci sono diverse nuove funzionalità, e di seguito ne troveremo un piccolissimo assaggio, giusto per farci “venir fame”.

Dichiarazioni Top-Level

Tra le nuove funzionalità, una delle più notevoli è l’introduzione di dichiarazioni top-level (o di primo livello). Per sapere cosa sono, diamo un’occhiata al seguente programma:

Ebbene, il precedente blocco potrà essere tranquillamente sostituito dal semplice ed unico:

Le istruzioni top-level consentono di concentrarsi su ciò che conta davvero in piccoli programmi e utilità per console e utilizzare C# con un approccio più orientato agli script.

Tipi di record

Un’altra interessante novità sono i tipi di record. Con i record, possiamo dichiarare un tipo di riferimento immutabile, ovvero un tipo basato sulla classe che non può essere modificato dopo la sua creazione. Un esempio di tipo di riferimento immutabile incorporato è la classe System.String. Dopo aver creato un’istanza di System.String, non è più possibile modificarne il valore.

Considera la seguente dichiarazione del tipo di record:

Possiamo creare un istanza del record Person come faremmo per una classe, ma non ne possiamo alterare ad esempio la proprietà FirstName.

Potremo comunque confrontare due istanze del record Person come si trattassero di tipologie primitive:

Init setters

C# 9 aggiunge anche la funzione di init setters per definire proprietà che possono essere solo inizializzate. Consideriamo la seguente definizione di classe:

Questa classe definisce una persona con proprietà LastName e FirstName che possono essere inizializzate, ma non modificate. La proprietà Address può essere invece modificata in qualsiasi momento:

3. .NET MAUI, the Universal UI

Come terzo punto, dobbiamo sapere che .NET 5 offre un nuovo modo di creare interfacce utente multipiattaforma. Grazie al framework UI dell’app multipiattaforma .NET, noto anche come .NET MAUI, saremo in grado di creare interfacce utente per Android, iOS, macOS e Windows con un unico progetto.

In realtà, questa funzionalità è ancora in corso e verrà rilasciata con .NET 6, ma possiamo iniziare a dare un’occhiata a .NET MAUI per essere pronto quando verrà rilasciato ufficialmente fin dal .NET 5.

.NET MAUI può essere considerato un’evoluzione di Xamarin.Forms, il framework open source per la creazione di app iOS e Android con un’unica base di codice .NET. Ma questo nuovo framework propone un modello universale per la creazione di interfacce utente su piattaforme mobili e desktop.

.NET MAUI

Oltre al buon vecchio Model-View-ViewModel (MVVM) pattern, .NET MAUI supporta anche il recentissimo Model-View-Update (MVU).

4. Supporto Single-File Applications

Altra grande feature che otterremo in .NET 5 è il supporto alle single-file applications, ovvero applicazioni pubblicate e distribuite come un singolo file. Ciò significa che la nostra applicazione e tutte le sue dipendenze sono raggruppate in un unico file.

Ad esempio, supponiamo di eseguire il seguente comando all’interno della cartella del nostro progetto .NET 5:

Otterremo un singolo file contenente l’intera applicazione creata per Linux, tutte le dipendenze usate nel  progetto ed il runtime .NET (–self-contained true). Ciò significa che non è nemmeno necessario installare il runtime .NET sul computer/server di destinazione.

Naturalmente, si potranno specificare questi parametri nella configurazione del progetto:

Notate bene che questa funzionalità non usa lo stesso approccio delle applicazioni a file singolo che puoi compilare in .NET Core 3.1. In .NET Core 3.1. L’applicazione a file singolo è solo un modo per creare pacchetti binari: in fase di esecuzione vengono poi scompattati in una cartella temporanea, caricati ed eseguiti. In .NET 5, l’applicazione a file singolo ha una nuova struttura interna e viene eseguita direttamente senza penalizzazioni delle prestazioni.

A questo link è possibile trovare la documentazione di questa tipologia di rilascio.

5. Tecnologie non più supportate

Per ultimo punto, è obbligo parlare anche di chi esce dal ciclo delle tecnologie supportate, non solo dei nuovi arrivati.

Come detto sopra, la revisione dell’architettura e il tentativo di rendere .NET 5 un vero e proprio framework di programmazione multipiattaforma ha portato alla rimozione di alcune funzionalità supportate in .NET Framework. Diamo una rapida occhiata alle funzionalità rimosse e alle possibili alternative.

Web Forms

Per molto tempo, ASP.NET Web Forms è stata la principale tecnologia per creare interfacce utente web dinamiche. Tuttavia, non è un segreto che la sua durata fosse strettamente legata al destino di .NET Framework. .NET Core non supporta Web Form, quindi il fatto che non sia più supportato in .NET 5 non dovrebbe essere una grande novità.

Tuttavia, abbiamo alcune alternative per creare interfacce utente web. Se stiamo realizzando applicazioni web tradizionali, Razor Pages è una di queste alternative. Se vuoi creare applicazioni a pagina singola, puoi usare invece Blazor.

Windows Communication Foundation (WCF)

Anche WCF, il framework di comunicazione tradizionale per Windows, sarà deprecato. Questo può sembrare un po’ scioccante per gli sviluppatori che lo hanno utilizzato per creare le loro applicazioni orientate ai servizi. Tuttavia, è abbastanza comprensibile se ci rendiamo conto che l’obiettivo principale di .NET 5 è diventare un framework multipiattaforma.

L’alternativa a WCF consigliata da Microsoft è la migrazione a gRPC. Ma se abbiamo nostalgia di WCF o vuoi preparare una transizione graduale, puoi provare il progetto open source CoreWCF.

Windows Workflow Foundation

Infine, .NET 5 non includerà nemmeno Windows Workflow Foundation, la tecnologia del motore del flusso di lavoro disponibile in .NET Framework. Non esiste un sostituto ufficiale per questa tecnologia. Tuttavia, potremo usare un progetto di porting open source, CoreWF, per tentare di spostare i flussi di lavoro esistenti su .NET 5 o crearne di nuovi.

Primi Passi Insieme

Nella seconda parte di questo articolo sperimenteremo insieme la creazione di un nuovo progetto web tramite Visual Studio sfruttando il framework .NET 5 e mettendo subito alla prova il suo aspetto multipiattaforma, pubblicandolo su di una macchina Linux (Ubuntu).

Non temiate la lunghezza della scrollbar verticale del vostro browser, la guida è stata resa il più user-friendly possibile riportando intere porzioni di codice e schermate dei “punti salienti”, ecco spiegato il motivo della sua lunghezza.

Creiamo il nuovo progetto con Visual Studio

Creiamo il nuovo progetto cross platform “MyCrossPlatformApp” partendo dal template “ASP.NET Core Web App”. Se non si trova il suddetto template tra quelli disponibili, assicurarsi di aver selezionato la voce “All platforms” e soprattutto che sia installata sul vostro Visual Studio la relativa SDK.

NB! E’ essenziale selezionare come Target Framework -> .NET 5

Una volta completato lo scaffolding del nuovo progetto possiamo tranquillamente procedere con la sua pubblicazione.

Non sono necessarie ulteriori modifiche essendo il nostro obiettivo ultimo l’esecuzione del progetto su una macchina Linux. Possiamo comunque provare a far partire il progetto per assicurarci che non contenga errori (e che Visual Studio non stia tentando di nascosto di sabotarci…).

Il risultato sarà la classica pagina di benvenuto del template selezionato.

Eradicati i nostri dubbi riguardo la bontà della compilazione del progetto, possiamo finalmente pubblicarlo.

Il risultato della pubblicazione sarà una cartella contenente exe, dll e files di configurazione del nostro applicativo, compilati per il rilascio sulla nostra piattaforma desiderata.

Procediamo dunque cliccando col destro sulla nostra soluzione nell’explorer di Visual Studio e selezionado la voce Publish.

Questo avvierà il wizard di creazione di un nuovo Profilo di Pubblicazione.

Delle varie modalità di pubblicazione, sceglieremo la più grezza e legacy, ovvero la pubblicazione su cartella/folder. In questo modo, lasciando tutte le impostazioni di default proposte nella successiva schermata, avremo il nostro risultato nella sotto cartella di progetto bin\Release\net5.0\publish .

Una volta creato il nuovo profilo di pubblicazione possiamo procedere cliccando dapprima su Publish (1) ed in seguito esaminando il risultato cliccando sulla cartella di output (2).

Et voilà! Una volta terminata la pubblicazione su cartella possiamo chiudere con Visual Studio ed iniziare a dedicarci alla nostra macchina Linux. Essendo il progetto compilato con un framework multipiattaforma (.NET5), nella cartella bin\Release\net5.0\publish avremo tutto il necessario per far partire l’app su qualsiasi Sistema Operativo in cui è installabile la relativa runtime.

Di seguito procederemo con la pubblicazione sull’ultima versione server Debian e l’ultima versione long-term support di Ubuntu Server.

UBUNTU 20.04 LTS &  Apache

Prerequisiti

  1. Salvo particolarissime eccezioni o esigenze, sarebbe ideale cominciare a riscaldarci sul terminale con la solita sfilza di formalismi necessari a partire con tutti i repositori e pacchetti aggiornati:
    1. sudo apt-get update
    1. sudo apt-get upgrade
    1. sudo apt-get dist-upgrade
    1. sudo apt-get autoclean
    1. sudo apt-get autoremove

  2. Nonostante sia un appunto banale e per molti scontato, tengo a precisare che per trasferire il nostro progetto sul server Ubuntu in questa guida faremo uso del protocollo SFTP. Sarà dunque necessario installare sulla macchina in questione la versione server di SSH (se non già presente) con il comando:
    1. sudo apt-get install openssh-server

Step#1 – Installazione Runtimes

Per prima cosa dobbiamo assicurarci che siano installate le runtime di .NET5 e ASP.NET Core 5. Procediamo con il seguente comando per listarle tutte:

dotnet –list-runtimes

Se il risultato dovesse essere il seguente (“command not found”) allora dobbiamo fare un passetto indietro, installandone almeno una.

Installare le runtime .NET non è complicato.
come già visto per l’SSH, possiamo tranquillamente procedere con la loro installazione tramite il packet manager di Ubuntu apt:

  • Runtime .NET5
    sudo apt-get install dotnet-runtime-5.0
  • Runtime ASP.NET Core 5
    sudo apt-get install aspnetcore-runtime-5.0

Con gran probabilità, arrivati a questo punto vi scontrerete con la mancanza dei pacchetti dotnet-runtime-5.0 e aspnetcore-runtime-5.0 negli attuali repository della vostra macchina, come da screen di seguito (“Unable to locate package (…)”) .

Non disperate: oltre alla guida ufficiale Microsoft per l’aggiunta del repository (LINK) potrete nuovamente fare affidamento a quanto segue di questa guida. Infatti, per l’aggiunta dei repository ufficiali Microsoft sul nostro server Ubuntu basterà eseguire i seguenti comandi:

curl -sSL https://packages.microsoft.com/keys/microsoft.asc | sudo tee /etc/apt/trusted.gpg.d/microsoft.asc
sudo apt-add-repository https://packages.microsoft.com/ubuntu/20.04/prod
sudo apt-get update

A questo punto saremo in grado di ritentare con successo l’installazione delle runtime .NET come descritto poche righe addietro, assicurandoci infine che compaiano nella lista fornita dal comando:

dotnet –list-runtimes

Step#2 – Installazione & Config. Apache

Dobbiamo sapere che le applicazioni .Net vengono eseguite su server Kestrel. Il nostro web server Apache fungerà da server proxy e gestirà il traffico dall’esterno della macchina reindirizzandolo al server Kestrel. Possiamo dunque vedere il nostro web server Apache come un middle layer per l’applicazione .Net .

Di seguito vedremo come installare e configurare un’installazione pulita di Apache sul nostro server Ubuntu per servire la nostra applicazione.

Diamo quindi i seguenti comando per installare Apache ed abilitare in seconda battutati i moduli proxy,proxy_http, proxy_html e proxy_wstunnel.

sudo apt-get install apache2
sudo a2enmod proxy proxy_http proxy_html proxy_wstunnel
sudo a2enmod rewrite
systemctl restart apache2

Possiamo confermare la corretta installazione di Apache navigando con un browser all’indirizzo del nostro server. Se tutto è andato liscio, il risultato sarà la pagina di default di Apache con tanto di messaggio evidenziato IT WORKS come da screen:

Arrivati a questo punto,dovremo creare un file conf per configurare il nostro proxy su Apache.
Forniamo dunque il seguente comando per entrare nell’editor di testo nano :

sudo nano /etc/apache2/conf-enabled/netcore.conf

Copiamo ora la seguente configurazione nel file vuoto appena aperto per poi salvarlo con la combinazione (per chi non la conoscesse) CTRL+O -> INVIO -> CTRL+X .

NB! La porta 5000 è quella usata di default dal server Kestrel con cui si eseguono le applicazioni .Net

<VirtualHost *:80> 
   ServerName localhost 
   ProxyPreserveHost On 
   ProxyPass / http://127.0.0.1:5000/
   ProxyPassReverse / http://127.0.0.1:5000/ 
   RewriteEngine on 
   RewriteCond %{HTTP:UPGRADE} ^WebSocket$ [NC] 
   RewriteCond %{HTTP:CONNECTION} Upgrade$ [NC] 
   RewriteRule /(.*) ws://127.0.0.1:5000/$1 [P] 
   ErrorLog /var/log/apache2/netcore-error.log 
   CustomLog /var/log/apache2/netcore-access.log common 
</VirtualHost>

Ora con il seguente comando ci assicuriamo che non siano presenti errori nella configurazione appena create su Apache:

sudo apachectl configtest

A prescindere dai vari warning segnati, se riceviamo infine il messaggio Syntax OK possiamo procedere con il riavvio di Apache:

sudo service apache2 restart

Effettuando nuovamente la navigazione con un browser puntando all’indirizzo della nostra macchina, ci accorgeremo di non avere più la pagina di default di Apache esposta, bensì un messaggio di Service Unavailable . Risultato del tutto normale poiché Apache sta già funzionando da server proxy, mirando in realtà alla porta 5000 della macchina sulla quale non è ancora stata avviata la nostra applicazione .Net con Kestrel.

Step#3 – Spostamento Progetto & Creazione Servizio

E’ giunto ora il momento di riversare il nostro progetto compilato sul nostro server Linux.

Come anticipato nelle premesse di questa guida, uno degli strumenti più comodi per chi lavora su una macchina Windows è WinSCP, con il quale potremo trasferire files tramite SFTP.

Prima di spostare i files, sarebbe utile creare preventivamente la cartella di destinazione del progetto, che nel nostro caso si chiamerà MyCrossPlatformApp e sarà nella home della mia utenza cerini.

cd /home/cerini
mkdir MyCrossPlatformApp

Ecco che una volta connessi con WinSCP potremo spostare comodamente il progetto nella cartella appena creata anche con un semplice Drag&Drop.

Possiamo finalmente testare il corretto funzionamento della nostra soluzione cross platform e della bontà della configurazione del reverse proxy di Apache avviando l’applicazione e facendo di conseguenza partire il server Kestrel sulla porta 5000 col comando:

dotnet MyCrossPlatformApp.dll

Visitando nuovamente col browser la nostra macchina, il messaggio di “Service Unavailable” sarà soltanto un lontano ricordo.

Rimane soltanto un ultimo “problema”:
l’esecuzione dell’applicazione è contestualizzata all’istanza di terminale che ha lanciato il comando dot, dunque fin quando non ne termineremo l’esecuzione con la combinazione di comandi CTRL+C, l’istanza di questo terminale sarà occupata da questo unico job, impedendoci di usarla per qualsiasi altro task.

E’ qui che entrano in gioco i service di Ubuntu. Un service (o servizio se preferite in italiano) su Ubuntu costituisce la gestione regolarizzata di uno o più processi in totale autonomia dell’OS ed in background.

Tra i vari parametri configurabili di un servizio, troviamo quelli che ne definiscono il tempo di esecuzione, partenza e comportamento in caso di errore, come ad esempio il riavvio od un nuovo tentativo ad una certa distanza temporale.

I servizi su Ubuntu sono facilmente gestibili con il comando service o il suo sinonimo systemctl, fornendo come parametro l’operazione da effettuare sul servizio specificato:enalbe, disable, stop, start, restart e status.

Creiamo dunque il file di configurazione per il servizio che si occuperà di avviare (e tenere avviata) la nostra applicazione .NET sul server.
Come in precedenza, usiamo l’editor nano per creare il suddetto file:

sudo nano /etc/systemd/system/MyCrossPlatformApp.service

Avviato l’editor del nuovo file vuoto, possiamo copiare al suo interno la seguente configurazione, salvandola infine con CTRL+O -> INVIO -> CTRL+X :

[Unit]

Description=ASP .NET Web Application

[Service]

WorkingDirectory=/home/cerini/MyCrossPlatformApp

ExecStart=/usr/bin/dotnet /home/cerini/MyCrossPlatformApp/ MyCrossPlatformApp.dll

Restart=always

# Restart service after 10 seconds if the dotnet service crashes:

RestartSec=10

SyslogIdentifier=dotnet5-demo

User=www-data

Environment=ASPNETCORE_ENVIRONMENT=Production

[Install]

WantedBy=multi-user.target


Tra le config più interessanti troviamo la WorkingDirectory con cui diamo il contesto della cartella di esecuzione, ExecStart che definisce il vero e proprio comando da eseguire (dotnet + dll), Restart e RestartSec con cui definiamo il comportamento in caso di errore/crash del servizio.

Possiamo dunque abilitare il servizio e tentarne l’avvio:

sudo systemctl enable MyCrossPlatformApp

sudo systemctl start MyCrossPlatformAppt

Controlliamo infine che sia correttamente partito con:

sudo systemctl status MyCrossPlatformApp

La prova del nove la potrete tranquillamente avere navigando come al solito dal vostro browser.

Provare per credere! E se vi sentite fortunati (e ne avete la possibilità) provate a riavviare il vostro server: il servizio avvierà la vostra applicazione .NET automaticamente una volta ripartito Ubuntu.

Articolo a cura di Luca Cerini, Senior Developer in Orbyta Tech, 07/09/2021

#jointherevolution

Introduci la tua esperienza professionale dall’università fino all’ingresso in ORBYTA 

Nel luglio del 2019 mi sono laureata in Lingue e letterature moderne presso l’Università degli Studi di Torino. A differenza di altri percorsi di formazione, sapevo che, terminati gli studi, avrei dovuto tracciare la mia strada e costruirmi un profilo professionale. 

Conseguita la laurea, ho iniziato a cercare contesti in cui potessi esprimermi al meglio e, dopo qualche esperienza in diverse realtà, è iniziato il mio percorso nell’ambito delle risorse umane presso un’agenzia per il lavoro.

L’esperienza in agenzia mi ha fatto appassionare al punto di voler ampliare la conoscenza del settore anche all’interno di un contesto aziendale. Di qui l’inizio in ORBYTA nel luglio del 2020 nell’ufficio HR.

Di cosa ti occupi e che valore porti all’azienda?

L’esperienza di stage nell’ufficio HR termina a febbraio 2021 con il mio ingresso in ORBYTA People.

Oggi mi occupo della gestione del flusso paghe per le società del gruppo e del servizio payroll e gestione risorse umane che offriamo alle aziende clienti. 

Il valore che porto all’azienda si traduce in passione, impegno ed entusiasmo. Mi piace lavorare bene e sodo per contribuire al raggiungimento degli obiettivi e al miglioramento dei processi.

Perché ti piace lavorare in ORBYTA?

Mi piace lavorare in ORBYTA perché viene dato valore alla parola di ciascuno. È un contesto dove è possibile esprimere il proprio potenziale, confrontarsi e formarsi.

Ogni giorno si vive una realtà stimolante e dinamica affiancata da professionisti che sono veri e propri mentori per la crescita personale e professionale.

Essere un Orbyter va oltre il concetto di lavoro. Significa condividere un progetto, avere una visione comune che stimoli la costante crescita di tutto il gruppo ed io sono contenta e fiera di farne parte.

#jointherevolution

Fonte: https://www.networkworld.com/article/2878394/mit-researchers-show-you-can-be-identified-by-a-just-few-data-points.html

Network Science e Social Network Analysis

Introduzione

I network (o reti) sono uno strumento potente ed efficace per rappresentare la realtà che ci circonda e sono infatti presenti in quasi ogni aspetto della nostra vita. Amici, parenti, il Web, le strade di una città… tutto può essere modellato sotto forma di network. Lo scopo di questa rappresentazione è quello di studiare un sistema cercando di catturarne la sua complessità e le relative cause. In generale, un network è la semplice descrizione di un insieme composto da entità interconnesse, che chiamiamo nodi, e le loro connessioni/relazioni, che chiamiamo link. I nodi possono rappresentare ogni genere di entità: persone, luoghi, siti web, cellule, etc. Le relazioni a loro volta possono esprimere ogni tipo di interazione/scambio/flusso che avviene fra due entità, quindi pagamenti, scambi di messaggi, like su Facebook, etc.

Nota: In questo articolo i social network vanno intesi come reti sociali e non come i siti di social networking come Facebook e Twitter.

I network sociali sono un particolare tipo di network dove i nodi sono persone interconnesse da un qualche tipo di relazione. Ci sono tantissimi tipi di social network, al punto che questa è la categoria di network più studiata in assoluto. Per esempio la sociologia, il ramo da cui è partito lo studio delle reti sociali, cerca di stabilire delle regole emergenti dal comportamento collettivo degli individui.  Nell’ambito della medicina si può studiare la propagazione di malattie attraverso una rete sociale, in economia si studia come il comportamento di un individuo influenza quello di un altro sulla base di meccanismi di incentivi ed aspettative degli altri. Nel campo della ricerca i social network vengono utilizzati per studiare gli autori più influenti e come hanno collaborato fra loro nello studio di un determinato argomento.

La complessità delle connessioni della società moderna, data da fenomeni come internet, crisi finanziarie o epidemie è data dal comportamento aggregato di gruppi di persone le cui azioni hanno conseguenze sul comportamento di tutti gli altri. Il crescente interesse verso lo studio di tale complessità ha reso la Social Network Analysis uno degli strumenti di visualizzazione e rappresentazione dei sistemi complessi più utilizzati.

Teoria dei Grafi

La Social Network Analysis ed in generale tutta la Network Science si basa sui concetti chiave della teoria dei grafi di nodo e legame, andando ad ampliare questa branca della matematica con una serie di termini e metriche propri, dati dallo sviluppo autonomo di questo campo di ricerca.

L’avvento della teoria dei grafi si riconduce a un aneddoto del 1736 della città Prussiana di Königsberg, città natale di Immanuel Kant e Leonhard Euler, per noi Eulero. Eulero si trovò ad affrontare un problema matematico legato alla città di Königsberg, la quale era divisa ai tempi in quattro settori dal fiume Pregel, connessi tra loro da sette ponti. Solo cinque di questi sono sopravvissuti ai bombardamenti della Seconda guerra mondiale e allo stesso modo molti edifici sono stati demoliti. Il problema con cui si cimentò Eulero, irrisolto fino a quel momento, era quello di collegare tutti e sette i ponti potendo passare solo una volta su ciascuno di questi.

Eulero formalizzò il problema ricorrendo a un grafo i cui nodi erano i quattro settori della città, e i collegamenti erano i ponti. Dimostrò così che un tale percorso esiste solo se tutti i nodi hanno grado (numero di link) pari, tranne la partenza e l’arrivo. Questo tipo di percorso, rinominato poi Eulerian path in suo onore, non è effettivamente possibile in questo sistema in quanto ognuno dei quattro nodi ha un numero dispari di connessioni. La vera novità di questo approccio fu l’aver formalizzato in forma topologica il problema, andando a definire questo tipo di percorso come una proprietà intrinseca del grafo.

La forza dei legami deboli e la Small-World property

La teoria della “forza dei legami deboli” nasce da uno studio di Mark Granovetter degli anni 60 diventato poi un classico della sociologia. Granovetter, attraverso una serie di interviste, andò a studiare come le persone che avevano recentemente cambiato mestiere a Boston fossero venute a conoscenza della nuova opportunità. La maggior parte di queste persone erano immigrati irlandesi, i quali erano soliti trascorrere una buona quantità di tempo nei pub. Il lavoro ed in particolare quello edilizio, settore principale di queste persone, era molto instabile portando a frequenti passaggi dallo stato di occupazione a quello di disoccupazione. L’obiettivo iniziale della ricerca era di capire il ruolo delle conversazioni nei pub nella ricerca del nuovo lavoro.  Scoprì che molte persone avevano trovato il nuovo lavoro attraverso i contatti personali e pertanto decise di soffermarsi proprio su questi. Emerse dalla sua ricerca che questi contatti erano perlopiù conoscenti piuttosto che amici stretti. Solo il 30% degli intervistati aveva trovato lavoro attraverso i contatti più stretti. 

Fonte: https://www.nature.com/articles/srep05739/figures/2

Da qui la distinzione tra legami forti e deboli. I legami forti erano amici e parenti, mentre i legami deboli semplici conoscenti. Granovetter teorizzò quindi che i legami forti sono maggiormente disposti a fornire un supporto emotivo, ma appartenendo alla stessa cerchia di chi in questo caso sta cercando lavoro, hanno meno possibilità di fornire informazioni che non conosciamo. I legami deboli a differenza, appartenendo a cerchie da noi distanti sono in contatto con realtà a noi sconosciute ed hanno per questo accesso a informazioni nuove. Le implicazioni di questo studio sono vastissime e tuttora oggetto di studio. Il perché i social media siano diventati uno strumento così potente è riconducibile proprio al concetto di legame debole. Essenzialmente, i social media non fanno altro che mantenere ed amplificare i legami deboli, definiti in questo caso come legami sociali che non richiedono alcun attaccamento emotivo, necessità di comunicare o tempo da dedicare. Nonostante questo, risultano estremamente potenti in quanto fungono da canali per il passaggio di informazioni tra persone distanti sia in termini fisici che sociali (es reddito, cultura, etc). Quando due persone comunicano attraverso un legame debole, l’informazione che passa attraverso di esso è di solito nuova, e proviene da un diverso punto di vista.

Dal punto di vista dei network i legami forti (come quelli tra coniugi e amici intimi) tendono a riunire i nodi in cluster stretti e densamente interconnessi. All’interno di questi cluster si sviluppa una conoscenza specifica ma non si generano conoscenze “distanti” a livello di contenuti. Poiché diverse nicchie conservano diversi tipi di conoscenza, sono i collegamenti tra i questi sub-network a permettere la condivisione. Tali collegamenti sono chiamati ponti. Granovetter ha quindi capito che nelle reti sociali i legami che tengono insieme la rete stessa sono, paradossalmente, i legami “deboli”.

La famosa teoria dei sei gradi di separazione si basa proprio su questo concetto, ovvero che attraverso i semplici legami deboli due persone qualunque del globo sono in grado di entrare in contatto mediante un massimo di sei persone. L’esperimento fu condotto negli anni 60 da Stanley Milgram, data a cui risale la prima prova empirica dell’esistenza dei cosiddetti network small world. L’idea era quella di misurare la distanza sociale fra sconosciuti. Furono quindi selezionate 160 persone in Kansas e Nebraska per mandare una lettera a una persona selezionata in Massachussets. Ogni persona doveva mandare la lettera alla persona di sua conoscenza che reputava più adatta a raggiungere il destinatario. In questo caso solo il 26% di lettere arrivarono a destinazione correttamente, mostrando però che il numero medio di intermediari erano di poco superiori a 6. L’esperimento fu ripetuto nel 2003 usando però le email. Anche in questo caso si mise in luce il fatto che il path medio in termini di persone erano 5-7 individui. La maggior parte dei network del mondo reale hanno il percorso critico (il più veloce) medio molto breve, secondo quella che viene definita small word property. Questa proprietà rende le reti molto efficienti in termini di velocità di propagazione delle informazioni.

Fonte: https://mathspig.wordpress.com/tag/6-degrees-of-separation-explained/

Clustering

Una caratteristica che si osserva nelle reti sociali è che gli individui tendono ad aggregarsi in comunità, dette cluster. Questa proprietà, già nota nella sociologia come transitività, è stata poi ripresa nella network science con il nome di clustering. Come tale, questo coefficiente esprime la misura di quanti amici di un individuo sono a loro volta amici fra loro. A livello di rete si calcola come frazione di tutti i possibili triangoli (o triadi) che esistono nella rete, mentre a livello di singolo nodo corrisponde alla frazione di tutti i possibili triangoli che contengono il nodo in esame.

Una delle modalità per cui si formano cluster è quella della vicinanza a un altro nodo. Anche questo concetto è ampiamente trattato nella Social Network Analysis, e prende il nome di assortatività. Essa esprime la preferenza per un nodo ad interagire con un altro nodo avente caratteristiche simili. Nel caso delle reti sociali queste caratteristiche possono essere sesso, età, luogo, argomenti di interesse e così via. Alcuni ricercatori hanno visto che è possibile stabilire con una certa accuratezza l’orientamento politico di un individuo anche se non presente nel suo profilo guardando le caratteristiche della sua cerchia di amicizie. Una regola empirica è che se due persone sono simili in qualche modo, è più probabile che si selezionino a vicenda e diventino due nodi interconnessi. A questo aspetto si lega la teoria delle bolle di filtraggio di Eli Pariser che sarebbe interessante approfondire, ma questo esula dal tema dell’articolo.

Watts–Strogatz Model

Per studiare come emergono le caratteristiche di un network, come la small world property o il clustering, si utilizzano degli algoritmi di simulazione che generano dei modelli. Questi modelli vengono poi comparati con i dati reali per capirne le differenze e studiarne i meccanismi.

Il modello Watts–Strogatz (1998) è un network avente proprietà small world che allo stesso tempo possiede un buon coefficiente di clustering. Può essere generato in modo sperimentale risultando in un network dove la maggior parte dei nodi sono collegati a un numero relativamente ristretto di vicini in maniera piuttosto regolare, con alcune eccezioni dati da legami deboli con nodi distanti. Watts e Strogatz notarono che nel mondo reale non si riscontravano pressoché in nessuna situazione né network regolari, dove tutti i nodi sono strettamente legati ai propri vicini, né network completamente randomici, dove invece i collegamenti fra nodi non seguono nessuna logica particolare. Osservarono infatti che la realtà circostante era sempre una via di mezzo fra questi due tipi di network, ovvero una forte aggregazione in cluster tipica di un network regolare e allo stesso tempo una forte propensione alla propagazione di informazioni secondo la small world property, tipica invece di un random network. La soluzione che proposero è quindi l’interpolazione di questi due estremi.

L’algoritmo di generazione di un modello Watts–Strogatz parte da un network regolare dove tutti i nodi sono connessi ai propri vicini, e in modo randomico elimina alcuni di questi collegamenti andandoli a sostituire con collegamenti a nodi più distanti. In questo modo le proprietà topologiche locali fra nodi vicini rimangono intatte, ma si permette ai legami deboli di fungere da collegamento con nodi anche molto distanti.

Fonte: https://www.nature.com/articles/30918

Il problema delle reti Watts-Strogatz è dato dall’inaccuratezza nella distribuzione dei gradi (il numero di collegamenti di ciascun nodo).  Il numero di vicini di un nodo è infatti circa lo stesso per tutti i nodi, e differisce leggermente dal valore medio, seguendo così una distribuzione di Poisson. Risulta così un network molto omogeneo, che non rispecchia però la distribuzione delle reti reali. Nel mondo reale si assiste infatti a una fortissima disuguaglianza fra il grado dei nodi, secondo quella che viene definita “legge di potenza”, ovvero ci sono molti nodi con poche connessioni e pochi nodi con molte connessioni. Barabasi e Albert hanno considerato questo aspetto andando a creare un modello che si basa sulla legge di potenza.  Una distribuzione che segue la legge di potenza è denominata power law distribution, distribuzione a invarianza di scala (scale-free distribution) o anche distribuzione di Pareto. La peculiarità di questo tipo di distribuzioni sta proprio nell’assenza di una scala caratteristica dei fenomeni. 

Fonte: http://networksciencebook.com/chapter/4#hubs

 Scale free and Barabasi-Albert Model

Il modello Barabasi-Albert (1999) si discosta dal modello Watts-Strogatz aggiungendo realismo nel meccanismo di clustering dei nuovi nodi. Mentre il modello Watts-Strogatz parte da un set di nodi dall’inizio alla fine, il Barabasi-Albert aggiunge i nodi uno per volta rendendo il modello dinamico.

L’idea alla base è di generare una rete secondo una progressiva aggregazione di nodi seguendo una logica di preferenza verso i nodi più grandi, chiamata attaccamento preferenziale. In altre parole, quando si aggiungono nuovi nodi, questi andranno a connettersi tendenzialmente a nodi già largamente interconnessi, che vengono definiti hub.

Fonte: https://makeagif.com/i/0Ccn3L

Questo principio viene anche definito come “rich get richer”, ovvero i nodi più grandi tendono a diventare ancora più grandi. La probabilità che un nuovo nodo si colleghi a uno vecchio è proporzionale al grado del vecchio nodo. Per esempio un nodo con grado 10 è 10 volte più probabile che venga raggiunto da un nuovo nodo rispetto a un altro nodo avente grado 1. La proprietà di small world viene in questo caso garantita proprio dagli hub, che fungono da ponte principale fra coppie di nodi non collegati.

Fonte: https://en.wikipedia.org/wiki/Mediation-driven_attachment_model

Questo tipo di modello trova un ampissimo riscontro nel mondo reale, come per esempio le pagine Web. Numerosi studi hanno dimostrato che più un sito è citato, ossia possiede più hyperlink, e più è probabile che verrà citato nuovamente e viceversa. La causa sottostante a questo fenomeno è spiegata dal fatto che più hyperlink ha un sito web e più è visibile, di conseguenza è più probabile che il sito riceva altri hyperlink.  Questo stesso meccanismo si manifesta allo stesso modo nella legge di Pareto, per cui la ricchezza tende a concentrarsi nelle mani di pochi individui molto ricchi mentre è molto scarsa nel resto della popolazione (il 20% della popolazione possiede l’80% delle risorse, oppure il 20% delle parole di una lingua compongono l’80% del parlato).

Misure di centralità

Spostando l’analisi a livello di singolo nodo all’interno della rete, la SNA permette di studiare le relazioni di ogni attore nella rete mostrandone le gerarchie e fornendo un quadro per spiegare la struttura e l’evoluzione dei singoli nodi e dei gruppi di nodi. Le reti sociali sono sistemi complessi e come tali necessitano di una moltitudine di metriche e strumenti di analisi. Le principali sono le centralità, ma vi sono anche la distribuzione dei gradi, la topologia della rete locale, la struttura della comunità e l’evoluzione della rete.

La prima domanda che potrebbe sorgere analizzando una rete è: chi è il più importante?

Ovviamente la risposta è dipende, e qui andremo a spiegare brevemente perché.

Generalmente sono le misure di centralità a rispondere a questa domanda. Le misure di centralità sono usate per calcolare l’importanza di un individuo all’interno del network, tuttavia sono vari i criteri di importanza: potere, l’influenza, o altre caratteristiche individuali delle persone. Per questo motivo ci sono diverse misure di centralità della rete. Analizzeremo le 4 principali.

Degree centrality

Se si vuole misurare il numero di connessioni che ha un individuo allora la degree centrality fa al caso nostro. Su Facebook per esempio corrisponderebbe al numero dei nostri amici. E’ logico pensare che più una persona abbia collegamenti e più abbia influenza sulle altre persone. Ma non è necessariamente così.  Scott Adams, il creatore del fumetto Dilbert, sostiene che il potere di una persona è inversamente proporzionale al numero di chiavi nel suo portachiavi. Un custode ha le chiavi di tutti gli uffici e nessun potere. L’amministratore delegato non ha bisogno di una chiave, c’è sempre qualcuno ad aprirgli la porta. Effettivamente sono molti i casi in cui una persona di potere ha relativamente pochi contatti e per questo sono necessarie altre metriche di centralità.

Una breve digressione può essere fatta riguardo le due sottomisure della degree-centrality date dal numero di link in entrata o in uscita di un nodo, ovvero centralità in-degree e out-degree. Questo aspetto è interessante perché viene usato per misurare il livello di fiducia verso un individuo della rete. Semplificando molto (in quanto bisognerebbe tenere conto di molti altri aspetti), un attore con un basso valore di fiducia può essere identificato da un alto valore di centralità out-degree a cui corrispondono bassi valori di centralità out-degree degli attori con cui comunica. Ciò può essere spiegato dal fatto che questo attore si sente sicuro nel diffondere informazioni, ma gli altri attori non diffondono queste informazioni perché non reputano affidabile tale informazione.

Fonte:https://cambridge-intelligence.com/social-network-analysis/

Closeness centrality

Un altro modo di misurare la centralità è quello di guardare quanto un nodo è “vicino” agli altri nodi. La closeness centrality è usata per misurare la lunghezza media del percorso più breve da un nodo verso un qualunque altro nodo. Maksim Tsvetovat e Alexander Kouznetsov la definiscono la misura dei gossippari poiché rappresenta l’abilità di un attore di trasmettere o condividere informazioni da un lato del network all’altro. Minore è la distanza totale nella rete e più la closeness centrality sarà alta. In altre parole, rappresenta la velocità con cui l’informazione può raggiungere altri nodi da un dato nodo di partenza: i gossippari fanno arrivare le informazioni molto più velocemente degli altri.

Betweeness Centrality

La betweeness centrality è una misura che viene usata per studiare il ruolo di un nodo nella propagazione di una informazione. Se un nodo è l’unico collegamento ponte fra altri due nodi si può dire che abbia una posizione in qualche modo privilegiata o strategica. La Betweeness Centrality va a misurare proprio questo valore. Viene infatti spesso usata per misurare il traffico nei network di trasporti. Si calcola andando a contare quante volte un nodo è attraversato da un percorso critico (il percorso più breve, o anche Eulerian path) rispetto al totale dei percorsi critici.

Se c’è un buco strutturale (una forma di discontinuità nel flusso di informazioni) in una rete, la persona che detiene la posizione di intermediazione può assumere una posizione strategica per collegare o scollegare i nodi in un gruppo, e quindi gode di un vantaggio competitivo rispetto agli altri nodi. Gli attori con un alto valore di betweeness centrality sono come dei guardiani che controllano il flusso di informazioni tra gli altri. 

Generalmente i nodi aventi alta betweeness sono quelli aventi anche alta degree centrality, in quanto sono i cosiddetti hub che abbiamo descritto sopra. Questo non è però il caso in cui un nodo va a collegare due regioni del network diverse e semplicemente scollegate. In questo caso il nodo può avere pochi collegamenti con altri nodi, ma fungere da ponte tra due regioni molto distanti della rete.

Cercando di mettere insieme i pezzi, si può dire che un nodo avente una alta betweeness centrality può corrispondere a uno dei due estremi di un legame debole di Granovetter, che a sua volta garantisce a un network la proprietà di small world vista sopra.

Eigenvector Centrality

Il detto “dimmi chi sono i tuoi amici e ti dirò chi sei” si traduce nella social network analysis nella centralità dell’autovettore. Questa misura ci dà informazioni su un attore sulla base delle relazioni che ha con i suoi vicini, cioè i suoi contatti più stretti. Di nuovo Maksim Tsvetovat e Alexander Kouznetsov hanno trovato l’analogia perfetta, ovvero Don Vito Corleone. Egli infatti con le misure di centralità precedenti non si sarebbe potuto riconoscere come il boss, poiché non ha molti collegamenti diretti e non scambia molte parole in giro. Ecco quindi l’utilità dell’eigenvector centrality. Sostanzialmente si basa sull’algoritmo di Bonacich, che iterativamente calcola un peso per ciascuno dei link di un nodo basandosi su quello degli attori vicini. Può essere definita come un’estensione della degree-centrality poiché va a guardare proprio questa metrica nei vicini, ed infatti un attore con alta eigenvector centrality è connesso a nodi aventi molte connessioni a loro volta.

Pagerank

Simile alla Eigenvector Centrality in quanto si basa sullo stesso principio di calcolo dei pesi ricorsivo è il pagerank, l’algoritmo sviluppato da Larry Page come parte essenziale delle prime versioni di Google per indicizzare le pagine Web. Il PageRank è una misura di centralità che calcola il prestigio di un nodo, inteso come pagina Web. Le pagine Web sono i nodi di un grafo orientato dove i link fra nodi sono gli  hyperlink alla pagina stessa (link alla pagina presenti su altre pagine web). Il grado di un nodo è calcolato come la probabilità che una persona capiti casualmente su quella pagina cliccando un link. 

Questo processo è conosciuto come random walk, ed è una semplice simulazione di come l’utente naviga nel web. La pagina con il più alto indice di ranking è quindi la destinazione più probabile. Si potrebbe pensare perchè non usare direttamente la in-degree centrality allora? Il Pagerank è in questo caso molto più efficiente perché tiene conto dell’importanza della pagina da cui proviene l’hyperlink. Ovvero se la pagina target viene citata dal Wall Street Journal sarà molto più alta in ranking rispetto a una pagina citata da un sito di spam. 

Conclusione 

Come abbiamo visto in questo articolo la SNA è uno strumento di analisi estremamente potente ed affascinante che può essere utilizzato in concomitanza con molti altri modelli nel contesto della data science. Uno di questi è la teoria dei giochi, con la quale è possibile applicare alcune delle analisi di cui abbiamo parlato, come vedremo nei prossimi articoli. 

Fonti

  • Albert, and Barabasi. Network Science. Cambridge University Press, 2016.
  • Easley, David, and Jon Kleinberg. Networks, Crowds, and Markets: Reasoning about a Highly Connected World. Cambridge University Press, 2010.
  • Menczer, Filippo, et al. A First Course in Network Science. Cambridge University Press, 2020.
  • Tsvetovat, Maksim, and Alexander Kouznetsov. Social Network Analysis for Startups. O’Reilly, 2011.
  • Zinoviev, Dimitry. Complex Network Analysis in Python. Adaobi Obi Tulton, 2018.

Articolo a cura di Giovanni Ceccaroni, Data Scientist in Orbyta Tech, 22.06.2021

#jointherevolution