CAP. X: teoria dei grafi - nodi, link e matrici Flashcards
Qual è il massimo numero di possibili connessioni all’interno di un gruppo (network) di n soggetti (nodi)?
Più grande è il gruppo, più legami sono necessari per unire i membri tra loro e al gruppo. Il numero massimo di legami all’interno di un gruppo in cui ognuno è legato a tutti gli altri è dato dall’equazione Links=[n(n-1)]/2
Ma solo se lo stile grafico che scegliamo è “indiretto” e “non ponderato” …. la teoria dei grafi ….
Definizione di Rete (network) nella Teoria dei Grafi
I grafi sono strutture matematiche discrete che rivestono interesse sia per la matematica che per un’ampia gamma di campi applicativi. Un grafo è un insieme di elementi detti nodi o vertici collegati fra loro da archi o lati. Più formalmente, si dice grafo una coppia ordinata G = (V, E) di insiemi, con V insieme dei nodi ed E insieme degli archi, tali che gli elementi di E siano coppie di elementi di V Due vertici u, v connessi da un arco e prendono nome di “estremi dell’arco”; l’arco e viene anche identificato con la coppia formata dai suoi estremi (u, v). Un arco che ha due estremi coincidenti si dice ricorsivo.
Definizione di Nodi e Link
Il Nodo o Vertice di un network rappresenta l’unità elementare o microscopica del grafo, e quindi ne indica le unità statistiche. Il Link rappresenta invece la relazione esistente tra due Nodi e genericamente questa può essere rappresentabile in forma Discreta o Continua, Diretta o Non Diretta.
Quali sono le 4 tipologie di reti che possiamo ottenere modificando la modalità della rappresentazione dei link?
In funzione della modalità con la quale si rappresentano gli archi, si ottengono quattro tipologie generali di network: non diretta-discreta (I), diretta-discreta (II), non diretta-pesata (III); diretta-pesata (IV)…
La rappresentazione di una rete può essere simmetrica o asimmetrica. Fare un esempio per ciascuno dei due casi.
schema a mano
Cos’è il grado di un nodo (grado di connettività)?
schema a mano
Cos’è il grado di centralità di un nodo?
schema a mano
Qual’è la differenza tra Grado di un nodo e Grado di Centralità di un nodo?
Il grado di centralità è il grado normalizzato (cioè, diviso per il numero massimo possibile di connessioni del soggetto i).
Cos’è la Betweenness di un nodo?
schema a mano
Definire il concetto di Nodi e Foglie nella teoria dei grafi spiegandone la differenza.
I nodi che hanno un alto grado di Centralità sono detti Hubs, mentre quelli con centrality bassa sono solitamente definiti foglie. Il loro ruolo all’interno della diffusione delle informazioni all’interno di un network può essere significativamente diverso e non banale.
Come possono essere usati il Grado, Centralità e Betweenness per caratterizzare una rete?
Quando ci spostiamo dalla descrizione delle unità microscopiche di un network (i nodi), alle proprietà Globali del grafo che lo rappresenta, oltre alle vecchie dimensioni osservabili, nascono e possono essere definite nuove emergenti proprietà. Il Grado Medio, la Centrality Media e la Betweennees Media del grafo stesso.
Definizione di Diametro di una rete.
Il più lungo dei cammini minimi esistenti all’interno della rete.
Definizione di Topologia di una rete.
Una topologia di rete è la rappresentazione della struttura geometrica di una rete di relazioni. Un nodo può avere una o più connessioni con gli altri secondo differenti schemi. La topologia di rete è determinata soltanto dalla configurazione dei collegamenti tra i nodi. Per la precisione, solitamente non riguardano la topologia di rete: le distanze tra i nodi, le interconnessioni fisiche, le velocità di trasmissione, i tipi di segnale.
Qual’è la relazione tra il numero di nodi di una rete (persone) e il numero massimo di possibili connessioni all’interno di tale rete?
Più grande è il gruppo, più legami sono necessari per unire i membri tra loro e al gruppo. Il numero massimo di legami all’interno di un gruppo in cui tutti sono collegati a tutti gli altri è dato dall’equazione Links=n(n-1)2 e il numero di legami necessari per connettere tutti i membri cresce esponenzialmente man mano che il gruppo diventa più grande.
