Teoria delle reti e delle decisioni

Teoria delle reti e delle decisioni

Definizioni

Grafi: relazione tra gli elementi di un insieme.

Reti: grafo a cui nodi/archi sono associati dei pesi, i quali hanno un significato diverso in base al contesto.

Insieme N: nodi o vertici del grafo che rappresentano gli oggetti dell'insieme di riferimento. N= {1,2,3}

Insieme E: spigoli del grafo che schematizzano la relazione esistente tra i nodi. E= {(1,2),(2,3),(3,1)}

Grafo orientato: se la relazione tra due nodi sia in una sola direzione. (i,j) ≠ (j,i)

Grafo non orientato: se le coppie (i,j), (j,i) rappresentano la stessa relazione.

• In un grafo orientato il nodo i è chiamato coda dell'arco mentre il nodo j è il nodo testa.
• In un grafo non orientato i nodi (i,j) sono adiacenti o lo spigolo è incidente su i e j.
• In un grafo orientato un arco (i,j) si dice che l'arco va da i a j.
• In un grafo non orientato si definisce il grado di un nodo i e si indica con d(i) il numero degli spigoli incidenti ad i.
• In un grafo orientato si definisce il grado entrante e uscente di un nodo i e si indicano con d(i)⁻, d(i)⁺ il numero degli archi entranti e uscenti.

Cammino: sequenza di nodi e spigoli; archi se il grafo è orientato. C= {2,(2,1)1,(1,3)3,(3,4)4}

Ciclo: sequenza non orientata di nodi e spigoli, dove il nodo iniziale coincide con il nodo finale.

Circuito: sequenza orientata di nodi e archi.

Grafo connesso: quando si prendono due nodi ed esiste almeno un cammino che collega due vertici considerati.

Grafo fortemente connesso: se si prende una coppia di nodi ed esiste un cammino che consente di andare dal nodo i al nodo j e viceversa.

Grafo debolmente connesso: se si ignora la direzione degli archi, il grafo risultante è connesso.

• I nodi sono isolati se non c'è nessuna relazione tra essi.
• Il grafo è sconnesso in due componenti connesse.

Grafo completo: Kn, se ogni nodo è collegato con tutti gli altri.

Grafo nullo: On, si individuano dei nodi ma che sono tutti isolati.

Grafo albero: se valgono due delle tre proprietà:

• Se G è connesso con una sola componente;
• Se G non ha cicli;
• Il numero degli spigoli di G è |E|=|V|-1

Sottografo: H=(V',E') È un grafo dove V' è un sottoinsieme di V ed E' è un sottoinsieme di E.

Albero ricoprente: T=(V',E') È un albero ricoprente di G se:

• T è un albero;
• V'=V;
• E' è un sottoinsieme di E.

Cricca/clique: È un sotto grafo completo massimale, tutti i nodi di C sono due a due adiacenti e nessun altro sotto grafo completo di G contiene C. (ogni grafo completo è una cricca).

Grafo bipartito: se l’insieme dei suoi nodi è suddiviso in due sottoinsiemi (S-T) tali che non esiste nessuno spigolo che collega tra loro nodi dello stesso abbinamento: → insieme. Sottoinsieme di spigoli tali che ogni nodo è collegato con al più uno spigolo.

Grafo foresta: se è privo di cicli e le componenti connesse sono degli alberi.

• Indici di centralità: misurano l’importanza di un nodo all’interno di una rete G = (V,A) e sono:

Misure di centralità

Betweenness centrality: misura la centralità di un nodo K dalla rete calcolata come il numero di cammini minimi che passano nel nodo K, esso nodo intermediario.

Closeness centrality: misura la possibilità di un nodo di comunicare con molti altri nodi utilizzando il minimo numero di nodi intermediari. Esso calcola quanta informazione passa tra i nodi attraverso il:

• Flow betweenness: che misura il livello del flusso massimo tra tutte le coppie di nodi di una rete che dipende da uno specifico nodo K = ammontare dell’informazione che usa il nodo K come nodo intermediario. Il valore è tra 0 e 1: ^∑ { i , j } C Fij (con k in alto) FBk = flow betweenness del nodo k∈ FBk = __________________________ Fij (k in alto) = flusso massimo tra i nodi ∑ { i , j } C | i j Fij i,j per il nodo k∈ ≠ Fij = flusso massimo tra i nodi i,j C = insieme delle coppie di nodi
• Flow closeness: misura la forza di propagazione di un flusso di informazioni da un nodo k a tutti gli altri nodi, la formula è: ∑ FCk = Fkj Fkj = flusso massimo tra il nodo k e j j∈V|j≠k
• Influenza tra gruppi: dati due insieme T - R di nodi della rete, con T∩R=∅, IG misura l’influenza dell’insieme dei nodi in T sull’insieme dei nodi in R, la formula è: ∑ ∑ IGtr = Fij Fij = flusso massimo tra il nodo e i j con i appartenente a T i∈T j=R e j a R

Caratterizzare: cercare di capire l’importanza di un nodo all’interno di una rete.

Misure di centralità in un grafo non orientato

G=(N,E) non è orientato, E: insieme degli spigoli di G, N: insieme dei nodi di G

1. Lunghezza media di un cammino: distanza geodesica media tra tutte le coppie di nodi nel grafo. È una misura della connessione tra i vertici del grafo, minore è la misura maggiore è la vicinanza tra i vertici del grafo = + compattezza del grafo. 1 ∑ L = dij = distanza dal nodo i al nodo j dji________ n= numero di nodi nel grafo 1\2n(n-1) i≥j
2. Coefficiente di raggruppamento locale: frazione delle coppie di nodi che sono vicini al nodo i e sono collegati tra loro: Cl(i)= →|ejk E : eij E eij E| misura il numero delle coppie dei nodi che∈ ∈ ∩ ∈ sono vicini al nodo i e tra loro sono collegati__________________________ → dj(di-1)\2 per il grado del nodo i
3. Coefficiente di raggruppamento globale: è la media dei coefficienti di raggruppamento locale e nelle reti sociali descrive la numerosità delle comunità di nodi che sono strettamente collegati tra loro. n ∑ Cl = 1\n Cl(i) i=1
4. Centralità assoluta di grado: si considera il grado (di) di un nodo i e misura l’importanza o la popolarità di un nodo della rete rispetto agli altri nodi.
5. Centralità relativa di grado: si considera il coefficiente di -1 di un nodo i e misura l’importanza o la popolarità relativa di un nodo della rete rispetto agli altri nodi. Pjk(i)____Pjk
6. Vicinanza: reciproco della somma delle distanze geodesiche da un nodo i a tutti gli altri nodi del grafo. Se è elevato significa che questo nodo ha una forte interazione con tutti gli altri nodi della rete. ∑ Cc(i)= 1\dij j≠i ∑
7. Betweenness centrality: Cb(i)=j,k≠i Pjk(i) = numero di cammini che collegano il nodo j al nodo k e che passano per il nodo i. Pjk = numero di cammini che collegano il nodo j al nodo k. Questo indice misura il grado di attrazione del nodo i rispetto a tutti gli altri nodi della rete.
8. Eigenvector centrality: misura l’importanza del nodo (Xi) rispetto ai suoi nodi vicini. ∑ Xi = 1\⋅ Xj j∈Ni Ni = insieme dei nodi che sono collegati ad i= “opportuno” parametro ⋅