lunes, 22 de agosto de 2011

Instrumentos para medir centralidad en una red

Supongamos que para poder contactarnos con la persona Pj tenemos primero que pasar por la persona Pk. Si este fuera el caso, esta última persona se encontraría en una posición central porque podría impedirnos llegar directamente a Pj. Esa posición central radica en que ese nodo puede controlar la información que fluye en la red. Podría, por ejemplo, impedir, facilitar o segar la transmisión de los mensajes.

En 1977, Linton Freeman, hoy profesor de sociología en la University of California – Irvine, publica “A set of measures of centrality based on betweenness”. La intención de Freeman es introducir tres medidas que pueden indicar la centralidad de un nodo en función de la capacidad de intermediación (betweenness).

Centralidad total de un nodo
Consideremos un par de nodos diferentes, por ejemplo Pi y Pj. De todos los senderos que conectan a estos nodos, uno o más de uno de ellos será el más corto. Los senderos más cortos se denominan geodésicos.
Si un nodo, distinto de Pi y de Pj, se encuentra en alguno de los geodésicos que unen a estos dos nodos, se considera que es central. Así, por ejemplo, en el siguiente sencillo grafo, Pk es un nodo central.
Al estar en el geodésico entre Pi y Pj, el nodo Pk tiene poder para sesgar la comunicación entre ellos.

En este otro caso hay dos geodésicos entre P1 y P3. Tanto el camino que va de P1 a P3 vía P2 como el que va vía P4, tienen la misma longitud. Por su puesto que la medida de longitud puede estar ponderada por elementos como velocidad de circulación (ej. Velocidad de transferencia entre servidores) o peligrosidad de la ruta. En este caso sólo tratamos con un modelo simple en donde las distancias están sólo en función de la cantidad de nodos que hay que atravesar hasta llegar a destino.
Entonces, aquí P2 ya no tiene tanto poder, justamente porque P1 puede tomar una ruta alternativa. La medida de centralidad tiene que capturar ese hecho. La propuesta de Freeman es establecer la centralidad de un nodo en función de la cantidad de geodésicos en los que este se encuentra. Más formalmente, definamos a gij como la cantidad de geodésicos entre i y j. Entonces, 1/gij es la probabilidad de que un mensaje pase por alguno de los geodésicos cuando la probabilidad de tomar cualquiera de los caminos más cortos es idéntica.
Ahora definimos a gij(pk) como el número de veces en las que el nodo Pk se encuentra en los geodésicos entre i y j. Así,
es la probabilidad de que para llegar de i a j por cualquiera de los caminos más cortos que los unen, tengamos antes que pasar por Pk. En el grafo anterior, bij(B)=1/2.

Para determinar la centralidad total de un nodo, tenemos que sumar todos las intermediaciones en las que se encuentra Pk con todos los demás nodos de la red. Es decir:
Esta medida depende de dos factores a) del lugar que ocupa Pk en la red y de b) la cantidad de nodos en la red.

Centralidad Relativa de un Nodo
En el caso anterior la centralidad depende de la cantidad de nodos que posee la red. Eso provoca que un nodo pueda obtener el mismo valor de centralidad cuando se encuentra en una red pequeña como cuando se encuentra en otra red más grande. Para tener en cuenta el tamaño de la red el autor propone la siguiente manera de relativizar la centralidad total del nodo. La centralidad máxima de un nodo se da cuando hay un único nodo que está en todos los geodésicos de la red. Eso ocurre en los grafos con forma de estrella o de rueda:
Si a cualquiera de esos grafos se la agrega un enlace más, el nodo Pk perderá centralidad. Justamente porque se abre otro camino geodésico en donde este no interviene.
Así, si n es igual a la cantidad de nodos de la red, entonces un grafo totalmente conectado, es decir, todos los nodos se conectan entre sí, tendrá n(n-1)/2 enlaces. De todos esos enlaces, habrá n-1 que están conectados con Pk. Entonces, la estrella más grande que se puede armar con n nodos alcanzará en su nodo más central un valor de CB igual a:
Con ese valor, que depende del tamaño de la red, podemos ponderar cada centralidad. En definitiva, la centralidad relativa es:
En otras palabras, la centralidad relativa es la centralidad absoluta dividida por la máxima centralidad que podría obtener un nodo en esa misma red si esta tuviera forma de estrella.

Centralidad de un grafo
La centralidad de un grafo está asociada a la relevancia o dependencia que podría tener cierto nodo en la red. Por ejemplo, una red que tuviese un solo punto por el que pasasen todas las comunicaciones sería más central que otra en donde las comunicaciones se dieran vía múltiples canales.
Freeman propone como medida de centralidad de un grafo realizar un promedio de las diferencias entre el nodo con mayor centralidad relativa y la centralidad de los demás nodos.
Si la red fuera una estrella, entonces esta función arrojará un valor igual a 1. Mientras que si todos los nodos tuviesen la misma centralidad relativa, el valor será 0.


Notas:
Linton Freeman: http://moreno.ss.uci.edu/
http://es.wikipedia.org/wiki/Geod%C3%A9sica

Freeman, L. (1977). "A set of measures of centrality based on betweenness." Sociometry 40(1): 35-41.

No hay comentarios: