Centralità

Question 1

Introduzione, definizione e tipologie studiate.

Answer 1

Quali sono i vertici centrali di un grafo? Quali sono i vertici più importanti?
-> centralità dipende dal problema che stiamo analizzando.

Def: una misura di centralità è una f che assegna a ogni vertice un numero R+ C(v) chiamato centralità di v.
v è più centrale di s se C(v) > C(s).
v è il più centrale del grafo se C(v)> C(tutti i vertici).

Tipologie studiate:
- C di grado.
- C di closeness.
- C di betweenness.

Question 2

C di grado

Answer 2

Misura la capacità di un vertice di relazionarsi direttamente con gli altri.

Si misura calcolando il grado di un vertice ovvero il numero di archi incidente in v.

Question 3

C di closeness

Answer 3

Misura quanto un nodo è vicino agli altri nodi della rete.

Versione assoluta: 1/sommatoria delle d(v,u) per ogni u appartenente a V.

Versione normalizzata che tiene conto del numero di vertici:
(n-1)/sommatoria delle d(v,u) per ogni u appartenente a V.

La v normalizzata va da 0 non compreso a 1 compreso.
Vale 1 se v è adiacente a tutti gli altri vertici del grafo.
Più clos(v) è alta e più il vertice si può relazionare rapidamente con gli altri vertici.

Question 4

C. di betweenness

Answer 4

Misura quanto un nodo è importante nella comunicazione tra diverse parti della rete.

betw(v)= sommatoria di gjw(v)/gjw.

gjw è il numero di cammini minimi tra j e w.
gjw(v) è il numero di cammini minimi tra j e w passante per v.

Per calcolare la betweenness mi conviene prima calcolare tutti i percorsi minimi tra tutti i vertici.