La centralidad de intermediación es un concepto asociado a la forma de detectar o medir el grado de influencia que un nodo o vértice posee dentro de un esquema o dentro de un grafo. Los algoritmos encargados de calificar los datos y medir su grado de centralidad de intermediación son utilizados usualmente para encontrar nodos que puedan servir como puente para conectar extremos distantes dentro de un grafo, creando así rutas más eficientes y más cortas.

¿Qué son los algoritmos de centralidad de intermediación?

Dentro de la teoría de grafos el concepto de centralidad esta asociado a la medida o valor que posee un nodo dentro de un grafo y esta puede ser de diferentes tipos. Uno de los tipos de centralidad que podemos conocer es la centralidad de intermediación. Esta es la que cuantifica la frecuencia o el número de oportunidades en las que un nodo actúa o sirve de conexión dentro de una ruta entre dos nodos determinados.

Cuando dentro de un grafo existen nodos de alta intermediación, estos pueden ser determinantes para el análisis ya que pueden fungir como reguladores de los flujos de información. En este caso los algoritmos de centralidad de intermediación se encargan de calcular la ruta más corta entre cada par de nodos pertenecientes a un grafo conectado utilizando el algoritmo de búsqueda de amplitud.

Cada nodo recibe una puntuación en función del número de estas rutas más cortas que pasan por el nodo. Los nodos que se encuentran con mayor frecuencia en estos caminos más cortos tendrán una puntuación más alta.

Casos de uso de los algoritmos de centralidad de intermediación

La centralidad de intermediación  es normalmente utilizada para entender el flujo determinado en una red. Esta propiedad tan especial hace que los algoritmos de centralidad  sean implementados para optimizar procesos de entrega de paquetes o redes de comunicación. En estos procesos se optimiza la ruta en la que el trafico debe transitar por la red determinada.

También son utilizados para identificar personas influyentes o condicionantes en sistemas de datos. Esto puede ser de especial utilidad para detectar fraudes bancarios o financiamiento de actividades ilegales, ya que se puede rastrear de forma eficiente el origen de los fondos a detectar.

Otra utilidad importante de los algoritmos de centralidad de intermediación  se encuentra en los entornos de redes sociales. Con la información analizada por el algoritmo pueden construirse sistemas de recomendación eficientes que dirigen las interacciones de personas influyentes a su segmento de mercado mejorando progresivamente su impacto.

Restricciones

Aunque estos algoritmos son muy eficientes, existen oportunidades en las que es mejor decantarse por otras opciones. La centralidad de intermediación supone que las comunicaciones entre vértices ocurren dentro de un camino más corto con cierta frecuencia, algo que en el plano de realidad no sucede. La aplicación del algoritmo nos da una representación aproximada, no exacta del comportamiento de los datos, por lo que si debemos obtener con precisión la distancia o los recorridos en una instancia de realidad, es necesario utilizar otro tipo de algoritmo.

Ejemplo base de la aplicación del algoritmo

Veamos un ejemplo práctico de aplicación de este tipo de algoritmo dentro de una red social. Con el se pretenderá determinar dentro de un grafo, la centralidad de intermediación de un numero determinado de usuarios para conocer la capacidad de influenciar en el entorno.

Introduciendo los datos para construir el grafo se tiene que:

MERGE (nAlice:User {id:'Alice'})
MERGE (nBridget:User {id:'Bridget'})
MERGE (nCharles:User {id:'Charles'})
MERGE (nDoug:User {id:'Doug'})
MERGE (nMark:User {id:'Mark'})
MERGE (nMichael:User {id:'Michael'})

MERGE (nAlice)-[:MANAGE]->(nBridget)
MERGE (nAlice)-[:MANAGE]->(nCharles)
MERGE (nAlice)-[:MANAGE]->(nDoug)
MERGE (nMark)-[:MANAGE]->(nAlice)
MERGE (nCharles)-[:MANAGE]->(nMichael);

Nos devuelve como resultado:

CALL algo.betweenness.stream('User','MANAGE',{direction:'out'})
YIELD nodeId, centrality

MATCH (user:User) WHERE id(user) = nodeId

RETURN user.id AS user,centrality
ORDER BY centrality DESC;

Aplicando el algoritmo obtenemos como resultado:

CALL algo.betweenness('User','MANAGE', {direction:'out',write:true, writeProperty:'centrality'})
YIELD nodes, minCentrality, maxCentrality, sumCentrality, loadMillis, computeMillis, writeMillis;

Obtenemos la siguiente tabla con la calificación del algoritmo

Name	Centrality weight
Alice	4
Charles	2
Bridget	0
Michael	0
Doug	0
Mark	0

Los resultados del algoritmo nos indican que Alice tiene una mayor posibilidad de influir dentro de la comunidad, debido a que representa la mayor cercanía entre todos los datos estudiados.

Esperamos que esta información sea de provecho para comprender de mejor manera el funcionamiento de este tipo de algoritmo.

Visita más de Grapheverywhere para descubrir todo los algoritmos de grafos.